Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/flow/mincost.py: 56%

1""" 

2Minimum 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 

7import networkx as nx 

8 

9 

10@nx._dispatch(node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}) 

11def min_cost_flow_cost(G, demand="demand", capacity="capacity", weight="weight"): 

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

13 

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

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

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

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

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

19 is equal to the demand of that node. 

20 

21 Parameters 

22 ---------- 

23 G : NetworkX graph 

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

25 to be found. 

26 

27 demand : string 

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

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

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

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

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

33 demand. Default value: 'demand'. 

34 

35 capacity : string 

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

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

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

39 infinite capacity. Default value: 'capacity'. 

40 

41 weight : string 

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

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

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

45 Default value: 'weight'. 

46 

47 Returns 

48 ------- 

49 flowCost : integer, float 

50 Cost of a minimum cost flow satisfying all demands. 

51 

52 Raises 

53 ------ 

54 NetworkXError 

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

56 not connected. 

57 

58 NetworkXUnfeasible 

59 This exception is raised in the following situations: 

60 

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

62 flow satisfying all demands. 

63 * There is no flow satisfying all demand. 

64 

65 NetworkXUnbounded 

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

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

68 satisfying all demands is unbounded below. 

69 

70 See also 

71 -------- 

72 cost_of_flow, max_flow_min_cost, min_cost_flow, network_simplex 

73 

74 Notes 

75 ----- 

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

77 are floating point numbers (overflows and roundoff errors can 

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

79 multiplying the relevant edge attributes by a convenient 

80 constant factor (eg 100). 

81 

82 Examples 

83 -------- 

84 A simple example of a min cost flow problem. 

85 

86 >>> G = nx.DiGraph() 

87 >>> G.add_node("a", demand=-5) 

88 >>> G.add_node("d", demand=5) 

89 >>> G.add_edge("a", "b", weight=3, capacity=4) 

90 >>> G.add_edge("a", "c", weight=6, capacity=10) 

91 >>> G.add_edge("b", "d", weight=1, capacity=9) 

92 >>> G.add_edge("c", "d", weight=2, capacity=5) 

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

94 >>> flowCost 

95 24 

96 """ 

97 return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[0] 

98 

99 

100@nx._dispatch(node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}) 

101def min_cost_flow(G, demand="demand", capacity="capacity", weight="weight"): 

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

103 

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

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

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

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

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

109 is equal to the demand of that node. 

110 

111 Parameters 

112 ---------- 

113 G : NetworkX graph 

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

115 to be found. 

116 

117 demand : string 

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

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

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

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

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

123 demand. Default value: 'demand'. 

124 

125 capacity : string 

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

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

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

129 infinite capacity. Default value: 'capacity'. 

130 

131 weight : string 

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

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

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

135 Default value: 'weight'. 

136 

137 Returns 

138 ------- 

139 flowDict : dictionary 

140 Dictionary of dictionaries keyed by nodes such that 

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

142 

143 Raises 

144 ------ 

145 NetworkXError 

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

147 not connected. 

148 

149 NetworkXUnfeasible 

150 This exception is raised in the following situations: 

151 

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

153 flow satisfying all demands. 

154 * There is no flow satisfying all demand. 

155 

156 NetworkXUnbounded 

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

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

159 satisfying all demands is unbounded below. 

160 

161 See also 

162 -------- 

163 cost_of_flow, max_flow_min_cost, min_cost_flow_cost, network_simplex 

164 

165 Notes 

166 ----- 

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

168 are floating point numbers (overflows and roundoff errors can 

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

170 multiplying the relevant edge attributes by a convenient 

171 constant factor (eg 100). 

172 

173 Examples 

174 -------- 

175 A simple example of a min cost flow problem. 

176 

177 >>> G = nx.DiGraph() 

178 >>> G.add_node("a", demand=-5) 

179 >>> G.add_node("d", demand=5) 

180 >>> G.add_edge("a", "b", weight=3, capacity=4) 

181 >>> G.add_edge("a", "c", weight=6, capacity=10) 

182 >>> G.add_edge("b", "d", weight=1, capacity=9) 

183 >>> G.add_edge("c", "d", weight=2, capacity=5) 

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

185 """ 

186 return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[1] 

187 

188 

189@nx._dispatch(edge_attrs={"weight": 0}) 

190def cost_of_flow(G, flowDict, weight="weight"): 

191 """Compute the cost of the flow given by flowDict on graph G. 

192 

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

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

195 flow don't have the same edge set. 

196 

197 Parameters 

198 ---------- 

199 G : NetworkX graph 

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

201 to be found. 

202 

203 weight : string 

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

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

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

207 Default value: 'weight'. 

208 

209 flowDict : dictionary 

210 Dictionary of dictionaries keyed by nodes such that 

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

212 

213 Returns 

214 ------- 

215 cost : Integer, float 

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

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

218 

219 See also 

220 -------- 

221 max_flow_min_cost, min_cost_flow, min_cost_flow_cost, network_simplex 

222 

223 Notes 

224 ----- 

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

226 are floating point numbers (overflows and roundoff errors can 

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

228 multiplying the relevant edge attributes by a convenient 

229 constant factor (eg 100). 

230 """ 

231 return sum((flowDict[u][v] * d.get(weight, 0) for u, v, d in G.edges(data=True))) 

232 

233 

234@nx._dispatch(edge_attrs={"capacity": float("inf"), "weight": 0}) 

235def max_flow_min_cost(G, s, t, capacity="capacity", weight="weight"): 

236 """Returns a maximum (s, t)-flow of minimum cost. 

237 

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

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

240 s to t whose total cost is minimized. 

241 

242 Parameters 

243 ---------- 

244 G : NetworkX graph 

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

246 to be found. 

247 

248 s: node label 

249 Source of the flow. 

250 

251 t: node label 

252 Destination of the flow. 

253 

254 capacity: string 

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

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

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

258 infinite capacity. Default value: 'capacity'. 

259 

260 weight: string 

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

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

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

264 Default value: 'weight'. 

265 

266 Returns 

267 ------- 

268 flowDict: dictionary 

269 Dictionary of dictionaries keyed by nodes such that 

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

271 

272 Raises 

273 ------ 

274 NetworkXError 

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

276 not connected. 

277 

278 NetworkXUnbounded 

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

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

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

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

283 is unbounded below. 

284 

285 See also 

286 -------- 

287 cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex 

288 

289 Notes 

290 ----- 

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

292 are floating point numbers (overflows and roundoff errors can 

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

294 multiplying the relevant edge attributes by a convenient 

295 constant factor (eg 100). 

296 

297 Examples 

298 -------- 

299 >>> G = nx.DiGraph() 

300 >>> G.add_edges_from( 

301 ... [ 

302 ... (1, 2, {"capacity": 12, "weight": 4}), 

303 ... (1, 3, {"capacity": 20, "weight": 6}), 

304 ... (2, 3, {"capacity": 6, "weight": -3}), 

305 ... (2, 6, {"capacity": 14, "weight": 1}), 

306 ... (3, 4, {"weight": 9}), 

307 ... (3, 5, {"capacity": 10, "weight": 5}), 

308 ... (4, 2, {"capacity": 19, "weight": 13}), 

309 ... (4, 5, {"capacity": 4, "weight": 0}), 

310 ... (5, 7, {"capacity": 28, "weight": 2}), 

311 ... (6, 5, {"capacity": 11, "weight": 1}), 

312 ... (6, 7, {"weight": 8}), 

313 ... (7, 4, {"capacity": 6, "weight": 6}), 

314 ... ] 

315 ... ) 

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

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

318 >>> mincost 

319 373 

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

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

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

323 True 

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

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

326 ... ) 

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

328 True 

329 

330 """ 

331 maxFlow = nx.maximum_flow_value(G, s, t, capacity=capacity) 

332 H = nx.DiGraph(G) 

333 H.add_node(s, demand=-maxFlow) 

334 H.add_node(t, demand=maxFlow) 

335 return min_cost_flow(H, capacity=capacity, weight=weight)