search

wting / python-graph

Automatically exported from code.google.com/p/python-graph
Other
5 stars 4 forks source link

Gomory-Hu algorithm #77

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
Johannes Reinhardt <jreinhardt@ist-dein-freund.de> provided the attached patch 
for the Gomory-Hu algorithm.

See also:
http://en.wikipedia.org/wiki/Gomory-Hu_tree

Original issue reported on code.google.com by pmatiello on 18 Jun 2010 at 12:17

Attachments:

GoogleCodeExporter commented 9 years ago 
This looks good, I can merge if you like (Pedro)?

I notice that there is only one test method and it only applies to undirected 
graphs. Can this algorithm be applied to other types of graph? I'm thinking of 
digraphs. Can we also expand out the tests and show that they can work as 
expected with big and utterly trivial graphs and digraphs (i.e. containing 0, 1 
or 2 nodes)?

Original comment by belindap...@googlemail.com on 20 Jun 2010 at 7:50

GoogleCodeExporter commented 9 years ago 
Don't worry about the merging: I'll do it soon. But I'd appreciate a few more 
test cases.

Also, according to Wikipedia, this algorithm is only for undirected graphs, so 
tests for digraphs are not needed.
http://en.wikipedia.org/wiki/Gomory-Hu_tree

Original comment by pmatiello on 20 Jun 2010 at 8:41

GoogleCodeExporter commented 9 years ago 
Hi all,

It would be nice to have this merged, it turns out to be a very useful 
algorithm. By now, I did it manually, but it would be good if you can add it to 
the next release (if you consider it appropriate).

Original comment by cerqu...@gmail.com on 23 Aug 2010 at 9:35

GoogleCodeExporter commented 9 years ago 
Merged in r710. Sorry for the delay.

BTW, if someone is willing to contribute a few tests for this algorithm, I 
would be very thankful. :)

Original comment by pmatiello on 23 Aug 2010 at 11:34

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 1 Oct 2010 at 7:52