Does igraph's gomory_hu_tree calculate the minimum cut tree?
Question: I'm trying to implement [this graph clustering algorithm (sec.
3.2)](http://projecteuclid.org/euclid.im/1109191029) with python-igraph. As I
do not want to calculate the minimum cut tree myself, I'm trying to use the
`gomory_hu_tree()` method. To play around with this method (and to provide a
MWE), I wrote the following:

    
    
    from igraph import *
    
    g= Graph()
    
    g.add_vertices(4)
    
    g.vs["name"] = ["0", "1", "2", "artificial"]
    
    g.add_edge("0", "1", weight=10.0)
    g.add_edge("0", "2", weight=20.0)
    g.add_edge("2", "1", weight=30.0)
    g.add_edge("artificial", "0", weight=100.0)
    g.add_edge("artificial", "1", weight=100.0)
    g.add_edge("artificial", "2", weight=100.0)
    
    t = g.gomory_hu_tree(capacity="weight")
    print t.es["flow"]
    print
    print t
    

I get the following output:

    
    
    [130.0, 140.0, 150.0]
    
    IGRAPH UNW- 4 3 --
    + attr: name (v), flow (e), weight (e)
    + edges (vertex names):
    0--1, 1--2, 2--artificial
    

But that is not a minimum cut tree! If the tree were like this, then the
removal of the edge between `1` and `2` would yield a partition of the graph
into the two subsets `{0, 1}` and `{2, t}` at a cost of 250. However, the
right answer is a cut into `{1}` and `{2, 0, t}` at a cost of just 140.

(By "cost" I mean the value of the respective cut.)

So, one (and the only) right answer for the min cut tree would have been

    
    
    0--artificial, 1--artificial, 2--artificial
    

What did I get wrong? Is it possibly wrong to use the `gomory_hu_tree()`
method in this context?

_Note:_ I originally [asked this question in a completely wrong
way](http://stackoverflow.com/questions/25297470/igraphs-gomory-hu-tree-not-
working).


Answer: Here are a couple of definitions:

1)A tree is called a **flow equivalent tree** if and only if for each pair of
nodes (u, v) maximal flow between these two nodes in a tree is the same as in
the original graph(and this implies that the cost of the minimum cut is the
same).

2)A tree satisfies a **cut property** if and only if for each pair of nodes
(u, v) the minimum cut in this tree is the same as in the original graph(not
just the cost is the same, but two subsets are the same too).

So the question is: What is A Gomory-Hu tree? There are two common
definitions:  
1)A flow equivalent tree.  
2)A flow equivalent tree that satisfies cut property.

Even though it is not documented what definition is used in this library, it
seems that they used the first one. So it is only guaranteed that the cost of
the cut is the same, not the cut itself. If you need to find the cut itself,
you can use `maxflow` method for a fixed pair of nodes.

