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