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


2 
# Copyright (C) 20112019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Jordi Torrents (jtorrents@milnou.net)

10 
# Dan Schult (dschult@colgate.edu)

11 
# Aric Hagberg (aric.hagberg@gmail.com)

12 
"""Biconnected components and articulation points."""

13 
import warnings as _warnings 
14 
from itertools import chain 
15 
import networkx as nx 
16 
from networkx.utils.decorators import not_implemented_for 
17  
18 
__all__ = [ 
19 
'biconnected_components',

20 
'biconnected_component_edges',

21 
'biconnected_component_subgraphs',

22 
'is_biconnected',

23 
'articulation_points',

24 
] 
25  
26  
27 
@not_implemented_for('directed') 
28 
def is_biconnected(G): 
29 
"""Returns True if the graph is biconnected, False otherwise.

30 

31 
A graph is biconnected if, and only if, it cannot be disconnected by

32 
removing only one node (and all edges incident on that node). If

33 
removing a node increases the number of disconnected components

34 
in the graph, that node is called an articulation point, or cut

35 
vertex. A biconnected graph has no articulation points.

36 

37 
Parameters

38 


39 
G : NetworkX Graph

40 
An undirected graph.

41 

42 
Returns

43 


44 
biconnected : bool

45 
True if the graph is biconnected, False otherwise.

46 

47 
Raises

48 


49 
NetworkXNotImplemented :

50 
If the input graph is not undirected.

51 

52 
Examples

53 


54 
>>> G = nx.path_graph(4)

55 
>>> print(nx.is_biconnected(G))

56 
False

57 
>>> G.add_edge(0, 3)

58 
>>> print(nx.is_biconnected(G))

59 
True

60 

61 
See Also

62 


63 
biconnected_components

64 
articulation_points

65 
biconnected_component_edges

66 
is_strongly_connected

67 
is_weakly_connected

68 
is_connected

69 
is_semiconnected

70 

71 
Notes

72 


73 
The algorithm to find articulation points and biconnected

74 
components is implemented using a nonrecursive depthfirstsearch

75 
(DFS) that keeps track of the highest level that back edges reach

76 
in the DFS tree. A node `n` is an articulation point if, and only

77 
if, there exists a subtree rooted at `n` such that there is no

78 
back edge from any successor of `n` that links to a predecessor of

79 
`n` in the DFS tree. By keeping track of all the edges traversed

80 
by the DFS we can obtain the biconnected components because all

81 
edges of a bicomponent will be traversed consecutively between

82 
articulation points.

83 

84 
References

85 


86 
.. [1] Hopcroft, J.; Tarjan, R. (1973).

87 
"Efficient algorithms for graph manipulation".

88 
Communications of the ACM 16: 372–378. doi:10.1145/362248.362272

89 

90 
"""

91 
bcc = list(biconnected_components(G))

92 
if len(bcc) == 1: 
93 
return len(bcc[0]) == len(G) 
94 
return False # Multiple bicomponents or No bicomponents (empty graph?) 
95 
# if len(bcc) == 0: # No bicomponents (it could be an empty graph)

96 
# return False

97 
# return len(bcc[0]) == len(G)

98  
99  
100 
@not_implemented_for('directed') 
101 
def biconnected_component_edges(G): 
102 
"""Returns a generator of lists of edges, one list for each biconnected

103 
component of the input graph.

104 

105 
Biconnected components are maximal subgraphs such that the removal of a

106 
node (and all edges incident on that node) will not disconnect the

107 
subgraph. Note that nodes may be part of more than one biconnected

108 
component. Those nodes are articulation points, or cut vertices.

109 
However, each edge belongs to one, and only one, biconnected component.

110 

111 
Notice that by convention a dyad is considered a biconnected component.

112 

113 
Parameters

114 


115 
G : NetworkX Graph

116 
An undirected graph.

117 

118 
Returns

119 


120 
edges : generator of lists

121 
Generator of lists of edges, one list for each bicomponent.

122 

123 
Raises

124 


125 
NetworkXNotImplemented :

126 
If the input graph is not undirected.

127 

128 
Examples

129 


130 
>>> G = nx.barbell_graph(4, 2)

131 
>>> print(nx.is_biconnected(G))

132 
False

133 
>>> bicomponents_edges = list(nx.biconnected_component_edges(G))

134 
>>> len(bicomponents_edges)

135 
5

136 
>>> G.add_edge(2, 8)

137 
>>> print(nx.is_biconnected(G))

138 
True

139 
>>> bicomponents_edges = list(nx.biconnected_component_edges(G))

140 
>>> len(bicomponents_edges)

141 
1

142 

143 
See Also

144 


145 
is_biconnected,

146 
biconnected_components,

147 
articulation_points,

148 

149 
Notes

150 


151 
The algorithm to find articulation points and biconnected

152 
components is implemented using a nonrecursive depthfirstsearch

153 
(DFS) that keeps track of the highest level that back edges reach

154 
in the DFS tree. A node `n` is an articulation point if, and only

155 
if, there exists a subtree rooted at `n` such that there is no

156 
back edge from any successor of `n` that links to a predecessor of

157 
`n` in the DFS tree. By keeping track of all the edges traversed

158 
by the DFS we can obtain the biconnected components because all

159 
edges of a bicomponent will be traversed consecutively between

160 
articulation points.

161 

162 
References

163 


164 
.. [1] Hopcroft, J.; Tarjan, R. (1973).

165 
"Efficient algorithms for graph manipulation".

166 
Communications of the ACM 16: 372–378. doi:10.1145/362248.362272

167 

168 
"""

169 
for comp in _biconnected_dfs(G, components=True): 
170 
yield comp

171  
172  
173 
@not_implemented_for('directed') 
174 
def biconnected_components(G): 
175 
"""Returns a generator of sets of nodes, one set for each biconnected

176 
component of the graph

177 

178 
Biconnected components are maximal subgraphs such that the removal of a

179 
node (and all edges incident on that node) will not disconnect the

180 
subgraph. Note that nodes may be part of more than one biconnected

181 
component. Those nodes are articulation points, or cut vertices. The

182 
removal of articulation points will increase the number of connected

183 
components of the graph.

184 

185 
Notice that by convention a dyad is considered a biconnected component.

186 

187 
Parameters

188 


189 
G : NetworkX Graph

190 
An undirected graph.

191 

192 
Returns

193 


194 
nodes : generator

195 
Generator of sets of nodes, one set for each biconnected component.

196 

197 
Raises

198 


199 
NetworkXNotImplemented :

200 
If the input graph is not undirected.

201 

202 
See Also

203 


204 
k_components : this function is a special case where k=2

205 
bridge_components : similar to this function, but is defined using

206 
2edgeconnectivity instead of 2nodeconnectivity.

207 

208 

209 
Examples

210 


211 
>>> G = nx.lollipop_graph(5, 1)

212 
>>> print(nx.is_biconnected(G))

213 
False

214 
>>> bicomponents = list(nx.biconnected_components(G))

215 
>>> len(bicomponents)

216 
2

217 
>>> G.add_edge(0, 5)

218 
>>> print(nx.is_biconnected(G))

219 
True

220 
>>> bicomponents = list(nx.biconnected_components(G))

221 
>>> len(bicomponents)

222 
1

223 

224 
You can generate a sorted list of biconnected components, largest

225 
first, using sort.

226 

227 
>>> G.remove_edge(0, 5)

228 
>>> [len(c) for c in sorted(nx.biconnected_components(G), key=len, reverse=True)]

229 
[5, 2]

230 

231 
If you only want the largest connected component, it's more

232 
efficient to use max instead of sort.

233 

234 
>>> Gc = max(nx.biconnected_components(G), key=len)

235 

236 
See Also

237 


238 
is_biconnected

239 
articulation_points

240 
biconnected_component_edges

241 

242 
Notes

243 


244 
The algorithm to find articulation points and biconnected

245 
components is implemented using a nonrecursive depthfirstsearch

246 
(DFS) that keeps track of the highest level that back edges reach

247 
in the DFS tree. A node `n` is an articulation point if, and only

248 
if, there exists a subtree rooted at `n` such that there is no

249 
back edge from any successor of `n` that links to a predecessor of

250 
`n` in the DFS tree. By keeping track of all the edges traversed

251 
by the DFS we can obtain the biconnected components because all

252 
edges of a bicomponent will be traversed consecutively between

253 
articulation points.

254 

255 
References

256 


257 
.. [1] Hopcroft, J.; Tarjan, R. (1973).

258 
"Efficient algorithms for graph manipulation".

259 
Communications of the ACM 16: 372–378. doi:10.1145/362248.362272

260 

261 
"""

262 
for comp in _biconnected_dfs(G, components=True): 
263 
yield set(chain.from_iterable(comp)) 
264  
265  
266 
@not_implemented_for('directed') 
267 
def biconnected_component_subgraphs(G, copy=True): 
268 
"""DEPRECATED: Use ``(G.subgraph(c) for c in biconnected_components(G))``

269 

270 
Or ``(G.subgraph(c).copy() for c in biconnected_components(G))``

271 
"""

272 
msg = "connected_component_subgraphs is deprecated and will be removed" \

273 
"in 2.2. Use (G.subgraph(c).copy() for c in biconnected_components(G))"

274 
_warnings.warn(msg, DeprecationWarning)

275 
for c in biconnected_components(G): 
276 
if copy:

277 
yield G.subgraph(c).copy()

278 
else:

279 
yield G.subgraph(c)

280  
281  
282 
@not_implemented_for('directed') 
283 
def articulation_points(G): 
284 
"""Yield the articulation points, or cut vertices, of a graph.

285 

286 
An articulation point or cut vertex is any node whose removal (along with

287 
all its incident edges) increases the number of connected components of

288 
a graph. An undirected connected graph without articulation points is

289 
biconnected. Articulation points belong to more than one biconnected

290 
component of a graph.

291 

292 
Notice that by convention a dyad is considered a biconnected component.

293 

294 
Parameters

295 


296 
G : NetworkX Graph

297 
An undirected graph.

298 

299 
Yields

300 


301 
node

302 
An articulation point in the graph.

303 

304 
Raises

305 


306 
NetworkXNotImplemented :

307 
If the input graph is not undirected.

308 

309 
Examples

310 


311 

312 
>>> G = nx.barbell_graph(4, 2)

313 
>>> print(nx.is_biconnected(G))

314 
False

315 
>>> len(list(nx.articulation_points(G)))

316 
4

317 
>>> G.add_edge(2, 8)

318 
>>> print(nx.is_biconnected(G))

319 
True

320 
>>> len(list(nx.articulation_points(G)))

321 
0

322 

323 
See Also

324 


325 
is_biconnected

326 
biconnected_components

327 
biconnected_component_edges

328 

329 
Notes

330 


331 
The algorithm to find articulation points and biconnected

332 
components is implemented using a nonrecursive depthfirstsearch

333 
(DFS) that keeps track of the highest level that back edges reach

334 
in the DFS tree. A node `n` is an articulation point if, and only

335 
if, there exists a subtree rooted at `n` such that there is no

336 
back edge from any successor of `n` that links to a predecessor of

337 
`n` in the DFS tree. By keeping track of all the edges traversed

338 
by the DFS we can obtain the biconnected components because all

339 
edges of a bicomponent will be traversed consecutively between

340 
articulation points.

341 

342 
References

343 


344 
.. [1] Hopcroft, J.; Tarjan, R. (1973).

345 
"Efficient algorithms for graph manipulation".

346 
Communications of the ACM 16: 372–378. doi:10.1145/362248.362272

347 

348 
"""

349 
seen = set()

350 
for articulation in _biconnected_dfs(G, components=False): 
351 
if articulation not in seen: 
352 
seen.add(articulation) 
353 
yield articulation

354  
355  
356 
@not_implemented_for('directed') 
357 
def _biconnected_dfs(G, components=True): 
358 
# depthfirst search algorithm to generate articulation points

359 
# and biconnected components

360 
visited = set()

361 
for start in G: 
362 
if start in visited: 
363 
continue

364 
discovery = {start: 0} # time of first discovery of node during search 
365 
low = {start: 0}

366 
root_children = 0

367 
visited.add(start) 
368 
edge_stack = [] 
369 
stack = [(start, start, iter(G[start]))]

370 
while stack:

371 
grandparent, parent, children = stack[1]

372 
try:

373 
child = next(children)

374 
if grandparent == child:

375 
continue

376 
if child in visited: 
377 
if discovery[child] <= discovery[parent]: # back edge 
378 
low[parent] = min(low[parent], discovery[child])

379 
if components:

380 
edge_stack.append((parent, child)) 
381 
else:

382 
low[child] = discovery[child] = len(discovery)

383 
visited.add(child) 
384 
stack.append((parent, child, iter(G[child])))

385 
if components:

386 
edge_stack.append((parent, child)) 
387 
except StopIteration: 
388 
stack.pop() 
389 
if len(stack) > 1: 
390 
if low[parent] >= discovery[grandparent]:

391 
if components:

392 
ind = edge_stack.index((grandparent, parent)) 
393 
yield edge_stack[ind:]

394 
edge_stack = edge_stack[:ind] 
395 
else:

396 
yield grandparent

397 
low[grandparent] = min(low[parent], low[grandparent])

398 
elif stack: # length 1 so grandparent is root 
399 
root_children += 1

400 
if components:

401 
ind = edge_stack.index((grandparent, parent)) 
402 
yield edge_stack[ind:]

403 
if not components: 
404 
# root node is articulation point if it has more than 1 child

405 
if root_children > 1: 
406 
yield start
