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(
15 edge_attrs={"capacity": float("inf")}, returns_graph=True, preserve_edge_attrs=True
16)
17def dinitz(G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None):
18 """Find a maximum single-commodity flow using Dinitz' algorithm.
20 This function returns the residual network resulting after computing
21 the maximum flow. See below for details about the conventions
22 NetworkX uses for defining residual networks.
24 This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$
25 edges [1]_.
28 Parameters
29 ----------
30 G : NetworkX graph
31 Edges of the graph are expected to have an attribute called
32 'capacity'. If this attribute is not present, the edge is
33 considered to have infinite capacity.
35 s : node
36 Source node for the flow.
38 t : node
39 Sink node for the flow.
41 capacity : string or function (default= 'capacity')
42 If this is a string, then edge capacity will be accessed via the
43 edge attribute with this key (that is, the capacity of the edge
44 joining `u` to `v` will be ``G.edges[u, v][capacity]``). If no
45 such edge attribute exists, the capacity of the edge is assumed to
46 be infinite.
48 If this is a function, the capacity of an edge is the value
49 returned by the function. The function must accept exactly three
50 positional arguments: the two endpoints of an edge and the
51 dictionary of edge attributes for that edge. The function must
52 return a number or None to indicate a hidden edge.
54 residual : NetworkX graph
55 Residual network on which the algorithm is to be executed. If None, a
56 new residual network is created. Default value: None.
58 value_only : bool
59 If True compute only the value of the maximum flow. This parameter
60 will be ignored by this algorithm because it is not applicable.
62 cutoff : integer, float
63 If specified, the algorithm will terminate when the flow value reaches
64 or exceeds the cutoff. In this case, it may be unable to immediately
65 determine a minimum cut. Default value: None.
67 Returns
68 -------
69 R : NetworkX DiGraph
70 Residual network after computing the maximum flow.
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.
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.
84 See also
85 --------
86 :meth:`maximum_flow`
87 :meth:`minimum_cut`
88 :meth:`preflow_push`
89 :meth:`shortest_augmenting_path`
91 Notes
92 -----
93 The residual network :samp:`R` from an input graph :samp:`G` has the
94 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
95 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
96 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
97 in :samp:`G`.
99 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
100 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
101 in :samp:`G` or zero otherwise. If the capacity is infinite,
102 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
103 that does not affect the solution of the problem. This value is stored in
104 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
105 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
106 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
108 The flow value, defined as the total flow into :samp:`t`, the sink, is
109 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
110 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
111 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
112 :samp:`s`-:samp:`t` cut.
114 Examples
115 --------
116 >>> from networkx.algorithms.flow import dinitz
118 The functions that implement flow algorithms and output a residual
119 network, such as this one, are not imported to the base NetworkX
120 namespace, so you have to explicitly import them from the flow package.
122 >>> G = nx.DiGraph()
123 >>> G.add_edge("x", "a", capacity=3.0)
124 >>> G.add_edge("x", "b", capacity=1.0)
125 >>> G.add_edge("a", "c", capacity=3.0)
126 >>> G.add_edge("b", "c", capacity=5.0)
127 >>> G.add_edge("b", "d", capacity=4.0)
128 >>> G.add_edge("d", "e", capacity=2.0)
129 >>> G.add_edge("c", "y", capacity=2.0)
130 >>> G.add_edge("e", "y", capacity=3.0)
131 >>> R = dinitz(G, "x", "y")
132 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
133 >>> flow_value
134 3.0
135 >>> flow_value == R.graph["flow_value"]
136 True
138 References
139 ----------
140 .. [1] Dinitz' Algorithm: The Original Version and Even's Version.
141 2006. Yefim Dinitz. In Theoretical Computer Science. Lecture
142 Notes in Computer Science. Volume 3895. pp 218-240.
143 https://doi.org/10.1007/11685654_10
145 """
146 R = dinitz_impl(G, s, t, capacity, residual, cutoff)
147 R.graph["algorithm"] = "dinitz"
148 nx._clear_cache(R)
149 return R
152def dinitz_impl(G, s, t, capacity, residual, cutoff):
153 if s not in G:
154 raise nx.NetworkXError(f"node {str(s)} not in graph")
155 if t not in G:
156 raise nx.NetworkXError(f"node {str(t)} not in graph")
157 if s == t:
158 raise nx.NetworkXError("source and sink are the same node")
160 if residual is None:
161 R = build_residual_network(G, capacity)
162 else:
163 R = residual
165 # Initialize/reset the residual network.
166 for u in R:
167 for e in R[u].values():
168 e["flow"] = 0
170 # Use an arbitrary high value as infinite. It is computed
171 # when building the residual network.
172 INF = R.graph["inf"]
174 if cutoff is None:
175 cutoff = INF
177 R_succ = R.succ
178 R_pred = R.pred
180 def breath_first_search():
181 parents = {}
182 vertex_dist = {s: 0}
183 queue = deque([(s, 0)])
184 # Record all the potential edges of shortest augmenting paths
185 while queue:
186 if t in parents:
187 break
188 u, dist = queue.popleft()
189 for v, attr in R_succ[u].items():
190 if attr["capacity"] - attr["flow"] > 0:
191 if v in parents:
192 if vertex_dist[v] == dist + 1:
193 parents[v].append(u)
194 else:
195 parents[v] = deque([u])
196 vertex_dist[v] = dist + 1
197 queue.append((v, dist + 1))
198 return parents
200 def depth_first_search(parents):
201 # DFS to find all the shortest augmenting paths
202 """Build a path using DFS starting from the sink"""
203 total_flow = 0
204 u = t
205 # path also functions as a stack
206 path = [u]
207 # The loop ends with no augmenting path left in the layered graph
208 while True:
209 if len(parents[u]) > 0:
210 v = parents[u][0]
211 path.append(v)
212 else:
213 path.pop()
214 if len(path) == 0:
215 break
216 v = path[-1]
217 parents[v].popleft()
218 # Augment the flow along the path found
219 if v == s:
220 flow = INF
221 for u, v in pairwise(path):
222 flow = min(flow, R_pred[u][v]["capacity"] - R_pred[u][v]["flow"])
223 for u, v in pairwise(reversed(path)):
224 R_pred[v][u]["flow"] += flow
225 R_pred[u][v]["flow"] -= flow
226 # Find the proper node to continue the search
227 if R_pred[v][u]["capacity"] - R_pred[v][u]["flow"] == 0:
228 parents[v].popleft()
229 while path[-1] != v:
230 path.pop()
231 total_flow += flow
232 v = path[-1]
233 u = v
234 return total_flow
236 flow_value = 0
237 while flow_value < cutoff:
238 parents = breath_first_search()
239 if t not in parents:
240 break
241 this_flow = depth_first_search(parents)
242 if this_flow * 2 > INF:
243 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
244 flow_value += this_flow
246 R.graph["flow_value"] = flow_value
247 return R