gomory_hu_tree(G, capacity='capacity', flow_func=None)
A Gomory-Hu tree of an undirected graph with capacities is a weighted tree that represents the minimum s-t cuts for all s-t pairs in the graph.
It only requires :None:None:`n-1` minimum cut computations instead of the obvious :None:None:`n(n-1)/2`. The tree represents all s-t cuts as the minimum cut value among any pair of nodes is the minimum edge weight in the shortest path between the two nodes in the Gomory-Hu tree.
The Gomory-Hu tree also has the property that removing the edge with the minimum weight in the shortest path between any two nodes leaves two connected components that form a partition of the nodes in G that defines the minimum s-t cut.
See Examples section below for details.
This implementation is based on Gusfield approach to compute Comory-Hu trees, which does not require node contractions and has the same computational complexity than the original method.
Undirected graph
Edges of the graph G are expected to have an attribute capacity that indicates how much flow the edge can support. If this attribute is not present, the edge is considered to have infinite capacity. Default value: 'capacity'.
Function to perform the underlying flow computations. Default value edmonds_karp
. This function performs better in sparse graphs with right tailed degree distributions. shortest_augmenting_path
will perform better in denser graphs.
Raised if the input graph is directed.
Raised if the input graph is an empty Graph.
A NetworkX graph representing the Gomory-Hu tree of the input graph.
Returns the Gomory-Hu tree of an undirected graph G.
maximum_flow
func
minimum_cut
func
>>> G = nx.karate_club_graph()
... nx.set_edge_attributes(G, 1, "capacity")
... T = nx.gomory_hu_tree(G)
... # The value of the minimum cut between any pair
... # of nodes in G is the minimum edge weight in the
... # shortest path between the two nodes in the
... # Gomory-Hu tree.
... def minimum_edge_weight_in_shortest_path(T, u, v):
... path = nx.shortest_path(T, u, v, weight="weight")
... return min((T[u][v]["weight"], (u, v)) for (u, v) in zip(path, path[1:]))
... u, v = 0, 33
... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
... cut_value 10
>>> nx.minimum_cut_value(G, u, v) 10
>>> # The Comory-Hu tree also has the property that removing the
... # edge with the minimum weight in the shortest path between
... # any two nodes leaves two connected components that form
... # a partition of the nodes in G that defines the minimum s-t
... # cut.
... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
... T.remove_edge(*edge)
... U, V = list(nx.connected_components(T))
... # Thus U and V form a partition that defines a minimum cut
... # between u and v in G. You can compute the edge cut set,
... # that is, the set of edges that if removed from G will
... # disconnect u from v in G, with this information:
... cutset = set()
... for x, nbrs in ((n, G[n]) for n in U):
... cutset.update((x, y) for y in nbrs if y in V)
... # Because we have set the capacities of all edges to 1
... # the cutset contains ten edges
... len(cutset) 10
>>> # You can use any maximum flow algorithm for the underlying
... # flow computations using the argument flow_func
... from networkx.algorithms import flow
... T = nx.gomory_hu_tree(G, flow_func=flow.boykov_kolmogorov)
... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
... cut_value 10
>>> nx.minimum_cut_value(G, u, v, flow_func=flow.boykov_kolmogorov) 10See :
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.flow.gomory_hu.gomory_hu_tree
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them