Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/connectivity/cuts.py: 12%
115 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Flow based cut algorithms
3"""
4import itertools
6import networkx as nx
8# Define the default maximum flow function to use in all flow based
9# cut algorithms.
10from networkx.algorithms.flow import build_residual_network, edmonds_karp
12default_flow_func = edmonds_karp
14from .utils import build_auxiliary_edge_connectivity, build_auxiliary_node_connectivity
16__all__ = [
17 "minimum_st_node_cut",
18 "minimum_node_cut",
19 "minimum_st_edge_cut",
20 "minimum_edge_cut",
21]
24@nx._dispatch(
25 graphs={"G": 0, "auxiliary?": 4, "residual?": 5},
26 preserve_edge_attrs={
27 "auxiliary": {"capacity": float("inf")},
28 "residual": {"capacity": float("inf")},
29 },
30 preserve_graph_attrs={"auxiliary", "residual"},
31)
32def minimum_st_edge_cut(G, s, t, flow_func=None, auxiliary=None, residual=None):
33 """Returns the edges of the cut-set of a minimum (s, t)-cut.
35 This function returns the set of edges of minimum cardinality that,
36 if removed, would destroy all paths among source and target in G.
37 Edge weights are not considered. See :meth:`minimum_cut` for
38 computing minimum cuts considering edge weights.
40 Parameters
41 ----------
42 G : NetworkX graph
44 s : node
45 Source node for the flow.
47 t : node
48 Sink node for the flow.
50 auxiliary : NetworkX DiGraph
51 Auxiliary digraph to compute flow based node connectivity. It has
52 to have a graph attribute called mapping with a dictionary mapping
53 node names in G and in the auxiliary digraph. If provided
54 it will be reused instead of recreated. Default value: None.
56 flow_func : function
57 A function for computing the maximum flow among a pair of nodes.
58 The function has to accept at least three parameters: a Digraph,
59 a source node, and a target node. And return a residual network
60 that follows NetworkX conventions (see :meth:`maximum_flow` for
61 details). If flow_func is None, the default maximum flow function
62 (:meth:`edmonds_karp`) is used. See :meth:`node_connectivity` for
63 details. The choice of the default function may change from version
64 to version and should not be relied on. Default value: None.
66 residual : NetworkX DiGraph
67 Residual network to compute maximum flow. If provided it will be
68 reused instead of recreated. Default value: None.
70 Returns
71 -------
72 cutset : set
73 Set of edges that, if removed from the graph, will disconnect it.
75 See also
76 --------
77 :meth:`minimum_cut`
78 :meth:`minimum_node_cut`
79 :meth:`minimum_edge_cut`
80 :meth:`stoer_wagner`
81 :meth:`node_connectivity`
82 :meth:`edge_connectivity`
83 :meth:`maximum_flow`
84 :meth:`edmonds_karp`
85 :meth:`preflow_push`
86 :meth:`shortest_augmenting_path`
88 Examples
89 --------
90 This function is not imported in the base NetworkX namespace, so you
91 have to explicitly import it from the connectivity package:
93 >>> from networkx.algorithms.connectivity import minimum_st_edge_cut
95 We use in this example the platonic icosahedral graph, which has edge
96 connectivity 5.
98 >>> G = nx.icosahedral_graph()
99 >>> len(minimum_st_edge_cut(G, 0, 6))
100 5
102 If you need to compute local edge cuts on several pairs of
103 nodes in the same graph, it is recommended that you reuse the
104 data structures that NetworkX uses in the computation: the
105 auxiliary digraph for edge connectivity, and the residual
106 network for the underlying maximum flow computation.
108 Example of how to compute local edge cuts among all pairs of
109 nodes of the platonic icosahedral graph reusing the data
110 structures.
112 >>> import itertools
113 >>> # You also have to explicitly import the function for
114 >>> # building the auxiliary digraph from the connectivity package
115 >>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
116 >>> H = build_auxiliary_edge_connectivity(G)
117 >>> # And the function for building the residual network from the
118 >>> # flow package
119 >>> from networkx.algorithms.flow import build_residual_network
120 >>> # Note that the auxiliary digraph has an edge attribute named capacity
121 >>> R = build_residual_network(H, "capacity")
122 >>> result = dict.fromkeys(G, dict())
123 >>> # Reuse the auxiliary digraph and the residual network by passing them
124 >>> # as parameters
125 >>> for u, v in itertools.combinations(G, 2):
126 ... k = len(minimum_st_edge_cut(G, u, v, auxiliary=H, residual=R))
127 ... result[u][v] = k
128 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
129 True
131 You can also use alternative flow algorithms for computing edge
132 cuts. For instance, in dense networks the algorithm
133 :meth:`shortest_augmenting_path` will usually perform better than
134 the default :meth:`edmonds_karp` which is faster for sparse
135 networks with highly skewed degree distributions. Alternative flow
136 functions have to be explicitly imported from the flow package.
138 >>> from networkx.algorithms.flow import shortest_augmenting_path
139 >>> len(minimum_st_edge_cut(G, 0, 6, flow_func=shortest_augmenting_path))
140 5
142 """
143 if flow_func is None:
144 flow_func = default_flow_func
146 if auxiliary is None:
147 H = build_auxiliary_edge_connectivity(G)
148 else:
149 H = auxiliary
151 kwargs = {"capacity": "capacity", "flow_func": flow_func, "residual": residual}
153 cut_value, partition = nx.minimum_cut(H, s, t, **kwargs)
154 reachable, non_reachable = partition
155 # Any edge in the original graph linking the two sets in the
156 # partition is part of the edge cutset
157 cutset = set()
158 for u, nbrs in ((n, G[n]) for n in reachable):
159 cutset.update((u, v) for v in nbrs if v in non_reachable)
161 return cutset
164@nx._dispatch(
165 graphs={"G": 0, "auxiliary?": 4, "residual?": 5},
166 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
167 preserve_node_attrs={"auxiliary": {"id": None}},
168 preserve_graph_attrs={"auxiliary", "residual"},
169)
170def minimum_st_node_cut(G, s, t, flow_func=None, auxiliary=None, residual=None):
171 r"""Returns a set of nodes of minimum cardinality that disconnect source
172 from target in G.
174 This function returns the set of nodes of minimum cardinality that,
175 if removed, would destroy all paths among source and target in G.
177 Parameters
178 ----------
179 G : NetworkX graph
181 s : node
182 Source node.
184 t : node
185 Target node.
187 flow_func : function
188 A function for computing the maximum flow among a pair of nodes.
189 The function has to accept at least three parameters: a Digraph,
190 a source node, and a target node. And return a residual network
191 that follows NetworkX conventions (see :meth:`maximum_flow` for
192 details). If flow_func is None, the default maximum flow function
193 (:meth:`edmonds_karp`) is used. See below for details. The choice
194 of the default function may change from version to version and
195 should not be relied on. Default value: None.
197 auxiliary : NetworkX DiGraph
198 Auxiliary digraph to compute flow based node connectivity. It has
199 to have a graph attribute called mapping with a dictionary mapping
200 node names in G and in the auxiliary digraph. If provided
201 it will be reused instead of recreated. Default value: None.
203 residual : NetworkX DiGraph
204 Residual network to compute maximum flow. If provided it will be
205 reused instead of recreated. Default value: None.
207 Returns
208 -------
209 cutset : set
210 Set of nodes that, if removed, would destroy all paths between
211 source and target in G.
213 Examples
214 --------
215 This function is not imported in the base NetworkX namespace, so you
216 have to explicitly import it from the connectivity package:
218 >>> from networkx.algorithms.connectivity import minimum_st_node_cut
220 We use in this example the platonic icosahedral graph, which has node
221 connectivity 5.
223 >>> G = nx.icosahedral_graph()
224 >>> len(minimum_st_node_cut(G, 0, 6))
225 5
227 If you need to compute local st cuts between several pairs of
228 nodes in the same graph, it is recommended that you reuse the
229 data structures that NetworkX uses in the computation: the
230 auxiliary digraph for node connectivity and node cuts, and the
231 residual network for the underlying maximum flow computation.
233 Example of how to compute local st node cuts reusing the data
234 structures:
236 >>> # You also have to explicitly import the function for
237 >>> # building the auxiliary digraph from the connectivity package
238 >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity
239 >>> H = build_auxiliary_node_connectivity(G)
240 >>> # And the function for building the residual network from the
241 >>> # flow package
242 >>> from networkx.algorithms.flow import build_residual_network
243 >>> # Note that the auxiliary digraph has an edge attribute named capacity
244 >>> R = build_residual_network(H, "capacity")
245 >>> # Reuse the auxiliary digraph and the residual network by passing them
246 >>> # as parameters
247 >>> len(minimum_st_node_cut(G, 0, 6, auxiliary=H, residual=R))
248 5
250 You can also use alternative flow algorithms for computing minimum st
251 node cuts. For instance, in dense networks the algorithm
252 :meth:`shortest_augmenting_path` will usually perform better than
253 the default :meth:`edmonds_karp` which is faster for sparse
254 networks with highly skewed degree distributions. Alternative flow
255 functions have to be explicitly imported from the flow package.
257 >>> from networkx.algorithms.flow import shortest_augmenting_path
258 >>> len(minimum_st_node_cut(G, 0, 6, flow_func=shortest_augmenting_path))
259 5
261 Notes
262 -----
263 This is a flow based implementation of minimum node cut. The algorithm
264 is based in solving a number of maximum flow computations to determine
265 the capacity of the minimum cut on an auxiliary directed network that
266 corresponds to the minimum node cut of G. It handles both directed
267 and undirected graphs. This implementation is based on algorithm 11
268 in [1]_.
270 See also
271 --------
272 :meth:`minimum_node_cut`
273 :meth:`minimum_edge_cut`
274 :meth:`stoer_wagner`
275 :meth:`node_connectivity`
276 :meth:`edge_connectivity`
277 :meth:`maximum_flow`
278 :meth:`edmonds_karp`
279 :meth:`preflow_push`
280 :meth:`shortest_augmenting_path`
282 References
283 ----------
284 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
285 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
287 """
288 if auxiliary is None:
289 H = build_auxiliary_node_connectivity(G)
290 else:
291 H = auxiliary
293 mapping = H.graph.get("mapping", None)
294 if mapping is None:
295 raise nx.NetworkXError("Invalid auxiliary digraph.")
296 if G.has_edge(s, t) or G.has_edge(t, s):
297 return {}
298 kwargs = {"flow_func": flow_func, "residual": residual, "auxiliary": H}
300 # The edge cut in the auxiliary digraph corresponds to the node cut in the
301 # original graph.
302 edge_cut = minimum_st_edge_cut(H, f"{mapping[s]}B", f"{mapping[t]}A", **kwargs)
303 # Each node in the original graph maps to two nodes of the auxiliary graph
304 node_cut = {H.nodes[node]["id"] for edge in edge_cut for node in edge}
305 return node_cut - {s, t}
308@nx._dispatch
309def minimum_node_cut(G, s=None, t=None, flow_func=None):
310 r"""Returns a set of nodes of minimum cardinality that disconnects G.
312 If source and target nodes are provided, this function returns the
313 set of nodes of minimum cardinality that, if removed, would destroy
314 all paths among source and target in G. If not, it returns a set
315 of nodes of minimum cardinality that disconnects G.
317 Parameters
318 ----------
319 G : NetworkX graph
321 s : node
322 Source node. Optional. Default value: None.
324 t : node
325 Target node. Optional. Default value: None.
327 flow_func : function
328 A function for computing the maximum flow among a pair of nodes.
329 The function has to accept at least three parameters: a Digraph,
330 a source node, and a target node. And return a residual network
331 that follows NetworkX conventions (see :meth:`maximum_flow` for
332 details). If flow_func is None, the default maximum flow function
333 (:meth:`edmonds_karp`) is used. See below for details. The
334 choice of the default function may change from version
335 to version and should not be relied on. Default value: None.
337 Returns
338 -------
339 cutset : set
340 Set of nodes that, if removed, would disconnect G. If source
341 and target nodes are provided, the set contains the nodes that
342 if removed, would destroy all paths between source and target.
344 Examples
345 --------
346 >>> # Platonic icosahedral graph has node connectivity 5
347 >>> G = nx.icosahedral_graph()
348 >>> node_cut = nx.minimum_node_cut(G)
349 >>> len(node_cut)
350 5
352 You can use alternative flow algorithms for the underlying maximum
353 flow computation. In dense networks the algorithm
354 :meth:`shortest_augmenting_path` will usually perform better
355 than the default :meth:`edmonds_karp`, which is faster for
356 sparse networks with highly skewed degree distributions. Alternative
357 flow functions have to be explicitly imported from the flow package.
359 >>> from networkx.algorithms.flow import shortest_augmenting_path
360 >>> node_cut == nx.minimum_node_cut(G, flow_func=shortest_augmenting_path)
361 True
363 If you specify a pair of nodes (source and target) as parameters,
364 this function returns a local st node cut.
366 >>> len(nx.minimum_node_cut(G, 3, 7))
367 5
369 If you need to perform several local st cuts among different
370 pairs of nodes on the same graph, it is recommended that you reuse
371 the data structures used in the maximum flow computations. See
372 :meth:`minimum_st_node_cut` for details.
374 Notes
375 -----
376 This is a flow based implementation of minimum node cut. The algorithm
377 is based in solving a number of maximum flow computations to determine
378 the capacity of the minimum cut on an auxiliary directed network that
379 corresponds to the minimum node cut of G. It handles both directed
380 and undirected graphs. This implementation is based on algorithm 11
381 in [1]_.
383 See also
384 --------
385 :meth:`minimum_st_node_cut`
386 :meth:`minimum_cut`
387 :meth:`minimum_edge_cut`
388 :meth:`stoer_wagner`
389 :meth:`node_connectivity`
390 :meth:`edge_connectivity`
391 :meth:`maximum_flow`
392 :meth:`edmonds_karp`
393 :meth:`preflow_push`
394 :meth:`shortest_augmenting_path`
396 References
397 ----------
398 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
399 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
401 """
402 if (s is not None and t is None) or (s is None and t is not None):
403 raise nx.NetworkXError("Both source and target must be specified.")
405 # Local minimum node cut.
406 if s is not None and t is not None:
407 if s not in G:
408 raise nx.NetworkXError(f"node {s} not in graph")
409 if t not in G:
410 raise nx.NetworkXError(f"node {t} not in graph")
411 return minimum_st_node_cut(G, s, t, flow_func=flow_func)
413 # Global minimum node cut.
414 # Analog to the algorithm 11 for global node connectivity in [1].
415 if G.is_directed():
416 if not nx.is_weakly_connected(G):
417 raise nx.NetworkXError("Input graph is not connected")
418 iter_func = itertools.permutations
420 def neighbors(v):
421 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)])
423 else:
424 if not nx.is_connected(G):
425 raise nx.NetworkXError("Input graph is not connected")
426 iter_func = itertools.combinations
427 neighbors = G.neighbors
429 # Reuse the auxiliary digraph and the residual network.
430 H = build_auxiliary_node_connectivity(G)
431 R = build_residual_network(H, "capacity")
432 kwargs = {"flow_func": flow_func, "auxiliary": H, "residual": R}
434 # Choose a node with minimum degree.
435 v = min(G, key=G.degree)
436 # Initial node cutset is all neighbors of the node with minimum degree.
437 min_cut = set(G[v])
438 # Compute st node cuts between v and all its non-neighbors nodes in G.
439 for w in set(G) - set(neighbors(v)) - {v}:
440 this_cut = minimum_st_node_cut(G, v, w, **kwargs)
441 if len(min_cut) >= len(this_cut):
442 min_cut = this_cut
443 # Also for non adjacent pairs of neighbors of v.
444 for x, y in iter_func(neighbors(v), 2):
445 if y in G[x]:
446 continue
447 this_cut = minimum_st_node_cut(G, x, y, **kwargs)
448 if len(min_cut) >= len(this_cut):
449 min_cut = this_cut
451 return min_cut
454@nx._dispatch
455def minimum_edge_cut(G, s=None, t=None, flow_func=None):
456 r"""Returns a set of edges of minimum cardinality that disconnects G.
458 If source and target nodes are provided, this function returns the
459 set of edges of minimum cardinality that, if removed, would break
460 all paths among source and target in G. If not, it returns a set of
461 edges of minimum cardinality that disconnects G.
463 Parameters
464 ----------
465 G : NetworkX graph
467 s : node
468 Source node. Optional. Default value: None.
470 t : node
471 Target node. Optional. Default value: None.
473 flow_func : function
474 A function for computing the maximum flow among a pair of nodes.
475 The function has to accept at least three parameters: a Digraph,
476 a source node, and a target node. And return a residual network
477 that follows NetworkX conventions (see :meth:`maximum_flow` for
478 details). If flow_func is None, the default maximum flow function
479 (:meth:`edmonds_karp`) is used. See below for details. The
480 choice of the default function may change from version
481 to version and should not be relied on. Default value: None.
483 Returns
484 -------
485 cutset : set
486 Set of edges that, if removed, would disconnect G. If source
487 and target nodes are provided, the set contains the edges that
488 if removed, would destroy all paths between source and target.
490 Examples
491 --------
492 >>> # Platonic icosahedral graph has edge connectivity 5
493 >>> G = nx.icosahedral_graph()
494 >>> len(nx.minimum_edge_cut(G))
495 5
497 You can use alternative flow algorithms for the underlying
498 maximum flow computation. In dense networks the algorithm
499 :meth:`shortest_augmenting_path` will usually perform better
500 than the default :meth:`edmonds_karp`, which is faster for
501 sparse networks with highly skewed degree distributions.
502 Alternative flow functions have to be explicitly imported
503 from the flow package.
505 >>> from networkx.algorithms.flow import shortest_augmenting_path
506 >>> len(nx.minimum_edge_cut(G, flow_func=shortest_augmenting_path))
507 5
509 If you specify a pair of nodes (source and target) as parameters,
510 this function returns the value of local edge connectivity.
512 >>> nx.edge_connectivity(G, 3, 7)
513 5
515 If you need to perform several local computations among different
516 pairs of nodes on the same graph, it is recommended that you reuse
517 the data structures used in the maximum flow computations. See
518 :meth:`local_edge_connectivity` for details.
520 Notes
521 -----
522 This is a flow based implementation of minimum edge cut. For
523 undirected graphs the algorithm works by finding a 'small' dominating
524 set of nodes of G (see algorithm 7 in [1]_) and computing the maximum
525 flow between an arbitrary node in the dominating set and the rest of
526 nodes in it. This is an implementation of algorithm 6 in [1]_. For
527 directed graphs, the algorithm does n calls to the max flow function.
528 The function raises an error if the directed graph is not weakly
529 connected and returns an empty set if it is weakly connected.
530 It is an implementation of algorithm 8 in [1]_.
532 See also
533 --------
534 :meth:`minimum_st_edge_cut`
535 :meth:`minimum_node_cut`
536 :meth:`stoer_wagner`
537 :meth:`node_connectivity`
538 :meth:`edge_connectivity`
539 :meth:`maximum_flow`
540 :meth:`edmonds_karp`
541 :meth:`preflow_push`
542 :meth:`shortest_augmenting_path`
544 References
545 ----------
546 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
547 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
549 """
550 if (s is not None and t is None) or (s is None and t is not None):
551 raise nx.NetworkXError("Both source and target must be specified.")
553 # reuse auxiliary digraph and residual network
554 H = build_auxiliary_edge_connectivity(G)
555 R = build_residual_network(H, "capacity")
556 kwargs = {"flow_func": flow_func, "residual": R, "auxiliary": H}
558 # Local minimum edge cut if s and t are not None
559 if s is not None and t is not None:
560 if s not in G:
561 raise nx.NetworkXError(f"node {s} not in graph")
562 if t not in G:
563 raise nx.NetworkXError(f"node {t} not in graph")
564 return minimum_st_edge_cut(H, s, t, **kwargs)
566 # Global minimum edge cut
567 # Analog to the algorithm for global edge connectivity
568 if G.is_directed():
569 # Based on algorithm 8 in [1]
570 if not nx.is_weakly_connected(G):
571 raise nx.NetworkXError("Input graph is not connected")
573 # Initial cutset is all edges of a node with minimum degree
574 node = min(G, key=G.degree)
575 min_cut = set(G.edges(node))
576 nodes = list(G)
577 n = len(nodes)
578 for i in range(n):
579 try:
580 this_cut = minimum_st_edge_cut(H, nodes[i], nodes[i + 1], **kwargs)
581 if len(this_cut) <= len(min_cut):
582 min_cut = this_cut
583 except IndexError: # Last node!
584 this_cut = minimum_st_edge_cut(H, nodes[i], nodes[0], **kwargs)
585 if len(this_cut) <= len(min_cut):
586 min_cut = this_cut
588 return min_cut
590 else: # undirected
591 # Based on algorithm 6 in [1]
592 if not nx.is_connected(G):
593 raise nx.NetworkXError("Input graph is not connected")
595 # Initial cutset is all edges of a node with minimum degree
596 node = min(G, key=G.degree)
597 min_cut = set(G.edges(node))
598 # A dominating set is \lambda-covering
599 # We need a dominating set with at least two nodes
600 for node in G:
601 D = nx.dominating_set(G, start_with=node)
602 v = D.pop()
603 if D:
604 break
605 else:
606 # in complete graphs the dominating set will always be of one node
607 # thus we return min_cut, which now contains the edges of a node
608 # with minimum degree
609 return min_cut
610 for w in D:
611 this_cut = minimum_st_edge_cut(H, v, w, **kwargs)
612 if len(this_cut) <= len(min_cut):
613 min_cut = this_cut
615 return min_cut