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"""
2Dinitz' algorithm for maximum flow problems.
3"""
5from collections import deque
7import networkx as nx
8from networkx.algorithms.flow.utils import build_residual_network
9from networkx.utils import pairwise
11__all__ = ["dinitz"]
14@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
15def dinitz(G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None):
16 """Find a maximum single-commodity flow using Dinitz' algorithm.
18 This function returns the residual network resulting after computing
19 the maximum flow. See below for details about the conventions
20 NetworkX uses for defining residual networks.
22 This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$
23 edges [1]_.
26 Parameters
27 ----------
28 G : 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
40 Edges of the graph G are expected to have an attribute capacity
41 that indicates how much flow the edge can support. If this
42 attribute is not present, the edge is considered to have
43 infinite capacity. Default value: 'capacity'.
45 residual : NetworkX graph
46 Residual network on which the algorithm is to be executed. If None, a
47 new residual network is created. Default value: None.
49 value_only : bool
50 If True compute only the value of the maximum flow. This parameter
51 will be ignored by this algorithm because it is not applicable.
53 cutoff : integer, float
54 If specified, the algorithm will terminate when the flow value reaches
55 or exceeds the cutoff. In this case, it may be unable to immediately
56 determine a minimum cut. Default value: None.
58 Returns
59 -------
60 R : NetworkX DiGraph
61 Residual network after computing the maximum flow.
63 Raises
64 ------
65 NetworkXError
66 The algorithm does not support MultiGraph and MultiDiGraph. If
67 the input graph is an instance of one of these two classes, a
68 NetworkXError is raised.
70 NetworkXUnbounded
71 If the graph has a path of infinite capacity, the value of a
72 feasible flow on the graph is unbounded above and the function
73 raises a NetworkXUnbounded.
75 See also
76 --------
77 :meth:`maximum_flow`
78 :meth:`minimum_cut`
79 :meth:`preflow_push`
80 :meth:`shortest_augmenting_path`
82 Notes
83 -----
84 The residual network :samp:`R` from an input graph :samp:`G` has the
85 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
86 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
87 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
88 in :samp:`G`.
90 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
91 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
92 in :samp:`G` or zero otherwise. If the capacity is infinite,
93 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
94 that does not affect the solution of the problem. This value is stored in
95 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
96 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
97 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
99 The flow value, defined as the total flow into :samp:`t`, the sink, is
100 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
101 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
102 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
103 :samp:`s`-:samp:`t` cut.
105 Examples
106 --------
107 >>> from networkx.algorithms.flow import dinitz
109 The functions that implement flow algorithms and output a residual
110 network, such as this one, are not imported to the base NetworkX
111 namespace, so you have to explicitly import them from the flow package.
113 >>> G = nx.DiGraph()
114 >>> G.add_edge("x", "a", capacity=3.0)
115 >>> G.add_edge("x", "b", capacity=1.0)
116 >>> G.add_edge("a", "c", capacity=3.0)
117 >>> G.add_edge("b", "c", capacity=5.0)
118 >>> G.add_edge("b", "d", capacity=4.0)
119 >>> G.add_edge("d", "e", capacity=2.0)
120 >>> G.add_edge("c", "y", capacity=2.0)
121 >>> G.add_edge("e", "y", capacity=3.0)
122 >>> R = dinitz(G, "x", "y")
123 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
124 >>> flow_value
125 3.0
126 >>> flow_value == R.graph["flow_value"]
127 True
129 References
130 ----------
131 .. [1] Dinitz' Algorithm: The Original Version and Even's Version.
132 2006. Yefim Dinitz. In Theoretical Computer Science. Lecture
133 Notes in Computer Science. Volume 3895. pp 218-240.
134 https://doi.org/10.1007/11685654_10
136 """
137 R = dinitz_impl(G, s, t, capacity, residual, cutoff)
138 R.graph["algorithm"] = "dinitz"
139 nx._clear_cache(R)
140 return R
143def dinitz_impl(G, s, t, capacity, residual, cutoff):
144 if s not in G:
145 raise nx.NetworkXError(f"node {str(s)} not in graph")
146 if t not in G:
147 raise nx.NetworkXError(f"node {str(t)} not in graph")
148 if s == t:
149 raise nx.NetworkXError("source and sink are the same node")
151 if residual is None:
152 R = build_residual_network(G, capacity)
153 else:
154 R = residual
156 # Initialize/reset the residual network.
157 for u in R:
158 for e in R[u].values():
159 e["flow"] = 0
161 # Use an arbitrary high value as infinite. It is computed
162 # when building the residual network.
163 INF = R.graph["inf"]
165 if cutoff is None:
166 cutoff = INF
168 R_succ = R.succ
169 R_pred = R.pred
171 def breath_first_search():
172 parents = {}
173 vertex_dist = {s: 0}
174 queue = deque([(s, 0)])
175 # Record all the potential edges of shortest augmenting paths
176 while queue:
177 if t in parents:
178 break
179 u, dist = queue.popleft()
180 for v, attr in R_succ[u].items():
181 if attr["capacity"] - attr["flow"] > 0:
182 if v in parents:
183 if vertex_dist[v] == dist + 1:
184 parents[v].append(u)
185 else:
186 parents[v] = deque([u])
187 vertex_dist[v] = dist + 1
188 queue.append((v, dist + 1))
189 return parents
191 def depth_first_search(parents):
192 # DFS to find all the shortest augmenting paths
193 """Build a path using DFS starting from the sink"""
194 total_flow = 0
195 u = t
196 # path also functions as a stack
197 path = [u]
198 # The loop ends with no augmenting path left in the layered graph
199 while True:
200 if len(parents[u]) > 0:
201 v = parents[u][0]
202 path.append(v)
203 else:
204 path.pop()
205 if len(path) == 0:
206 break
207 v = path[-1]
208 parents[v].popleft()
209 # Augment the flow along the path found
210 if v == s:
211 flow = INF
212 for u, v in pairwise(path):
213 flow = min(flow, R_pred[u][v]["capacity"] - R_pred[u][v]["flow"])
214 for u, v in pairwise(reversed(path)):
215 R_pred[v][u]["flow"] += flow
216 R_pred[u][v]["flow"] -= flow
217 # Find the proper node to continue the search
218 if R_pred[v][u]["capacity"] - R_pred[v][u]["flow"] == 0:
219 parents[v].popleft()
220 while path[-1] != v:
221 path.pop()
222 total_flow += flow
223 v = path[-1]
224 u = v
225 return total_flow
227 flow_value = 0
228 while flow_value < cutoff:
229 parents = breath_first_search()
230 if t not in parents:
231 break
232 this_flow = depth_first_search(parents)
233 if this_flow * 2 > INF:
234 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
235 flow_value += this_flow
237 R.graph["flow_value"] = flow_value
238 return R