Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/connectivity/cuts.py: 13%

1"""

2Flow based cut algorithms

3"""

5import itertools

7import networkx as nx

9# Define the default maximum flow function to use in all flow based

10# cut algorithms.

11from networkx.algorithms.flow import build_residual_network, edmonds_karp

13from .utils import build_auxiliary_edge_connectivity, build_auxiliary_node_connectivity

15default_flow_func = edmonds_karp

17__all__ = [

18 "minimum_st_node_cut",

19 "minimum_node_cut",

20 "minimum_st_edge_cut",

21 "minimum_edge_cut",

22]

25@nx._dispatchable(

26 graphs={"G": 0, "auxiliary?": 4},

27 preserve_edge_attrs={"auxiliary": {"capacity": float("inf")}},

28 preserve_graph_attrs={"auxiliary"},

29)

30def minimum_st_edge_cut(G, s, t, flow_func=None, auxiliary=None, residual=None):

31 """Returns the edges of the cut-set of a minimum (s, t)-cut.

33 This function returns the set of edges of minimum cardinality that,

34 if removed, would destroy all paths among source and target in G.

35 Edge weights are not considered. See :meth:`minimum_cut` for

36 computing minimum cuts considering edge weights.

38 Parameters

39 ----------

40 G : NetworkX graph

42 s : node

43 Source node for the flow.

45 t : node

46 Sink node for the flow.

48 auxiliary : NetworkX DiGraph

49 Auxiliary digraph to compute flow based node connectivity. It has

50 to have a graph attribute called mapping with a dictionary mapping

51 node names in G and in the auxiliary digraph. If provided

52 it will be reused instead of recreated. Default value: None.

54 flow_func : function

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

56 The function has to accept at least three parameters: a Digraph,

57 a source node, and a target node. And return a residual network

58 that follows NetworkX conventions (see :meth:`maximum_flow` for

59 details). If flow_func is None, the default maximum flow function

60 (:meth:`edmonds_karp`) is used. See :meth:`node_connectivity` for

61 details. The choice of the default function may change from version

62 to version and should not be relied on. Default value: None.

64 residual : NetworkX DiGraph

65 Residual network to compute maximum flow. If provided it will be

66 reused instead of recreated. Default value: None.

68 Returns

69 -------

70 cutset : set

71 Set of edges that, if removed from the graph, will disconnect it.

73 See also

74 --------

75 :meth:`minimum_cut`

76 :meth:`minimum_node_cut`

77 :meth:`minimum_edge_cut`

78 :meth:`stoer_wagner`

79 :meth:`node_connectivity`

80 :meth:`edge_connectivity`

81 :meth:`maximum_flow`

82 :meth:`edmonds_karp`

83 :meth:`preflow_push`

84 :meth:`shortest_augmenting_path`

86 Examples

87 --------

88 This function is not imported in the base NetworkX namespace, so you

89 have to explicitly import it from the connectivity package:

91 >>> from networkx.algorithms.connectivity import minimum_st_edge_cut

93 We use in this example the platonic icosahedral graph, which has edge

94 connectivity 5.

96 >>> G = nx.icosahedral_graph()

97 >>> len(minimum_st_edge_cut(G, 0, 6))

98 5

100 If you need to compute local edge cuts on several pairs of

101 nodes in the same graph, it is recommended that you reuse the

102 data structures that NetworkX uses in the computation: the

103 auxiliary digraph for edge connectivity, and the residual

104 network for the underlying maximum flow computation.

105

106 Example of how to compute local edge cuts among all pairs of

107 nodes of the platonic icosahedral graph reusing the data

108 structures.

109

110 >>> import itertools

111 >>> # You also have to explicitly import the function for

112 >>> # building the auxiliary digraph from the connectivity package

113 >>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity

114 >>> H = build_auxiliary_edge_connectivity(G)

115 >>> # And the function for building the residual network from the

116 >>> # flow package

117 >>> from networkx.algorithms.flow import build_residual_network

118 >>> # Note that the auxiliary digraph has an edge attribute named capacity

119 >>> R = build_residual_network(H, "capacity")

120 >>> result = dict.fromkeys(G, dict())

121 >>> # Reuse the auxiliary digraph and the residual network by passing them

122 >>> # as parameters

123 >>> for u, v in itertools.combinations(G, 2):

124 ... k = len(minimum_st_edge_cut(G, u, v, auxiliary=H, residual=R))

125 ... result[u][v] = k

126 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))

127 True

128

129 You can also use alternative flow algorithms for computing edge

130 cuts. For instance, in dense networks the algorithm

131 :meth:`shortest_augmenting_path` will usually perform better than

132 the default :meth:`edmonds_karp` which is faster for sparse

133 networks with highly skewed degree distributions. Alternative flow

134 functions have to be explicitly imported from the flow package.

135

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

137 >>> len(minimum_st_edge_cut(G, 0, 6, flow_func=shortest_augmenting_path))

138 5

139

140 """

141 if flow_func is None:

142 flow_func = default_flow_func

143

144 if auxiliary is None:

145 H = build_auxiliary_edge_connectivity(G)

146 else:

147 H = auxiliary

148

149 kwargs = {"capacity": "capacity", "flow_func": flow_func, "residual": residual}

150

151 cut_value, partition = nx.minimum_cut(H, s, t, **kwargs)

152 reachable, non_reachable = partition

153 # Any edge in the original graph linking the two sets in the

154 # partition is part of the edge cutset

155 cutset = set()

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

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

158

159 return cutset

160

161

162@nx._dispatchable(

163 graphs={"G": 0, "auxiliary?": 4},

164 preserve_node_attrs={"auxiliary": {"id": None}},

165 preserve_graph_attrs={"auxiliary"},

166)

167def minimum_st_node_cut(G, s, t, flow_func=None, auxiliary=None, residual=None):

168 r"""Returns a set of nodes of minimum cardinality that disconnect source

169 from target in G.

170

171 This function returns the set of nodes of minimum cardinality that,

172 if removed, would destroy all paths among source and target in G.

173

174 Parameters

175 ----------

176 G : NetworkX graph

177

178 s : node

179 Source node.

180

181 t : node

182 Target node.

183

184 flow_func : function

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

186 The function has to accept at least three parameters: a Digraph,

187 a source node, and a target node. And return a residual network

188 that follows NetworkX conventions (see :meth:`maximum_flow` for

189 details). If flow_func is None, the default maximum flow function

190 (:meth:`edmonds_karp`) is used. See below for details. The choice

191 of the default function may change from version to version and

192 should not be relied on. Default value: None.

193

194 auxiliary : NetworkX DiGraph

195 Auxiliary digraph to compute flow based node connectivity. It has

196 to have a graph attribute called mapping with a dictionary mapping

197 node names in G and in the auxiliary digraph. If provided

198 it will be reused instead of recreated. Default value: None.

199

200 residual : NetworkX DiGraph

201 Residual network to compute maximum flow. If provided it will be

202 reused instead of recreated. Default value: None.

203

204 Returns

205 -------

206 cutset : set

207 Set of nodes that, if removed, would destroy all paths between

208 source and target in G.

209

210 Returns an empty set if source and target are either in different

211 components or are directly connected by an edge, as no node removal

212 can destroy the path.

213

214 Examples

215 --------

216 This function is not imported in the base NetworkX namespace, so you

217 have to explicitly import it from the connectivity package:

218

219 >>> from networkx.algorithms.connectivity import minimum_st_node_cut

220

221 We use in this example the platonic icosahedral graph, which has node

222 connectivity 5.

223

224 >>> G = nx.icosahedral_graph()

225 >>> len(minimum_st_node_cut(G, 0, 6))

226 5

227

228 If you need to compute local st cuts between several pairs of

229 nodes in the same graph, it is recommended that you reuse the

230 data structures that NetworkX uses in the computation: the

231 auxiliary digraph for node connectivity and node cuts, and the

232 residual network for the underlying maximum flow computation.

233

234 Example of how to compute local st node cuts reusing the data

235 structures:

236

237 >>> # You also have to explicitly import the function for

238 >>> # building the auxiliary digraph from the connectivity package

239 >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity

240 >>> H = build_auxiliary_node_connectivity(G)

241 >>> # And the function for building the residual network from the

242 >>> # flow package

243 >>> from networkx.algorithms.flow import build_residual_network

244 >>> # Note that the auxiliary digraph has an edge attribute named capacity

245 >>> R = build_residual_network(H, "capacity")

246 >>> # Reuse the auxiliary digraph and the residual network by passing them

247 >>> # as parameters

248 >>> len(minimum_st_node_cut(G, 0, 6, auxiliary=H, residual=R))

249 5

250

251 You can also use alternative flow algorithms for computing minimum st

252 node cuts. For instance, in dense networks the algorithm

253 :meth:`shortest_augmenting_path` will usually perform better than

254 the default :meth:`edmonds_karp` which is faster for sparse

255 networks with highly skewed degree distributions. Alternative flow

256 functions have to be explicitly imported from the flow package.

257

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

259 >>> len(minimum_st_node_cut(G, 0, 6, flow_func=shortest_augmenting_path))

260 5

261

262 Notes

263 -----

264 This is a flow based implementation of minimum node cut. The algorithm

265 is based in solving a number of maximum flow computations to determine

266 the capacity of the minimum cut on an auxiliary directed network that

267 corresponds to the minimum node cut of G. It handles both directed

268 and undirected graphs. This implementation is based on algorithm 11

269 in [1]_.

270

271 See also

272 --------

273 :meth:`minimum_node_cut`

274 :meth:`minimum_edge_cut`

275 :meth:`stoer_wagner`

276 :meth:`node_connectivity`

277 :meth:`edge_connectivity`

278 :meth:`maximum_flow`

279 :meth:`edmonds_karp`

280 :meth:`preflow_push`

281 :meth:`shortest_augmenting_path`

282

283 References

284 ----------

285 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.

286 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

287

288 """

289 if auxiliary is None:

290 H = build_auxiliary_node_connectivity(G)

291 else:

292 H = auxiliary

293

294 mapping = H.graph.get("mapping", None)

295 if mapping is None:

296 raise nx.NetworkXError("Invalid auxiliary digraph.")

297 if G.has_edge(s, t) or G.has_edge(t, s):

298 return set()

299 kwargs = {"flow_func": flow_func, "residual": residual, "auxiliary": H}

300

301 # The edge cut in the auxiliary digraph corresponds to the node cut in the

302 # original graph.

303 edge_cut = minimum_st_edge_cut(H, f"{mapping[s]}B", f"{mapping[t]}A", **kwargs)

304 # Each node in the original graph maps to two nodes of the auxiliary graph

305 node_cut = {H.nodes[node]["id"] for edge in edge_cut for node in edge}

306 return node_cut - {s, t}

307

308

309@nx._dispatchable

310def minimum_node_cut(G, s=None, t=None, flow_func=None):

311 r"""Returns a set of nodes of minimum cardinality that disconnects G.

312

313 If source and target nodes are provided, this function returns the

314 set of nodes of minimum cardinality that, if removed, would destroy

315 all paths among source and target in G. If not, it returns a set

316 of nodes of minimum cardinality that disconnects G.

317

318 Parameters

319 ----------

320 G : NetworkX graph

321

322 s : node

323 Source node. Optional. Default value: None.

324

325 t : node

326 Target node. Optional. Default value: None.

327

328 flow_func : function

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

330 The function has to accept at least three parameters: a Digraph,

331 a source node, and a target node. And return a residual network

332 that follows NetworkX conventions (see :meth:`maximum_flow` for

333 details). If flow_func is None, the default maximum flow function

334 (:meth:`edmonds_karp`) is used. See below for details. The

335 choice of the default function may change from version

336 to version and should not be relied on. Default value: None.

337

338 Returns

339 -------

340 cutset : set

341 Set of nodes that, if removed, would disconnect G. If source

342 and target nodes are provided, the set contains the nodes that

343 if removed, would destroy all paths between source and target.

344

345 Examples

346 --------

347 >>> # Platonic icosahedral graph has node connectivity 5

348 >>> G = nx.icosahedral_graph()

349 >>> node_cut = nx.minimum_node_cut(G)

350 >>> len(node_cut)

351 5

352

353 You can use alternative flow algorithms for the underlying maximum

354 flow computation. In dense networks the algorithm

355 :meth:`shortest_augmenting_path` will usually perform better

356 than the default :meth:`edmonds_karp`, which is faster for

357 sparse networks with highly skewed degree distributions. Alternative

358 flow functions have to be explicitly imported from the flow package.

359

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

361 >>> node_cut == nx.minimum_node_cut(G, flow_func=shortest_augmenting_path)

362 True

363

364 If you specify a pair of nodes (source and target) as parameters,

365 this function returns a local st node cut.

366

367 >>> len(nx.minimum_node_cut(G, 3, 7))

368 5

369

370 If you need to perform several local st cuts among different

371 pairs of nodes on the same graph, it is recommended that you reuse

372 the data structures used in the maximum flow computations. See

373 :meth:`minimum_st_node_cut` for details.

374

375 Notes

376 -----

377 This is a flow based implementation of minimum node cut. The algorithm

378 is based in solving a number of maximum flow computations to determine

379 the capacity of the minimum cut on an auxiliary directed network that

380 corresponds to the minimum node cut of G. It handles both directed

381 and undirected graphs. This implementation is based on algorithm 11

382 in [1]_.

383

384 See also

385 --------

386 :meth:`minimum_st_node_cut`

387 :meth:`minimum_cut`

388 :meth:`minimum_edge_cut`

389 :meth:`stoer_wagner`

390 :meth:`node_connectivity`

391 :meth:`edge_connectivity`

392 :meth:`maximum_flow`

393 :meth:`edmonds_karp`

394 :meth:`preflow_push`

395 :meth:`shortest_augmenting_path`

396

397 References

398 ----------

399 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.

400 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

401

402 """

403 if (s is not None and t is None) or (s is None and t is not None):

404 raise nx.NetworkXError("Both source and target must be specified.")

405

406 # Local minimum node cut.

407 if s is not None and t is not None:

408 if s not in G:

409 raise nx.NetworkXError(f"node {s} not in graph")

410 if t not in G:

411 raise nx.NetworkXError(f"node {t} not in graph")

412 return minimum_st_node_cut(G, s, t, flow_func=flow_func)

413

414 # Global minimum node cut.

415 # Analog to the algorithm 11 for global node connectivity in [1].

416 if G.is_directed():

417 if not nx.is_weakly_connected(G):

418 raise nx.NetworkXError("Input graph is not connected")

419 iter_func = itertools.permutations

420

421 def neighbors(v):

422 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)])

423

424 else:

425 if not nx.is_connected(G):

426 raise nx.NetworkXError("Input graph is not connected")

427 iter_func = itertools.combinations

428 neighbors = G.neighbors

429

430 # Reuse the auxiliary digraph and the residual network.

431 H = build_auxiliary_node_connectivity(G)

432 R = build_residual_network(H, "capacity")

433 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}

434

435 # Choose a node with minimum degree.

436 v = min(G, key=G.degree)

437 # Initial node cutset is all neighbors of the node with minimum degree.

438 min_cut = set(G[v])

439 # Compute st node cuts between v and all its non-neighbors nodes in G.

440 for w in set(G) - set(neighbors(v)) - {v}:

441 this_cut = minimum_st_node_cut(G, v, w, **kwargs)

442 if len(min_cut) >= len(this_cut):

443 min_cut = this_cut

444 # Also for non adjacent pairs of neighbors of v.

445 for x, y in iter_func(neighbors(v), 2):

446 if y in G[x]:

447 continue

448 this_cut = minimum_st_node_cut(G, x, y, **kwargs)

449 if len(min_cut) >= len(this_cut):

450 min_cut = this_cut

451

452 return min_cut

453

454

455@nx._dispatchable

456def minimum_edge_cut(G, s=None, t=None, flow_func=None):

457 r"""Returns a set of edges of minimum cardinality that disconnects G.

458

459 If source and target nodes are provided, this function returns the

460 set of edges of minimum cardinality that, if removed, would break

461 all paths among source and target in G. If not, it returns a set of

462 edges of minimum cardinality that disconnects G.

463

464 Parameters

465 ----------

466 G : NetworkX graph

467

468 s : node

469 Source node. Optional. Default value: None.

470

471 t : node

472 Target node. Optional. Default value: None.

473

474 flow_func : function

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

476 The function has to accept at least three parameters: a Digraph,

477 a source node, and a target node. And return a residual network

478 that follows NetworkX conventions (see :meth:`maximum_flow` for

479 details). If flow_func is None, the default maximum flow function

480 (:meth:`edmonds_karp`) is used. See below for details. The

481 choice of the default function may change from version

482 to version and should not be relied on. Default value: None.

483

484 Returns

485 -------

486 cutset : set

487 Set of edges that, if removed, would disconnect G. If source

488 and target nodes are provided, the set contains the edges that

489 if removed, would destroy all paths between source and target.

490

491 Examples

492 --------

493 >>> # Platonic icosahedral graph has edge connectivity 5

494 >>> G = nx.icosahedral_graph()

495 >>> len(nx.minimum_edge_cut(G))

496 5

497

498 You can use alternative flow algorithms for the underlying

499 maximum flow computation. In dense networks the algorithm

500 :meth:`shortest_augmenting_path` will usually perform better

501 than the default :meth:`edmonds_karp`, which is faster for

502 sparse networks with highly skewed degree distributions.

503 Alternative flow functions have to be explicitly imported

504 from the flow package.

505

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

507 >>> len(nx.minimum_edge_cut(G, flow_func=shortest_augmenting_path))

508 5

509

510 If you specify a pair of nodes (source and target) as parameters,

511 this function returns the value of local edge connectivity.

512

513 >>> nx.edge_connectivity(G, 3, 7)

514 5

515

516 If you need to perform several local computations among different

517 pairs of nodes on the same graph, it is recommended that you reuse

518 the data structures used in the maximum flow computations. See

519 :meth:`local_edge_connectivity` for details.

520

521 Notes

522 -----

523 This is a flow based implementation of minimum edge cut. For

524 undirected graphs the algorithm works by finding a 'small' dominating

525 set of nodes of G (see algorithm 7 in [1]_) and computing the maximum

526 flow between an arbitrary node in the dominating set and the rest of

527 nodes in it. This is an implementation of algorithm 6 in [1]_. For

528 directed graphs, the algorithm does n calls to the max flow function.

529 The function raises an error if the directed graph is not weakly

530 connected and returns an empty set if it is weakly connected.

531 It is an implementation of algorithm 8 in [1]_.

532

533 See also

534 --------

535 :meth:`minimum_st_edge_cut`

536 :meth:`minimum_node_cut`

537 :meth:`stoer_wagner`

538 :meth:`node_connectivity`

539 :meth:`edge_connectivity`

540 :meth:`maximum_flow`

541 :meth:`edmonds_karp`

542 :meth:`preflow_push`

543 :meth:`shortest_augmenting_path`

544

545 References

546 ----------

547 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.

548 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

549

550 """

551 if (s is not None and t is None) or (s is None and t is not None):

552 raise nx.NetworkXError("Both source and target must be specified.")

553

554 # reuse auxiliary digraph and residual network

555 H = build_auxiliary_edge_connectivity(G)

556 R = build_residual_network(H, "capacity")

557 kwargs = {"flow_func": flow_func, "residual": R, "auxiliary": H}

558

559 # Local minimum edge cut if s and t are not None

560 if s is not None and t is not None:

561 if s not in G:

562 raise nx.NetworkXError(f"node {s} not in graph")

563 if t not in G:

564 raise nx.NetworkXError(f"node {t} not in graph")

565 return minimum_st_edge_cut(H, s, t, **kwargs)

566

567 # Global minimum edge cut

568 # Analog to the algorithm for global edge connectivity

569 if G.is_directed():

570 # Based on algorithm 8 in [1]

571 if not nx.is_weakly_connected(G):

572 raise nx.NetworkXError("Input graph is not connected")

573

574 # Initial cutset is all edges of a node with minimum degree

575 node = min(G, key=G.degree)

576 min_cut = set(G.edges(node))

577 nodes = list(G)

578 n = len(nodes)

579 for i in range(n):

580 try:

581 this_cut = minimum_st_edge_cut(H, nodes[i], nodes[i + 1], **kwargs)

582 if len(this_cut) <= len(min_cut):

583 min_cut = this_cut

584 except IndexError: # Last node!

585 this_cut = minimum_st_edge_cut(H, nodes[i], nodes[0], **kwargs)

586 if len(this_cut) <= len(min_cut):

587 min_cut = this_cut

588

589 return min_cut

590

591 else: # undirected

592 # Based on algorithm 6 in [1]

593 if not nx.is_connected(G):

594 raise nx.NetworkXError("Input graph is not connected")

595

596 # Initial cutset is all edges of a node with minimum degree

597 node = min(G, key=G.degree)

598 min_cut = set(G.edges(node))

599 # A dominating set is \lambda-covering

600 # We need a dominating set with at least two nodes

601 for node in G:

602 D = nx.dominating_set(G, start_with=node)

603 v = D.pop()

604 if D:

605 break

606 else:

607 # in complete graphs the dominating set will always be of one node

608 # thus we return min_cut, which now contains the edges of a node

609 # with minimum degree

610 return min_cut

611 for w in D:

612 this_cut = minimum_st_edge_cut(H, v, w, **kwargs)

613 if len(this_cut) <= len(min_cut):

614 min_cut = this_cut

615

616 return min_cut