COIN-OR::LEMON - Graph Library

Opened 14 years ago

Closed 14 years ago

#327 closed defect (fixed)

Network Simplex doesn't handle graph changes.

Reported by: Alpar Juttner Owned by: Peter Kovacs
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 Peter Kovacs 14 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 14 years ago by Alpar Juttner

Revision id: 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 14 years ago by Peter Kovacs

Status: newassigned

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 14 years ago by 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.

comment:4 Changed 14 years ago by Peter Kovacs

Milestone: LEMON 1.2 release

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

comment:6 in reply to:  5 Changed 14 years ago by 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.

comment:7 Changed 14 years ago by Alpar Juttner

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 ; Changed 14 years ago by 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.

comment:9 in reply to:  8 Changed 14 years ago by 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!

comment:10 Changed 14 years ago by 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.

Changed 14 years ago by Peter Kovacs

comment:11 in reply to:  10 Changed 14 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

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.