Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/flow/mincost.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 Minimum cost flow algorithms on directed connected graphs. | |
3 """ | |
4 | |
5 __all__ = ["min_cost_flow_cost", "min_cost_flow", "cost_of_flow", "max_flow_min_cost"] | |
6 | |
7 import networkx as nx | |
8 | |
9 | |
10 def min_cost_flow_cost(G, demand="demand", capacity="capacity", weight="weight"): | |
11 r"""Find the cost of a minimum cost flow satisfying all demands in digraph G. | |
12 | |
13 G is a digraph with edge costs and capacities and in which nodes | |
14 have demand, i.e., they want to send or receive some amount of | |
15 flow. A negative demand means that the node wants to send flow, a | |
16 positive demand means that the node want to receive flow. A flow on | |
17 the digraph G satisfies all demand if the net flow into each node | |
18 is equal to the demand of that node. | |
19 | |
20 Parameters | |
21 ---------- | |
22 G : NetworkX graph | |
23 DiGraph on which a minimum cost flow satisfying all demands is | |
24 to be found. | |
25 | |
26 demand : string | |
27 Nodes of the graph G are expected to have an attribute demand | |
28 that indicates how much flow a node wants to send (negative | |
29 demand) or receive (positive demand). Note that the sum of the | |
30 demands should be 0 otherwise the problem in not feasible. If | |
31 this attribute is not present, a node is considered to have 0 | |
32 demand. Default value: 'demand'. | |
33 | |
34 capacity : string | |
35 Edges of the graph G are expected to have an attribute capacity | |
36 that indicates how much flow the edge can support. If this | |
37 attribute is not present, the edge is considered to have | |
38 infinite capacity. Default value: 'capacity'. | |
39 | |
40 weight : string | |
41 Edges of the graph G are expected to have an attribute weight | |
42 that indicates the cost incurred by sending one unit of flow on | |
43 that edge. If not present, the weight is considered to be 0. | |
44 Default value: 'weight'. | |
45 | |
46 Returns | |
47 ------- | |
48 flowCost : integer, float | |
49 Cost of a minimum cost flow satisfying all demands. | |
50 | |
51 Raises | |
52 ------ | |
53 NetworkXError | |
54 This exception is raised if the input graph is not directed or | |
55 not connected. | |
56 | |
57 NetworkXUnfeasible | |
58 This exception is raised in the following situations: | |
59 | |
60 * The sum of the demands is not zero. Then, there is no | |
61 flow satisfying all demands. | |
62 * There is no flow satisfying all demand. | |
63 | |
64 NetworkXUnbounded | |
65 This exception is raised if the digraph G has a cycle of | |
66 negative cost and infinite capacity. Then, the cost of a flow | |
67 satisfying all demands is unbounded below. | |
68 | |
69 See also | |
70 -------- | |
71 cost_of_flow, max_flow_min_cost, min_cost_flow, network_simplex | |
72 | |
73 Notes | |
74 ----- | |
75 This algorithm is not guaranteed to work if edge weights or demands | |
76 are floating point numbers (overflows and roundoff errors can | |
77 cause problems). As a workaround you can use integer numbers by | |
78 multiplying the relevant edge attributes by a convenient | |
79 constant factor (eg 100). | |
80 | |
81 Examples | |
82 -------- | |
83 A simple example of a min cost flow problem. | |
84 | |
85 >>> G = nx.DiGraph() | |
86 >>> G.add_node("a", demand=-5) | |
87 >>> G.add_node("d", demand=5) | |
88 >>> G.add_edge("a", "b", weight=3, capacity=4) | |
89 >>> G.add_edge("a", "c", weight=6, capacity=10) | |
90 >>> G.add_edge("b", "d", weight=1, capacity=9) | |
91 >>> G.add_edge("c", "d", weight=2, capacity=5) | |
92 >>> flowCost = nx.min_cost_flow_cost(G) | |
93 >>> flowCost | |
94 24 | |
95 """ | |
96 return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[0] | |
97 | |
98 | |
99 def min_cost_flow(G, demand="demand", capacity="capacity", weight="weight"): | |
100 r"""Returns a minimum cost flow satisfying all demands in digraph G. | |
101 | |
102 G is a digraph with edge costs and capacities and in which nodes | |
103 have demand, i.e., they want to send or receive some amount of | |
104 flow. A negative demand means that the node wants to send flow, a | |
105 positive demand means that the node want to receive flow. A flow on | |
106 the digraph G satisfies all demand if the net flow into each node | |
107 is equal to the demand of that node. | |
108 | |
109 Parameters | |
110 ---------- | |
111 G : NetworkX graph | |
112 DiGraph on which a minimum cost flow satisfying all demands is | |
113 to be found. | |
114 | |
115 demand : string | |
116 Nodes of the graph G are expected to have an attribute demand | |
117 that indicates how much flow a node wants to send (negative | |
118 demand) or receive (positive demand). Note that the sum of the | |
119 demands should be 0 otherwise the problem in not feasible. If | |
120 this attribute is not present, a node is considered to have 0 | |
121 demand. Default value: 'demand'. | |
122 | |
123 capacity : string | |
124 Edges of the graph G are expected to have an attribute capacity | |
125 that indicates how much flow the edge can support. If this | |
126 attribute is not present, the edge is considered to have | |
127 infinite capacity. Default value: 'capacity'. | |
128 | |
129 weight : string | |
130 Edges of the graph G are expected to have an attribute weight | |
131 that indicates the cost incurred by sending one unit of flow on | |
132 that edge. If not present, the weight is considered to be 0. | |
133 Default value: 'weight'. | |
134 | |
135 Returns | |
136 ------- | |
137 flowDict : dictionary | |
138 Dictionary of dictionaries keyed by nodes such that | |
139 flowDict[u][v] is the flow edge (u, v). | |
140 | |
141 Raises | |
142 ------ | |
143 NetworkXError | |
144 This exception is raised if the input graph is not directed or | |
145 not connected. | |
146 | |
147 NetworkXUnfeasible | |
148 This exception is raised in the following situations: | |
149 | |
150 * The sum of the demands is not zero. Then, there is no | |
151 flow satisfying all demands. | |
152 * There is no flow satisfying all demand. | |
153 | |
154 NetworkXUnbounded | |
155 This exception is raised if the digraph G has a cycle of | |
156 negative cost and infinite capacity. Then, the cost of a flow | |
157 satisfying all demands is unbounded below. | |
158 | |
159 See also | |
160 -------- | |
161 cost_of_flow, max_flow_min_cost, min_cost_flow_cost, network_simplex | |
162 | |
163 Notes | |
164 ----- | |
165 This algorithm is not guaranteed to work if edge weights or demands | |
166 are floating point numbers (overflows and roundoff errors can | |
167 cause problems). As a workaround you can use integer numbers by | |
168 multiplying the relevant edge attributes by a convenient | |
169 constant factor (eg 100). | |
170 | |
171 Examples | |
172 -------- | |
173 A simple example of a min cost flow problem. | |
174 | |
175 >>> G = nx.DiGraph() | |
176 >>> G.add_node("a", demand=-5) | |
177 >>> G.add_node("d", demand=5) | |
178 >>> G.add_edge("a", "b", weight=3, capacity=4) | |
179 >>> G.add_edge("a", "c", weight=6, capacity=10) | |
180 >>> G.add_edge("b", "d", weight=1, capacity=9) | |
181 >>> G.add_edge("c", "d", weight=2, capacity=5) | |
182 >>> flowDict = nx.min_cost_flow(G) | |
183 """ | |
184 return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[1] | |
185 | |
186 | |
187 def cost_of_flow(G, flowDict, weight="weight"): | |
188 """Compute the cost of the flow given by flowDict on graph G. | |
189 | |
190 Note that this function does not check for the validity of the | |
191 flow flowDict. This function will fail if the graph G and the | |
192 flow don't have the same edge set. | |
193 | |
194 Parameters | |
195 ---------- | |
196 G : NetworkX graph | |
197 DiGraph on which a minimum cost flow satisfying all demands is | |
198 to be found. | |
199 | |
200 weight : string | |
201 Edges of the graph G are expected to have an attribute weight | |
202 that indicates the cost incurred by sending one unit of flow on | |
203 that edge. If not present, the weight is considered to be 0. | |
204 Default value: 'weight'. | |
205 | |
206 flowDict : dictionary | |
207 Dictionary of dictionaries keyed by nodes such that | |
208 flowDict[u][v] is the flow edge (u, v). | |
209 | |
210 Returns | |
211 ------- | |
212 cost : Integer, float | |
213 The total cost of the flow. This is given by the sum over all | |
214 edges of the product of the edge's flow and the edge's weight. | |
215 | |
216 See also | |
217 -------- | |
218 max_flow_min_cost, min_cost_flow, min_cost_flow_cost, network_simplex | |
219 | |
220 Notes | |
221 ----- | |
222 This algorithm is not guaranteed to work if edge weights or demands | |
223 are floating point numbers (overflows and roundoff errors can | |
224 cause problems). As a workaround you can use integer numbers by | |
225 multiplying the relevant edge attributes by a convenient | |
226 constant factor (eg 100). | |
227 """ | |
228 return sum((flowDict[u][v] * d.get(weight, 0) for u, v, d in G.edges(data=True))) | |
229 | |
230 | |
231 def max_flow_min_cost(G, s, t, capacity="capacity", weight="weight"): | |
232 """Returns a maximum (s, t)-flow of minimum cost. | |
233 | |
234 G is a digraph with edge costs and capacities. There is a source | |
235 node s and a sink node t. This function finds a maximum flow from | |
236 s to t whose total cost is minimized. | |
237 | |
238 Parameters | |
239 ---------- | |
240 G : NetworkX graph | |
241 DiGraph on which a minimum cost flow satisfying all demands is | |
242 to be found. | |
243 | |
244 s: node label | |
245 Source of the flow. | |
246 | |
247 t: node label | |
248 Destination of the flow. | |
249 | |
250 capacity: string | |
251 Edges of the graph G are expected to have an attribute capacity | |
252 that indicates how much flow the edge can support. If this | |
253 attribute is not present, the edge is considered to have | |
254 infinite capacity. Default value: 'capacity'. | |
255 | |
256 weight: string | |
257 Edges of the graph G are expected to have an attribute weight | |
258 that indicates the cost incurred by sending one unit of flow on | |
259 that edge. If not present, the weight is considered to be 0. | |
260 Default value: 'weight'. | |
261 | |
262 Returns | |
263 ------- | |
264 flowDict: dictionary | |
265 Dictionary of dictionaries keyed by nodes such that | |
266 flowDict[u][v] is the flow edge (u, v). | |
267 | |
268 Raises | |
269 ------ | |
270 NetworkXError | |
271 This exception is raised if the input graph is not directed or | |
272 not connected. | |
273 | |
274 NetworkXUnbounded | |
275 This exception is raised if there is an infinite capacity path | |
276 from s to t in G. In this case there is no maximum flow. This | |
277 exception is also raised if the digraph G has a cycle of | |
278 negative cost and infinite capacity. Then, the cost of a flow | |
279 is unbounded below. | |
280 | |
281 See also | |
282 -------- | |
283 cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex | |
284 | |
285 Notes | |
286 ----- | |
287 This algorithm is not guaranteed to work if edge weights or demands | |
288 are floating point numbers (overflows and roundoff errors can | |
289 cause problems). As a workaround you can use integer numbers by | |
290 multiplying the relevant edge attributes by a convenient | |
291 constant factor (eg 100). | |
292 | |
293 Examples | |
294 -------- | |
295 >>> G = nx.DiGraph() | |
296 >>> G.add_edges_from( | |
297 ... [ | |
298 ... (1, 2, {"capacity": 12, "weight": 4}), | |
299 ... (1, 3, {"capacity": 20, "weight": 6}), | |
300 ... (2, 3, {"capacity": 6, "weight": -3}), | |
301 ... (2, 6, {"capacity": 14, "weight": 1}), | |
302 ... (3, 4, {"weight": 9}), | |
303 ... (3, 5, {"capacity": 10, "weight": 5}), | |
304 ... (4, 2, {"capacity": 19, "weight": 13}), | |
305 ... (4, 5, {"capacity": 4, "weight": 0}), | |
306 ... (5, 7, {"capacity": 28, "weight": 2}), | |
307 ... (6, 5, {"capacity": 11, "weight": 1}), | |
308 ... (6, 7, {"weight": 8}), | |
309 ... (7, 4, {"capacity": 6, "weight": 6}), | |
310 ... ] | |
311 ... ) | |
312 >>> mincostFlow = nx.max_flow_min_cost(G, 1, 7) | |
313 >>> mincost = nx.cost_of_flow(G, mincostFlow) | |
314 >>> mincost | |
315 373 | |
316 >>> from networkx.algorithms.flow import maximum_flow | |
317 >>> maxFlow = maximum_flow(G, 1, 7)[1] | |
318 >>> nx.cost_of_flow(G, maxFlow) >= mincost | |
319 True | |
320 >>> mincostFlowValue = sum((mincostFlow[u][7] for u in G.predecessors(7))) - sum( | |
321 ... (mincostFlow[7][v] for v in G.successors(7)) | |
322 ... ) | |
323 >>> mincostFlowValue == nx.maximum_flow_value(G, 1, 7) | |
324 True | |
325 | |
326 """ | |
327 maxFlow = nx.maximum_flow_value(G, s, t, capacity=capacity) | |
328 H = nx.DiGraph(G) | |
329 H.add_node(s, demand=-maxFlow) | |
330 H.add_node(t, demand=maxFlow) | |
331 return min_cost_flow(H, capacity=capacity, weight=weight) |