### annotate env/lib/python3.9/site-packages/networkx/algorithms/flow/mincost.py @ 0:4f3585e2f14bdraftdefaulttip

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