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

1"""

2Maximum flow (and minimum cut) algorithms on capacitated graphs.

3"""

4import networkx as nx

6from .boykovkolmogorov import boykov_kolmogorov

7from .dinitz_alg import dinitz

8from .edmondskarp import edmonds_karp

9from .preflowpush import preflow_push

10from .shortestaugmentingpath import shortest_augmenting_path

11from .utils import build_flow_dict

13# Define the default flow function for computing maximum flow.

14default_flow_func = preflow_push

16__all__ = ["maximum_flow", "maximum_flow_value", "minimum_cut", "minimum_cut_value"]

19@nx._dispatch(graphs="flowG", edge_attrs={"capacity": float("inf")})

20def maximum_flow(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):

21 """Find a maximum single-commodity flow.

23 Parameters

24 ----------

25 flowG : NetworkX graph

26 Edges of the graph are expected to have an attribute called

27 'capacity'. If this attribute is not present, the edge is

28 considered to have infinite capacity.

30 _s : node

31 Source node for the flow.

33 _t : node

34 Sink node for the flow.

36 capacity : string

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

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

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

40 infinite capacity. Default value: 'capacity'.

42 flow_func : function

43 A function for computing the maximum flow among a pair of nodes

44 in a capacitated graph. The function has to accept at least three

45 parameters: a Graph or Digraph, a source node, and a target node.

46 And return a residual network that follows NetworkX conventions

47 (see Notes). If flow_func is None, the default maximum

48 flow function (:meth:`preflow_push`) is used. See below for

49 alternative algorithms. The choice of the default function may change

50 from version to version and should not be relied on. Default value:

51 None.

53 kwargs : Any other keyword parameter is passed to the function that

54 computes the maximum flow.

56 Returns

57 -------

58 flow_value : integer, float

59 Value of the maximum flow, i.e., net outflow from the source.

61 flow_dict : dict

62 A dictionary containing the value of the flow that went through

63 each edge.

65 Raises

66 ------

67 NetworkXError

68 The algorithm does not support MultiGraph and MultiDiGraph. If

69 the input graph is an instance of one of these two classes, a

70 NetworkXError is raised.

72 NetworkXUnbounded

73 If the graph has a path of infinite capacity, the value of a

74 feasible flow on the graph is unbounded above and the function

75 raises a NetworkXUnbounded.

77 See also

78 --------

79 :meth:`maximum_flow_value`

80 :meth:`minimum_cut`

81 :meth:`minimum_cut_value`

82 :meth:`edmonds_karp`

83 :meth:`preflow_push`

84 :meth:`shortest_augmenting_path`

86 Notes

87 -----

88 The function used in the flow_func parameter has to return a residual

89 network that follows NetworkX conventions:

91 The residual network :samp:`R` from an input graph :samp:`G` has the

92 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair

93 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a

94 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists

95 in :samp:`G`.

97 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`

98 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists

99 in :samp:`G` or zero otherwise. If the capacity is infinite,

100 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value

101 that does not affect the solution of the problem. This value is stored in

102 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,

103 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and

104 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.

105

106 The flow value, defined as the total flow into :samp:`t`, the sink, is

107 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using

108 only edges :samp:`(u, v)` such that

109 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum

110 :samp:`s`-:samp:`t` cut.

111

112 Specific algorithms may store extra data in :samp:`R`.

113

114 The function should supports an optional boolean parameter value_only. When

115 True, it can optionally terminate the algorithm as soon as the maximum flow

116 value and the minimum cut can be determined.

117

118 Examples

119 --------

120 >>> G = nx.DiGraph()

121 >>> G.add_edge("x", "a", capacity=3.0)

122 >>> G.add_edge("x", "b", capacity=1.0)

123 >>> G.add_edge("a", "c", capacity=3.0)

124 >>> G.add_edge("b", "c", capacity=5.0)

125 >>> G.add_edge("b", "d", capacity=4.0)

126 >>> G.add_edge("d", "e", capacity=2.0)

127 >>> G.add_edge("c", "y", capacity=2.0)

128 >>> G.add_edge("e", "y", capacity=3.0)

129

130 maximum_flow returns both the value of the maximum flow and a

131 dictionary with all flows.

132

133 >>> flow_value, flow_dict = nx.maximum_flow(G, "x", "y")

134 >>> flow_value

135 3.0

136 >>> print(flow_dict["x"]["b"])

137 1.0

138

139 You can also use alternative algorithms for computing the

140 maximum flow by using the flow_func parameter.

141

142 >>> from networkx.algorithms.flow import shortest_augmenting_path

143 >>> flow_value == nx.maximum_flow(G, "x", "y", flow_func=shortest_augmenting_path)[

144 ... 0

145 ... ]

146 True

147

148 """

149 if flow_func is None:

150 if kwargs:

151 raise nx.NetworkXError(

152 "You have to explicitly set a flow_func if"

153 " you need to pass parameters via kwargs."

154 )

155 flow_func = default_flow_func

156

157 if not callable(flow_func):

158 raise nx.NetworkXError("flow_func has to be callable.")

159

160 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=False, **kwargs)

161 flow_dict = build_flow_dict(flowG, R)

162

163 return (R.graph["flow_value"], flow_dict)

164

165

166@nx._dispatch(graphs="flowG", edge_attrs={"capacity": float("inf")})

167def maximum_flow_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):

168 """Find the value of maximum single-commodity flow.

169

170 Parameters

171 ----------

172 flowG : NetworkX graph

173 Edges of the graph are expected to have an attribute called

174 'capacity'. If this attribute is not present, the edge is

175 considered to have infinite capacity.

176

177 _s : node

178 Source node for the flow.

179

180 _t : node

181 Sink node for the flow.

182

183 capacity : string

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

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

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

187 infinite capacity. Default value: 'capacity'.

188

189 flow_func : function

190 A function for computing the maximum flow among a pair of nodes

191 in a capacitated graph. The function has to accept at least three

192 parameters: a Graph or Digraph, a source node, and a target node.

193 And return a residual network that follows NetworkX conventions

194 (see Notes). If flow_func is None, the default maximum

195 flow function (:meth:`preflow_push`) is used. See below for

196 alternative algorithms. The choice of the default function may change

197 from version to version and should not be relied on. Default value:

198 None.

199

200 kwargs : Any other keyword parameter is passed to the function that

201 computes the maximum flow.

202

203 Returns

204 -------

205 flow_value : integer, float

206 Value of the maximum flow, i.e., net outflow from the source.

207

208 Raises

209 ------

210 NetworkXError

211 The algorithm does not support MultiGraph and MultiDiGraph. If

212 the input graph is an instance of one of these two classes, a

213 NetworkXError is raised.

214

215 NetworkXUnbounded

216 If the graph has a path of infinite capacity, the value of a

217 feasible flow on the graph is unbounded above and the function

218 raises a NetworkXUnbounded.

219

220 See also

221 --------

222 :meth:`maximum_flow`

223 :meth:`minimum_cut`

224 :meth:`minimum_cut_value`

225 :meth:`edmonds_karp`

226 :meth:`preflow_push`

227 :meth:`shortest_augmenting_path`

228

229 Notes

230 -----

231 The function used in the flow_func parameter has to return a residual

232 network that follows NetworkX conventions:

233

234 The residual network :samp:`R` from an input graph :samp:`G` has the

235 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair

236 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a

237 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists

238 in :samp:`G`.

239

240 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`

241 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists

242 in :samp:`G` or zero otherwise. If the capacity is infinite,

243 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value

244 that does not affect the solution of the problem. This value is stored in

245 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,

246 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and

247 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.

248

249 The flow value, defined as the total flow into :samp:`t`, the sink, is

250 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using

251 only edges :samp:`(u, v)` such that

252 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum

253 :samp:`s`-:samp:`t` cut.

254

255 Specific algorithms may store extra data in :samp:`R`.

256

257 The function should supports an optional boolean parameter value_only. When

258 True, it can optionally terminate the algorithm as soon as the maximum flow

259 value and the minimum cut can be determined.

260

261 Examples

262 --------

263 >>> G = nx.DiGraph()

264 >>> G.add_edge("x", "a", capacity=3.0)

265 >>> G.add_edge("x", "b", capacity=1.0)

266 >>> G.add_edge("a", "c", capacity=3.0)

267 >>> G.add_edge("b", "c", capacity=5.0)

268 >>> G.add_edge("b", "d", capacity=4.0)

269 >>> G.add_edge("d", "e", capacity=2.0)

270 >>> G.add_edge("c", "y", capacity=2.0)

271 >>> G.add_edge("e", "y", capacity=3.0)

272

273 maximum_flow_value computes only the value of the

274 maximum flow:

275

276 >>> flow_value = nx.maximum_flow_value(G, "x", "y")

277 >>> flow_value

278 3.0

279

280 You can also use alternative algorithms for computing the

281 maximum flow by using the flow_func parameter.

282

283 >>> from networkx.algorithms.flow import shortest_augmenting_path

284 >>> flow_value == nx.maximum_flow_value(

285 ... G, "x", "y", flow_func=shortest_augmenting_path

286 ... )

287 True

288

289 """

290 if flow_func is None:

291 if kwargs:

292 raise nx.NetworkXError(

293 "You have to explicitly set a flow_func if"

294 " you need to pass parameters via kwargs."

295 )

296 flow_func = default_flow_func

297

298 if not callable(flow_func):

299 raise nx.NetworkXError("flow_func has to be callable.")

300

301 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)

302

303 return R.graph["flow_value"]

304

305

306@nx._dispatch(graphs="flowG", edge_attrs={"capacity": float("inf")})

307def minimum_cut(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):

308 """Compute the value and the node partition of a minimum (s, t)-cut.

309

310 Use the max-flow min-cut theorem, i.e., the capacity of a minimum

311 capacity cut is equal to the flow value of a maximum flow.

312

313 Parameters

314 ----------

315 flowG : NetworkX graph

316 Edges of the graph are expected to have an attribute called

317 'capacity'. If this attribute is not present, the edge is

318 considered to have infinite capacity.

319

320 _s : node

321 Source node for the flow.

322

323 _t : node

324 Sink node for the flow.

325

326 capacity : string

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

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

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

330 infinite capacity. Default value: 'capacity'.

331

332 flow_func : function

333 A function for computing the maximum flow among a pair of nodes

334 in a capacitated graph. The function has to accept at least three

335 parameters: a Graph or Digraph, a source node, and a target node.

336 And return a residual network that follows NetworkX conventions

337 (see Notes). If flow_func is None, the default maximum

338 flow function (:meth:`preflow_push`) is used. See below for

339 alternative algorithms. The choice of the default function may change

340 from version to version and should not be relied on. Default value:

341 None.

342

343 kwargs : Any other keyword parameter is passed to the function that

344 computes the maximum flow.

345

346 Returns

347 -------

348 cut_value : integer, float

349 Value of the minimum cut.

350

351 partition : pair of node sets

352 A partitioning of the nodes that defines a minimum cut.

353

354 Raises

355 ------

356 NetworkXUnbounded

357 If the graph has a path of infinite capacity, all cuts have

358 infinite capacity and the function raises a NetworkXError.

359

360 See also

361 --------

362 :meth:`maximum_flow`

363 :meth:`maximum_flow_value`

364 :meth:`minimum_cut_value`

365 :meth:`edmonds_karp`

366 :meth:`preflow_push`

367 :meth:`shortest_augmenting_path`

368

369 Notes

370 -----

371 The function used in the flow_func parameter has to return a residual

372 network that follows NetworkX conventions:

373

374 The residual network :samp:`R` from an input graph :samp:`G` has the

375 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair

376 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a

377 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists

378 in :samp:`G`.

379

380 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`

381 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists

382 in :samp:`G` or zero otherwise. If the capacity is infinite,

383 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value

384 that does not affect the solution of the problem. This value is stored in

385 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,

386 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and

387 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.

388

389 The flow value, defined as the total flow into :samp:`t`, the sink, is

390 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using

391 only edges :samp:`(u, v)` such that

392 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum

393 :samp:`s`-:samp:`t` cut.

394

395 Specific algorithms may store extra data in :samp:`R`.

396

397 The function should supports an optional boolean parameter value_only. When

398 True, it can optionally terminate the algorithm as soon as the maximum flow

399 value and the minimum cut can be determined.

400

401 Examples

402 --------

403 >>> G = nx.DiGraph()

404 >>> G.add_edge("x", "a", capacity=3.0)

405 >>> G.add_edge("x", "b", capacity=1.0)

406 >>> G.add_edge("a", "c", capacity=3.0)

407 >>> G.add_edge("b", "c", capacity=5.0)

408 >>> G.add_edge("b", "d", capacity=4.0)

409 >>> G.add_edge("d", "e", capacity=2.0)

410 >>> G.add_edge("c", "y", capacity=2.0)

411 >>> G.add_edge("e", "y", capacity=3.0)

412

413 minimum_cut computes both the value of the

414 minimum cut and the node partition:

415

416 >>> cut_value, partition = nx.minimum_cut(G, "x", "y")

417 >>> reachable, non_reachable = partition

418

419 'partition' here is a tuple with the two sets of nodes that define

420 the minimum cut. You can compute the cut set of edges that induce

421 the minimum cut as follows:

422

423 >>> cutset = set()

424 >>> for u, nbrs in ((n, G[n]) for n in reachable):

425 ... cutset.update((u, v) for v in nbrs if v in non_reachable)

426 >>> print(sorted(cutset))

427 [('c', 'y'), ('x', 'b')]

428 >>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset)

429 True

430

431 You can also use alternative algorithms for computing the

432 minimum cut by using the flow_func parameter.

433

434 >>> from networkx.algorithms.flow import shortest_augmenting_path

435 >>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0]

436 True

437

438 """

439 if flow_func is None:

440 if kwargs:

441 raise nx.NetworkXError(

442 "You have to explicitly set a flow_func if"

443 " you need to pass parameters via kwargs."

444 )

445 flow_func = default_flow_func

446

447 if not callable(flow_func):

448 raise nx.NetworkXError("flow_func has to be callable.")

449

450 if kwargs.get("cutoff") is not None and flow_func is preflow_push:

451 raise nx.NetworkXError("cutoff should not be specified.")

452

453 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)

454 # Remove saturated edges from the residual network

455 cutset = [(u, v, d) for u, v, d in R.edges(data=True) if d["flow"] == d["capacity"]]

456 R.remove_edges_from(cutset)

457

458 # Then, reachable and non reachable nodes from source in the

459 # residual network form the node partition that defines

460 # the minimum cut.

461 non_reachable = set(dict(nx.shortest_path_length(R, target=_t)))

462 partition = (set(flowG) - non_reachable, non_reachable)

463 # Finally add again cutset edges to the residual network to make

464 # sure that it is reusable.

465 if cutset is not None:

466 R.add_edges_from(cutset)

467 return (R.graph["flow_value"], partition)

468

469

470@nx._dispatch(graphs="flowG", edge_attrs={"capacity": float("inf")})

471def minimum_cut_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):

472 """Compute the value of a minimum (s, t)-cut.

473

474 Use the max-flow min-cut theorem, i.e., the capacity of a minimum

475 capacity cut is equal to the flow value of a maximum flow.

476

477 Parameters

478 ----------

479 flowG : NetworkX graph

480 Edges of the graph are expected to have an attribute called

481 'capacity'. If this attribute is not present, the edge is

482 considered to have infinite capacity.

483

484 _s : node

485 Source node for the flow.

486

487 _t : node

488 Sink node for the flow.

489

490 capacity : string

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

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

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

494 infinite capacity. Default value: 'capacity'.

495

496 flow_func : function

497 A function for computing the maximum flow among a pair of nodes

498 in a capacitated graph. The function has to accept at least three

499 parameters: a Graph or Digraph, a source node, and a target node.

500 And return a residual network that follows NetworkX conventions

501 (see Notes). If flow_func is None, the default maximum

502 flow function (:meth:`preflow_push`) is used. See below for

503 alternative algorithms. The choice of the default function may change

504 from version to version and should not be relied on. Default value:

505 None.

506

507 kwargs : Any other keyword parameter is passed to the function that

508 computes the maximum flow.

509

510 Returns

511 -------

512 cut_value : integer, float

513 Value of the minimum cut.

514

515 Raises

516 ------

517 NetworkXUnbounded

518 If the graph has a path of infinite capacity, all cuts have

519 infinite capacity and the function raises a NetworkXError.

520

521 See also

522 --------

523 :meth:`maximum_flow`

524 :meth:`maximum_flow_value`

525 :meth:`minimum_cut`

526 :meth:`edmonds_karp`

527 :meth:`preflow_push`

528 :meth:`shortest_augmenting_path`

529

530 Notes

531 -----

532 The function used in the flow_func parameter has to return a residual

533 network that follows NetworkX conventions:

534

535 The residual network :samp:`R` from an input graph :samp:`G` has the

536 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair

537 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a

538 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists

539 in :samp:`G`.

540

541 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`

542 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists

543 in :samp:`G` or zero otherwise. If the capacity is infinite,

544 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value

545 that does not affect the solution of the problem. This value is stored in

546 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,

547 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and

548 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.

549

550 The flow value, defined as the total flow into :samp:`t`, the sink, is

551 stored in :samp:`R.graph['flow_value']`. Reachability to :samp:`t` using

552 only edges :samp:`(u, v)` such that

553 :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum

554 :samp:`s`-:samp:`t` cut.

555

556 Specific algorithms may store extra data in :samp:`R`.

557

558 The function should supports an optional boolean parameter value_only. When

559 True, it can optionally terminate the algorithm as soon as the maximum flow

560 value and the minimum cut can be determined.

561

562 Examples

563 --------

564 >>> G = nx.DiGraph()

565 >>> G.add_edge("x", "a", capacity=3.0)

566 >>> G.add_edge("x", "b", capacity=1.0)

567 >>> G.add_edge("a", "c", capacity=3.0)

568 >>> G.add_edge("b", "c", capacity=5.0)

569 >>> G.add_edge("b", "d", capacity=4.0)

570 >>> G.add_edge("d", "e", capacity=2.0)

571 >>> G.add_edge("c", "y", capacity=2.0)

572 >>> G.add_edge("e", "y", capacity=3.0)

573

574 minimum_cut_value computes only the value of the

575 minimum cut:

576

577 >>> cut_value = nx.minimum_cut_value(G, "x", "y")

578 >>> cut_value

579 3.0

580

581 You can also use alternative algorithms for computing the

582 minimum cut by using the flow_func parameter.

583

584 >>> from networkx.algorithms.flow import shortest_augmenting_path

585 >>> cut_value == nx.minimum_cut_value(

586 ... G, "x", "y", flow_func=shortest_augmenting_path

587 ... )

588 True

589

590 """

591 if flow_func is None:

592 if kwargs:

593 raise nx.NetworkXError(

594 "You have to explicitly set a flow_func if"

595 " you need to pass parameters via kwargs."

596 )

597 flow_func = default_flow_func

598

599 if not callable(flow_func):

600 raise nx.NetworkXError("flow_func has to be callable.")

601

602 if kwargs.get("cutoff") is not None and flow_func is preflow_push:

603 raise nx.NetworkXError("cutoff should not be specified.")

604

605 R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)

606

607 return R.graph["flow_value"]