Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/flow/shortestaugmentingpath.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 Shortest augmenting path algorithm for maximum flow problems. | |
3 """ | |
4 | |
5 from collections import deque | |
6 import networkx as nx | |
7 from .utils import build_residual_network, CurrentEdge | |
8 from .edmondskarp import edmonds_karp_core | |
9 | |
10 __all__ = ["shortest_augmenting_path"] | |
11 | |
12 | |
13 def shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff): | |
14 """Implementation of the shortest augmenting path algorithm. | |
15 """ | |
16 if s not in G: | |
17 raise nx.NetworkXError(f"node {str(s)} not in graph") | |
18 if t not in G: | |
19 raise nx.NetworkXError(f"node {str(t)} not in graph") | |
20 if s == t: | |
21 raise nx.NetworkXError("source and sink are the same node") | |
22 | |
23 if residual is None: | |
24 R = build_residual_network(G, capacity) | |
25 else: | |
26 R = residual | |
27 | |
28 R_nodes = R.nodes | |
29 R_pred = R.pred | |
30 R_succ = R.succ | |
31 | |
32 # Initialize/reset the residual network. | |
33 for u in R: | |
34 for e in R_succ[u].values(): | |
35 e["flow"] = 0 | |
36 | |
37 # Initialize heights of the nodes. | |
38 heights = {t: 0} | |
39 q = deque([(t, 0)]) | |
40 while q: | |
41 u, height = q.popleft() | |
42 height += 1 | |
43 for v, attr in R_pred[u].items(): | |
44 if v not in heights and attr["flow"] < attr["capacity"]: | |
45 heights[v] = height | |
46 q.append((v, height)) | |
47 | |
48 if s not in heights: | |
49 # t is not reachable from s in the residual network. The maximum flow | |
50 # must be zero. | |
51 R.graph["flow_value"] = 0 | |
52 return R | |
53 | |
54 n = len(G) | |
55 m = R.size() / 2 | |
56 | |
57 # Initialize heights and 'current edge' data structures of the nodes. | |
58 for u in R: | |
59 R_nodes[u]["height"] = heights[u] if u in heights else n | |
60 R_nodes[u]["curr_edge"] = CurrentEdge(R_succ[u]) | |
61 | |
62 # Initialize counts of nodes in each level. | |
63 counts = [0] * (2 * n - 1) | |
64 for u in R: | |
65 counts[R_nodes[u]["height"]] += 1 | |
66 | |
67 inf = R.graph["inf"] | |
68 | |
69 def augment(path): | |
70 """Augment flow along a path from s to t. | |
71 """ | |
72 # Determine the path residual capacity. | |
73 flow = inf | |
74 it = iter(path) | |
75 u = next(it) | |
76 for v in it: | |
77 attr = R_succ[u][v] | |
78 flow = min(flow, attr["capacity"] - attr["flow"]) | |
79 u = v | |
80 if flow * 2 > inf: | |
81 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.") | |
82 # Augment flow along the path. | |
83 it = iter(path) | |
84 u = next(it) | |
85 for v in it: | |
86 R_succ[u][v]["flow"] += flow | |
87 R_succ[v][u]["flow"] -= flow | |
88 u = v | |
89 return flow | |
90 | |
91 def relabel(u): | |
92 """Relabel a node to create an admissible edge. | |
93 """ | |
94 height = n - 1 | |
95 for v, attr in R_succ[u].items(): | |
96 if attr["flow"] < attr["capacity"]: | |
97 height = min(height, R_nodes[v]["height"]) | |
98 return height + 1 | |
99 | |
100 if cutoff is None: | |
101 cutoff = float("inf") | |
102 | |
103 # Phase 1: Look for shortest augmenting paths using depth-first search. | |
104 | |
105 flow_value = 0 | |
106 path = [s] | |
107 u = s | |
108 d = n if not two_phase else int(min(m ** 0.5, 2 * n ** (2.0 / 3))) | |
109 done = R_nodes[s]["height"] >= d | |
110 while not done: | |
111 height = R_nodes[u]["height"] | |
112 curr_edge = R_nodes[u]["curr_edge"] | |
113 # Depth-first search for the next node on the path to t. | |
114 while True: | |
115 v, attr = curr_edge.get() | |
116 if height == R_nodes[v]["height"] + 1 and attr["flow"] < attr["capacity"]: | |
117 # Advance to the next node following an admissible edge. | |
118 path.append(v) | |
119 u = v | |
120 break | |
121 try: | |
122 curr_edge.move_to_next() | |
123 except StopIteration: | |
124 counts[height] -= 1 | |
125 if counts[height] == 0: | |
126 # Gap heuristic: If relabeling causes a level to become | |
127 # empty, a minimum cut has been identified. The algorithm | |
128 # can now be terminated. | |
129 R.graph["flow_value"] = flow_value | |
130 return R | |
131 height = relabel(u) | |
132 if u == s and height >= d: | |
133 if not two_phase: | |
134 # t is disconnected from s in the residual network. No | |
135 # more augmenting paths exist. | |
136 R.graph["flow_value"] = flow_value | |
137 return R | |
138 else: | |
139 # t is at least d steps away from s. End of phase 1. | |
140 done = True | |
141 break | |
142 counts[height] += 1 | |
143 R_nodes[u]["height"] = height | |
144 if u != s: | |
145 # After relabeling, the last edge on the path is no longer | |
146 # admissible. Retreat one step to look for an alternative. | |
147 path.pop() | |
148 u = path[-1] | |
149 break | |
150 if u == t: | |
151 # t is reached. Augment flow along the path and reset it for a new | |
152 # depth-first search. | |
153 flow_value += augment(path) | |
154 if flow_value >= cutoff: | |
155 R.graph["flow_value"] = flow_value | |
156 return R | |
157 path = [s] | |
158 u = s | |
159 | |
160 # Phase 2: Look for shortest augmenting paths using breadth-first search. | |
161 flow_value += edmonds_karp_core(R, s, t, cutoff - flow_value) | |
162 | |
163 R.graph["flow_value"] = flow_value | |
164 return R | |
165 | |
166 | |
167 def shortest_augmenting_path( | |
168 G, | |
169 s, | |
170 t, | |
171 capacity="capacity", | |
172 residual=None, | |
173 value_only=False, | |
174 two_phase=False, | |
175 cutoff=None, | |
176 ): | |
177 r"""Find a maximum single-commodity flow using the shortest augmenting path | |
178 algorithm. | |
179 | |
180 This function returns the residual network resulting after computing | |
181 the maximum flow. See below for details about the conventions | |
182 NetworkX uses for defining residual networks. | |
183 | |
184 This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$ | |
185 edges. | |
186 | |
187 | |
188 Parameters | |
189 ---------- | |
190 G : NetworkX graph | |
191 Edges of the graph are expected to have an attribute called | |
192 'capacity'. If this attribute is not present, the edge is | |
193 considered to have infinite capacity. | |
194 | |
195 s : node | |
196 Source node for the flow. | |
197 | |
198 t : node | |
199 Sink node for the flow. | |
200 | |
201 capacity : string | |
202 Edges of the graph G are expected to have an attribute capacity | |
203 that indicates how much flow the edge can support. If this | |
204 attribute is not present, the edge is considered to have | |
205 infinite capacity. Default value: 'capacity'. | |
206 | |
207 residual : NetworkX graph | |
208 Residual network on which the algorithm is to be executed. If None, a | |
209 new residual network is created. Default value: None. | |
210 | |
211 value_only : bool | |
212 If True compute only the value of the maximum flow. This parameter | |
213 will be ignored by this algorithm because it is not applicable. | |
214 | |
215 two_phase : bool | |
216 If True, a two-phase variant is used. The two-phase variant improves | |
217 the running time on unit-capacity networks from $O(nm)$ to | |
218 $O(\min(n^{2/3}, m^{1/2}) m)$. Default value: False. | |
219 | |
220 cutoff : integer, float | |
221 If specified, the algorithm will terminate when the flow value reaches | |
222 or exceeds the cutoff. In this case, it may be unable to immediately | |
223 determine a minimum cut. Default value: None. | |
224 | |
225 Returns | |
226 ------- | |
227 R : NetworkX DiGraph | |
228 Residual network after computing the maximum flow. | |
229 | |
230 Raises | |
231 ------ | |
232 NetworkXError | |
233 The algorithm does not support MultiGraph and MultiDiGraph. If | |
234 the input graph is an instance of one of these two classes, a | |
235 NetworkXError is raised. | |
236 | |
237 NetworkXUnbounded | |
238 If the graph has a path of infinite capacity, the value of a | |
239 feasible flow on the graph is unbounded above and the function | |
240 raises a NetworkXUnbounded. | |
241 | |
242 See also | |
243 -------- | |
244 :meth:`maximum_flow` | |
245 :meth:`minimum_cut` | |
246 :meth:`edmonds_karp` | |
247 :meth:`preflow_push` | |
248 | |
249 Notes | |
250 ----- | |
251 The residual network :samp:`R` from an input graph :samp:`G` has the | |
252 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair | |
253 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a | |
254 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists | |
255 in :samp:`G`. | |
256 | |
257 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']` | |
258 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists | |
259 in :samp:`G` or zero otherwise. If the capacity is infinite, | |
260 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value | |
261 that does not affect the solution of the problem. This value is stored in | |
262 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`, | |
263 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and | |
264 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`. | |
265 | |
266 The flow value, defined as the total flow into :samp:`t`, the sink, is | |
267 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not | |
268 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such | |
269 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum | |
270 :samp:`s`-:samp:`t` cut. | |
271 | |
272 Examples | |
273 -------- | |
274 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
275 | |
276 The functions that implement flow algorithms and output a residual | |
277 network, such as this one, are not imported to the base NetworkX | |
278 namespace, so you have to explicitly import them from the flow package. | |
279 | |
280 >>> G = nx.DiGraph() | |
281 >>> G.add_edge("x", "a", capacity=3.0) | |
282 >>> G.add_edge("x", "b", capacity=1.0) | |
283 >>> G.add_edge("a", "c", capacity=3.0) | |
284 >>> G.add_edge("b", "c", capacity=5.0) | |
285 >>> G.add_edge("b", "d", capacity=4.0) | |
286 >>> G.add_edge("d", "e", capacity=2.0) | |
287 >>> G.add_edge("c", "y", capacity=2.0) | |
288 >>> G.add_edge("e", "y", capacity=3.0) | |
289 >>> R = shortest_augmenting_path(G, "x", "y") | |
290 >>> flow_value = nx.maximum_flow_value(G, "x", "y") | |
291 >>> flow_value | |
292 3.0 | |
293 >>> flow_value == R.graph["flow_value"] | |
294 True | |
295 | |
296 """ | |
297 R = shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff) | |
298 R.graph["algorithm"] = "shortest_augmenting_path" | |
299 return R |