Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/flow/maxflow.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 Maximum flow (and minimum cut) algorithms on capacitated graphs. | |
3 """ | |
4 import networkx as nx | |
5 | |
6 from .boykovkolmogorov import boykov_kolmogorov | |
7 from .dinitz_alg import dinitz | |
8 from .edmondskarp import edmonds_karp | |
9 from .preflowpush import preflow_push | |
10 from .shortestaugmentingpath import shortest_augmenting_path | |
11 from .utils import build_flow_dict | |
12 | |
13 # Define the default flow function for computing maximum flow. | |
14 default_flow_func = preflow_push | |
15 # Functions that don't support cutoff for minimum cut computations. | |
16 flow_funcs = [ | |
17 boykov_kolmogorov, | |
18 dinitz, | |
19 edmonds_karp, | |
20 preflow_push, | |
21 shortest_augmenting_path, | |
22 ] | |
23 | |
24 __all__ = ["maximum_flow", "maximum_flow_value", "minimum_cut", "minimum_cut_value"] | |
25 | |
26 | |
27 def maximum_flow(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs): | |
28 """Find a maximum single-commodity flow. | |
29 | |
30 Parameters | |
31 ---------- | |
32 flowG : NetworkX graph | |
33 Edges of the graph are expected to have an attribute called | |
34 'capacity'. If this attribute is not present, the edge is | |
35 considered to have infinite capacity. | |
36 | |
37 _s : node | |
38 Source node for the flow. | |
39 | |
40 _t : node | |
41 Sink node for the flow. | |
42 | |
43 capacity : string | |
44 Edges of the graph G are expected to have an attribute capacity | |
45 that indicates how much flow the edge can support. If this | |
46 attribute is not present, the edge is considered to have | |
47 infinite capacity. Default value: 'capacity'. | |
48 | |
49 flow_func : function | |
50 A function for computing the maximum flow among a pair of nodes | |
51 in a capacitated graph. The function has to accept at least three | |
52 parameters: a Graph or Digraph, a source node, and a target node. | |
53 And return a residual network that follows NetworkX conventions | |
54 (see Notes). If flow_func is None, the default maximum | |
55 flow function (:meth:`preflow_push`) is used. See below for | |
56 alternative algorithms. The choice of the default function may change | |
57 from version to version and should not be relied on. Default value: | |
58 None. | |
59 | |
60 kwargs : Any other keyword parameter is passed to the function that | |
61 computes the maximum flow. | |
62 | |
63 Returns | |
64 ------- | |
65 flow_value : integer, float | |
66 Value of the maximum flow, i.e., net outflow from the source. | |
67 | |
68 flow_dict : dict | |
69 A dictionary containing the value of the flow that went through | |
70 each edge. | |
71 | |
72 Raises | |
73 ------ | |
74 NetworkXError | |
75 The algorithm does not support MultiGraph and MultiDiGraph. If | |
76 the input graph is an instance of one of these two classes, a | |
77 NetworkXError is raised. | |
78 | |
79 NetworkXUnbounded | |
80 If the graph has a path of infinite capacity, the value of a | |
81 feasible flow on the graph is unbounded above and the function | |
82 raises a NetworkXUnbounded. | |
83 | |
84 See also | |
85 -------- | |
86 :meth:`maximum_flow_value` | |
87 :meth:`minimum_cut` | |
88 :meth:`minimum_cut_value` | |
89 :meth:`edmonds_karp` | |
90 :meth:`preflow_push` | |
91 :meth:`shortest_augmenting_path` | |
92 | |
93 Notes | |
94 ----- | |
95 The function used in the flow_func parameter has to return a residual | |
96 network that follows NetworkX conventions: | |
97 | |
98 The residual network :samp:`R` from an input graph :samp:`G` has the | |
99 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair | |
100 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a | |
101 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists | |
102 in :samp:`G`. | |
103 | |
104 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']` | |
105 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists | |
106 in :samp:`G` or zero otherwise. If the capacity is infinite, | |
107 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value | |
108 that does not affect the solution of the problem. This value is stored in | |
109 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`, | |
110 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and | |
111 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`. | |
112 | |
113 The flow value, defined as the total flow into :samp:`t`, the sink, is | |
114 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using | |
115 only edges :samp:`(u, v)` such that | |
116 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum | |
117 :samp:`s`-:samp:`t` cut. | |
118 | |
119 Specific algorithms may store extra data in :samp:`R`. | |
120 | |
121 The function should supports an optional boolean parameter value_only. When | |
122 True, it can optionally terminate the algorithm as soon as the maximum flow | |
123 value and the minimum cut can be determined. | |
124 | |
125 Examples | |
126 -------- | |
127 >>> G = nx.DiGraph() | |
128 >>> G.add_edge("x", "a", capacity=3.0) | |
129 >>> G.add_edge("x", "b", capacity=1.0) | |
130 >>> G.add_edge("a", "c", capacity=3.0) | |
131 >>> G.add_edge("b", "c", capacity=5.0) | |
132 >>> G.add_edge("b", "d", capacity=4.0) | |
133 >>> G.add_edge("d", "e", capacity=2.0) | |
134 >>> G.add_edge("c", "y", capacity=2.0) | |
135 >>> G.add_edge("e", "y", capacity=3.0) | |
136 | |
137 maximum_flow returns both the value of the maximum flow and a | |
138 dictionary with all flows. | |
139 | |
140 >>> flow_value, flow_dict = nx.maximum_flow(G, "x", "y") | |
141 >>> flow_value | |
142 3.0 | |
143 >>> print(flow_dict["x"]["b"]) | |
144 1.0 | |
145 | |
146 You can also use alternative algorithms for computing the | |
147 maximum flow by using the flow_func parameter. | |
148 | |
149 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
150 >>> flow_value == nx.maximum_flow(G, "x", "y", flow_func=shortest_augmenting_path)[ | |
151 ... 0 | |
152 ... ] | |
153 True | |
154 | |
155 """ | |
156 if flow_func is None: | |
157 if kwargs: | |
158 raise nx.NetworkXError( | |
159 "You have to explicitly set a flow_func if" | |
160 " you need to pass parameters via kwargs." | |
161 ) | |
162 flow_func = default_flow_func | |
163 | |
164 if not callable(flow_func): | |
165 raise nx.NetworkXError("flow_func has to be callable.") | |
166 | |
167 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=False, **kwargs) | |
168 flow_dict = build_flow_dict(flowG, R) | |
169 | |
170 return (R.graph["flow_value"], flow_dict) | |
171 | |
172 | |
173 def maximum_flow_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs): | |
174 """Find the value of maximum single-commodity flow. | |
175 | |
176 Parameters | |
177 ---------- | |
178 flowG : NetworkX graph | |
179 Edges of the graph are expected to have an attribute called | |
180 'capacity'. If this attribute is not present, the edge is | |
181 considered to have infinite capacity. | |
182 | |
183 _s : node | |
184 Source node for the flow. | |
185 | |
186 _t : node | |
187 Sink node for the flow. | |
188 | |
189 capacity : string | |
190 Edges of the graph G are expected to have an attribute capacity | |
191 that indicates how much flow the edge can support. If this | |
192 attribute is not present, the edge is considered to have | |
193 infinite capacity. Default value: 'capacity'. | |
194 | |
195 flow_func : function | |
196 A function for computing the maximum flow among a pair of nodes | |
197 in a capacitated graph. The function has to accept at least three | |
198 parameters: a Graph or Digraph, a source node, and a target node. | |
199 And return a residual network that follows NetworkX conventions | |
200 (see Notes). If flow_func is None, the default maximum | |
201 flow function (:meth:`preflow_push`) is used. See below for | |
202 alternative algorithms. The choice of the default function may change | |
203 from version to version and should not be relied on. Default value: | |
204 None. | |
205 | |
206 kwargs : Any other keyword parameter is passed to the function that | |
207 computes the maximum flow. | |
208 | |
209 Returns | |
210 ------- | |
211 flow_value : integer, float | |
212 Value of the maximum flow, i.e., net outflow from the source. | |
213 | |
214 Raises | |
215 ------ | |
216 NetworkXError | |
217 The algorithm does not support MultiGraph and MultiDiGraph. If | |
218 the input graph is an instance of one of these two classes, a | |
219 NetworkXError is raised. | |
220 | |
221 NetworkXUnbounded | |
222 If the graph has a path of infinite capacity, the value of a | |
223 feasible flow on the graph is unbounded above and the function | |
224 raises a NetworkXUnbounded. | |
225 | |
226 See also | |
227 -------- | |
228 :meth:`maximum_flow` | |
229 :meth:`minimum_cut` | |
230 :meth:`minimum_cut_value` | |
231 :meth:`edmonds_karp` | |
232 :meth:`preflow_push` | |
233 :meth:`shortest_augmenting_path` | |
234 | |
235 Notes | |
236 ----- | |
237 The function used in the flow_func parameter has to return a residual | |
238 network that follows NetworkX conventions: | |
239 | |
240 The residual network :samp:`R` from an input graph :samp:`G` has the | |
241 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair | |
242 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a | |
243 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists | |
244 in :samp:`G`. | |
245 | |
246 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']` | |
247 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists | |
248 in :samp:`G` or zero otherwise. If the capacity is infinite, | |
249 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value | |
250 that does not affect the solution of the problem. This value is stored in | |
251 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`, | |
252 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and | |
253 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`. | |
254 | |
255 The flow value, defined as the total flow into :samp:`t`, the sink, is | |
256 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using | |
257 only edges :samp:`(u, v)` such that | |
258 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum | |
259 :samp:`s`-:samp:`t` cut. | |
260 | |
261 Specific algorithms may store extra data in :samp:`R`. | |
262 | |
263 The function should supports an optional boolean parameter value_only. When | |
264 True, it can optionally terminate the algorithm as soon as the maximum flow | |
265 value and the minimum cut can be determined. | |
266 | |
267 Examples | |
268 -------- | |
269 >>> G = nx.DiGraph() | |
270 >>> G.add_edge("x", "a", capacity=3.0) | |
271 >>> G.add_edge("x", "b", capacity=1.0) | |
272 >>> G.add_edge("a", "c", capacity=3.0) | |
273 >>> G.add_edge("b", "c", capacity=5.0) | |
274 >>> G.add_edge("b", "d", capacity=4.0) | |
275 >>> G.add_edge("d", "e", capacity=2.0) | |
276 >>> G.add_edge("c", "y", capacity=2.0) | |
277 >>> G.add_edge("e", "y", capacity=3.0) | |
278 | |
279 maximum_flow_value computes only the value of the | |
280 maximum flow: | |
281 | |
282 >>> flow_value = nx.maximum_flow_value(G, "x", "y") | |
283 >>> flow_value | |
284 3.0 | |
285 | |
286 You can also use alternative algorithms for computing the | |
287 maximum flow by using the flow_func parameter. | |
288 | |
289 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
290 >>> flow_value == nx.maximum_flow_value( | |
291 ... G, "x", "y", flow_func=shortest_augmenting_path | |
292 ... ) | |
293 True | |
294 | |
295 """ | |
296 if flow_func is None: | |
297 if kwargs: | |
298 raise nx.NetworkXError( | |
299 "You have to explicitly set a flow_func if" | |
300 " you need to pass parameters via kwargs." | |
301 ) | |
302 flow_func = default_flow_func | |
303 | |
304 if not callable(flow_func): | |
305 raise nx.NetworkXError("flow_func has to be callable.") | |
306 | |
307 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs) | |
308 | |
309 return R.graph["flow_value"] | |
310 | |
311 | |
312 def minimum_cut(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs): | |
313 """Compute the value and the node partition of a minimum (s, t)-cut. | |
314 | |
315 Use the max-flow min-cut theorem, i.e., the capacity of a minimum | |
316 capacity cut is equal to the flow value of a maximum flow. | |
317 | |
318 Parameters | |
319 ---------- | |
320 flowG : NetworkX graph | |
321 Edges of the graph are expected to have an attribute called | |
322 'capacity'. If this attribute is not present, the edge is | |
323 considered to have infinite capacity. | |
324 | |
325 _s : node | |
326 Source node for the flow. | |
327 | |
328 _t : node | |
329 Sink node for the flow. | |
330 | |
331 capacity : string | |
332 Edges of the graph G are expected to have an attribute capacity | |
333 that indicates how much flow the edge can support. If this | |
334 attribute is not present, the edge is considered to have | |
335 infinite capacity. Default value: 'capacity'. | |
336 | |
337 flow_func : function | |
338 A function for computing the maximum flow among a pair of nodes | |
339 in a capacitated graph. The function has to accept at least three | |
340 parameters: a Graph or Digraph, a source node, and a target node. | |
341 And return a residual network that follows NetworkX conventions | |
342 (see Notes). If flow_func is None, the default maximum | |
343 flow function (:meth:`preflow_push`) is used. See below for | |
344 alternative algorithms. The choice of the default function may change | |
345 from version to version and should not be relied on. Default value: | |
346 None. | |
347 | |
348 kwargs : Any other keyword parameter is passed to the function that | |
349 computes the maximum flow. | |
350 | |
351 Returns | |
352 ------- | |
353 cut_value : integer, float | |
354 Value of the minimum cut. | |
355 | |
356 partition : pair of node sets | |
357 A partitioning of the nodes that defines a minimum cut. | |
358 | |
359 Raises | |
360 ------ | |
361 NetworkXUnbounded | |
362 If the graph has a path of infinite capacity, all cuts have | |
363 infinite capacity and the function raises a NetworkXError. | |
364 | |
365 See also | |
366 -------- | |
367 :meth:`maximum_flow` | |
368 :meth:`maximum_flow_value` | |
369 :meth:`minimum_cut_value` | |
370 :meth:`edmonds_karp` | |
371 :meth:`preflow_push` | |
372 :meth:`shortest_augmenting_path` | |
373 | |
374 Notes | |
375 ----- | |
376 The function used in the flow_func parameter has to return a residual | |
377 network that follows NetworkX conventions: | |
378 | |
379 The residual network :samp:`R` from an input graph :samp:`G` has the | |
380 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair | |
381 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a | |
382 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists | |
383 in :samp:`G`. | |
384 | |
385 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']` | |
386 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists | |
387 in :samp:`G` or zero otherwise. If the capacity is infinite, | |
388 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value | |
389 that does not affect the solution of the problem. This value is stored in | |
390 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`, | |
391 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and | |
392 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`. | |
393 | |
394 The flow value, defined as the total flow into :samp:`t`, the sink, is | |
395 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using | |
396 only edges :samp:`(u, v)` such that | |
397 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum | |
398 :samp:`s`-:samp:`t` cut. | |
399 | |
400 Specific algorithms may store extra data in :samp:`R`. | |
401 | |
402 The function should supports an optional boolean parameter value_only. When | |
403 True, it can optionally terminate the algorithm as soon as the maximum flow | |
404 value and the minimum cut can be determined. | |
405 | |
406 Examples | |
407 -------- | |
408 >>> G = nx.DiGraph() | |
409 >>> G.add_edge("x", "a", capacity=3.0) | |
410 >>> G.add_edge("x", "b", capacity=1.0) | |
411 >>> G.add_edge("a", "c", capacity=3.0) | |
412 >>> G.add_edge("b", "c", capacity=5.0) | |
413 >>> G.add_edge("b", "d", capacity=4.0) | |
414 >>> G.add_edge("d", "e", capacity=2.0) | |
415 >>> G.add_edge("c", "y", capacity=2.0) | |
416 >>> G.add_edge("e", "y", capacity=3.0) | |
417 | |
418 minimum_cut computes both the value of the | |
419 minimum cut and the node partition: | |
420 | |
421 >>> cut_value, partition = nx.minimum_cut(G, "x", "y") | |
422 >>> reachable, non_reachable = partition | |
423 | |
424 'partition' here is a tuple with the two sets of nodes that define | |
425 the minimum cut. You can compute the cut set of edges that induce | |
426 the minimum cut as follows: | |
427 | |
428 >>> cutset = set() | |
429 >>> for u, nbrs in ((n, G[n]) for n in reachable): | |
430 ... cutset.update((u, v) for v in nbrs if v in non_reachable) | |
431 >>> print(sorted(cutset)) | |
432 [('c', 'y'), ('x', 'b')] | |
433 >>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset) | |
434 True | |
435 | |
436 You can also use alternative algorithms for computing the | |
437 minimum cut by using the flow_func parameter. | |
438 | |
439 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
440 >>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0] | |
441 True | |
442 | |
443 """ | |
444 if flow_func is None: | |
445 if kwargs: | |
446 raise nx.NetworkXError( | |
447 "You have to explicitly set a flow_func if" | |
448 " you need to pass parameters via kwargs." | |
449 ) | |
450 flow_func = default_flow_func | |
451 | |
452 if not callable(flow_func): | |
453 raise nx.NetworkXError("flow_func has to be callable.") | |
454 | |
455 if kwargs.get("cutoff") is not None and flow_func in flow_funcs: | |
456 raise nx.NetworkXError("cutoff should not be specified.") | |
457 | |
458 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs) | |
459 # Remove saturated edges from the residual network | |
460 cutset = [(u, v, d) for u, v, d in R.edges(data=True) if d["flow"] == d["capacity"]] | |
461 R.remove_edges_from(cutset) | |
462 | |
463 # Then, reachable and non reachable nodes from source in the | |
464 # residual network form the node partition that defines | |
465 # the minimum cut. | |
466 non_reachable = set(dict(nx.shortest_path_length(R, target=_t))) | |
467 partition = (set(flowG) - non_reachable, non_reachable) | |
468 # Finally add again cutset edges to the residual network to make | |
469 # sure that it is reusable. | |
470 if cutset is not None: | |
471 R.add_edges_from(cutset) | |
472 return (R.graph["flow_value"], partition) | |
473 | |
474 | |
475 def minimum_cut_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs): | |
476 """Compute the value of a minimum (s, t)-cut. | |
477 | |
478 Use the max-flow min-cut theorem, i.e., the capacity of a minimum | |
479 capacity cut is equal to the flow value of a maximum flow. | |
480 | |
481 Parameters | |
482 ---------- | |
483 flowG : NetworkX graph | |
484 Edges of the graph are expected to have an attribute called | |
485 'capacity'. If this attribute is not present, the edge is | |
486 considered to have infinite capacity. | |
487 | |
488 _s : node | |
489 Source node for the flow. | |
490 | |
491 _t : node | |
492 Sink node for the flow. | |
493 | |
494 capacity : string | |
495 Edges of the graph G are expected to have an attribute capacity | |
496 that indicates how much flow the edge can support. If this | |
497 attribute is not present, the edge is considered to have | |
498 infinite capacity. Default value: 'capacity'. | |
499 | |
500 flow_func : function | |
501 A function for computing the maximum flow among a pair of nodes | |
502 in a capacitated graph. The function has to accept at least three | |
503 parameters: a Graph or Digraph, a source node, and a target node. | |
504 And return a residual network that follows NetworkX conventions | |
505 (see Notes). If flow_func is None, the default maximum | |
506 flow function (:meth:`preflow_push`) is used. See below for | |
507 alternative algorithms. The choice of the default function may change | |
508 from version to version and should not be relied on. Default value: | |
509 None. | |
510 | |
511 kwargs : Any other keyword parameter is passed to the function that | |
512 computes the maximum flow. | |
513 | |
514 Returns | |
515 ------- | |
516 cut_value : integer, float | |
517 Value of the minimum cut. | |
518 | |
519 Raises | |
520 ------ | |
521 NetworkXUnbounded | |
522 If the graph has a path of infinite capacity, all cuts have | |
523 infinite capacity and the function raises a NetworkXError. | |
524 | |
525 See also | |
526 -------- | |
527 :meth:`maximum_flow` | |
528 :meth:`maximum_flow_value` | |
529 :meth:`minimum_cut` | |
530 :meth:`edmonds_karp` | |
531 :meth:`preflow_push` | |
532 :meth:`shortest_augmenting_path` | |
533 | |
534 Notes | |
535 ----- | |
536 The function used in the flow_func parameter has to return a residual | |
537 network that follows NetworkX conventions: | |
538 | |
539 The residual network :samp:`R` from an input graph :samp:`G` has the | |
540 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair | |
541 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a | |
542 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists | |
543 in :samp:`G`. | |
544 | |
545 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']` | |
546 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists | |
547 in :samp:`G` or zero otherwise. If the capacity is infinite, | |
548 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value | |
549 that does not affect the solution of the problem. This value is stored in | |
550 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`, | |
551 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and | |
552 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`. | |
553 | |
554 The flow value, defined as the total flow into :samp:`t`, the sink, is | |
555 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using | |
556 only edges :samp:`(u, v)` such that | |
557 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum | |
558 :samp:`s`-:samp:`t` cut. | |
559 | |
560 Specific algorithms may store extra data in :samp:`R`. | |
561 | |
562 The function should supports an optional boolean parameter value_only. When | |
563 True, it can optionally terminate the algorithm as soon as the maximum flow | |
564 value and the minimum cut can be determined. | |
565 | |
566 Examples | |
567 -------- | |
568 >>> G = nx.DiGraph() | |
569 >>> G.add_edge("x", "a", capacity=3.0) | |
570 >>> G.add_edge("x", "b", capacity=1.0) | |
571 >>> G.add_edge("a", "c", capacity=3.0) | |
572 >>> G.add_edge("b", "c", capacity=5.0) | |
573 >>> G.add_edge("b", "d", capacity=4.0) | |
574 >>> G.add_edge("d", "e", capacity=2.0) | |
575 >>> G.add_edge("c", "y", capacity=2.0) | |
576 >>> G.add_edge("e", "y", capacity=3.0) | |
577 | |
578 minimum_cut_value computes only the value of the | |
579 minimum cut: | |
580 | |
581 >>> cut_value = nx.minimum_cut_value(G, "x", "y") | |
582 >>> cut_value | |
583 3.0 | |
584 | |
585 You can also use alternative algorithms for computing the | |
586 minimum cut by using the flow_func parameter. | |
587 | |
588 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
589 >>> cut_value == nx.minimum_cut_value( | |
590 ... G, "x", "y", flow_func=shortest_augmenting_path | |
591 ... ) | |
592 True | |
593 | |
594 """ | |
595 if flow_func is None: | |
596 if kwargs: | |
597 raise nx.NetworkXError( | |
598 "You have to explicitly set a flow_func if" | |
599 " you need to pass parameters via kwargs." | |
600 ) | |
601 flow_func = default_flow_func | |
602 | |
603 if not callable(flow_func): | |
604 raise nx.NetworkXError("flow_func has to be callable.") | |
605 | |
606 if kwargs.get("cutoff") is not None and flow_func in flow_funcs: | |
607 raise nx.NetworkXError("cutoff should not be specified.") | |
608 | |
609 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs) | |
610 | |
611 return R.graph["flow_value"] |