Tolerance in min cut algorithms

[Peter Kovacs]

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?

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

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

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

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

2. Should we add tolerance support to GomoryHu?

[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?

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

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

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

[Alpar Juttner]

And what about the tolerance support in GomoryHu?

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

[Peter Kovacs]

Replying to alpar:

And what about the tolerance support in GomoryHu?

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

[Peter Kovacs]

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