Port Gomory-Hu algorithm

[Alpar Juttner]

It affects

• lemon/gomory_hu_tree.h

[Tapolcai János]

ported from lemon 0.7

[Tapolcai János]

The 33085d6328e4.patch compiles but the test gives a segfault.

[Balazs Dezso]

Fixes

[Balazs Dezso]

In [926295286bdb] I have fixed some problems:

• Missing include in header file
• Use proper map name in lgf
• Fix cutValue() checking function

I have tested the original version, however instead of segfault I got exception (wrong map name). The fixed version were compiled for me, and the test passed.

[Balazs Dezso]

Add files to the build system

[Alpar Juttner]

Some random comments:

• It would be nice to make it possible for the user to walk on the tree, or at least iterate on the edges of a path between two nodes. Currently it cannot be done. It might be enough to provide a public access to the order data.
• Beyond the current minCutMap(), it might be useful to have a possibility to iterate through the edges of a cut like this.

  for(GomoryHuTree<Graph>::MinCut cut(gomory, s, t);cut !=INVALID;++cut)
  

[Alpar Juttner]

Another comment:

If the value of a minimum cut is std::numeric_limits<Value>::max(), then the minCutValue() and minCutMap functions will not work correctly. I guess, it can be fixed by changing the value comparisons in the if statements from < to <= when looking for the minimum value element on the path.

Isn't this bug appear at other places in the algorithm?

[Alpar Juttner]

And another one:

The performance of minCutMap() could probably be increased by placing the line

        std::vector<Node> st;

outside the for cycle and make it empty at each iterations.

[Alpar Juttner]

One more:

minCutMap(s,t, cut) should consistently set cut[s] to true and cut[t] to false.

[Alpar Juttner]

[5ecf45167d4e] implements the ideas above, unfortunately with no documentation.

Shame on me.

[Alpar Juttner]

Could anyone tell me why do we have an init()/start() separation in the public API? Does it have any practical use?

[Alpar Juttner]

Tha attached bundle file​ contains three changesets.

• [924887566bf2] is the original port of Janos + the bugfixes added by deba ([926295286bdb]) + some more added by me the have make distcheck run.
• [ccd2d3a3001e] is the implementation of the ideas above, plus a thorough revision of the doc.
• [e72bacfea6b7] renames GomoryHuTree to GomoryHu.

[Peter Kovacs]

[d6b40ebb2617] is a doc improvement on the top of [e72bacfea6b7].

I think the bundle file and this changeset should go to the main branch.

[Alpar Juttner]

The changesets went to the main branch.