Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Gomory-Hu tree of undirected Graphs.
3"""
5import networkx as nx
6from networkx.utils import not_implemented_for
8from .edmondskarp import edmonds_karp
9from .utils import build_residual_network
11default_flow_func = edmonds_karp
13__all__ = ["gomory_hu_tree"]
16@not_implemented_for("directed")
17@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
18def gomory_hu_tree(G, capacity="capacity", flow_func=None):
19 r"""Returns the Gomory-Hu tree of an undirected graph G.
21 A Gomory-Hu tree of an undirected graph with capacities is a
22 weighted tree that represents the minimum s-t cuts for all s-t
23 pairs in the graph.
25 It only requires `n-1` minimum cut computations instead of the
26 obvious `n(n-1)/2`. The tree represents all s-t cuts as the
27 minimum cut value among any pair of nodes is the minimum edge
28 weight in the shortest path between the two nodes in the
29 Gomory-Hu tree.
31 The Gomory-Hu tree also has the property that removing the
32 edge with the minimum weight in the shortest path between
33 any two nodes leaves two connected components that form
34 a partition of the nodes in G that defines the minimum s-t
35 cut.
37 See Examples section below for details.
39 Parameters
40 ----------
41 G : NetworkX graph
42 Undirected graph
44 capacity : string
45 Edges of the graph G are expected to have an attribute capacity
46 that indicates how much flow the edge can support. If this
47 attribute is not present, the edge is considered to have
48 infinite capacity. Default value: 'capacity'.
50 flow_func : function
51 Function to perform the underlying flow computations. Default value
52 :func:`edmonds_karp`. This function performs better in sparse graphs
53 with right tailed degree distributions.
54 :func:`shortest_augmenting_path` will perform better in denser
55 graphs.
57 Returns
58 -------
59 Tree : NetworkX graph
60 A NetworkX graph representing the Gomory-Hu tree of the input graph.
62 Raises
63 ------
64 NetworkXNotImplemented
65 Raised if the input graph is directed.
67 NetworkXError
68 Raised if the input graph is an empty Graph.
70 Examples
71 --------
72 >>> G = nx.karate_club_graph()
73 >>> nx.set_edge_attributes(G, 1, "capacity")
74 >>> T = nx.gomory_hu_tree(G)
75 >>> # The value of the minimum cut between any pair
76 ... # of nodes in G is the minimum edge weight in the
77 ... # shortest path between the two nodes in the
78 ... # Gomory-Hu tree.
79 ... def minimum_edge_weight_in_shortest_path(T, u, v):
80 ... path = nx.shortest_path(T, u, v, weight="weight")
81 ... return min((T[u][v]["weight"], (u, v)) for (u, v) in zip(path, path[1:]))
82 >>> u, v = 0, 33
83 >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
84 >>> cut_value
85 10
86 >>> nx.minimum_cut_value(G, u, v)
87 10
88 >>> # The Gomory-Hu tree also has the property that removing the
89 ... # edge with the minimum weight in the shortest path between
90 ... # any two nodes leaves two connected components that form
91 ... # a partition of the nodes in G that defines the minimum s-t
92 ... # cut.
93 ... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
94 >>> T.remove_edge(*edge)
95 >>> U, V = list(nx.connected_components(T))
96 >>> # Thus U and V form a partition that defines a minimum cut
97 ... # between u and v in G. You can compute the edge cut set,
98 ... # that is, the set of edges that if removed from G will
99 ... # disconnect u from v in G, with this information:
100 ... cutset = set()
101 >>> for x, nbrs in ((n, G[n]) for n in U):
102 ... cutset.update((x, y) for y in nbrs if y in V)
103 >>> # Because we have set the capacities of all edges to 1
104 ... # the cutset contains ten edges
105 ... len(cutset)
106 10
107 >>> # You can use any maximum flow algorithm for the underlying
108 ... # flow computations using the argument flow_func
109 ... from networkx.algorithms import flow
110 >>> T = nx.gomory_hu_tree(G, flow_func=flow.boykov_kolmogorov)
111 >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
112 >>> cut_value
113 10
114 >>> nx.minimum_cut_value(G, u, v, flow_func=flow.boykov_kolmogorov)
115 10
117 Notes
118 -----
119 This implementation is based on Gusfield approach [1]_ to compute
120 Gomory-Hu trees, which does not require node contractions and has
121 the same computational complexity than the original method.
123 See also
124 --------
125 :func:`minimum_cut`
126 :func:`maximum_flow`
128 References
129 ----------
130 .. [1] Gusfield D: Very simple methods for all pairs network flow analysis.
131 SIAM J Comput 19(1):143-155, 1990.
133 """
134 if flow_func is None:
135 flow_func = default_flow_func
137 if len(G) == 0: # empty graph
138 msg = "Empty Graph does not have a Gomory-Hu tree representation"
139 raise nx.NetworkXError(msg)
141 # Start the tree as a star graph with an arbitrary node at the center
142 tree = {}
143 labels = {}
144 iter_nodes = iter(G)
145 root = next(iter_nodes)
146 for n in iter_nodes:
147 tree[n] = root
149 # Reuse residual network
150 R = build_residual_network(G, capacity)
152 # For all the leaves in the star graph tree (that is n-1 nodes).
153 for source in tree:
154 # Find neighbor in the tree
155 target = tree[source]
156 # compute minimum cut
157 cut_value, partition = nx.minimum_cut(
158 G, source, target, capacity=capacity, flow_func=flow_func, residual=R
159 )
160 labels[(source, target)] = cut_value
161 # Update the tree
162 # Source will always be in partition[0] and target in partition[1]
163 for node in partition[0]:
164 if node != source and node in tree and tree[node] == target:
165 tree[node] = source
166 labels[node, source] = labels.get((node, target), cut_value)
167 #
168 if target != root and tree[target] in partition[0]:
169 labels[source, tree[target]] = labels[target, tree[target]]
170 labels[target, source] = cut_value
171 tree[source] = tree[target]
172 tree[target] = source
174 # Build the tree
175 T = nx.Graph()
176 T.add_nodes_from(G)
177 T.add_weighted_edges_from(((u, v, labels[u, v]) for u, v in tree.items()))
178 return T