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)