COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 9 years ago

#66 closed task (done)

Port Gomory-Hu algorithm

Reported by: alpar Owned by: deba
Priority: major Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc: deba
Revision id:

Description

It affects

  • lemon/gomory_hu_tree.h

Attachments (6)

33085d6328e4.patch (10.4 KB) - added by jtapolcai 9 years ago.
ported from lemon 0.7
926295286bdb.patch (1.9 KB) - added by deba 9 years ago.
Fixes
75075dd0b33a.patch (1.4 KB) - added by deba 9 years ago.
Add files to the build system
5ecf45167d4e.patch (6.2 KB) - added by alpar 9 years ago.
gomory-port-924887566bf2-ccd2d3a3001e-e72bacfea6b7.bundle (8.3 KB) - added by alpar 9 years ago.
gomory-doc-d6b40ebb2617.patch (10.7 KB) - added by kpeter 9 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 10 years ago by alpar

  • Milestone changed from LEMON 1.0 release to Post 1.0

comment:2 Changed 10 years ago by alpar

  • Milestone LEMON 1.1 release deleted

Changed 9 years ago by jtapolcai

ported from lemon 0.7

comment:3 Changed 9 years ago by jtapolcai

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

Changed 9 years ago by deba

Fixes

comment:4 Changed 9 years ago by deba

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.

Changed 9 years ago by deba

Add files to the build system

comment:5 Changed 9 years ago by alpar

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)
    

comment:6 Changed 9 years ago by alpar

  • Milestone set to LEMON 1.1 release
  • Owner changed from alpar to deba

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?

comment:7 Changed 9 years ago by alpar

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.

comment:8 Changed 9 years ago by alpar

One more:

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

Changed 9 years ago by alpar

comment:9 Changed 9 years ago by alpar

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

Shame on me.

comment:10 Changed 9 years ago by alpar

  • Cc deba added

comment:11 Changed 9 years ago by alpar

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

comment:12 Changed 9 years ago by alpar

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.

Changed 9 years ago by kpeter

comment:13 Changed 9 years ago by kpeter

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

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

comment:14 Changed 9 years ago by alpar

  • Resolution set to done
  • Status changed from new to closed

The changesets went to the main branch.

Note: See TracTickets for help on using tickets.