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(
18 edge_attrs={"capacity": float("inf")}, returns_graph=True, preserve_edge_attrs=True
19)
20def gomory_hu_tree(G, capacity="capacity", flow_func=None):
21 r"""Returns the Gomory-Hu tree of an undirected graph G.
23 A Gomory-Hu tree of an undirected graph with capacities is a
24 weighted tree that represents the minimum s-t cuts for all s-t
25 pairs in the graph.
27 It only requires `n-1` minimum cut computations instead of the
28 obvious `n(n-1)/2`. The tree represents all s-t cuts as the
29 minimum cut value among any pair of nodes is the minimum edge
30 weight in the shortest path between the two nodes in the
31 Gomory-Hu tree.
33 The Gomory-Hu tree also has the property that removing the
34 edge with the minimum weight in the shortest path between
35 any two nodes leaves two connected components that form
36 a partition of the nodes in G that defines the minimum s-t
37 cut.
39 See Examples section below for details.
41 Parameters
42 ----------
43 G : NetworkX graph
44 Undirected graph
46 capacity : string or function (default= 'capacity')
47 If this is a string, then edge capacity will be accessed via the
48 edge attribute with this key (that is, the capacity of the edge
49 joining `u` to `v` will be ``G.edges[u, v][capacity]``). If no
50 such edge attribute exists, the capacity of the edge is assumed to
51 be infinite.
53 If this is a function, the capacity of an edge is the value
54 returned by the function. The function must accept exactly three
55 positional arguments: the two endpoints of an edge and the
56 dictionary of edge attributes for that edge. The function must
57 return a number or None to indicate a hidden edge.
59 flow_func : function
60 Function to perform the underlying flow computations. Default value
61 :func:`edmonds_karp`. This function performs better in sparse graphs
62 with right tailed degree distributions.
63 :func:`shortest_augmenting_path` will perform better in denser
64 graphs.
66 Returns
67 -------
68 Tree : NetworkX graph
69 A NetworkX graph representing the Gomory-Hu tree of the input graph.
71 Raises
72 ------
73 NetworkXNotImplemented
74 Raised if the input graph is directed.
76 NetworkXError
77 Raised if the input graph is an empty Graph.
79 Examples
80 --------
81 >>> G = nx.karate_club_graph()
82 >>> nx.set_edge_attributes(G, 1, "capacity")
83 >>> T = nx.gomory_hu_tree(G)
84 >>> # The value of the minimum cut between any pair
85 ... # of nodes in G is the minimum edge weight in the
86 ... # shortest path between the two nodes in the
87 ... # Gomory-Hu tree.
88 ... def minimum_edge_weight_in_shortest_path(T, u, v):
89 ... path = nx.shortest_path(T, u, v, weight="weight")
90 ... return min((T[u][v]["weight"], (u, v)) for (u, v) in zip(path, path[1:]))
91 >>> u, v = 0, 33
92 >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
93 >>> cut_value
94 10
95 >>> nx.minimum_cut_value(G, u, v)
96 10
97 >>> # The Gomory-Hu tree also has the property that removing the
98 ... # edge with the minimum weight in the shortest path between
99 ... # any two nodes leaves two connected components that form
100 ... # a partition of the nodes in G that defines the minimum s-t
101 ... # cut.
102 ... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
103 >>> T.remove_edge(*edge)
104 >>> U, V = list(nx.connected_components(T))
105 >>> # Thus U and V form a partition that defines a minimum cut
106 ... # between u and v in G. You can compute the edge cut set,
107 ... # that is, the set of edges that if removed from G will
108 ... # disconnect u from v in G, with this information:
109 ... cutset = set()
110 >>> for x, nbrs in ((n, G[n]) for n in U):
111 ... cutset.update((x, y) for y in nbrs if y in V)
112 >>> # Because we have set the capacities of all edges to 1
113 ... # the cutset contains ten edges
114 ... len(cutset)
115 10
116 >>> # You can use any maximum flow algorithm for the underlying
117 ... # flow computations using the argument flow_func
118 ... from networkx.algorithms import flow
119 >>> T = nx.gomory_hu_tree(G, flow_func=flow.boykov_kolmogorov)
120 >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
121 >>> cut_value
122 10
123 >>> nx.minimum_cut_value(G, u, v, flow_func=flow.boykov_kolmogorov)
124 10
126 Notes
127 -----
128 This implementation is based on Gusfield approach [1]_ to compute
129 Gomory-Hu trees, which does not require node contractions and has
130 the same computational complexity than the original method.
132 See also
133 --------
134 :func:`minimum_cut`
135 :func:`maximum_flow`
137 References
138 ----------
139 .. [1] Gusfield D: Very simple methods for all pairs network flow analysis.
140 SIAM J Comput 19(1):143-155, 1990.
142 """
143 if flow_func is None:
144 flow_func = default_flow_func
146 if len(G) == 0: # empty graph
147 msg = "Empty Graph does not have a Gomory-Hu tree representation"
148 raise nx.NetworkXError(msg)
150 # Start the tree as a star graph with an arbitrary node at the center
151 tree = {}
152 labels = {}
153 iter_nodes = iter(G)
154 root = next(iter_nodes)
155 for n in iter_nodes:
156 tree[n] = root
158 # Reuse residual network
159 R = build_residual_network(G, capacity)
161 # For all the leaves in the star graph tree (that is n-1 nodes).
162 for source in tree:
163 # Find neighbor in the tree
164 target = tree[source]
165 # compute minimum cut
166 cut_value, partition = nx.minimum_cut(
167 G, source, target, capacity=capacity, flow_func=flow_func, residual=R
168 )
169 labels[(source, target)] = cut_value
170 # Update the tree
171 # Source will always be in partition[0] and target in partition[1]
172 for node in partition[0]:
173 if node != source and node in tree and tree[node] == target:
174 tree[node] = source
175 labels[node, source] = labels.get((node, target), cut_value)
176 #
177 if target != root and tree[target] in partition[0]:
178 labels[source, tree[target]] = labels[target, tree[target]]
179 labels[target, source] = cut_value
180 tree[source] = tree[target]
181 tree[target] = source
183 # Build the tree
184 T = nx.Graph()
185 T.add_nodes_from(G)
186 T.add_weighted_edges_from(((u, v, labels[u, v]) for u, v in tree.items()))
187 return T