### comparison env/lib/python3.9/site-packages/networkx/algorithms/flow/shortestaugmentingpath.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """
2 Shortest augmenting path algorithm for maximum flow problems.
3 """
4
5 from collections import deque
6 import networkx as nx
7 from .utils import build_residual_network, CurrentEdge
8 from .edmondskarp import edmonds_karp_core
9
10 __all__ = ["shortest_augmenting_path"]
11
12
13 def shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff):
14 """Implementation of the shortest augmenting path algorithm.
15 """
16 if s not in G:
17 raise nx.NetworkXError(f"node {str(s)} not in graph")
18 if t not in G:
19 raise nx.NetworkXError(f"node {str(t)} not in graph")
20 if s == t:
21 raise nx.NetworkXError("source and sink are the same node")
22
23 if residual is None:
24 R = build_residual_network(G, capacity)
25 else:
26 R = residual
27
28 R_nodes = R.nodes
29 R_pred = R.pred
30 R_succ = R.succ
31
32 # Initialize/reset the residual network.
33 for u in R:
34 for e in R_succ[u].values():
35 e["flow"] = 0
36
37 # Initialize heights of the nodes.
38 heights = {t: 0}
39 q = deque([(t, 0)])
40 while q:
41 u, height = q.popleft()
42 height += 1
43 for v, attr in R_pred[u].items():
44 if v not in heights and attr["flow"] < attr["capacity"]:
45 heights[v] = height
46 q.append((v, height))
47
48 if s not in heights:
49 # t is not reachable from s in the residual network. The maximum flow
50 # must be zero.
51 R.graph["flow_value"] = 0
52 return R
53
54 n = len(G)
55 m = R.size() / 2
56
57 # Initialize heights and 'current edge' data structures of the nodes.
58 for u in R:
59 R_nodes[u]["height"] = heights[u] if u in heights else n
60 R_nodes[u]["curr_edge"] = CurrentEdge(R_succ[u])
61
62 # Initialize counts of nodes in each level.
63 counts =  * (2 * n - 1)
64 for u in R:
65 counts[R_nodes[u]["height"]] += 1
66
67 inf = R.graph["inf"]
68
69 def augment(path):
70 """Augment flow along a path from s to t.
71 """
72 # Determine the path residual capacity.
73 flow = inf
74 it = iter(path)
75 u = next(it)
76 for v in it:
77 attr = R_succ[u][v]
78 flow = min(flow, attr["capacity"] - attr["flow"])
79 u = v
80 if flow * 2 > inf:
81 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
82 # Augment flow along the path.
83 it = iter(path)
84 u = next(it)
85 for v in it:
86 R_succ[u][v]["flow"] += flow
87 R_succ[v][u]["flow"] -= flow
88 u = v
89 return flow
90
91 def relabel(u):
92 """Relabel a node to create an admissible edge.
93 """
94 height = n - 1
95 for v, attr in R_succ[u].items():
96 if attr["flow"] < attr["capacity"]:
97 height = min(height, R_nodes[v]["height"])
98 return height + 1
99
100 if cutoff is None:
101 cutoff = float("inf")
102
103 # Phase 1: Look for shortest augmenting paths using depth-first search.
104
105 flow_value = 0
106 path = [s]
107 u = s
108 d = n if not two_phase else int(min(m ** 0.5, 2 * n ** (2.0 / 3)))
109 done = R_nodes[s]["height"] >= d
110 while not done:
111 height = R_nodes[u]["height"]
112 curr_edge = R_nodes[u]["curr_edge"]
113 # Depth-first search for the next node on the path to t.
114 while True:
115 v, attr = curr_edge.get()
116 if height == R_nodes[v]["height"] + 1 and attr["flow"] < attr["capacity"]:
118 path.append(v)
119 u = v
120 break
121 try:
122 curr_edge.move_to_next()
123 except StopIteration:
124 counts[height] -= 1
125 if counts[height] == 0:
126 # Gap heuristic: If relabeling causes a level to become
127 # empty, a minimum cut has been identified. The algorithm
128 # can now be terminated.
129 R.graph["flow_value"] = flow_value
130 return R
131 height = relabel(u)
132 if u == s and height >= d:
133 if not two_phase:
134 # t is disconnected from s in the residual network. No
135 # more augmenting paths exist.
136 R.graph["flow_value"] = flow_value
137 return R
138 else:
139 # t is at least d steps away from s. End of phase 1.
140 done = True
141 break
142 counts[height] += 1
143 R_nodes[u]["height"] = height
144 if u != s:
145 # After relabeling, the last edge on the path is no longer
146 # admissible. Retreat one step to look for an alternative.
147 path.pop()
148 u = path[-1]
149 break
150 if u == t:
151 # t is reached. Augment flow along the path and reset it for a new
152 # depth-first search.
153 flow_value += augment(path)
154 if flow_value >= cutoff:
155 R.graph["flow_value"] = flow_value
156 return R
157 path = [s]
158 u = s
159
160 # Phase 2: Look for shortest augmenting paths using breadth-first search.
161 flow_value += edmonds_karp_core(R, s, t, cutoff - flow_value)
162
163 R.graph["flow_value"] = flow_value
164 return R
165
166
167 def shortest_augmenting_path(
168 G,
169 s,
170 t,
171 capacity="capacity",
172 residual=None,
173 value_only=False,
174 two_phase=False,
175 cutoff=None,
176 ):
177 r"""Find a maximum single-commodity flow using the shortest augmenting path
178 algorithm.
179
180 This function returns the residual network resulting after computing
181 the maximum flow. See below for details about the conventions
182 NetworkX uses for defining residual networks.
183
184 This algorithm has a running time of \$O(n^2 m)\$ for \$n\$ nodes and \$m\$
185 edges.
186
187
188 Parameters
189 ----------
190 G : NetworkX graph
191 Edges of the graph are expected to have an attribute called
192 'capacity'. If this attribute is not present, the edge is
193 considered to have infinite capacity.
194
195 s : node
196 Source node for the flow.
197
198 t : node
199 Sink node for the flow.
200
201 capacity : string
202 Edges of the graph G are expected to have an attribute capacity
203 that indicates how much flow the edge can support. If this
204 attribute is not present, the edge is considered to have
205 infinite capacity. Default value: 'capacity'.
206
207 residual : NetworkX graph
208 Residual network on which the algorithm is to be executed. If None, a
209 new residual network is created. Default value: None.
210
211 value_only : bool
212 If True compute only the value of the maximum flow. This parameter
213 will be ignored by this algorithm because it is not applicable.
214
215 two_phase : bool
216 If True, a two-phase variant is used. The two-phase variant improves
217 the running time on unit-capacity networks from \$O(nm)\$ to
218 \$O(\min(n^{2/3}, m^{1/2}) m)\$. Default value: False.
219
220 cutoff : integer, float
221 If specified, the algorithm will terminate when the flow value reaches
222 or exceeds the cutoff. In this case, it may be unable to immediately
223 determine a minimum cut. Default value: None.
224
225 Returns
226 -------
227 R : NetworkX DiGraph
228 Residual network after computing the maximum flow.
229
230 Raises
231 ------
232 NetworkXError
233 The algorithm does not support MultiGraph and MultiDiGraph. If
234 the input graph is an instance of one of these two classes, a
235 NetworkXError is raised.
236
237 NetworkXUnbounded
238 If the graph has a path of infinite capacity, the value of a
239 feasible flow on the graph is unbounded above and the function
240 raises a NetworkXUnbounded.
241
243 --------
244 :meth:`maximum_flow`
245 :meth:`minimum_cut`
246 :meth:`edmonds_karp`
247 :meth:`preflow_push`
248
249 Notes
250 -----
251 The residual network :samp:`R` from an input graph :samp:`G` has the
252 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
253 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
254 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
255 in :samp:`G`.
256
257 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
258 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
259 in :samp:`G` or zero otherwise. If the capacity is infinite,
260 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
261 that does not affect the solution of the problem. This value is stored in
262 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
263 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
264 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
265
266 The flow value, defined as the total flow into :samp:`t`, the sink, is
267 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
268 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
269 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
270 :samp:`s`-:samp:`t` cut.
271
272 Examples
273 --------
274 >>> from networkx.algorithms.flow import shortest_augmenting_path
275
276 The functions that implement flow algorithms and output a residual
277 network, such as this one, are not imported to the base NetworkX
278 namespace, so you have to explicitly import them from the flow package.
279
280 >>> G = nx.DiGraph()