Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/connectivity/kcutsets.py: 13%
89 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Kanevsky all minimum node k cutsets algorithm.
3"""
4import copy
5from collections import defaultdict
6from itertools import combinations
7from operator import itemgetter
9import networkx as nx
10from networkx.algorithms.flow import (
11 build_residual_network,
12 edmonds_karp,
13 shortest_augmenting_path,
14)
16from .utils import build_auxiliary_node_connectivity
18default_flow_func = edmonds_karp
21__all__ = ["all_node_cuts"]
24@nx._dispatch
25def all_node_cuts(G, k=None, flow_func=None):
26 r"""Returns all minimum k cutsets of an undirected graph G.
28 This implementation is based on Kanevsky's algorithm [1]_ for finding all
29 minimum-size node cut-sets of an undirected graph G; ie the set (or sets)
30 of nodes of cardinality equal to the node connectivity of G. Thus if
31 removed, would break G into two or more connected components.
33 Parameters
34 ----------
35 G : NetworkX graph
36 Undirected graph
38 k : Integer
39 Node connectivity of the input graph. If k is None, then it is
40 computed. Default value: None.
42 flow_func : function
43 Function to perform the underlying flow computations. Default value is
44 :func:`~networkx.algorithms.flow.edmonds_karp`. This function performs
45 better in sparse graphs with right tailed degree distributions.
46 :func:`~networkx.algorithms.flow.shortest_augmenting_path` will
47 perform better in denser graphs.
50 Returns
51 -------
52 cuts : a generator of node cutsets
53 Each node cutset has cardinality equal to the node connectivity of
54 the input graph.
56 Examples
57 --------
58 >>> # A two-dimensional grid graph has 4 cutsets of cardinality 2
59 >>> G = nx.grid_2d_graph(5, 5)
60 >>> cutsets = list(nx.all_node_cuts(G))
61 >>> len(cutsets)
62 4
63 >>> all(2 == len(cutset) for cutset in cutsets)
64 True
65 >>> nx.node_connectivity(G)
66 2
68 Notes
69 -----
70 This implementation is based on the sequential algorithm for finding all
71 minimum-size separating vertex sets in a graph [1]_. The main idea is to
72 compute minimum cuts using local maximum flow computations among a set
73 of nodes of highest degree and all other non-adjacent nodes in the Graph.
74 Once we find a minimum cut, we add an edge between the high degree
75 node and the target node of the local maximum flow computation to make
76 sure that we will not find that minimum cut again.
78 See also
79 --------
80 node_connectivity
81 edmonds_karp
82 shortest_augmenting_path
84 References
85 ----------
86 .. [1] Kanevsky, A. (1993). Finding all minimum-size separating vertex
87 sets in a graph. Networks 23(6), 533--541.
88 http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract
90 """
91 if not nx.is_connected(G):
92 raise nx.NetworkXError("Input graph is disconnected.")
94 # Address some corner cases first.
95 # For complete Graphs
96 if nx.density(G) == 1:
97 for cut_set in combinations(G, len(G) - 1):
98 yield set(cut_set)
99 return
100 # Initialize data structures.
101 # Keep track of the cuts already computed so we do not repeat them.
102 seen = []
103 # Even-Tarjan reduction is what we call auxiliary digraph
104 # for node connectivity.
105 H = build_auxiliary_node_connectivity(G)
106 H_nodes = H.nodes # for speed
107 mapping = H.graph["mapping"]
108 # Keep a copy of original predecessors, H will be modified later.
109 # Shallow copy is enough.
110 original_H_pred = copy.copy(H._pred)
111 R = build_residual_network(H, "capacity")
112 kwargs = {"capacity": "capacity", "residual": R}
113 # Define default flow function
114 if flow_func is None:
115 flow_func = default_flow_func
116 if flow_func is shortest_augmenting_path:
117 kwargs["two_phase"] = True
118 # Begin the actual algorithm
119 # step 1: Find node connectivity k of G
120 if k is None:
121 k = nx.node_connectivity(G, flow_func=flow_func)
122 # step 2:
123 # Find k nodes with top degree, call it X:
124 X = {n for n, d in sorted(G.degree(), key=itemgetter(1), reverse=True)[:k]}
125 # Check if X is a k-node-cutset
126 if _is_separating_set(G, X):
127 seen.append(X)
128 yield X
130 for x in X:
131 # step 3: Compute local connectivity flow of x with all other
132 # non adjacent nodes in G
133 non_adjacent = set(G) - X - set(G[x])
134 for v in non_adjacent:
135 # step 4: compute maximum flow in an Even-Tarjan reduction H of G
136 # and step 5: build the associated residual network R
137 R = flow_func(H, f"{mapping[x]}B", f"{mapping[v]}A", **kwargs)
138 flow_value = R.graph["flow_value"]
140 if flow_value == k:
141 # Find the nodes incident to the flow.
142 E1 = flowed_edges = [
143 (u, w) for (u, w, d) in R.edges(data=True) if d["flow"] != 0
144 ]
145 VE1 = incident_nodes = {n for edge in E1 for n in edge}
146 # Remove saturated edges form the residual network.
147 # Note that reversed edges are introduced with capacity 0
148 # in the residual graph and they need to be removed too.
149 saturated_edges = [
150 (u, w, d)
151 for (u, w, d) in R.edges(data=True)
152 if d["capacity"] == d["flow"] or d["capacity"] == 0
153 ]
154 R.remove_edges_from(saturated_edges)
155 R_closure = nx.transitive_closure(R)
156 # step 6: shrink the strongly connected components of
157 # residual flow network R and call it L.
158 L = nx.condensation(R)
159 cmap = L.graph["mapping"]
160 inv_cmap = defaultdict(list)
161 for n, scc in cmap.items():
162 inv_cmap[scc].append(n)
163 # Find the incident nodes in the condensed graph.
164 VE1 = {cmap[n] for n in VE1}
165 # step 7: Compute all antichains of L;
166 # they map to closed sets in H.
167 # Any edge in H that links a closed set is part of a cutset.
168 for antichain in nx.antichains(L):
169 # Only antichains that are subsets of incident nodes counts.
170 # Lemma 8 in reference.
171 if not set(antichain).issubset(VE1):
172 continue
173 # Nodes in an antichain of the condensation graph of
174 # the residual network map to a closed set of nodes that
175 # define a node partition of the auxiliary digraph H
176 # through taking all of antichain's predecessors in the
177 # transitive closure.
178 S = set()
179 for scc in antichain:
180 S.update(inv_cmap[scc])
181 S_ancestors = set()
182 for n in S:
183 S_ancestors.update(R_closure._pred[n])
184 S.update(S_ancestors)
185 if f"{mapping[x]}B" not in S or f"{mapping[v]}A" in S:
186 continue
187 # Find the cutset that links the node partition (S,~S) in H
188 cutset = set()
189 for u in S:
190 cutset.update((u, w) for w in original_H_pred[u] if w not in S)
191 # The edges in H that form the cutset are internal edges
192 # (ie edges that represent a node of the original graph G)
193 if any(H_nodes[u]["id"] != H_nodes[w]["id"] for u, w in cutset):
194 continue
195 node_cut = {H_nodes[u]["id"] for u, _ in cutset}
197 if len(node_cut) == k:
198 # The cut is invalid if it includes internal edges of
199 # end nodes. The other half of Lemma 8 in ref.
200 if x in node_cut or v in node_cut:
201 continue
202 if node_cut not in seen:
203 yield node_cut
204 seen.append(node_cut)
206 # Add an edge (x, v) to make sure that we do not
207 # find this cutset again. This is equivalent
208 # of adding the edge in the input graph
209 # G.add_edge(x, v) and then regenerate H and R:
210 # Add edges to the auxiliary digraph.
211 # See build_residual_network for convention we used
212 # in residual graphs.
213 H.add_edge(f"{mapping[x]}B", f"{mapping[v]}A", capacity=1)
214 H.add_edge(f"{mapping[v]}B", f"{mapping[x]}A", capacity=1)
215 # Add edges to the residual network.
216 R.add_edge(f"{mapping[x]}B", f"{mapping[v]}A", capacity=1)
217 R.add_edge(f"{mapping[v]}A", f"{mapping[x]}B", capacity=0)
218 R.add_edge(f"{mapping[v]}B", f"{mapping[x]}A", capacity=1)
219 R.add_edge(f"{mapping[x]}A", f"{mapping[v]}B", capacity=0)
221 # Add again the saturated edges to reuse the residual network
222 R.add_edges_from(saturated_edges)
225def _is_separating_set(G, cut):
226 """Assumes that the input graph is connected"""
227 if len(cut) == len(G) - 1:
228 return True
230 H = nx.restricted_view(G, cut, [])
231 if nx.is_connected(H):
232 return False
233 return True