def cut_tree(igraph, caps = None):
<EOL>graph = digraph()<EOL>graph.add_graph(igraph)<EOL>if not caps:<EOL><INDENT>caps = {}<EOL>for edge in graph.edges():<EOL><INDENT>caps[edge] = igraph.edge_weight(edge)<EOL><DEDENT><DEDENT>f = {}<EOL>n = {}<EOL>N = <NUM_LIT:0><EOL>for node in graph.nodes():<EOL><INDENT>n[N] = node<EOL>N = N + <NUM_LIT:1><EOL><DEDENT>p = {}.fromkeys(range(N),<NUM_LIT:0>)<EOL>p[<NUM_LIT:0>] = None<EOL>for s in range(<NUM_LIT:1>,N):<EOL><INDENT>t = p[s]<EOL>S = []<EOL>(flow,cut) = maximum_flow(graph,n[s],n[t],caps)<EOL>for i in range(N):<EOL><INDENT>if cut[n[i]] == <NUM_LIT:0>:<EOL><INDENT>S.append(i)<EOL><DEDENT><DEDENT>value = cut_value(graph,flow,cut)<EOL>f[s] = value<EOL>for i in range(N):<EOL><INDENT>if i == s:<EOL><INDENT>continue<EOL><DEDENT>if i in S and p[i] == t:<EOL><INDENT>p[i] = s<EOL><DEDENT><DEDENT>if p[t] in S:<EOL><INDENT>p[s] = p[t]<EOL>p[t] = s<EOL>f[s] = f[t]<EOL>f[t] = value<EOL><DEDENT><DEDENT>b = {}<EOL>for i in range(<NUM_LIT:1>,N):<EOL><INDENT>b[(n[i],n[p[i]])] = f[i]<EOL><DEDENT>return b<EOL>
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