Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/flow/edmondskarp.py: 9%
92 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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"]
11@nx._dispatch(
12 graphs="R",
13 preserve_edge_attrs={"R": {"capacity": float("inf"), "flow": 0}},
14 preserve_graph_attrs=True,
15)
16def edmonds_karp_core(R, s, t, cutoff):
17 """Implementation of the Edmonds-Karp algorithm."""
18 R_nodes = R.nodes
19 R_pred = R.pred
20 R_succ = R.succ
22 inf = R.graph["inf"]
24 def augment(path):
25 """Augment flow along a path from s to t."""
26 # Determine the path residual capacity.
27 flow = inf
28 it = iter(path)
29 u = next(it)
30 for v in it:
31 attr = R_succ[u][v]
32 flow = min(flow, attr["capacity"] - attr["flow"])
33 u = v
34 if flow * 2 > inf:
35 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
36 # Augment flow along the path.
37 it = iter(path)
38 u = next(it)
39 for v in it:
40 R_succ[u][v]["flow"] += flow
41 R_succ[v][u]["flow"] -= flow
42 u = v
43 return flow
45 def bidirectional_bfs():
46 """Bidirectional breadth-first search for an augmenting path."""
47 pred = {s: None}
48 q_s = [s]
49 succ = {t: None}
50 q_t = [t]
51 while True:
52 q = []
53 if len(q_s) <= len(q_t):
54 for u in q_s:
55 for v, attr in R_succ[u].items():
56 if v not in pred and attr["flow"] < attr["capacity"]:
57 pred[v] = u
58 if v in succ:
59 return v, pred, succ
60 q.append(v)
61 if not q:
62 return None, None, None
63 q_s = q
64 else:
65 for u in q_t:
66 for v, attr in R_pred[u].items():
67 if v not in succ and attr["flow"] < attr["capacity"]:
68 succ[v] = u
69 if v in pred:
70 return v, pred, succ
71 q.append(v)
72 if not q:
73 return None, None, None
74 q_t = q
76 # Look for shortest augmenting paths using breadth-first search.
77 flow_value = 0
78 while flow_value < cutoff:
79 v, pred, succ = bidirectional_bfs()
80 if pred is None:
81 break
82 path = [v]
83 # Trace a path from s to v.
84 u = v
85 while u != s:
86 u = pred[u]
87 path.append(u)
88 path.reverse()
89 # Trace a path from v to t.
90 u = v
91 while u != t:
92 u = succ[u]
93 path.append(u)
94 flow_value += augment(path)
96 return flow_value
99def edmonds_karp_impl(G, s, t, capacity, residual, cutoff):
100 """Implementation of the Edmonds-Karp algorithm."""
101 if s not in G:
102 raise nx.NetworkXError(f"node {str(s)} not in graph")
103 if t not in G:
104 raise nx.NetworkXError(f"node {str(t)} not in graph")
105 if s == t:
106 raise nx.NetworkXError("source and sink are the same node")
108 if residual is None:
109 R = build_residual_network(G, capacity)
110 else:
111 R = residual
113 # Initialize/reset the residual network.
114 for u in R:
115 for e in R[u].values():
116 e["flow"] = 0
118 if cutoff is None:
119 cutoff = float("inf")
120 R.graph["flow_value"] = edmonds_karp_core(R, s, t, cutoff)
122 return R
125@nx._dispatch(
126 graphs={"G": 0, "residual?": 4},
127 edge_attrs={"capacity": float("inf")},
128 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
129 preserve_graph_attrs={"residual"},
130)
131def edmonds_karp(
132 G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None
133):
134 """Find a maximum single-commodity flow using the Edmonds-Karp algorithm.
136 This function returns the residual network resulting after computing
137 the maximum flow. See below for details about the conventions
138 NetworkX uses for defining residual networks.
140 This algorithm has a running time of $O(n m^2)$ for $n$ nodes and $m$
141 edges.
144 Parameters
145 ----------
146 G : NetworkX graph
147 Edges of the graph are expected to have an attribute called
148 'capacity'. If this attribute is not present, the edge is
149 considered to have infinite capacity.
151 s : node
152 Source node for the flow.
154 t : node
155 Sink node for the flow.
157 capacity : string
158 Edges of the graph G are expected to have an attribute capacity
159 that indicates how much flow the edge can support. If this
160 attribute is not present, the edge is considered to have
161 infinite capacity. Default value: 'capacity'.
163 residual : NetworkX graph
164 Residual network on which the algorithm is to be executed. If None, a
165 new residual network is created. Default value: None.
167 value_only : bool
168 If True compute only the value of the maximum flow. This parameter
169 will be ignored by this algorithm because it is not applicable.
171 cutoff : integer, float
172 If specified, the algorithm will terminate when the flow value reaches
173 or exceeds the cutoff. In this case, it may be unable to immediately
174 determine a minimum cut. Default value: None.
176 Returns
177 -------
178 R : NetworkX DiGraph
179 Residual network after computing the maximum flow.
181 Raises
182 ------
183 NetworkXError
184 The algorithm does not support MultiGraph and MultiDiGraph. If
185 the input graph is an instance of one of these two classes, a
186 NetworkXError is raised.
188 NetworkXUnbounded
189 If the graph has a path of infinite capacity, the value of a
190 feasible flow on the graph is unbounded above and the function
191 raises a NetworkXUnbounded.
193 See also
194 --------
195 :meth:`maximum_flow`
196 :meth:`minimum_cut`
197 :meth:`preflow_push`
198 :meth:`shortest_augmenting_path`
200 Notes
201 -----
202 The residual network :samp:`R` from an input graph :samp:`G` has the
203 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
204 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
205 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
206 in :samp:`G`.
208 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
209 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
210 in :samp:`G` or zero otherwise. If the capacity is infinite,
211 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
212 that does not affect the solution of the problem. This value is stored in
213 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
214 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
215 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
217 The flow value, defined as the total flow into :samp:`t`, the sink, is
218 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
219 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
220 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
221 :samp:`s`-:samp:`t` cut.
223 Examples
224 --------
225 >>> from networkx.algorithms.flow import edmonds_karp
227 The functions that implement flow algorithms and output a residual
228 network, such as this one, are not imported to the base NetworkX
229 namespace, so you have to explicitly import them from the flow package.
231 >>> G = nx.DiGraph()
232 >>> G.add_edge("x", "a", capacity=3.0)
233 >>> G.add_edge("x", "b", capacity=1.0)
234 >>> G.add_edge("a", "c", capacity=3.0)
235 >>> G.add_edge("b", "c", capacity=5.0)
236 >>> G.add_edge("b", "d", capacity=4.0)
237 >>> G.add_edge("d", "e", capacity=2.0)
238 >>> G.add_edge("c", "y", capacity=2.0)
239 >>> G.add_edge("e", "y", capacity=3.0)
240 >>> R = edmonds_karp(G, "x", "y")
241 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
242 >>> flow_value
243 3.0
244 >>> flow_value == R.graph["flow_value"]
245 True
247 """
248 R = edmonds_karp_impl(G, s, t, capacity, residual, cutoff)
249 R.graph["algorithm"] = "edmonds_karp"
250 return R