COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 10 years ago

#66 closed task (done)

Port Gomory-Hu algorithm

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: major Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc: Balazs Dezso
Revision id:

Description

It affects

  • lemon/gomory_hu_tree.h

Attachments (6)

33085d6328e4.patch (10.4 KB) - added by Tapolcai János 10 years ago.
ported from lemon 0.7
926295286bdb.patch (1.9 KB) - added by Balazs Dezso 10 years ago.
Fixes
75075dd0b33a.patch (1.4 KB) - added by Balazs Dezso 10 years ago.
Add files to the build system
5ecf45167d4e.patch (6.2 KB) - added by Alpar Juttner 10 years ago.
gomory-port-924887566bf2-ccd2d3a3001e-e72bacfea6b7.bundle (8.3 KB) - added by Alpar Juttner 10 years ago.
gomory-doc-d6b40ebb2617.patch (10.7 KB) - added by Peter Kovacs 10 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:2 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

Changed 10 years ago by Tapolcai János

Attachment: 33085d6328e4.patch added

ported from lemon 0.7

comment:3 Changed 10 years ago by Tapolcai János

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

Changed 10 years ago by Balazs Dezso

Attachment: 926295286bdb.patch added

Fixes

comment:4 Changed 10 years ago by 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.

Changed 10 years ago by Balazs Dezso

Attachment: 75075dd0b33a.patch added

Add files to the build system

comment:5 Changed 10 years ago by 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)
    

comment:6 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 release
Owner: changed from Alpar Juttner to Balazs Dezso

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 10 years ago by 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.

comment:8 Changed 10 years ago by Alpar Juttner

One more:

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

Changed 10 years ago by Alpar Juttner

Attachment: 5ecf45167d4e.patch added

comment:9 Changed 10 years ago by Alpar Juttner

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

Shame on me.

comment:10 Changed 10 years ago by Alpar Juttner

Cc: Balazs Dezso added

comment:11 Changed 10 years ago by Alpar Juttner

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 10 years ago by 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.

Changed 10 years ago by Peter Kovacs

comment:13 Changed 10 years ago by 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.

comment:14 Changed 10 years ago by Alpar Juttner

Resolution: done
Status: newclosed

The changesets went to the main branch.

Note: See TracTickets for help on using tickets.