igraph's Gomory–Hu tree not working?
Question: When I try the following with `python-igraph`:

    
    
    from igraph import *
    
    g= Graph()
    
    g.add_vertices(3)
    
    g.vs["name"] = ["0", "1", "3"]
    
    g.add_edge("0", "1", weight=0.0)
    g.add_edge("1", "3", weight=10.0)
    g.add_edge("0", "3", weight=10.0)
    
    t = g.gomory_hu_tree(capacity="weight")
    print t
    

I get the output:

    
    
    IGRAPH UNW- 3 2 --
    + attr: name (v), flow (e), weight (e)
    + edges (vertex names):
    0--1, 1--3
    

This makes no sense as vertex "3" is connected to the other vertices through
edges with high weight. Therefor the minimum cut tree `t` should be a star
with center "3". This is obviously not the case...


Answer: The algorithm is working fine. The minimum cost to disconnect any two nodes is
10.0. All trees which are subgraphs of this graph are valid Gomory-Hu trees.
In fact, this is the case for any K3 which has two edges of identical weight
and a third of less weight.

Consider the brute-force approach. Since the minimum cost to disconnect any
two nodes is 10.0, the complete minimum cut graph is the three nodes connected
with edges of weight 10.0. By symmetry, this graph has three equally valid
Gomory-Hu trees consisting of any two of the edges of the complete minimum cut
graph.

So 0--1--3, 1--3--0, and 3--0--1 are all acceptable Gomory-Hu trees of the
graph above.

In fact, for any graph of n nodes which has a complete minimum cut graph with
all edges equal, the Gomory-Hu tree is any tree which connects every node.

