COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 8 years ago

#306 closed task (fixed)

Tolerance in min cut algorithms

Reported by: kpeter Owned by: kpeter
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 kpeter 8 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 9 years ago by kpeter

  • Status changed from new to assigned

comment:2 in reply to: ↑ description ; follow-up: Changed 9 years ago by deba

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 9 years ago by kpeter

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 follow-up: Changed 8 years ago by 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.
  1. Should we add tolerance support to GomoryHu?

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

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 8 years ago by kpeter

comment:6 Changed 8 years ago by kpeter

[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 follow-up: Changed 8 years ago by 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.

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

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 follow-up: Changed 8 years ago by alpar

And what about the tolerance support in GomoryHu?

comment:10 in reply to: ↑ 8 Changed 8 years ago by kpeter

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 8 years ago by kpeter

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 8 years ago by kpeter

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

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

Note: See TracTickets for help on using tickets.