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"""
2Shortest augmenting path algorithm for maximum flow problems.
3"""
5from collections import deque
7import networkx as nx
9from .edmondskarp import edmonds_karp_core
10from .utils import CurrentEdge, build_residual_network
12__all__ = ["shortest_augmenting_path"]
15def shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff):
16 """Implementation of the shortest augmenting path algorithm."""
17 if s not in G:
18 raise nx.NetworkXError(f"node {str(s)} not in graph")
19 if t not in G:
20 raise nx.NetworkXError(f"node {str(t)} not in graph")
21 if s == t:
22 raise nx.NetworkXError("source and sink are the same node")
24 if residual is None:
25 R = build_residual_network(G, capacity)
26 else:
27 R = residual
29 R_nodes = R.nodes
30 R_pred = R.pred
31 R_succ = R.succ
33 # Initialize/reset the residual network.
34 for u in R:
35 for e in R_succ[u].values():
36 e["flow"] = 0
38 # Initialize heights of the nodes.
39 heights = {t: 0}
40 q = deque([(t, 0)])
41 while q:
42 u, height = q.popleft()
43 height += 1
44 for v, attr in R_pred[u].items():
45 if v not in heights and attr["flow"] < attr["capacity"]:
46 heights[v] = height
47 q.append((v, height))
49 if s not in heights:
50 # t is not reachable from s in the residual network. The maximum flow
51 # must be zero.
52 R.graph["flow_value"] = 0
53 return R
55 n = len(G)
56 m = R.size() / 2
58 # Initialize heights and 'current edge' data structures of the nodes.
59 for u in R:
60 R_nodes[u]["height"] = heights[u] if u in heights else n
61 R_nodes[u]["curr_edge"] = CurrentEdge(R_succ[u])
63 # Initialize counts of nodes in each level.
64 counts = [0] * (2 * n - 1)
65 for u in R:
66 counts[R_nodes[u]["height"]] += 1
68 inf = R.graph["inf"]
70 def augment(path):
71 """Augment flow along a path from s to t."""
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
91 def relabel(u):
92 """Relabel a node to create an admissible edge."""
93 height = n - 1
94 for v, attr in R_succ[u].items():
95 if attr["flow"] < attr["capacity"]:
96 height = min(height, R_nodes[v]["height"])
97 return height + 1
99 if cutoff is None:
100 cutoff = float("inf")
102 # Phase 1: Look for shortest augmenting paths using depth-first search.
104 flow_value = 0
105 path = [s]
106 u = s
107 d = n if not two_phase else int(min(m**0.5, 2 * n ** (2.0 / 3)))
108 done = R_nodes[s]["height"] >= d
109 while not done:
110 height = R_nodes[u]["height"]
111 curr_edge = R_nodes[u]["curr_edge"]
112 # Depth-first search for the next node on the path to t.
113 while True:
114 v, attr = curr_edge.get()
115 if height == R_nodes[v]["height"] + 1 and attr["flow"] < attr["capacity"]:
116 # Advance to the next node following an admissible edge.
117 path.append(v)
118 u = v
119 break
120 try:
121 curr_edge.move_to_next()
122 except StopIteration:
123 counts[height] -= 1
124 if counts[height] == 0:
125 # Gap heuristic: If relabeling causes a level to become
126 # empty, a minimum cut has been identified. The algorithm
127 # can now be terminated.
128 R.graph["flow_value"] = flow_value
129 return R
130 height = relabel(u)
131 if u == s and height >= d:
132 if not two_phase:
133 # t is disconnected from s in the residual network. No
134 # more augmenting paths exist.
135 R.graph["flow_value"] = flow_value
136 return R
137 else:
138 # t is at least d steps away from s. End of phase 1.
139 done = True
140 break
141 counts[height] += 1
142 R_nodes[u]["height"] = height
143 if u != s:
144 # After relabeling, the last edge on the path is no longer
145 # admissible. Retreat one step to look for an alternative.
146 path.pop()
147 u = path[-1]
148 break
149 if u == t:
150 # t is reached. Augment flow along the path and reset it for a new
151 # depth-first search.
152 flow_value += augment(path)
153 if flow_value >= cutoff:
154 R.graph["flow_value"] = flow_value
155 return R
156 path = [s]
157 u = s
159 # Phase 2: Look for shortest augmenting paths using breadth-first search.
160 flow_value += edmonds_karp_core(R, s, t, cutoff - flow_value)
162 R.graph["flow_value"] = flow_value
163 return R
166@nx._dispatchable(
167 edge_attrs={"capacity": float("inf")}, returns_graph=True, preserve_edge_attrs=True
168)
169def shortest_augmenting_path(
170 G,
171 s,
172 t,
173 capacity="capacity",
174 residual=None,
175 value_only=False,
176 two_phase=False,
177 cutoff=None,
178):
179 r"""Find a maximum single-commodity flow using the shortest augmenting path
180 algorithm.
182 This function returns the residual network resulting after computing
183 the maximum flow. See below for details about the conventions
184 NetworkX uses for defining residual networks.
186 This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$
187 edges.
190 Parameters
191 ----------
192 G : NetworkX graph
193 Edges of the graph are expected to have an attribute called
194 'capacity'. If this attribute is not present, the edge is
195 considered to have infinite capacity.
197 s : node
198 Source node for the flow.
200 t : node
201 Sink node for the flow.
203 capacity : string or function (default= 'capacity')
204 If this is a string, then edge capacity will be accessed via the
205 edge attribute with this key (that is, the capacity of the edge
206 joining `u` to `v` will be ``G.edges[u, v][capacity]``). If no
207 such edge attribute exists, the capacity of the edge is assumed to
208 be infinite.
210 If this is a function, the capacity of an edge is the value
211 returned by the function. The function must accept exactly three
212 positional arguments: the two endpoints of an edge and the
213 dictionary of edge attributes for that edge. The function must
214 return a number or None to indicate a hidden edge.
216 residual : NetworkX graph
217 Residual network on which the algorithm is to be executed. If None, a
218 new residual network is created. Default value: None.
220 value_only : bool
221 If True compute only the value of the maximum flow. This parameter
222 will be ignored by this algorithm because it is not applicable.
224 two_phase : bool
225 If True, a two-phase variant is used. The two-phase variant improves
226 the running time on unit-capacity networks from $O(nm)$ to
227 $O(\min(n^{2/3}, m^{1/2}) m)$. Default value: False.
229 cutoff : integer, float
230 If specified, the algorithm will terminate when the flow value reaches
231 or exceeds the cutoff. In this case, it may be unable to immediately
232 determine a minimum cut. Default value: None.
234 Returns
235 -------
236 R : NetworkX DiGraph
237 Residual network after computing the maximum flow.
239 Raises
240 ------
241 NetworkXError
242 The algorithm does not support MultiGraph and MultiDiGraph. If
243 the input graph is an instance of one of these two classes, a
244 NetworkXError is raised.
246 NetworkXUnbounded
247 If the graph has a path of infinite capacity, the value of a
248 feasible flow on the graph is unbounded above and the function
249 raises a NetworkXUnbounded.
251 See also
252 --------
253 :meth:`maximum_flow`
254 :meth:`minimum_cut`
255 :meth:`edmonds_karp`
256 :meth:`preflow_push`
258 Notes
259 -----
260 The residual network :samp:`R` from an input graph :samp:`G` has the
261 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
262 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
263 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
264 in :samp:`G`.
266 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
267 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
268 in :samp:`G` or zero otherwise. If the capacity is infinite,
269 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
270 that does not affect the solution of the problem. This value is stored in
271 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
272 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
273 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
275 The flow value, defined as the total flow into :samp:`t`, the sink, is
276 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
277 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
278 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
279 :samp:`s`-:samp:`t` cut.
281 Examples
282 --------
283 >>> from networkx.algorithms.flow import shortest_augmenting_path
285 The functions that implement flow algorithms and output a residual
286 network, such as this one, are not imported to the base NetworkX
287 namespace, so you have to explicitly import them from the flow package.
289 >>> G = nx.DiGraph()
290 >>> G.add_edge("x", "a", capacity=3.0)
291 >>> G.add_edge("x", "b", capacity=1.0)
292 >>> G.add_edge("a", "c", capacity=3.0)
293 >>> G.add_edge("b", "c", capacity=5.0)
294 >>> G.add_edge("b", "d", capacity=4.0)
295 >>> G.add_edge("d", "e", capacity=2.0)
296 >>> G.add_edge("c", "y", capacity=2.0)
297 >>> G.add_edge("e", "y", capacity=3.0)
298 >>> R = shortest_augmenting_path(G, "x", "y")
299 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
300 >>> flow_value
301 3.0
302 >>> flow_value == R.graph["flow_value"]
303 True
305 """
306 R = shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff)
307 R.graph["algorithm"] = "shortest_augmenting_path"
308 nx._clear_cache(R)
309 return R