Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/flow/dinitz_alg.py: 12%
67 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Dinitz' algorithm for maximum flow problems.
3"""
4from collections import deque
6import networkx as nx
7from networkx.algorithms.flow.utils import build_residual_network
8from networkx.utils import pairwise
10__all__ = ["dinitz"]
13@nx._dispatch(
14 graphs={"G": 0, "residual?": 4},
15 edge_attrs={"capacity": float("inf")},
16 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
17 preserve_graph_attrs={"residual"},
18)
19def dinitz(G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None):
20 """Find a maximum single-commodity flow using Dinitz' algorithm.
22 This function returns the residual network resulting after computing
23 the maximum flow. See below for details about the conventions
24 NetworkX uses for defining residual networks.
26 This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$
27 edges [1]_.
30 Parameters
31 ----------
32 G : 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.
37 s : node
38 Source node for the flow.
40 t : node
41 Sink node for the flow.
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'.
49 residual : NetworkX graph
50 Residual network on which the algorithm is to be executed. If None, a
51 new residual network is created. Default value: None.
53 value_only : bool
54 If True compute only the value of the maximum flow. This parameter
55 will be ignored by this algorithm because it is not applicable.
57 cutoff : integer, float
58 If specified, the algorithm will terminate when the flow value reaches
59 or exceeds the cutoff. In this case, it may be unable to immediately
60 determine a minimum cut. Default value: None.
62 Returns
63 -------
64 R : NetworkX DiGraph
65 Residual network after computing the maximum flow.
67 Raises
68 ------
69 NetworkXError
70 The algorithm does not support MultiGraph and MultiDiGraph. If
71 the input graph is an instance of one of these two classes, a
72 NetworkXError is raised.
74 NetworkXUnbounded
75 If the graph has a path of infinite capacity, the value of a
76 feasible flow on the graph is unbounded above and the function
77 raises a NetworkXUnbounded.
79 See also
80 --------
81 :meth:`maximum_flow`
82 :meth:`minimum_cut`
83 :meth:`preflow_push`
84 :meth:`shortest_augmenting_path`
86 Notes
87 -----
88 The residual network :samp:`R` from an input graph :samp:`G` has the
89 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
90 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
91 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
92 in :samp:`G`.
94 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
95 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
96 in :samp:`G` or zero otherwise. If the capacity is infinite,
97 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
98 that does not affect the solution of the problem. This value is stored in
99 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
100 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
101 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
103 The flow value, defined as the total flow into :samp:`t`, the sink, is
104 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
105 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
106 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
107 :samp:`s`-:samp:`t` cut.
109 Examples
110 --------
111 >>> from networkx.algorithms.flow import dinitz
113 The functions that implement flow algorithms and output a residual
114 network, such as this one, are not imported to the base NetworkX
115 namespace, so you have to explicitly import them from the flow package.
117 >>> G = nx.DiGraph()
118 >>> G.add_edge("x", "a", capacity=3.0)
119 >>> G.add_edge("x", "b", capacity=1.0)
120 >>> G.add_edge("a", "c", capacity=3.0)
121 >>> G.add_edge("b", "c", capacity=5.0)
122 >>> G.add_edge("b", "d", capacity=4.0)
123 >>> G.add_edge("d", "e", capacity=2.0)
124 >>> G.add_edge("c", "y", capacity=2.0)
125 >>> G.add_edge("e", "y", capacity=3.0)
126 >>> R = dinitz(G, "x", "y")
127 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
128 >>> flow_value
129 3.0
130 >>> flow_value == R.graph["flow_value"]
131 True
133 References
134 ----------
135 .. [1] Dinitz' Algorithm: The Original Version and Even's Version.
136 2006. Yefim Dinitz. In Theoretical Computer Science. Lecture
137 Notes in Computer Science. Volume 3895. pp 218-240.
138 https://doi.org/10.1007/11685654_10
140 """
141 R = dinitz_impl(G, s, t, capacity, residual, cutoff)
142 R.graph["algorithm"] = "dinitz"
143 return R
146def dinitz_impl(G, s, t, capacity, residual, cutoff):
147 if s not in G:
148 raise nx.NetworkXError(f"node {str(s)} not in graph")
149 if t not in G:
150 raise nx.NetworkXError(f"node {str(t)} not in graph")
151 if s == t:
152 raise nx.NetworkXError("source and sink are the same node")
154 if residual is None:
155 R = build_residual_network(G, capacity)
156 else:
157 R = residual
159 # Initialize/reset the residual network.
160 for u in R:
161 for e in R[u].values():
162 e["flow"] = 0
164 # Use an arbitrary high value as infinite. It is computed
165 # when building the residual network.
166 INF = R.graph["inf"]
168 if cutoff is None:
169 cutoff = INF
171 R_succ = R.succ
172 R_pred = R.pred
174 def breath_first_search():
175 parents = {}
176 queue = deque([s])
177 while queue:
178 if t in parents:
179 break
180 u = queue.popleft()
181 for v in R_succ[u]:
182 attr = R_succ[u][v]
183 if v not in parents and attr["capacity"] - attr["flow"] > 0:
184 parents[v] = u
185 queue.append(v)
186 return parents
188 def depth_first_search(parents):
189 """Build a path using DFS starting from the sink"""
190 path = []
191 u = t
192 flow = INF
193 while u != s:
194 path.append(u)
195 v = parents[u]
196 flow = min(flow, R_pred[u][v]["capacity"] - R_pred[u][v]["flow"])
197 u = v
198 path.append(s)
199 # Augment the flow along the path found
200 if flow > 0:
201 for u, v in pairwise(path):
202 R_pred[u][v]["flow"] += flow
203 R_pred[v][u]["flow"] -= flow
204 return flow
206 flow_value = 0
207 while flow_value < cutoff:
208 parents = breath_first_search()
209 if t not in parents:
210 break
211 this_flow = depth_first_search(parents)
212 if this_flow * 2 > INF:
213 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
214 flow_value += this_flow
216 R.graph["flow_value"] = flow_value
217 return R