ioftools / networkxMiCe / networkxmaster / networkx / algorithms / approximation / connectivity.py @ 5cef0f13
History  View  Annotate  Download (12.7 KB)
1 
""" Fast approximation for node connectivity


2 
"""

3 
# Copyright (C) 2015 by

4 
# Jordi Torrents <jtorrents@milnou.net>

5 
# All rights reserved.

6 
# BSD license.

7 
import itertools 
8 
from operator import itemgetter 
9  
10 
import networkx as nx 
11  
12 
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>']) 
13  
14 
__all__ = ['local_node_connectivity',

15 
'node_connectivity',

16 
'all_pairs_node_connectivity']

17  
18 
INF = float('inf') 
19  
20  
21 
def local_node_connectivity(G, source, target, cutoff=None): 
22 
"""Compute node connectivity between source and target.

23 

24 
Pairwise or local node connectivity between two distinct and nonadjacent

25 
nodes is the minimum number of nodes that must be removed (minimum

26 
separating cutset) to disconnect them. By Menger's theorem, this is equal

27 
to the number of node independent paths (paths that share no nodes other

28 
than source and target). Which is what we compute in this function.

29 

30 
This algorithm is a fast approximation that gives an strict lower

31 
bound on the actual number of node independent paths between two nodes [1]_.

32 
It works for both directed and undirected graphs.

33 

34 
Parameters

35 


36 

37 
G : NetworkX graph

38 

39 
source : node

40 
Starting node for node connectivity

41 

42 
target : node

43 
Ending node for node connectivity

44 

45 
cutoff : integer

46 
Maximum node connectivity to consider. If None, the minimum degree

47 
of source or target is used as a cutoff. Default value None.

48 

49 
Returns

50 


51 
k: integer

52 
pairwise node connectivity

53 

54 
Examples

55 


56 
>>> # Platonic octahedral graph has node connectivity 4

57 
>>> # for each non adjacent node pair

58 
>>> from networkx.algorithms import approximation as approx

59 
>>> G = nx.octahedral_graph()

60 
>>> approx.local_node_connectivity(G, 0, 5)

61 
4

62 

63 
Notes

64 


65 
This algorithm [1]_ finds node independents paths between two nodes by

66 
computing their shortest path using BFS, marking the nodes of the path

67 
found as 'used' and then searching other shortest paths excluding the

68 
nodes marked as used until no more paths exist. It is not exact because

69 
a shortest path could use nodes that, if the path were longer, may belong

70 
to two different node independent paths. Thus it only guarantees an

71 
strict lower bound on node connectivity.

72 

73 
Note that the authors propose a further refinement, losing accuracy and

74 
gaining speed, which is not implemented yet.

75 

76 
See also

77 


78 
all_pairs_node_connectivity

79 
node_connectivity

80 

81 
References

82 


83 
.. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for

84 
NodeIndependent Paths. Santa Fe Institute Working Paper #0107035

85 
http://eclectic.ss.uci.edu/~drwhite/working.pdf

86 

87 
"""

88 
if target == source:

89 
raise nx.NetworkXError("source and target have to be different nodes.") 
90  
91 
# Maximum possible node independent paths

92 
if G.is_directed():

93 
possible = min(G.out_degree(source), G.in_degree(target))

94 
else:

95 
possible = min(G.degree(source), G.degree(target))

96  
97 
K = 0

98 
if not possible: 
99 
return K

100  
101 
if cutoff is None: 
102 
cutoff = INF 
103  
104 
exclude = set()

105 
for i in range(min(possible, cutoff)): 
106 
try:

107 
path = _bidirectional_shortest_path(G, source, target, exclude) 
108 
exclude.update(set(path))

109 
K += 1

110 
except nx.NetworkXNoPath:

111 
break

112  
113 
return K

114  
115  
116 
def node_connectivity(G, s=None, t=None): 
117 
r"""Returns an approximation for node connectivity for a graph or digraph G.

118 

119 
Node connectivity is equal to the minimum number of nodes that

120 
must be removed to disconnect G or render it trivial. By Menger's theorem,

121 
this is equal to the number of node independent paths (paths that

122 
share no nodes other than source and target).

123 

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

125 
local node connectivity: the minimum number of nodes that must be

126 
removed to break all paths from source to target in G.

127 

128 
This algorithm is based on a fast approximation that gives an strict lower

129 
bound on the actual number of node independent paths between two nodes [1]_.

130 
It works for both directed and undirected graphs.

131 

132 
Parameters

133 


134 
G : NetworkX graph

135 
Undirected graph

136 

137 
s : node

138 
Source node. Optional. Default value: None.

139 

140 
t : node

141 
Target node. Optional. Default value: None.

142 

143 
Returns

144 


145 
K : integer

146 
Node connectivity of G, or local node connectivity if source

147 
and target are provided.

148 

149 
Examples

150 


151 
>>> # Platonic octahedral graph is 4nodeconnected

152 
>>> from networkx.algorithms import approximation as approx

153 
>>> G = nx.octahedral_graph()

154 
>>> approx.node_connectivity(G)

155 
4

156 

157 
Notes

158 


159 
This algorithm [1]_ finds node independents paths between two nodes by

160 
computing their shortest path using BFS, marking the nodes of the path

161 
found as 'used' and then searching other shortest paths excluding the

162 
nodes marked as used until no more paths exist. It is not exact because

163 
a shortest path could use nodes that, if the path were longer, may belong

164 
to two different node independent paths. Thus it only guarantees an

165 
strict lower bound on node connectivity.

166 

167 
See also

168 


169 
all_pairs_node_connectivity

170 
local_node_connectivity

171 

172 
References

173 


174 
.. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for

175 
NodeIndependent Paths. Santa Fe Institute Working Paper #0107035

176 
http://eclectic.ss.uci.edu/~drwhite/working.pdf

177 

178 
"""

179 
if (s is not None and t is None) or (s is None and t is not None): 
180 
raise nx.NetworkXError('Both source and target must be specified.') 
181  
182 
# Local node connectivity

183 
if s is not None and t is not None: 
184 
if s not in G: 
185 
raise nx.NetworkXError('node %s not in graph' % s) 
186 
if t not in G: 
187 
raise nx.NetworkXError('node %s not in graph' % t) 
188 
return local_node_connectivity(G, s, t)

189  
190 
# Global node connectivity

191 
if G.is_directed():

192 
connected_func = nx.is_weakly_connected 
193 
iter_func = itertools.permutations 
194  
195 
def neighbors(v): 
196 
return itertools.chain(G.predecessors(v), G.successors(v))

197 
else:

198 
connected_func = nx.is_connected 
199 
iter_func = itertools.combinations 
200 
neighbors = G.neighbors 
201  
202 
if not connected_func(G): 
203 
return 0 
204  
205 
# Choose a node with minimum degree

206 
v, minimum_degree = min(G.degree(), key=itemgetter(1)) 
207 
# Node connectivity is bounded by minimum degree

208 
K = minimum_degree 
209 
# compute local node connectivity with all nonneighbors nodes

210 
# and store the minimum

211 
for w in set(G)  set(neighbors(v))  set([v]): 
212 
K = min(K, local_node_connectivity(G, v, w, cutoff=K))

213 
# Same for non adjacent pairs of neighbors of v

214 
for x, y in iter_func(neighbors(v), 2): 
215 
if y not in G[x] and x != y: 
216 
K = min(K, local_node_connectivity(G, x, y, cutoff=K))

217 
return K

218  
219  
220 
def all_pairs_node_connectivity(G, nbunch=None, cutoff=None): 
221 
""" Compute node connectivity between all pairs of nodes.

222 

223 
Pairwise or local node connectivity between two distinct and nonadjacent

224 
nodes is the minimum number of nodes that must be removed (minimum

225 
separating cutset) to disconnect them. By Menger's theorem, this is equal

226 
to the number of node independent paths (paths that share no nodes other

227 
than source and target). Which is what we compute in this function.

228 

229 
This algorithm is a fast approximation that gives an strict lower

230 
bound on the actual number of node independent paths between two nodes [1]_.

231 
It works for both directed and undirected graphs.

232 

233 

234 
Parameters

235 


236 
G : NetworkX graph

237 

238 
nbunch: container

239 
Container of nodes. If provided node connectivity will be computed

240 
only over pairs of nodes in nbunch.

241 

242 
cutoff : integer

243 
Maximum node connectivity to consider. If None, the minimum degree

244 
of source or target is used as a cutoff in each pair of nodes.

245 
Default value None.

246 

247 
Returns

248 


249 
K : dictionary

250 
Dictionary, keyed by source and target, of pairwise node connectivity

251 

252 
See Also

253 


254 
local_node_connectivity

255 
all_pairs_node_connectivity

256 

257 
References

258 


259 
.. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for

260 
NodeIndependent Paths. Santa Fe Institute Working Paper #0107035

261 
http://eclectic.ss.uci.edu/~drwhite/working.pdf

262 
"""

263 
if nbunch is None: 
264 
nbunch = G 
265 
else:

266 
nbunch = set(nbunch)

267  
268 
directed = G.is_directed() 
269 
if directed:

270 
iter_func = itertools.permutations 
271 
else:

272 
iter_func = itertools.combinations 
273  
274 
all_pairs = {n: {} for n in nbunch} 
275  
276 
for u, v in iter_func(nbunch, 2): 
277 
k = local_node_connectivity(G, u, v, cutoff=cutoff) 
278 
all_pairs[u][v] = k 
279 
if not directed: 
280 
all_pairs[v][u] = k 
281  
282 
return all_pairs

283  
284  
285 
def _bidirectional_shortest_path(G, source, target, exclude): 
286 
"""Returns shortest path between source and target ignoring nodes in the

287 
container 'exclude'.

288 

289 
Parameters

290 


291 

292 
G : NetworkX graph

293 

294 
source : node

295 
Starting node for path

296 

297 
target : node

298 
Ending node for path

299 

300 
exclude: container

301 
Container for nodes to exclude from the search for shortest paths

302 

303 
Returns

304 


305 
path: list

306 
Shortest path between source and target ignoring nodes in 'exclude'

307 

308 
Raises

309 


310 
NetworkXNoPath: exception

311 
If there is no path or if nodes are adjacent and have only one path

312 
between them

313 

314 
Notes

315 


316 
This function and its helper are originally from

317 
networkx.algorithms.shortest_paths.unweighted and are modified to

318 
accept the extra parameter 'exclude', which is a container for nodes

319 
already used in other paths that should be ignored.

320 

321 
References

322 


323 
.. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for

324 
NodeIndependent Paths. Santa Fe Institute Working Paper #0107035

325 
http://eclectic.ss.uci.edu/~drwhite/working.pdf

326 

327 
"""

328 
# call helper to do the real work

329 
results = _bidirectional_pred_succ(G, source, target, exclude) 
330 
pred, succ, w = results 
331  
332 
# build path from pred+w+succ

333 
path = [] 
334 
# from source to w

335 
while w is not None: 
336 
path.append(w) 
337 
w = pred[w] 
338 
path.reverse() 
339 
# from w to target

340 
w = succ[path[1]]

341 
while w is not None: 
342 
path.append(w) 
343 
w = succ[w] 
344  
345 
return path

346  
347  
348 
def _bidirectional_pred_succ(G, source, target, exclude): 
349 
# does BFS from both source and target and meets in the middle

350 
# excludes nodes in the container "exclude" from the search

351 
if source is None or target is None: 
352 
raise nx.NetworkXException(

353 
"Bidirectional shortest path called without source or target")

354 
if target == source:

355 
return ({target: None}, {source: None}, source) 
356  
357 
# handle either directed or undirected

358 
if G.is_directed():

359 
Gpred = G.predecessors 
360 
Gsucc = G.successors 
361 
else:

362 
Gpred = G.neighbors 
363 
Gsucc = G.neighbors 
364  
365 
# predecesssor and successors in search

366 
pred = {source: None}

367 
succ = {target: None}

368  
369 
# initialize fringes, start with forward

370 
forward_fringe = [source] 
371 
reverse_fringe = [target] 
372  
373 
level = 0

374  
375 
while forward_fringe and reverse_fringe: 
376 
# Make sure that we iterate one step forward and one step backwards

377 
# thus source and target will only trigger "found path" when they are

378 
# adjacent and then they can be safely included in the container 'exclude'

379 
level += 1

380 
if not level % 2 == 0: 
381 
this_level = forward_fringe 
382 
forward_fringe = [] 
383 
for v in this_level: 
384 
for w in Gsucc(v): 
385 
if w in exclude: 
386 
continue

387 
if w not in pred: 
388 
forward_fringe.append(w) 
389 
pred[w] = v 
390 
if w in succ: 
391 
return pred, succ, w # found path 
392 
else:

393 
this_level = reverse_fringe 
394 
reverse_fringe = [] 
395 
for v in this_level: 
396 
for w in Gpred(v): 
397 
if w in exclude: 
398 
continue

399 
if w not in succ: 
400 
succ[w] = v 
401 
reverse_fringe.append(w) 
402 
if w in pred: 
403 
return pred, succ, w # found path 
404  
405 
raise nx.NetworkXNoPath("No path between %s and %s." % (source, target)) 