Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/flow/shortestaugmentingpath.py: 7%
115 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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._dispatch(
167 graphs={"G": 0, "residual?": 4},
168 edge_attrs={"capacity": float("inf")},
169 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
170 preserve_graph_attrs={"residual"},
171)
172def shortest_augmenting_path(
173 G,
174 s,
175 t,
176 capacity="capacity",
177 residual=None,
178 value_only=False,
179 two_phase=False,
180 cutoff=None,
181):
182 r"""Find a maximum single-commodity flow using the shortest augmenting path
183 algorithm.
185 This function returns the residual network resulting after computing
186 the maximum flow. See below for details about the conventions
187 NetworkX uses for defining residual networks.
189 This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$
190 edges.
193 Parameters
194 ----------
195 G : NetworkX graph
196 Edges of the graph are expected to have an attribute called
197 'capacity'. If this attribute is not present, the edge is
198 considered to have infinite capacity.
200 s : node
201 Source node for the flow.
203 t : node
204 Sink node for the flow.
206 capacity : string
207 Edges of the graph G are expected to have an attribute capacity
208 that indicates how much flow the edge can support. If this
209 attribute is not present, the edge is considered to have
210 infinite capacity. Default value: 'capacity'.
212 residual : NetworkX graph
213 Residual network on which the algorithm is to be executed. If None, a
214 new residual network is created. Default value: None.
216 value_only : bool
217 If True compute only the value of the maximum flow. This parameter
218 will be ignored by this algorithm because it is not applicable.
220 two_phase : bool
221 If True, a two-phase variant is used. The two-phase variant improves
222 the running time on unit-capacity networks from $O(nm)$ to
223 $O(\min(n^{2/3}, m^{1/2}) m)$. Default value: False.
225 cutoff : integer, float
226 If specified, the algorithm will terminate when the flow value reaches
227 or exceeds the cutoff. In this case, it may be unable to immediately
228 determine a minimum cut. Default value: None.
230 Returns
231 -------
232 R : NetworkX DiGraph
233 Residual network after computing the maximum flow.
235 Raises
236 ------
237 NetworkXError
238 The algorithm does not support MultiGraph and MultiDiGraph. If
239 the input graph is an instance of one of these two classes, a
240 NetworkXError is raised.
242 NetworkXUnbounded
243 If the graph has a path of infinite capacity, the value of a
244 feasible flow on the graph is unbounded above and the function
245 raises a NetworkXUnbounded.
247 See also
248 --------
249 :meth:`maximum_flow`
250 :meth:`minimum_cut`
251 :meth:`edmonds_karp`
252 :meth:`preflow_push`
254 Notes
255 -----
256 The residual network :samp:`R` from an input graph :samp:`G` has the
257 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
258 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
259 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
260 in :samp:`G`.
262 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
263 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
264 in :samp:`G` or zero otherwise. If the capacity is infinite,
265 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
266 that does not affect the solution of the problem. This value is stored in
267 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
268 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
269 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
271 The flow value, defined as the total flow into :samp:`t`, the sink, is
272 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
273 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
274 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
275 :samp:`s`-:samp:`t` cut.
277 Examples
278 --------
279 >>> from networkx.algorithms.flow import shortest_augmenting_path
281 The functions that implement flow algorithms and output a residual
282 network, such as this one, are not imported to the base NetworkX
283 namespace, so you have to explicitly import them from the flow package.
285 >>> G = nx.DiGraph()
286 >>> G.add_edge("x", "a", capacity=3.0)
287 >>> G.add_edge("x", "b", capacity=1.0)
288 >>> G.add_edge("a", "c", capacity=3.0)
289 >>> G.add_edge("b", "c", capacity=5.0)
290 >>> G.add_edge("b", "d", capacity=4.0)
291 >>> G.add_edge("d", "e", capacity=2.0)
292 >>> G.add_edge("c", "y", capacity=2.0)
293 >>> G.add_edge("e", "y", capacity=3.0)
294 >>> R = shortest_augmenting_path(G, "x", "y")
295 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
296 >>> flow_value
297 3.0
298 >>> flow_value == R.graph["flow_value"]
299 True
301 """
302 R = shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff)
303 R.graph["algorithm"] = "shortest_augmenting_path"
304 return R