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