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(edge_attrs={"capacity": float("inf")}, returns_graph=True)
121def edmonds_karp(
122 G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None
123):
124 """Find a maximum single-commodity flow using the Edmonds-Karp algorithm.
126 This function returns the residual network resulting after computing
127 the maximum flow. See below for details about the conventions
128 NetworkX uses for defining residual networks.
130 This algorithm has a running time of $O(n m^2)$ for $n$ nodes and $m$
131 edges.
134 Parameters
135 ----------
136 G : NetworkX graph
137 Edges of the graph are expected to have an attribute called
138 'capacity'. If this attribute is not present, the edge is
139 considered to have infinite capacity.
141 s : node
142 Source node for the flow.
144 t : node
145 Sink node for the flow.
147 capacity : string
148 Edges of the graph G are expected to have an attribute capacity
149 that indicates how much flow the edge can support. If this
150 attribute is not present, the edge is considered to have
151 infinite capacity. Default value: 'capacity'.
153 residual : NetworkX graph
154 Residual network on which the algorithm is to be executed. If None, a
155 new residual network is created. Default value: None.
157 value_only : bool
158 If True compute only the value of the maximum flow. This parameter
159 will be ignored by this algorithm because it is not applicable.
161 cutoff : integer, float
162 If specified, the algorithm will terminate when the flow value reaches
163 or exceeds the cutoff. In this case, it may be unable to immediately
164 determine a minimum cut. Default value: None.
166 Returns
167 -------
168 R : NetworkX DiGraph
169 Residual network after computing the maximum flow.
171 Raises
172 ------
173 NetworkXError
174 The algorithm does not support MultiGraph and MultiDiGraph. If
175 the input graph is an instance of one of these two classes, a
176 NetworkXError is raised.
178 NetworkXUnbounded
179 If the graph has a path of infinite capacity, the value of a
180 feasible flow on the graph is unbounded above and the function
181 raises a NetworkXUnbounded.
183 See also
184 --------
185 :meth:`maximum_flow`
186 :meth:`minimum_cut`
187 :meth:`preflow_push`
188 :meth:`shortest_augmenting_path`
190 Notes
191 -----
192 The residual network :samp:`R` from an input graph :samp:`G` has the
193 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
194 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
195 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
196 in :samp:`G`.
198 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
199 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
200 in :samp:`G` or zero otherwise. If the capacity is infinite,
201 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
202 that does not affect the solution of the problem. This value is stored in
203 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
204 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
205 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
207 The flow value, defined as the total flow into :samp:`t`, the sink, is
208 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
209 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
210 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
211 :samp:`s`-:samp:`t` cut.
213 Examples
214 --------
215 >>> from networkx.algorithms.flow import edmonds_karp
217 The functions that implement flow algorithms and output a residual
218 network, such as this one, are not imported to the base NetworkX
219 namespace, so you have to explicitly import them from the flow package.
221 >>> G = nx.DiGraph()
222 >>> G.add_edge("x", "a", capacity=3.0)
223 >>> G.add_edge("x", "b", capacity=1.0)
224 >>> G.add_edge("a", "c", capacity=3.0)
225 >>> G.add_edge("b", "c", capacity=5.0)
226 >>> G.add_edge("b", "d", capacity=4.0)
227 >>> G.add_edge("d", "e", capacity=2.0)
228 >>> G.add_edge("c", "y", capacity=2.0)
229 >>> G.add_edge("e", "y", capacity=3.0)
230 >>> R = edmonds_karp(G, "x", "y")
231 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
232 >>> flow_value
233 3.0
234 >>> flow_value == R.graph["flow_value"]
235 True
237 """
238 R = edmonds_karp_impl(G, s, t, capacity, residual, cutoff)
239 R.graph["algorithm"] = "edmonds_karp"
240 nx._clear_cache(R)
241 return R