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(edge_attrs={"capacity": float("inf")}, returns_graph=True)
167def 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.
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.
184 This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$
185 edges.
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.
195 s : node
196 Source node for the flow.
198 t : node
199 Sink node for the flow.
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'.
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.
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.
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.
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.
225 Returns
226 -------
227 R : NetworkX DiGraph
228 Residual network after computing the maximum flow.
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.
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.
242 See also
243 --------
244 :meth:`maximum_flow`
245 :meth:`minimum_cut`
246 :meth:`edmonds_karp`
247 :meth:`preflow_push`
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`.
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']`.
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.
272 Examples
273 --------
274 >>> from networkx.algorithms.flow import shortest_augmenting_path
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.
280 >>> G = nx.DiGraph()
281 >>> G.add_edge("x", "a", capacity=3.0)
282 >>> G.add_edge("x", "b", capacity=1.0)
283 >>> G.add_edge("a", "c", capacity=3.0)
284 >>> G.add_edge("b", "c", capacity=5.0)
285 >>> G.add_edge("b", "d", capacity=4.0)
286 >>> G.add_edge("d", "e", capacity=2.0)
287 >>> G.add_edge("c", "y", capacity=2.0)
288 >>> G.add_edge("e", "y", capacity=3.0)
289 >>> R = shortest_augmenting_path(G, "x", "y")
290 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
291 >>> flow_value
292 3.0
293 >>> flow_value == R.graph["flow_value"]
294 True
296 """
297 R = shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff)
298 R.graph["algorithm"] = "shortest_augmenting_path"
299 nx._clear_cache(R)
300 return R