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