COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#327 closed defect (fixed)

Network Simplex doesn't handle graph changes.

Reported by: alpar Owned by: kpeter
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id: 1a7fe3bef514

Description

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.

Attachments (1)

327-mcf-reset-75c97c3786d6.patch (35.3 KB) - added by kpeter 9 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 follow-up: Changed 9 years ago by alpar

  • Revision id set to 1a7fe3bef514

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().

comment:2 in reply to: ↑ description Changed 9 years ago by kpeter

  • Status changed from new to assigned

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).

comment:3 in reply to: ↑ 1 Changed 9 years ago by kpeter

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.

comment:4 Changed 9 years ago by kpeter

  • Milestone set to LEMON 1.2 release

comment:5 follow-up: Changed 9 years ago by 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().

comment:6 in reply to: ↑ 5 Changed 9 years ago by alpar

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.

comment:7 follow-up: Changed 9 years ago by alpar

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

comment:8 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by kpeter

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.

comment:9 in reply to: ↑ 8 Changed 9 years ago by alpar

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!

comment:10 follow-up: Changed 9 years ago by kpeter

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.

Changed 9 years ago by kpeter

comment:11 in reply to: ↑ 10 Changed 9 years ago by alpar

  • Resolution set to fixed
  • Status changed from assigned to closed

Replying to kpeter:

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

It is in the main branch now.

Note: See TracTickets for help on using tickets.