Network Simplex doesn't handle graph changes.

[Alpar Juttner]

The NetworkSimplex class crashes is the graph is changed after its construction, even if it takes place before the first upperMap(), lowerMap() etc invocation. The problem with this is that if it is a member or the class, them it must be constructed when the parent class is constructed and the corresponding graph may be empty at that time.

I see the implementation difficulties here, but at least the reset() member function could take care of it.

And the doc should be very clear about this issue, of course.

[Alpar Juttner]

If there are performance issues, the we might want more reset functions:

• reset() - reset everything
• resetParams() - this would do what reset() currently does.

Alternatively we can keep reset() as is, plus implement resetAll().

[Peter Kovacs]

Replying to alpar:

The NetworkSimplex class crashes is the graph is changed after its construction, even if it takes place before the first upperMap(), lowerMap() etc invocation.

Definitely. See the doc of its run() and reset() functions: "However, the underlying digraph must not be modified after this class have been constructed, since it copies and extends the graph.".

The problem with this is that if it is a member or the class, them it must be constructed when the parent class is constructed and the corresponding graph may be empty at that time.

I see. However, this problem can be overcome using a dynamically created instance of NetworkSimplex, though it is bit less convenient.

I see the implementation difficulties here, but at least the reset() member function could take care of it.

And the doc should be very clear about this issue, of course.

I think, it is absolutely clear (see above). However, this note could be underlined more. E.g. we can add it to the doc of the class itself, not only to the doc of run() and reset().

Note that the same issue will present for all the other MCF classes if they are merged (see #180).

[Peter Kovacs]

Replying to alpar:

If there are performance issues, the we might want more reset functions:

Performance is a real issue here, since copying the graph is not a cheap operation.

• reset() - reset everything
• resetParams() - this would do what reset() currently does.

Alternatively we can keep reset() as is, plus implement resetAll().

I prefer the second solution (to keep compatbility). It would be a clear extension to the current interface.

[Peter Kovacs]

Could you help to make decision about the names? Which one do you find the best? Do you have other idea?

• reset() + resetGraph() (or resetDigraph())
• reset() + resetAll() or fullReset()
• resetParams() + reset()

Currently, I sligthly prefer using reset() and fullReset().

[Alpar Juttner]

Replying to kpeter:

Could you help to make decision about the names? Which one do you find the best? Do you have other idea?

• reset() + resetGraph() (or resetDigraph())
• reset() + resetAll() or fullReset()
• resetParams() + reset()

Currently, I sligthly prefer using reset() and fullReset().

I would prefer resetParams()/reset(), but not object these ones either.

[Alpar Juttner]

Shall we expect this feature to be implemented in the near future? Or should we postpone it to 1.3?

[Peter Kovacs]

Replying to alpar:

Shall we expect this feature to be implemented in the near future? Or should we postpone it to 1.3?

The other min cost flow algoritmhs will be merged soon (see #180). After that, I would like to implement this feature for all of them. So we shouldn't postpone the ticket.

[Alpar Juttner]

Replying to kpeter:

The other min cost flow algoritmhs will be merged soon (see #180). After that, I would like to implement this feature for all of them. So we shouldn't postpone the ticket.

Very good!

[Peter Kovacs]

The attached patch [75c97c3786d6] realizes these changes for all the four MCF classes.

Now reset() resets all the internal data structures, makes a copy of the digraph and resets all parameters (maps). resetParams() resets only the parameters, thus it is significantly faster. The latter one is what was called reset() until now.

[Alpar Juttner]

Replying to kpeter:

The attached patch [75c97c3786d6] realizes these changes for all the four MCF classes.

It is in the main branch now.