## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/algorithms/flow/mincost.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"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) |