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(graphs="flowG", edge_attrs={"capacity": float("inf")})
21def maximum_flow(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
22 """Find a maximum single-commodity flow.
24 Parameters
25 ----------
26 flowG : NetworkX graph
27 Edges of the graph are expected to have an attribute called
28 'capacity'. If this attribute is not present, the edge is
29 considered to have infinite capacity.
31 _s : node
32 Source node for the flow.
34 _t : node
35 Sink node for the flow.
37 capacity : string
38 Edges of the graph G are expected to have an attribute capacity
39 that indicates how much flow the edge can support. If this
40 attribute is not present, the edge is considered to have
41 infinite capacity. Default value: 'capacity'.
43 flow_func : function
44 A function for computing the maximum flow among a pair of nodes
45 in a capacitated graph. The function has to accept at least three
46 parameters: a Graph or Digraph, a source node, and a target node.
47 And return a residual network that follows NetworkX conventions
48 (see Notes). If flow_func is None, the default maximum
49 flow function (:meth:`preflow_push`) is used. See below for
50 alternative algorithms. The choice of the default function may change
51 from version to version and should not be relied on. Default value:
52 None.
54 kwargs : Any other keyword parameter is passed to the function that
55 computes the maximum flow.
57 Returns
58 -------
59 flow_value : integer, float
60 Value of the maximum flow, i.e., net outflow from the source.
62 flow_dict : dict
63 A dictionary containing the value of the flow that went through
64 each edge.
66 Raises
67 ------
68 NetworkXError
69 The algorithm does not support MultiGraph and MultiDiGraph. If
70 the input graph is an instance of one of these two classes, a
71 NetworkXError is raised.
73 NetworkXUnbounded
74 If the graph has a path of infinite capacity, the value of a
75 feasible flow on the graph is unbounded above and the function
76 raises a NetworkXUnbounded.
78 See also
79 --------
80 :meth:`maximum_flow_value`
81 :meth:`minimum_cut`
82 :meth:`minimum_cut_value`
83 :meth:`edmonds_karp`
84 :meth:`preflow_push`
85 :meth:`shortest_augmenting_path`
87 Notes
88 -----
89 The function used in the flow_func parameter has to return a residual
90 network that follows NetworkX conventions:
92 The residual network :samp:`R` from an input graph :samp:`G` has the
93 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
94 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
95 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
96 in :samp:`G`.
98 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
99 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
100 in :samp:`G` or zero otherwise. If the capacity is infinite,
101 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
102 that does not affect the solution of the problem. This value is stored in
103 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
104 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
105 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
107 The flow value, defined as the total flow into :samp:`t`, the sink, is
108 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using
109 only edges :samp:`(u, v)` such that
110 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
111 :samp:`s`-:samp:`t` cut.
113 Specific algorithms may store extra data in :samp:`R`.
115 The function should supports an optional boolean parameter value_only. When
116 True, it can optionally terminate the algorithm as soon as the maximum flow
117 value and the minimum cut can be determined.
119 Note that the resulting maximum flow may contain flow cycles,
120 back-flow to the source, or some flow exiting the sink.
121 These are possible if there are cycles in the network.
123 Examples
124 --------
125 >>> G = nx.DiGraph()
126 >>> G.add_edge("x", "a", capacity=3.0)
127 >>> G.add_edge("x", "b", capacity=1.0)
128 >>> G.add_edge("a", "c", capacity=3.0)
129 >>> G.add_edge("b", "c", capacity=5.0)
130 >>> G.add_edge("b", "d", capacity=4.0)
131 >>> G.add_edge("d", "e", capacity=2.0)
132 >>> G.add_edge("c", "y", capacity=2.0)
133 >>> G.add_edge("e", "y", capacity=3.0)
135 maximum_flow returns both the value of the maximum flow and a
136 dictionary with all flows.
138 >>> flow_value, flow_dict = nx.maximum_flow(G, "x", "y")
139 >>> flow_value
140 3.0
141 >>> print(flow_dict["x"]["b"])
142 1.0
144 You can also use alternative algorithms for computing the
145 maximum flow by using the flow_func parameter.
147 >>> from networkx.algorithms.flow import shortest_augmenting_path
148 >>> flow_value == nx.maximum_flow(G, "x", "y", flow_func=shortest_augmenting_path)[
149 ... 0
150 ... ]
151 True
153 """
154 if flow_func is None:
155 if kwargs:
156 raise nx.NetworkXError(
157 "You have to explicitly set a flow_func if"
158 " you need to pass parameters via kwargs."
159 )
160 flow_func = default_flow_func
162 if not callable(flow_func):
163 raise nx.NetworkXError("flow_func has to be callable.")
165 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=False, **kwargs)
166 flow_dict = build_flow_dict(flowG, R)
168 return (R.graph["flow_value"], flow_dict)
171@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
172def maximum_flow_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
173 """Find the value of maximum single-commodity flow.
175 Parameters
176 ----------
177 flowG : NetworkX graph
178 Edges of the graph are expected to have an attribute called
179 'capacity'. If this attribute is not present, the edge is
180 considered to have infinite capacity.
182 _s : node
183 Source node for the flow.
185 _t : node
186 Sink node for the flow.
188 capacity : string
189 Edges of the graph G are expected to have an attribute capacity
190 that indicates how much flow the edge can support. If this
191 attribute is not present, the edge is considered to have
192 infinite capacity. Default value: 'capacity'.
194 flow_func : function
195 A function for computing the maximum flow among a pair of nodes
196 in a capacitated graph. The function has to accept at least three
197 parameters: a Graph or Digraph, a source node, and a target node.
198 And return a residual network that follows NetworkX conventions
199 (see Notes). If flow_func is None, the default maximum
200 flow function (:meth:`preflow_push`) is used. See below for
201 alternative algorithms. The choice of the default function may change
202 from version to version and should not be relied on. Default value:
203 None.
205 kwargs : Any other keyword parameter is passed to the function that
206 computes the maximum flow.
208 Returns
209 -------
210 flow_value : integer, float
211 Value of the maximum flow, i.e., net outflow from the source.
213 Raises
214 ------
215 NetworkXError
216 The algorithm does not support MultiGraph and MultiDiGraph. If
217 the input graph is an instance of one of these two classes, a
218 NetworkXError is raised.
220 NetworkXUnbounded
221 If the graph has a path of infinite capacity, the value of a
222 feasible flow on the graph is unbounded above and the function
223 raises a NetworkXUnbounded.
225 See also
226 --------
227 :meth:`maximum_flow`
228 :meth:`minimum_cut`
229 :meth:`minimum_cut_value`
230 :meth:`edmonds_karp`
231 :meth:`preflow_push`
232 :meth:`shortest_augmenting_path`
234 Notes
235 -----
236 The function used in the flow_func parameter has to return a residual
237 network that follows NetworkX conventions:
239 The residual network :samp:`R` from an input graph :samp:`G` has the
240 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
241 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
242 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
243 in :samp:`G`.
245 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
246 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
247 in :samp:`G` or zero otherwise. If the capacity is infinite,
248 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
249 that does not affect the solution of the problem. This value is stored in
250 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
251 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
252 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
254 The flow value, defined as the total flow into :samp:`t`, the sink, is
255 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using
256 only edges :samp:`(u, v)` such that
257 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
258 :samp:`s`-:samp:`t` cut.
260 Specific algorithms may store extra data in :samp:`R`.
262 The function should supports an optional boolean parameter value_only. When
263 True, it can optionally terminate the algorithm as soon as the maximum flow
264 value and the minimum cut can be determined.
266 Examples
267 --------
268 >>> G = nx.DiGraph()
269 >>> G.add_edge("x", "a", capacity=3.0)
270 >>> G.add_edge("x", "b", capacity=1.0)
271 >>> G.add_edge("a", "c", capacity=3.0)
272 >>> G.add_edge("b", "c", capacity=5.0)
273 >>> G.add_edge("b", "d", capacity=4.0)
274 >>> G.add_edge("d", "e", capacity=2.0)
275 >>> G.add_edge("c", "y", capacity=2.0)
276 >>> G.add_edge("e", "y", capacity=3.0)
278 maximum_flow_value computes only the value of the
279 maximum flow:
281 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
282 >>> flow_value
283 3.0
285 You can also use alternative algorithms for computing the
286 maximum flow by using the flow_func parameter.
288 >>> from networkx.algorithms.flow import shortest_augmenting_path
289 >>> flow_value == nx.maximum_flow_value(
290 ... G, "x", "y", flow_func=shortest_augmenting_path
291 ... )
292 True
294 """
295 if flow_func is None:
296 if kwargs:
297 raise nx.NetworkXError(
298 "You have to explicitly set a flow_func if"
299 " you need to pass parameters via kwargs."
300 )
301 flow_func = default_flow_func
303 if not callable(flow_func):
304 raise nx.NetworkXError("flow_func has to be callable.")
306 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
308 return R.graph["flow_value"]
311@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
312def 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.
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.
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.
325 _s : node
326 Source node for the flow.
328 _t : node
329 Sink node for the flow.
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'.
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.
348 kwargs : Any other keyword parameter is passed to the function that
349 computes the maximum flow.
351 Returns
352 -------
353 cut_value : integer, float
354 Value of the minimum cut.
356 partition : pair of node sets
357 A partitioning of the nodes that defines a minimum cut.
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.
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`
374 Notes
375 -----
376 The function used in the flow_func parameter has to return a residual
377 network that follows NetworkX conventions:
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`.
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']`.
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.
400 Specific algorithms may store extra data in :samp:`R`.
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.
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)
418 minimum_cut computes both the value of the
419 minimum cut and the node partition:
421 >>> cut_value, partition = nx.minimum_cut(G, "x", "y")
422 >>> reachable, non_reachable = partition
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:
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
436 You can also use alternative algorithms for computing the
437 minimum cut by using the flow_func parameter.
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
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
452 if not callable(flow_func):
453 raise nx.NetworkXError("flow_func has to be callable.")
455 if kwargs.get("cutoff") is not None and flow_func is preflow_push:
456 raise nx.NetworkXError("cutoff should not be specified.")
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)
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(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 R.add_edges_from(cutset)
471 return (R.graph["flow_value"], partition)
474@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
475def minimum_cut_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
476 """Compute the value of a minimum (s, t)-cut.
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.
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.
488 _s : node
489 Source node for the flow.
491 _t : node
492 Sink node for the flow.
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'.
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.
511 kwargs : Any other keyword parameter is passed to the function that
512 computes the maximum flow.
514 Returns
515 -------
516 cut_value : integer, float
517 Value of the minimum cut.
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.
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`
534 Notes
535 -----
536 The function used in the flow_func parameter has to return a residual
537 network that follows NetworkX conventions:
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`.
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']`.
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.
560 Specific algorithms may store extra data in :samp:`R`.
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.
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)
578 minimum_cut_value computes only the value of the
579 minimum cut:
581 >>> cut_value = nx.minimum_cut_value(G, "x", "y")
582 >>> cut_value
583 3.0
585 You can also use alternative algorithms for computing the
586 minimum cut by using the flow_func parameter.
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
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
603 if not callable(flow_func):
604 raise nx.NetworkXError("flow_func has to be callable.")
606 if kwargs.get("cutoff") is not None and flow_func is preflow_push:
607 raise nx.NetworkXError("cutoff should not be specified.")
609 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
611 return R.graph["flow_value"]