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"""
2Edmonds-Karp algorithm for maximum flow problems.
3"""
5import networkx as nx
6from networkx.algorithms.flow.utils import build_residual_network
8__all__ = ["edmonds_karp"]
11def edmonds_karp_core(R, s, t, cutoff):
12 """Implementation of the Edmonds-Karp algorithm."""
13 R_nodes = R.nodes
14 R_pred = R.pred
15 R_succ = R.succ
17 inf = R.graph["inf"]
19 def augment(path):
20 """Augment flow along a path from s to t."""
21 # Determine the path residual capacity.
22 flow = inf
23 it = iter(path)
24 u = next(it)
25 for v in it:
26 attr = R_succ[u][v]
27 flow = min(flow, attr["capacity"] - attr["flow"])
28 u = v
29 if flow * 2 > inf:
30 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
31 # Augment flow along the path.
32 it = iter(path)
33 u = next(it)
34 for v in it:
35 R_succ[u][v]["flow"] += flow
36 R_succ[v][u]["flow"] -= flow
37 u = v
38 return flow
40 def bidirectional_bfs():
41 """Bidirectional breadth-first search for an augmenting path."""
42 pred = {s: None}
43 q_s = [s]
44 succ = {t: None}
45 q_t = [t]
46 while True:
47 q = []
48 if len(q_s) <= len(q_t):
49 for u in q_s:
50 for v, attr in R_succ[u].items():
51 if v not in pred and attr["flow"] < attr["capacity"]:
52 pred[v] = u
53 if v in succ:
54 return v, pred, succ
55 q.append(v)
56 if not q:
57 return None, None, None
58 q_s = q
59 else:
60 for u in q_t:
61 for v, attr in R_pred[u].items():
62 if v not in succ and attr["flow"] < attr["capacity"]:
63 succ[v] = u
64 if v in pred:
65 return v, pred, succ
66 q.append(v)
67 if not q:
68 return None, None, None
69 q_t = q
71 # Look for shortest augmenting paths using breadth-first search.
72 flow_value = 0
73 while flow_value < cutoff:
74 v, pred, succ = bidirectional_bfs()
75 if pred is None:
76 break
77 path = [v]
78 # Trace a path from s to v.
79 u = v
80 while u != s:
81 u = pred[u]
82 path.append(u)
83 path.reverse()
84 # Trace a path from v to t.
85 u = v
86 while u != t:
87 u = succ[u]
88 path.append(u)
89 flow_value += augment(path)
91 return flow_value
94def edmonds_karp_impl(G, s, t, capacity, residual, cutoff):
95 """Implementation of the Edmonds-Karp algorithm."""
96 if s not in G:
97 raise nx.NetworkXError(f"node {str(s)} not in graph")
98 if t not in G:
99 raise nx.NetworkXError(f"node {str(t)} not in graph")
100 if s == t:
101 raise nx.NetworkXError("source and sink are the same node")
103 if residual is None:
104 R = build_residual_network(G, capacity)
105 else:
106 R = residual
108 # Initialize/reset the residual network.
109 for u in R:
110 for e in R[u].values():
111 e["flow"] = 0
113 if cutoff is None:
114 cutoff = float("inf")
115 R.graph["flow_value"] = edmonds_karp_core(R, s, t, cutoff)
117 return R
120@nx._dispatchable(
121 edge_attrs={"capacity": float("inf")}, returns_graph=True, preserve_edge_attrs=True
122)
123def edmonds_karp(
124 G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None
125):
126 """Find a maximum single-commodity flow using the Edmonds-Karp algorithm.
128 This function returns the residual network resulting after computing
129 the maximum flow. See below for details about the conventions
130 NetworkX uses for defining residual networks.
132 This algorithm has a running time of $O(n m^2)$ for $n$ nodes and $m$
133 edges.
136 Parameters
137 ----------
138 G : NetworkX graph
139 Edges of the graph are expected to have an attribute called
140 'capacity'. If this attribute is not present, the edge is
141 considered to have infinite capacity.
143 s : node
144 Source node for the flow.
146 t : node
147 Sink node for the flow.
149 capacity : string or function (default= 'capacity')
150 If this is a string, then edge capacity will be accessed via the
151 edge attribute with this key (that is, the capacity of the edge
152 joining `u` to `v` will be ``G.edges[u, v][capacity]``). If no
153 such edge attribute exists, the capacity of the edge is assumed to
154 be infinite.
156 If this is a function, the capacity of an edge is the value
157 returned by the function. The function must accept exactly three
158 positional arguments: the two endpoints of an edge and the
159 dictionary of edge attributes for that edge. The function must
160 return a number or None to indicate a hidden edge.
162 residual : NetworkX graph
163 Residual network on which the algorithm is to be executed. If None, a
164 new residual network is created. Default value: None.
166 value_only : bool
167 If True compute only the value of the maximum flow. This parameter
168 will be ignored by this algorithm because it is not applicable.
170 cutoff : integer, float
171 If specified, the algorithm will terminate when the flow value reaches
172 or exceeds the cutoff. In this case, it may be unable to immediately
173 determine a minimum cut. Default value: None.
175 Returns
176 -------
177 R : NetworkX DiGraph
178 Residual network after computing the maximum flow.
180 Raises
181 ------
182 NetworkXError
183 The algorithm does not support MultiGraph and MultiDiGraph. If
184 the input graph is an instance of one of these two classes, a
185 NetworkXError is raised.
187 NetworkXUnbounded
188 If the graph has a path of infinite capacity, the value of a
189 feasible flow on the graph is unbounded above and the function
190 raises a NetworkXUnbounded.
192 See also
193 --------
194 :meth:`maximum_flow`
195 :meth:`minimum_cut`
196 :meth:`preflow_push`
197 :meth:`shortest_augmenting_path`
199 Notes
200 -----
201 The residual network :samp:`R` from an input graph :samp:`G` has the
202 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
203 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
204 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
205 in :samp:`G`.
207 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
208 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
209 in :samp:`G` or zero otherwise. If the capacity is infinite,
210 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
211 that does not affect the solution of the problem. This value is stored in
212 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
213 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
214 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
216 The flow value, defined as the total flow into :samp:`t`, the sink, is
217 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
218 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
219 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
220 :samp:`s`-:samp:`t` cut.
222 Examples
223 --------
224 >>> from networkx.algorithms.flow import edmonds_karp
226 The functions that implement flow algorithms and output a residual
227 network, such as this one, are not imported to the base NetworkX
228 namespace, so you have to explicitly import them from the flow package.
230 >>> G = nx.DiGraph()
231 >>> G.add_edge("x", "a", capacity=3.0)
232 >>> G.add_edge("x", "b", capacity=1.0)
233 >>> G.add_edge("a", "c", capacity=3.0)
234 >>> G.add_edge("b", "c", capacity=5.0)
235 >>> G.add_edge("b", "d", capacity=4.0)
236 >>> G.add_edge("d", "e", capacity=2.0)
237 >>> G.add_edge("c", "y", capacity=2.0)
238 >>> G.add_edge("e", "y", capacity=3.0)
239 >>> R = edmonds_karp(G, "x", "y")
240 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
241 >>> flow_value
242 3.0
243 >>> flow_value == R.graph["flow_value"]
244 True
246 """
247 R = edmonds_karp_impl(G, s, t, capacity, residual, cutoff)
248 R.graph["algorithm"] = "edmonds_karp"
249 nx._clear_cache(R)
250 return R