Construct a Gomory-Hu cut tree by applying the algorithm of Gusfield.

    @type igraph: graph
    @param igraph: Graph

    @type caps: dictionary
    @param caps: Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge
    will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
    
    @rtype: dictionary
    @return: Gomory-Hu cut tree as a dictionary, where each edge is associated with its weight

def cut_tree(igraph, caps = None):
    """
    Construct a Gomory-Hu cut tree by applying the algorithm of Gusfield.

    @type igraph: graph
    @param igraph: Graph

    @type caps: dictionary
    @param caps: Dictionary specifying a maximum capacity for each edge. If not given, the weight of the edge
    will be used as its capacity. Otherwise, for each edge (a,b), caps[(a,b)] should be given.
    
    @rtype: dictionary
    @return: Gomory-Hu cut tree as a dictionary, where each edge is associated with its weight
    """

    #maximum flow needs a digraph, we get a graph
    #I think this conversion relies on implementation details outside the api and may break in the future
    graph = digraph()
    graph.add_graph(igraph)

    #handle optional argument
    if not caps:
        caps = {}
        for edge in graph.edges():
            caps[edge] = igraph.edge_weight(edge)

    #temporary flow variable
    f = {}

    #we use a numbering of the nodes for easier handling
    n = {}
    N = 0
    for node in graph.nodes():
        n[N] = node
        N = N + 1

    #predecessor function
    p = {}.fromkeys(range(N),0)
    p[0] = None

    for s in range(1,N):
        t = p[s]
        S = []
        #max flow calculation
        (flow,cut) = maximum_flow(graph,n[s],n[t],caps)
        for i in range(N):
            if cut[n[i]] == 0:
                S.append(i)
        
        value = cut_value(graph,flow,cut)

        f[s] = value

        for i in range(N):
            if i == s:
                continue
            if i in S and p[i] == t:
                p[i] = s
        if p[t] in S:
            p[s] = p[t]
            p[t] = s
            f[s] = f[t]
            f[t] = value

    #cut tree is a dictionary, where each edge is associated with its weight
    b = {}
    for i in range(1,N):
        b[(n[i],n[p[i]])] = f[i]
    return b