ioftools / networkxMiCe / networkxmaster / networkx / algorithms / flow / mincost.py @ 5cef0f13
History  View  Annotate  Download (12.2 KB)
1 
# * coding: utf8 *


2 
"""

3 
Minimum cost flow algorithms on directed connected graphs.

4 
"""

5  
6 
__author__ = """Loïc SéguinC. <loicseguin@gmail.com>"""

7 
# Copyright (C) 2010 Loïc SéguinC. <loicseguin@gmail.com>

8 
# All rights reserved.

9 
# BSD license.

10  
11  
12 
__all__ = ['min_cost_flow_cost',

13 
'min_cost_flow',

14 
'cost_of_flow',

15 
'max_flow_min_cost']

16  
17 
import networkx as nx 
18  
19  
20 
def min_cost_flow_cost(G, demand='demand', capacity='capacity', 
21 
weight='weight'):

22 
r"""Find the cost of a minimum cost flow satisfying all demands in digraph G.

23 

24 
G is a digraph with edge costs and capacities and in which nodes

25 
have demand, i.e., they want to send or receive some amount of

26 
flow. A negative demand means that the node wants to send flow, a

27 
positive demand means that the node want to receive flow. A flow on

28 
the digraph G satisfies all demand if the net flow into each node

29 
is equal to the demand of that node.

30 

31 
Parameters

32 


33 
G : NetworkX graph

34 
DiGraph on which a minimum cost flow satisfying all demands is

35 
to be found.

36 

37 
demand : string

38 
Nodes of the graph G are expected to have an attribute demand

39 
that indicates how much flow a node wants to send (negative

40 
demand) or receive (positive demand). Note that the sum of the

41 
demands should be 0 otherwise the problem in not feasible. If

42 
this attribute is not present, a node is considered to have 0

43 
demand. Default value: 'demand'.

44 

45 
capacity : string

46 
Edges of the graph G are expected to have an attribute capacity

47 
that indicates how much flow the edge can support. If this

48 
attribute is not present, the edge is considered to have

49 
infinite capacity. Default value: 'capacity'.

50 

51 
weight : string

52 
Edges of the graph G are expected to have an attribute weight

53 
that indicates the cost incurred by sending one unit of flow on

54 
that edge. If not present, the weight is considered to be 0.

55 
Default value: 'weight'.

56 

57 
Returns

58 


59 
flowCost : integer, float

60 
Cost of a minimum cost flow satisfying all demands.

61 

62 
Raises

63 


64 
NetworkXError

65 
This exception is raised if the input graph is not directed or

66 
not connected.

67 

68 
NetworkXUnfeasible

69 
This exception is raised in the following situations:

70 

71 
* The sum of the demands is not zero. Then, there is no

72 
flow satisfying all demands.

73 
* There is no flow satisfying all demand.

74 

75 
NetworkXUnbounded

76 
This exception is raised if the digraph G has a cycle of

77 
negative cost and infinite capacity. Then, the cost of a flow

78 
satisfying all demands is unbounded below.

79 

80 
See also

81 


82 
cost_of_flow, max_flow_min_cost, min_cost_flow, network_simplex

83 

84 
Notes

85 


86 
This algorithm is not guaranteed to work if edge weights or demands

87 
are floating point numbers (overflows and roundoff errors can

88 
cause problems). As a workaround you can use integer numbers by

89 
multiplying the relevant edge attributes by a convenient

90 
constant factor (eg 100).

91 

92 
Examples

93 


94 
A simple example of a min cost flow problem.

95 

96 
>>> import networkx as nx

97 
>>> G = nx.DiGraph()

98 
>>> G.add_node('a', demand = 5)

99 
>>> G.add_node('d', demand = 5)

100 
>>> G.add_edge('a', 'b', weight = 3, capacity = 4)

101 
>>> G.add_edge('a', 'c', weight = 6, capacity = 10)

102 
>>> G.add_edge('b', 'd', weight = 1, capacity = 9)

103 
>>> G.add_edge('c', 'd', weight = 2, capacity = 5)

104 
>>> flowCost = nx.min_cost_flow_cost(G)

105 
>>> flowCost

106 
24

107 
"""

108 
return nx.network_simplex(G, demand=demand, capacity=capacity,

109 
weight=weight)[0]

110  
111  
112 
def min_cost_flow(G, demand='demand', capacity='capacity', 
113 
weight='weight'):

114 
r"""Returns a minimum cost flow satisfying all demands in digraph G.

115 

116 
G is a digraph with edge costs and capacities and in which nodes

117 
have demand, i.e., they want to send or receive some amount of

118 
flow. A negative demand means that the node wants to send flow, a

119 
positive demand means that the node want to receive flow. A flow on

120 
the digraph G satisfies all demand if the net flow into each node

121 
is equal to the demand of that node.

122 

123 
Parameters

124 


125 
G : NetworkX graph

126 
DiGraph on which a minimum cost flow satisfying all demands is

127 
to be found.

128 

129 
demand : string

130 
Nodes of the graph G are expected to have an attribute demand

131 
that indicates how much flow a node wants to send (negative

132 
demand) or receive (positive demand). Note that the sum of the

133 
demands should be 0 otherwise the problem in not feasible. If

134 
this attribute is not present, a node is considered to have 0

135 
demand. Default value: 'demand'.

136 

137 
capacity : string

138 
Edges of the graph G are expected to have an attribute capacity

139 
that indicates how much flow the edge can support. If this

140 
attribute is not present, the edge is considered to have

141 
infinite capacity. Default value: 'capacity'.

142 

143 
weight : string

144 
Edges of the graph G are expected to have an attribute weight

145 
that indicates the cost incurred by sending one unit of flow on

146 
that edge. If not present, the weight is considered to be 0.

147 
Default value: 'weight'.

148 

149 
Returns

150 


151 
flowDict : dictionary

152 
Dictionary of dictionaries keyed by nodes such that

153 
flowDict[u][v] is the flow edge (u, v).

154 

155 
Raises

156 


157 
NetworkXError

158 
This exception is raised if the input graph is not directed or

159 
not connected.

160 

161 
NetworkXUnfeasible

162 
This exception is raised in the following situations:

163 

164 
* The sum of the demands is not zero. Then, there is no

165 
flow satisfying all demands.

166 
* There is no flow satisfying all demand.

167 

168 
NetworkXUnbounded

169 
This exception is raised if the digraph G has a cycle of

170 
negative cost and infinite capacity. Then, the cost of a flow

171 
satisfying all demands is unbounded below.

172 

173 
See also

174 


175 
cost_of_flow, max_flow_min_cost, min_cost_flow_cost, network_simplex

176 

177 
Notes

178 


179 
This algorithm is not guaranteed to work if edge weights or demands

180 
are floating point numbers (overflows and roundoff errors can

181 
cause problems). As a workaround you can use integer numbers by

182 
multiplying the relevant edge attributes by a convenient

183 
constant factor (eg 100).

184 

185 
Examples

186 


187 
A simple example of a min cost flow problem.

188 

189 
>>> import networkx as nx

190 
>>> G = nx.DiGraph()

191 
>>> G.add_node('a', demand = 5)

192 
>>> G.add_node('d', demand = 5)

193 
>>> G.add_edge('a', 'b', weight = 3, capacity = 4)

194 
>>> G.add_edge('a', 'c', weight = 6, capacity = 10)

195 
>>> G.add_edge('b', 'd', weight = 1, capacity = 9)

196 
>>> G.add_edge('c', 'd', weight = 2, capacity = 5)

197 
>>> flowDict = nx.min_cost_flow(G)

198 
"""

199 
return nx.network_simplex(G, demand=demand, capacity=capacity,

200 
weight=weight)[1]

201  
202  
203 
def cost_of_flow(G, flowDict, weight='weight'): 
204 
"""Compute the cost of the flow given by flowDict on graph G.

205 

206 
Note that this function does not check for the validity of the

207 
flow flowDict. This function will fail if the graph G and the

208 
flow don't have the same edge set.

209 

210 
Parameters

211 


212 
G : NetworkX graph

213 
DiGraph on which a minimum cost flow satisfying all demands is

214 
to be found.

215 

216 
weight : string

217 
Edges of the graph G are expected to have an attribute weight

218 
that indicates the cost incurred by sending one unit of flow on

219 
that edge. If not present, the weight is considered to be 0.

220 
Default value: 'weight'.

221 

222 
flowDict : dictionary

223 
Dictionary of dictionaries keyed by nodes such that

224 
flowDict[u][v] is the flow edge (u, v).

225 

226 
Returns

227 


228 
cost : Integer, float

229 
The total cost of the flow. This is given by the sum over all

230 
edges of the product of the edge's flow and the edge's weight.

231 

232 
See also

233 


234 
max_flow_min_cost, min_cost_flow, min_cost_flow_cost, network_simplex

235 

236 
Notes

237 


238 
This algorithm is not guaranteed to work if edge weights or demands

239 
are floating point numbers (overflows and roundoff errors can

240 
cause problems). As a workaround you can use integer numbers by

241 
multiplying the relevant edge attributes by a convenient

242 
constant factor (eg 100).

243 
"""

244 
return sum((flowDict[u][v] * d.get(weight, 0) 
245 
for u, v, d in G.edges(data=True))) 
246  
247  
248 
def max_flow_min_cost(G, s, t, capacity='capacity', weight='weight'): 
249 
"""Returns a maximum (s, t)flow of minimum cost.

250 

251 
G is a digraph with edge costs and capacities. There is a source

252 
node s and a sink node t. This function finds a maximum flow from

253 
s to t whose total cost is minimized.

254 

255 
Parameters

256 


257 
G : NetworkX graph

258 
DiGraph on which a minimum cost flow satisfying all demands is

259 
to be found.

260 

261 
s: node label

262 
Source of the flow.

263 

264 
t: node label

265 
Destination of the flow.

266 

267 
capacity: string

268 
Edges of the graph G are expected to have an attribute capacity

269 
that indicates how much flow the edge can support. If this

270 
attribute is not present, the edge is considered to have

271 
infinite capacity. Default value: 'capacity'.

272 

273 
weight: string

274 
Edges of the graph G are expected to have an attribute weight

275 
that indicates the cost incurred by sending one unit of flow on

276 
that edge. If not present, the weight is considered to be 0.

277 
Default value: 'weight'.

278 

279 
Returns

280 


281 
flowDict: dictionary

282 
Dictionary of dictionaries keyed by nodes such that

283 
flowDict[u][v] is the flow edge (u, v).

284 

285 
Raises

286 


287 
NetworkXError

288 
This exception is raised if the input graph is not directed or

289 
not connected.

290 

291 
NetworkXUnbounded

292 
This exception is raised if there is an infinite capacity path

293 
from s to t in G. In this case there is no maximum flow. This

294 
exception is also raised if the digraph G has a cycle of

295 
negative cost and infinite capacity. Then, the cost of a flow

296 
is unbounded below.

297 

298 
See also

299 


300 
cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex

301 

302 
Notes

303 


304 
This algorithm is not guaranteed to work if edge weights or demands

305 
are floating point numbers (overflows and roundoff errors can

306 
cause problems). As a workaround you can use integer numbers by

307 
multiplying the relevant edge attributes by a convenient

308 
constant factor (eg 100).

309 

310 
Examples

311 


312 
>>> G = nx.DiGraph()

313 
>>> G.add_edges_from([(1, 2, {'capacity': 12, 'weight': 4}),

314 
... (1, 3, {'capacity': 20, 'weight': 6}),

315 
... (2, 3, {'capacity': 6, 'weight': 3}),

316 
... (2, 6, {'capacity': 14, 'weight': 1}),

317 
... (3, 4, {'weight': 9}),

318 
... (3, 5, {'capacity': 10, 'weight': 5}),

319 
... (4, 2, {'capacity': 19, 'weight': 13}),

320 
... (4, 5, {'capacity': 4, 'weight': 0}),

321 
... (5, 7, {'capacity': 28, 'weight': 2}),

322 
... (6, 5, {'capacity': 11, 'weight': 1}),

323 
... (6, 7, {'weight': 8}),

324 
... (7, 4, {'capacity': 6, 'weight': 6})])

325 
>>> mincostFlow = nx.max_flow_min_cost(G, 1, 7)

326 
>>> mincost = nx.cost_of_flow(G, mincostFlow)

327 
>>> mincost

328 
373

329 
>>> from networkx.algorithms.flow import maximum_flow

330 
>>> maxFlow = maximum_flow(G, 1, 7)[1]

331 
>>> nx.cost_of_flow(G, maxFlow) >= mincost

332 
True

333 
>>> mincostFlowValue = (sum((mincostFlow[u][7] for u in G.predecessors(7)))

334 
...  sum((mincostFlow[7][v] for v in G.successors(7))))

335 
>>> mincostFlowValue == nx.maximum_flow_value(G, 1, 7)

336 
True

337 

338 
"""

339 
maxFlow = nx.maximum_flow_value(G, s, t, capacity=capacity) 
340 
H = nx.DiGraph(G) 
341 
H.add_node(s, demand=maxFlow) 
342 
H.add_node(t, demand=maxFlow) 
343 
return min_cost_flow(H, capacity=capacity, weight=weight)
