ioftools / networkxMiCe / networkxmaster / networkx / algorithms / connectivity / kcutsets.py @ 5cef0f13
History  View  Annotate  Download (9.53 KB)
1 
# * coding: utf8 *


2 
"""

3 
Kanevsky all minimum node k cutsets algorithm.

4 
"""

5 
import copy 
6 
from collections import defaultdict 
7 
from itertools import combinations 
8 
from operator import itemgetter 
9  
10 
import networkx as nx 
11 
from .utils import build_auxiliary_node_connectivity 
12 
from networkx.algorithms.flow import ( 
13 
build_residual_network, 
14 
edmonds_karp, 
15 
shortest_augmenting_path, 
16 
) 
17 
default_flow_func = edmonds_karp 
18  
19  
20 
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>']) 
21  
22 
__all__ = ['all_node_cuts']

23  
24  
25 
def all_node_cuts(G, k=None, flow_func=None): 
26 
r"""Returns all minimum k cutsets of an undirected graph G.

27 

28 
This implementation is based on Kanevsky's algorithm [1]_ for finding all

29 
minimumsize node cutsets 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.

32 

33 
Parameters

34 


35 
G : NetworkX graph

36 
Undirected graph

37 

38 
k : Integer

39 
Node connectivity of the input graph. If k is None, then it is

40 
computed. Default value: None.

41 

42 
flow_func : function

43 
Function to perform the underlying flow computations. Default value

44 
edmonds_karp. This function performs better in sparse graphs with

45 
right tailed degree distributions. shortest_augmenting_path will

46 
perform better in denser graphs.

47 

48 

49 
Returns

50 


51 
cuts : a generator of node cutsets

52 
Each node cutset has cardinality equal to the node connectivity of

53 
the input graph.

54 

55 
Examples

56 


57 
>>> # A twodimensional grid graph has 4 cutsets of cardinality 2

58 
>>> G = nx.grid_2d_graph(5, 5)

59 
>>> cutsets = list(nx.all_node_cuts(G))

60 
>>> len(cutsets)

61 
4

62 
>>> all(2 == len(cutset) for cutset in cutsets)

63 
True

64 
>>> nx.node_connectivity(G)

65 
2

66 

67 
Notes

68 


69 
This implementation is based on the sequential algorithm for finding all

70 
minimumsize separating vertex sets in a graph [1]_. The main idea is to

71 
compute minimum cuts using local maximum flow computations among a set

72 
of nodes of highest degree and all other nonadjacent nodes in the Graph.

73 
Once we find a minimum cut, we add an edge between the high degree

74 
node and the target node of the local maximum flow computation to make

75 
sure that we will not find that minimum cut again.

76 

77 
See also

78 


79 
node_connectivity

80 
edmonds_karp

81 
shortest_augmenting_path

82 

83 
References

84 


85 
.. [1] Kanevsky, A. (1993). Finding all minimumsize separating vertex

86 
sets in a graph. Networks 23(6), 533541.

87 
http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract

88 

89 
"""

90 
if not nx.is_connected(G): 
91 
raise nx.NetworkXError('Input graph is disconnected.') 
92  
93 
# Address some corner cases first.

94 
# For complete Graphs

95 
if nx.density(G) == 1: 
96 
for cut_set in combinations(G, len(G)  1): 
97 
yield set(cut_set) 
98 
return

99 
# Initialize data structures.

100 
# Keep track of the cuts already computed so we do not repeat them.

101 
seen = [] 
102 
# EvenTarjan reduction is what we call auxiliary digraph

103 
# for node connectivity.

104 
H = build_auxiliary_node_connectivity(G) 
105 
H_nodes = H.nodes # for speed

106 
mapping = H.graph['mapping']

107 
# Keep a copy of original predecessors, H will be modified later.

108 
# Shallow copy is enough.

109 
original_H_pred = copy.copy(H._pred) 
110 
R = build_residual_network(H, 'capacity')

111 
kwargs = dict(capacity='capacity', residual=R) 
112 
# Define default flow function

113 
if flow_func is None: 
114 
flow_func = default_flow_func 
115 
if flow_func is shortest_augmenting_path: 
116 
kwargs['two_phase'] = True 
117 
# Begin the actual algorithm

118 
# step 1: Find node connectivity k of G

119 
if k is None: 
120 
k = nx.node_connectivity(G, flow_func=flow_func) 
121 
# step 2:

122 
# Find k nodes with top degree, call it X:

123 
X = {n for n, d in sorted(G.degree(), key=itemgetter(1), reverse=True)[:k]} 
124 
# Check if X is a knodecutset

125 
if _is_separating_set(G, X):

126 
seen.append(X) 
127 
yield X

128  
129 
for x in X: 
130 
# step 3: Compute local connectivity flow of x with all other

131 
# non adjacent nodes in G

132 
non_adjacent = set(G)  X  set(G[x]) 
133 
for v in non_adjacent: 
134 
# step 4: compute maximum flow in an EvenTarjan reduction H of G

135 
# and step 5: build the associated residual network R

136 
R = flow_func(H, '%sB' % mapping[x], '%sA' % mapping[v], **kwargs) 
137 
flow_value = R.graph['flow_value']

138  
139 
if flow_value == k:

140 
# Find the nodes incident to the flow.

141 
E1 = flowed_edges = [(u, w) for (u, w, d) in 
142 
R.edges(data=True)

143 
if d['flow'] != 0] 
144 
VE1 = incident_nodes = set([n for edge in E1 for n in edge]) 
145 
# Remove saturated edges form the residual network.

146 
# Note that reversed edges are introduced with capacity 0

147 
# in the residual graph and they need to be removed too.

148 
saturated_edges = [(u, w, d) for (u, w, d) in 
149 
R.edges(data=True)

150 
if d['capacity'] == d['flow'] 
151 
or d['capacity'] == 0] 
152 
R.remove_edges_from(saturated_edges) 
153 
R_closure = nx.transitive_closure(R) 
154 
# step 6: shrink the strongly connected components of

155 
# residual flow network R and call it L.

156 
L = nx.condensation(R) 
157 
cmap = L.graph['mapping']

158 
inv_cmap = defaultdict(list)

159 
for n, scc in cmap.items(): 
160 
inv_cmap[scc].append(n) 
161 
# Find the incident nodes in the condensed graph.

162 
VE1 = set([cmap[n] for n in VE1]) 
163 
# step 7: Compute all antichains of L;

164 
# they map to closed sets in H.

165 
# Any edge in H that links a closed set is part of a cutset.

166 
for antichain in nx.antichains(L): 
167 
# Only antichains that are subsets of incident nodes counts.

168 
# Lemma 8 in reference.

169 
if not set(antichain).issubset(VE1): 
170 
continue

171 
# Nodes in an antichain of the condensation graph of

172 
# the residual network map to a closed set of nodes that

173 
# define a node partition of the auxiliary digraph H

174 
# through taking all of antichain's predecessors in the

175 
# transitive closure.

176 
S = set()

177 
for scc in antichain: 
178 
S.update(inv_cmap[scc]) 
179 
S_ancestors = set()

180 
for n in S: 
181 
S_ancestors.update(R_closure._pred[n]) 
182 
S.update(S_ancestors) 
183 
if '%sB' % mapping[x] not in S or '%sA' % mapping[v] in S: 
184 
continue

185 
# Find the cutset that links the node partition (S,~S) in H

186 
cutset = set()

187 
for u in S: 
188 
cutset.update((u, w) 
189 
for w in original_H_pred[u] if w not in S) 
190 
# The edges in H that form the cutset are internal edges

191 
# (ie edges that represent a node of the original graph G)

192 
if any([H_nodes[u]['id'] != H_nodes[w]['id'] 
193 
for u, w in cutset]): 
194 
continue

195 
node_cut = {H_nodes[u]['id'] for u, _ in cutset} 
196  
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) 
205  
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('%sB' % mapping[x], '%sA' % mapping[v], 
214 
capacity=1)

215 
H.add_edge('%sB' % mapping[v], '%sA' % mapping[x], 
216 
capacity=1)

217 
# Add edges to the residual network.

218 
R.add_edge('%sB' % mapping[x], '%sA' % mapping[v], 
219 
capacity=1)

220 
R.add_edge('%sA' % mapping[v], '%sB' % mapping[x], 
221 
capacity=0)

222 
R.add_edge('%sB' % mapping[v], '%sA' % mapping[x], 
223 
capacity=1)

224 
R.add_edge('%sA' % mapping[x], '%sB' % mapping[v], 
225 
capacity=0)

226  
227 
# Add again the saturated edges to reuse the residual network

228 
R.add_edges_from(saturated_edges) 
229  
230  
231 
def _is_separating_set(G, cut): 
232 
"""Assumes that the input graph is connected"""

233 
if len(cut) == len(G)  1: 
234 
return True 
235  
236 
H = nx.restricted_view(G, cut, []) 
237 
if nx.is_connected(H):

238 
return False 
239 
return True 