COIN-OR::LEMON - Graph Library

Opened 15 years ago

Closed 14 years ago

#306 closed task (fixed)

Tolerance in min cut algorithms

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

  1. In HaoOrlin class the Tolerance type can be set by an optional template parameter and the tolerance object can be set by an optional constructor parameter. On the other hand, in Preflow and Circulation classes Tolerance can be set using a named template parameter and the object can be set using tolerance() function. Maybe it would be better to apply the same solution for them, since HaoOrlin is a quite similar algorithm class. Another reason is that the solution applied in HaoOrlin provides less flexibility and seems to be a bit strange compared to the interface of other classes. As far as I understand this class implements a data structure that is similar to the elevator structures. Maybe it could be replaced by elevators, but then a traits class would be needed. However introducing traits class for HaoOrlin (just like in Preflow and Circulation) would cause a small incompatibility with the latest release (only in optional parameters). What do you think? Would it be important to modify this solution? Would it be allowable after the release of this class?
  1. For GomoryHu class Tolerance type/object cannot be set, however it could be useful. The tolerance type and object could be passed to the Preflow instances used by the algorithm.

Attachments (1)

306-930ddeafdb20.patch (962 bytes) - added by Peter Kovacs 14 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 15 years ago by Peter Kovacs

Status: newassigned

comment:2 in reply to:  description ; Changed 14 years ago by Balazs Dezso

Replying to kpeter:

  1. In HaoOrlin class the Tolerance type can be set by an optional template parameter and the tolerance object can be set by an optional constructor parameter. On the other hand, in Preflow and Circulation classes Tolerance can be set using a named template parameter and the object can be set using tolerance() function. Maybe it would be better to apply the same solution for them, since HaoOrlin is a quite similar algorithm class. Another reason is that the solution applied in HaoOrlin provides less flexibility and seems to be a bit strange compared to the interface of other classes. As far as I understand this class implements a data structure that is similar to the elevator structures. Maybe it could be replaced by elevators, but then a traits class would be needed. However introducing traits class for HaoOrlin (just like in Preflow and Circulation) would cause a small incompatibility with the latest release (only in optional parameters). What do you think? Would it be important to modify this solution? Would it be allowable after the release of this class?

I would like to reflect just the question of using elevators in HaoOrlin?. It is not a good idea. The elevators can be used to implement the gap heuristic, i.e. when an empty levels occurs in the structure, it is possible to lift all the nodes to the highest level. On the other hand, in this algorithm the nodes above the empty level become dormant nodes. In the current implementation the dormant nodes are not moved out from the "elevator" structure, just the levels are marked to be dormant. It cannot be implemented with elevators, therefore it should not be replaced.

Of course, the uniform tolerance handling would be good, but I do not feel that it is an important question.

comment:3 in reply to:  2 Changed 14 years ago by Peter Kovacs

Replying to deba:

I would like to reflect just the question of using elevators in HaoOrlin?. It is not a good idea. ...

I see.

Of course, the uniform tolerance handling would be good, but I do not feel that it is an important question.

I find it strange to pass the tolerance object as a constructor parameter. Separate set/get functions would be better and similar to other classes. I think, the main question is wheter we could change the interface this way, or not (since this class has already been released).

comment:4 Changed 14 years ago by Peter Kovacs

  1. Should/could we modify the interface of HaoOrlin to be similar to Preflow and Circulation (releted to the tolerance support)? Or such a modification is rejected due to compatiblity requirements.
  1. Should we add tolerance support to GomoryHu?

comment:5 in reply to:  4 Changed 14 years ago by Alpar Juttner

Replying to kpeter:

  1. Should/could we modify the interface of HaoOrlin to be similar to Preflow and Circulation (releted to the tolerance support)? Or such a modification is rejected due to compatiblity requirements.

Is it impossible to do it in a backward compatible way?

Changed 14 years ago by Peter Kovacs

Attachment: 306-930ddeafdb20.patch added

comment:6 Changed 14 years ago by Peter Kovacs

[930ddeafdb20] adds functions for set and get the tolerance object, just like in Preflow. This is the maximum modification that can be done in a backward compatible way.

comment:7 Changed 14 years ago by Peter Kovacs

[930ddeafdb20] went to the main branch. Does it mean that we can close this ticket? Maybe, backward compatibility is more important than forcing similar interface for HaoOrlin and Preflow.

comment:8 in reply to:  7 ; Changed 14 years ago by Alpar Juttner

Replying to kpeter:

[930ddeafdb20] went to the main branch. Does it mean that we can close this ticket? Maybe, backward compatibility is more important than forcing similar interface for HaoOrlin and Preflow.

As of [930ddeafdb20], I still think't that two interface are really different. In we want, we can still introduce a fourth template parameter for the traits. It won't affect the backward compatibility.

comment:9 Changed 14 years ago by Alpar Juttner

And what about the tolerance support in GomoryHu?

comment:10 in reply to:  8 Changed 14 years ago by Peter Kovacs

Replying to alpar:

As of [930ddeafdb20], I still think't that two interface are really different. In we want, we can still introduce a fourth template parameter for the traits. It won't affect the backward compatibility.

Yes, we could introduce a traits class parameter, but if we do it, then it would be better to also have the specification of the tolerance type in the traits class, not as a separate template parameter (and have a template named parameter for that, of course). Just like in Preflow and Circulation.

comment:11 in reply to:  9 Changed 14 years ago by Peter Kovacs

Replying to alpar:

And what about the tolerance support in GomoryHu?

I've already created a separate ticket for that, see #352.

comment:12 Changed 14 years ago by Peter Kovacs

Resolution: fixed
Status: assignedclosed

I think, we can close this ticket. See #352 for the follow-up.

Note: See TracTickets for help on using tickets.