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