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