## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / connectivity.py @ 5cef0f13

History | View | Annotate | Download (12.7 KB)

1 | 5cef0f13 | tiamilani | ```
""" 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 | ```
Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
``` |
||

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 4-node-connected
``` |
||

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 | ```
Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
``` |
||

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 non-neighbors 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 | ```
Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
``` |
||

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 | ```
Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
``` |
||

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)) |