Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/flow/capacityscaling.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 Capacity scaling minimum cost flow algorithm. | |
3 """ | |
4 | |
5 __all__ = ["capacity_scaling"] | |
6 | |
7 from itertools import chain | |
8 from math import log | |
9 import networkx as nx | |
10 from ...utils import BinaryHeap | |
11 from ...utils import generate_unique_node | |
12 from ...utils import not_implemented_for | |
13 from ...utils import arbitrary_element | |
14 | |
15 | |
16 def _detect_unboundedness(R): | |
17 """Detect infinite-capacity negative cycles. | |
18 """ | |
19 s = generate_unique_node() | |
20 G = nx.DiGraph() | |
21 G.add_nodes_from(R) | |
22 | |
23 # Value simulating infinity. | |
24 inf = R.graph["inf"] | |
25 # True infinity. | |
26 f_inf = float("inf") | |
27 for u in R: | |
28 for v, e in R[u].items(): | |
29 # Compute the minimum weight of infinite-capacity (u, v) edges. | |
30 w = f_inf | |
31 for k, e in e.items(): | |
32 if e["capacity"] == inf: | |
33 w = min(w, e["weight"]) | |
34 if w != f_inf: | |
35 G.add_edge(u, v, weight=w) | |
36 | |
37 if nx.negative_edge_cycle(G): | |
38 raise nx.NetworkXUnbounded( | |
39 "Negative cost cycle of infinite capacity found. " | |
40 "Min cost flow may be unbounded below." | |
41 ) | |
42 | |
43 | |
44 @not_implemented_for("undirected") | |
45 def _build_residual_network(G, demand, capacity, weight): | |
46 """Build a residual network and initialize a zero flow. | |
47 """ | |
48 if sum(G.nodes[u].get(demand, 0) for u in G) != 0: | |
49 raise nx.NetworkXUnfeasible("Sum of the demands should be 0.") | |
50 | |
51 R = nx.MultiDiGraph() | |
52 R.add_nodes_from( | |
53 (u, {"excess": -G.nodes[u].get(demand, 0), "potential": 0}) for u in G | |
54 ) | |
55 | |
56 inf = float("inf") | |
57 # Detect selfloops with infinite capacities and negative weights. | |
58 for u, v, e in nx.selfloop_edges(G, data=True): | |
59 if e.get(weight, 0) < 0 and e.get(capacity, inf) == inf: | |
60 raise nx.NetworkXUnbounded( | |
61 "Negative cost cycle of infinite capacity found. " | |
62 "Min cost flow may be unbounded below." | |
63 ) | |
64 | |
65 # Extract edges with positive capacities. Self loops excluded. | |
66 if G.is_multigraph(): | |
67 edge_list = [ | |
68 (u, v, k, e) | |
69 for u, v, k, e in G.edges(data=True, keys=True) | |
70 if u != v and e.get(capacity, inf) > 0 | |
71 ] | |
72 else: | |
73 edge_list = [ | |
74 (u, v, 0, e) | |
75 for u, v, e in G.edges(data=True) | |
76 if u != v and e.get(capacity, inf) > 0 | |
77 ] | |
78 # Simulate infinity with the larger of the sum of absolute node imbalances | |
79 # the sum of finite edge capacities or any positive value if both sums are | |
80 # zero. This allows the infinite-capacity edges to be distinguished for | |
81 # unboundedness detection and directly participate in residual capacity | |
82 # calculation. | |
83 inf = ( | |
84 max( | |
85 sum(abs(R.nodes[u]["excess"]) for u in R), | |
86 2 | |
87 * sum( | |
88 e[capacity] | |
89 for u, v, k, e in edge_list | |
90 if capacity in e and e[capacity] != inf | |
91 ), | |
92 ) | |
93 or 1 | |
94 ) | |
95 for u, v, k, e in edge_list: | |
96 r = min(e.get(capacity, inf), inf) | |
97 w = e.get(weight, 0) | |
98 # Add both (u, v) and (v, u) into the residual network marked with the | |
99 # original key. (key[1] == True) indicates the (u, v) is in the | |
100 # original network. | |
101 R.add_edge(u, v, key=(k, True), capacity=r, weight=w, flow=0) | |
102 R.add_edge(v, u, key=(k, False), capacity=0, weight=-w, flow=0) | |
103 | |
104 # Record the value simulating infinity. | |
105 R.graph["inf"] = inf | |
106 | |
107 _detect_unboundedness(R) | |
108 | |
109 return R | |
110 | |
111 | |
112 def _build_flow_dict(G, R, capacity, weight): | |
113 """Build a flow dictionary from a residual network. | |
114 """ | |
115 inf = float("inf") | |
116 flow_dict = {} | |
117 if G.is_multigraph(): | |
118 for u in G: | |
119 flow_dict[u] = {} | |
120 for v, es in G[u].items(): | |
121 flow_dict[u][v] = { | |
122 # Always saturate negative selfloops. | |
123 k: ( | |
124 0 | |
125 if ( | |
126 u != v or e.get(capacity, inf) <= 0 or e.get(weight, 0) >= 0 | |
127 ) | |
128 else e[capacity] | |
129 ) | |
130 for k, e in es.items() | |
131 } | |
132 for v, es in R[u].items(): | |
133 if v in flow_dict[u]: | |
134 flow_dict[u][v].update( | |
135 (k[0], e["flow"]) for k, e in es.items() if e["flow"] > 0 | |
136 ) | |
137 else: | |
138 for u in G: | |
139 flow_dict[u] = { | |
140 # Always saturate negative selfloops. | |
141 v: ( | |
142 0 | |
143 if (u != v or e.get(capacity, inf) <= 0 or e.get(weight, 0) >= 0) | |
144 else e[capacity] | |
145 ) | |
146 for v, e in G[u].items() | |
147 } | |
148 flow_dict[u].update( | |
149 (v, e["flow"]) | |
150 for v, es in R[u].items() | |
151 for e in es.values() | |
152 if e["flow"] > 0 | |
153 ) | |
154 return flow_dict | |
155 | |
156 | |
157 def capacity_scaling( | |
158 G, demand="demand", capacity="capacity", weight="weight", heap=BinaryHeap | |
159 ): | |
160 r"""Find a minimum cost flow satisfying all demands in digraph G. | |
161 | |
162 This is a capacity scaling successive shortest augmenting path algorithm. | |
163 | |
164 G is a digraph with edge costs and capacities and in which nodes | |
165 have demand, i.e., they want to send or receive some amount of | |
166 flow. A negative demand means that the node wants to send flow, a | |
167 positive demand means that the node want to receive flow. A flow on | |
168 the digraph G satisfies all demand if the net flow into each node | |
169 is equal to the demand of that node. | |
170 | |
171 Parameters | |
172 ---------- | |
173 G : NetworkX graph | |
174 DiGraph or MultiDiGraph on which a minimum cost flow satisfying all | |
175 demands is to be found. | |
176 | |
177 demand : string | |
178 Nodes of the graph G are expected to have an attribute demand | |
179 that indicates how much flow a node wants to send (negative | |
180 demand) or receive (positive demand). Note that the sum of the | |
181 demands should be 0 otherwise the problem in not feasible. If | |
182 this attribute is not present, a node is considered to have 0 | |
183 demand. Default value: 'demand'. | |
184 | |
185 capacity : string | |
186 Edges of the graph G are expected to have an attribute capacity | |
187 that indicates how much flow the edge can support. If this | |
188 attribute is not present, the edge is considered to have | |
189 infinite capacity. Default value: 'capacity'. | |
190 | |
191 weight : string | |
192 Edges of the graph G are expected to have an attribute weight | |
193 that indicates the cost incurred by sending one unit of flow on | |
194 that edge. If not present, the weight is considered to be 0. | |
195 Default value: 'weight'. | |
196 | |
197 heap : class | |
198 Type of heap to be used in the algorithm. It should be a subclass of | |
199 :class:`MinHeap` or implement a compatible interface. | |
200 | |
201 If a stock heap implementation is to be used, :class:`BinaryHeap` is | |
202 recommended over :class:`PairingHeap` for Python implementations without | |
203 optimized attribute accesses (e.g., CPython) despite a slower | |
204 asymptotic running time. For Python implementations with optimized | |
205 attribute accesses (e.g., PyPy), :class:`PairingHeap` provides better | |
206 performance. Default value: :class:`BinaryHeap`. | |
207 | |
208 Returns | |
209 ------- | |
210 flowCost : integer | |
211 Cost of a minimum cost flow satisfying all demands. | |
212 | |
213 flowDict : dictionary | |
214 If G is a digraph, a dict-of-dicts keyed by nodes such that | |
215 flowDict[u][v] is the flow on edge (u, v). | |
216 If G is a MultiDiGraph, a dict-of-dicts-of-dicts keyed by nodes | |
217 so that flowDict[u][v][key] is the flow on edge (u, v, key). | |
218 | |
219 Raises | |
220 ------ | |
221 NetworkXError | |
222 This exception is raised if the input graph is not directed, | |
223 not connected. | |
224 | |
225 NetworkXUnfeasible | |
226 This exception is raised in the following situations: | |
227 | |
228 * The sum of the demands is not zero. Then, there is no | |
229 flow satisfying all demands. | |
230 * There is no flow satisfying all demand. | |
231 | |
232 NetworkXUnbounded | |
233 This exception is raised if the digraph G has a cycle of | |
234 negative cost and infinite capacity. Then, the cost of a flow | |
235 satisfying all demands is unbounded below. | |
236 | |
237 Notes | |
238 ----- | |
239 This algorithm does not work if edge weights are floating-point numbers. | |
240 | |
241 See also | |
242 -------- | |
243 :meth:`network_simplex` | |
244 | |
245 Examples | |
246 -------- | |
247 A simple example of a min cost flow problem. | |
248 | |
249 >>> G = nx.DiGraph() | |
250 >>> G.add_node("a", demand=-5) | |
251 >>> G.add_node("d", demand=5) | |
252 >>> G.add_edge("a", "b", weight=3, capacity=4) | |
253 >>> G.add_edge("a", "c", weight=6, capacity=10) | |
254 >>> G.add_edge("b", "d", weight=1, capacity=9) | |
255 >>> G.add_edge("c", "d", weight=2, capacity=5) | |
256 >>> flowCost, flowDict = nx.capacity_scaling(G) | |
257 >>> flowCost | |
258 24 | |
259 >>> flowDict # doctest: +SKIP | |
260 {'a': {'c': 1, 'b': 4}, 'c': {'d': 1}, 'b': {'d': 4}, 'd': {}} | |
261 | |
262 It is possible to change the name of the attributes used for the | |
263 algorithm. | |
264 | |
265 >>> G = nx.DiGraph() | |
266 >>> G.add_node("p", spam=-4) | |
267 >>> G.add_node("q", spam=2) | |
268 >>> G.add_node("a", spam=-2) | |
269 >>> G.add_node("d", spam=-1) | |
270 >>> G.add_node("t", spam=2) | |
271 >>> G.add_node("w", spam=3) | |
272 >>> G.add_edge("p", "q", cost=7, vacancies=5) | |
273 >>> G.add_edge("p", "a", cost=1, vacancies=4) | |
274 >>> G.add_edge("q", "d", cost=2, vacancies=3) | |
275 >>> G.add_edge("t", "q", cost=1, vacancies=2) | |
276 >>> G.add_edge("a", "t", cost=2, vacancies=4) | |
277 >>> G.add_edge("d", "w", cost=3, vacancies=4) | |
278 >>> G.add_edge("t", "w", cost=4, vacancies=1) | |
279 >>> flowCost, flowDict = nx.capacity_scaling( | |
280 ... G, demand="spam", capacity="vacancies", weight="cost" | |
281 ... ) | |
282 >>> flowCost | |
283 37 | |
284 >>> flowDict # doctest: +SKIP | |
285 {'a': {'t': 4}, 'd': {'w': 2}, 'q': {'d': 1}, 'p': {'q': 2, 'a': 2}, 't': {'q': 1, 'w': 1}, 'w': {}} | |
286 """ | |
287 R = _build_residual_network(G, demand, capacity, weight) | |
288 | |
289 inf = float("inf") | |
290 # Account cost of negative selfloops. | |
291 flow_cost = sum( | |
292 0 | |
293 if e.get(capacity, inf) <= 0 or e.get(weight, 0) >= 0 | |
294 else e[capacity] * e[weight] | |
295 for u, v, e in nx.selfloop_edges(G, data=True) | |
296 ) | |
297 | |
298 # Determine the maxmimum edge capacity. | |
299 wmax = max(chain([-inf], (e["capacity"] for u, v, e in R.edges(data=True)))) | |
300 if wmax == -inf: | |
301 # Residual network has no edges. | |
302 return flow_cost, _build_flow_dict(G, R, capacity, weight) | |
303 | |
304 R_nodes = R.nodes | |
305 R_succ = R.succ | |
306 | |
307 delta = 2 ** int(log(wmax, 2)) | |
308 while delta >= 1: | |
309 # Saturate Δ-residual edges with negative reduced costs to achieve | |
310 # Δ-optimality. | |
311 for u in R: | |
312 p_u = R_nodes[u]["potential"] | |
313 for v, es in R_succ[u].items(): | |
314 for k, e in es.items(): | |
315 flow = e["capacity"] - e["flow"] | |
316 if e["weight"] - p_u + R_nodes[v]["potential"] < 0: | |
317 flow = e["capacity"] - e["flow"] | |
318 if flow >= delta: | |
319 e["flow"] += flow | |
320 R_succ[v][u][(k[0], not k[1])]["flow"] -= flow | |
321 R_nodes[u]["excess"] -= flow | |
322 R_nodes[v]["excess"] += flow | |
323 # Determine the Δ-active nodes. | |
324 S = set() | |
325 T = set() | |
326 S_add = S.add | |
327 S_remove = S.remove | |
328 T_add = T.add | |
329 T_remove = T.remove | |
330 for u in R: | |
331 excess = R_nodes[u]["excess"] | |
332 if excess >= delta: | |
333 S_add(u) | |
334 elif excess <= -delta: | |
335 T_add(u) | |
336 # Repeatedly augment flow from S to T along shortest paths until | |
337 # Δ-feasibility is achieved. | |
338 while S and T: | |
339 s = arbitrary_element(S) | |
340 t = None | |
341 # Search for a shortest path in terms of reduce costs from s to | |
342 # any t in T in the Δ-residual network. | |
343 d = {} | |
344 pred = {s: None} | |
345 h = heap() | |
346 h_insert = h.insert | |
347 h_get = h.get | |
348 h_insert(s, 0) | |
349 while h: | |
350 u, d_u = h.pop() | |
351 d[u] = d_u | |
352 if u in T: | |
353 # Path found. | |
354 t = u | |
355 break | |
356 p_u = R_nodes[u]["potential"] | |
357 for v, es in R_succ[u].items(): | |
358 if v in d: | |
359 continue | |
360 wmin = inf | |
361 # Find the minimum-weighted (u, v) Δ-residual edge. | |
362 for k, e in es.items(): | |
363 if e["capacity"] - e["flow"] >= delta: | |
364 w = e["weight"] | |
365 if w < wmin: | |
366 wmin = w | |
367 kmin = k | |
368 emin = e | |
369 if wmin == inf: | |
370 continue | |
371 # Update the distance label of v. | |
372 d_v = d_u + wmin - p_u + R_nodes[v]["potential"] | |
373 if h_insert(v, d_v): | |
374 pred[v] = (u, kmin, emin) | |
375 if t is not None: | |
376 # Augment Δ units of flow from s to t. | |
377 while u != s: | |
378 v = u | |
379 u, k, e = pred[v] | |
380 e["flow"] += delta | |
381 R_succ[v][u][(k[0], not k[1])]["flow"] -= delta | |
382 # Account node excess and deficit. | |
383 R_nodes[s]["excess"] -= delta | |
384 R_nodes[t]["excess"] += delta | |
385 if R_nodes[s]["excess"] < delta: | |
386 S_remove(s) | |
387 if R_nodes[t]["excess"] > -delta: | |
388 T_remove(t) | |
389 # Update node potentials. | |
390 d_t = d[t] | |
391 for u, d_u in d.items(): | |
392 R_nodes[u]["potential"] -= d_u - d_t | |
393 else: | |
394 # Path not found. | |
395 S_remove(s) | |
396 delta //= 2 | |
397 | |
398 if any(R.nodes[u]["excess"] != 0 for u in R): | |
399 raise nx.NetworkXUnfeasible("No flow satisfying all demands.") | |
400 | |
401 # Calculate the flow cost. | |
402 for u in R: | |
403 for v, es in R_succ[u].items(): | |
404 for e in es.values(): | |
405 flow = e["flow"] | |
406 if flow > 0: | |
407 flow_cost += flow * e["weight"] | |
408 | |
409 return flow_cost, _build_flow_dict(G, R, capacity, weight) |