1"""Biconnected components and articulation points.""" 2from itertools import chain 3from networkx.utils.decorators import not_implemented_for 4 5__all__ = [ 6 "biconnected_components", 7 "biconnected_component_edges", 8 "is_biconnected", 9 "articulation_points", 10] 11 12 13@not_implemented_for("directed") 14def is_biconnected(G): 15 """Returns True if the graph is biconnected, False otherwise. 16 17 A graph is biconnected if, and only if, it cannot be disconnected by 18 removing only one node (and all edges incident on that node). If 19 removing a node increases the number of disconnected components 20 in the graph, that node is called an articulation point, or cut 21 vertex. A biconnected graph has no articulation points. 22 23 Parameters 24 ---------- 25 G : NetworkX Graph 26 An undirected graph. 27 28 Returns 29 ------- 30 biconnected : bool 31 True if the graph is biconnected, False otherwise. 32 33 Raises 34 ------ 35 NetworkXNotImplemented 36 If the input graph is not undirected. 37 38 Examples 39 -------- 40 >>> G = nx.path_graph(4) 41 >>> print(nx.is_biconnected(G)) 42 False 43 >>> G.add_edge(0, 3) 44 >>> print(nx.is_biconnected(G)) 45 True 46 47 See Also 48 -------- 49 biconnected_components 50 articulation_points 51 biconnected_component_edges 52 is_strongly_connected 53 is_weakly_connected 54 is_connected 55 is_semiconnected 56 57 Notes 58 ----- 59 The algorithm to find articulation points and biconnected 60 components is implemented using a non-recursive depth-first-search 61 (DFS) that keeps track of the highest level that back edges reach 62 in the DFS tree. A node `n` is an articulation point if, and only 63 if, there exists a subtree rooted at `n` such that there is no 64 back edge from any successor of `n` that links to a predecessor of 65 `n` in the DFS tree. By keeping track of all the edges traversed 66 by the DFS we can obtain the biconnected components because all 67 edges of a bicomponent will be traversed consecutively between 68 articulation points. 69 70 References 71 ---------- 72 .. [1] Hopcroft, J.; Tarjan, R. (1973). 73 "Efficient algorithms for graph manipulation". 74 Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 75 76 """ 77 bcc = list(biconnected_components(G)) 78 if len(bcc) == 1: 79 return len(bcc[0]) == len(G) 80 return False # Multiple bicomponents or No bicomponents (empty graph?) 81 82 83# if len(bcc) == 0: # No bicomponents (it could be an empty graph) 84# return False 85# return len(bcc[0]) == len(G) 86 87 88@not_implemented_for("directed") 89def biconnected_component_edges(G): 90 """Returns a generator of lists of edges, one list for each biconnected 91 component of the input graph. 92 93 Biconnected components are maximal subgraphs such that the removal of a 94 node (and all edges incident on that node) will not disconnect the 95 subgraph. Note that nodes may be part of more than one biconnected 96 component. Those nodes are articulation points, or cut vertices. 97 However, each edge belongs to one, and only one, biconnected component. 98 99 Notice that by convention a dyad is considered a biconnected component. 100 101 Parameters 102 ---------- 103 G : NetworkX Graph 104 An undirected graph. 105 106 Returns 107 ------- 108 edges : generator of lists 109 Generator of lists of edges, one list for each bicomponent. 110 111 Raises 112 ------ 113 NetworkXNotImplemented 114 If the input graph is not undirected. 115 116 Examples 117 -------- 118 >>> G = nx.barbell_graph(4, 2) 119 >>> print(nx.is_biconnected(G)) 120 False 121 >>> bicomponents_edges = list(nx.biconnected_component_edges(G)) 122 >>> len(bicomponents_edges) 123 5 124 >>> G.add_edge(2, 8) 125 >>> print(nx.is_biconnected(G)) 126 True 127 >>> bicomponents_edges = list(nx.biconnected_component_edges(G)) 128 >>> len(bicomponents_edges) 129 1 130 131 See Also 132 -------- 133 is_biconnected, 134 biconnected_components, 135 articulation_points, 136 137 Notes 138 ----- 139 The algorithm to find articulation points and biconnected 140 components is implemented using a non-recursive depth-first-search 141 (DFS) that keeps track of the highest level that back edges reach 142 in the DFS tree. A node `n` is an articulation point if, and only 143 if, there exists a subtree rooted at `n` such that there is no 144 back edge from any successor of `n` that links to a predecessor of 145 `n` in the DFS tree. By keeping track of all the edges traversed 146 by the DFS we can obtain the biconnected components because all 147 edges of a bicomponent will be traversed consecutively between 148 articulation points. 149 150 References 151 ---------- 152 .. [1] Hopcroft, J.; Tarjan, R. (1973). 153 "Efficient algorithms for graph manipulation". 154 Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 155 156 """ 157 yield from _biconnected_dfs(G, components=True) 158 159 160@not_implemented_for("directed") 161def biconnected_components(G): 162 """Returns a generator of sets of nodes, one set for each biconnected 163 component of the graph 164 165 Biconnected components are maximal subgraphs such that the removal of a 166 node (and all edges incident on that node) will not disconnect the 167 subgraph. Note that nodes may be part of more than one biconnected 168 component. Those nodes are articulation points, or cut vertices. The 169 removal of articulation points will increase the number of connected 170 components of the graph. 171 172 Notice that by convention a dyad is considered a biconnected component. 173 174 Parameters 175 ---------- 176 G : NetworkX Graph 177 An undirected graph. 178 179 Returns 180 ------- 181 nodes : generator 182 Generator of sets of nodes, one set for each biconnected component. 183 184 Raises 185 ------ 186 NetworkXNotImplemented 187 If the input graph is not undirected. 188 189 Examples 190 -------- 191 >>> G = nx.lollipop_graph(5, 1) 192 >>> print(nx.is_biconnected(G)) 193 False 194 >>> bicomponents = list(nx.biconnected_components(G)) 195 >>> len(bicomponents) 196 2 197 >>> G.add_edge(0, 5) 198 >>> print(nx.is_biconnected(G)) 199 True 200 >>> bicomponents = list(nx.biconnected_components(G)) 201 >>> len(bicomponents) 202 1 203 204 You can generate a sorted list of biconnected components, largest 205 first, using sort. 206 207 >>> G.remove_edge(0, 5) 208 >>> [len(c) for c in sorted(nx.biconnected_components(G), key=len, reverse=True)] 209 [5, 2] 210 211 If you only want the largest connected component, it's more 212 efficient to use max instead of sort. 213 214 >>> Gc = max(nx.biconnected_components(G), key=len) 215 216 To create the components as subgraphs use: 217 ``(G.subgraph(c).copy() for c in biconnected_components(G))`` 218 219 See Also 220 -------- 221 is_biconnected 222 articulation_points 223 biconnected_component_edges 224 k_components : this function is a special case where k=2 225 bridge_components : similar to this function, but is defined using 226 2-edge-connectivity instead of 2-node-connectivity. 227 228 Notes 229 ----- 230 The algorithm to find articulation points and biconnected 231 components is implemented using a non-recursive depth-first-search 232 (DFS) that keeps track of the highest level that back edges reach 233 in the DFS tree. A node `n` is an articulation point if, and only 234 if, there exists a subtree rooted at `n` such that there is no 235 back edge from any successor of `n` that links to a predecessor of 236 `n` in the DFS tree. By keeping track of all the edges traversed 237 by the DFS we can obtain the biconnected components because all 238 edges of a bicomponent will be traversed consecutively between 239 articulation points. 240 241 References 242 ---------- 243 .. [1] Hopcroft, J.; Tarjan, R. (1973). 244 "Efficient algorithms for graph manipulation". 245 Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 246 247 """ 248 for comp in _biconnected_dfs(G, components=True): 249 yield set(chain.from_iterable(comp)) 250 251 252@not_implemented_for("directed") 253def articulation_points(G): 254 """Yield the articulation points, or cut vertices, of a graph. 255 256 An articulation point or cut vertex is any node whose removal (along with 257 all its incident edges) increases the number of connected components of 258 a graph. An undirected connected graph without articulation points is 259 biconnected. Articulation points belong to more than one biconnected 260 component of a graph. 261 262 Notice that by convention a dyad is considered a biconnected component. 263 264 Parameters 265 ---------- 266 G : NetworkX Graph 267 An undirected graph. 268 269 Yields 270 ------ 271 node 272 An articulation point in the graph. 273 274 Raises 275 ------ 276 NetworkXNotImplemented 277 If the input graph is not undirected. 278 279 Examples 280 -------- 281 282 >>> G = nx.barbell_graph(4, 2) 283 >>> print(nx.is_biconnected(G)) 284 False 285 >>> len(list(nx.articulation_points(G))) 286 4 287 >>> G.add_edge(2, 8) 288 >>> print(nx.is_biconnected(G)) 289 True 290 >>> len(list(nx.articulation_points(G))) 291 0 292 293 See Also 294 -------- 295 is_biconnected 296 biconnected_components 297 biconnected_component_edges 298 299 Notes 300 ----- 301 The algorithm to find articulation points and biconnected 302 components is implemented using a non-recursive depth-first-search 303 (DFS) that keeps track of the highest level that back edges reach 304 in the DFS tree. A node `n` is an articulation point if, and only 305 if, there exists a subtree rooted at `n` such that there is no 306 back edge from any successor of `n` that links to a predecessor of 307 `n` in the DFS tree. By keeping track of all the edges traversed 308 by the DFS we can obtain the biconnected components because all 309 edges of a bicomponent will be traversed consecutively between 310 articulation points. 311 312 References 313 ---------- 314 .. [1] Hopcroft, J.; Tarjan, R. (1973). 315 "Efficient algorithms for graph manipulation". 316 Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 317 318 """ 319 seen = set() 320 for articulation in _biconnected_dfs(G, components=False): 321 if articulation not in seen: 322 seen.add(articulation) 323 yield articulation 324 325 326@not_implemented_for("directed") 327def _biconnected_dfs(G, components=True): 328 # depth-first search algorithm to generate articulation points 329 # and biconnected components 330 visited = set() 331 for start in G: 332 if start in visited: 333 continue 334 discovery = {start: 0} # time of first discovery of node during search 335 low = {start: 0} 336 root_children = 0 337 visited.add(start) 338 edge_stack = [] 339 stack = [(start, start, iter(G[start]))] 340 while stack: 341 grandparent, parent, children = stack[-1] 342 try: 343 child = next(children) 344 if grandparent == child: 345 continue 346 if child in visited: 347 if discovery[child] <= discovery[parent]: # back edge 348 low[parent] = min(low[parent], discovery[child]) 349 if components: 350 edge_stack.append((parent, child)) 351 else: 352 low[child] = discovery[child] = len(discovery) 353 visited.add(child) 354 stack.append((parent, child, iter(G[child]))) 355 if components: 356 edge_stack.append((parent, child)) 357 except StopIteration: 358 stack.pop() 359 if len(stack) > 1: 360 if low[parent] >= discovery[grandparent]: 361 if components: 362 ind = edge_stack.index((grandparent, parent)) 363 yield edge_stack[ind:] 364 edge_stack = edge_stack[:ind] 365 else: 366 yield grandparent 367 low[grandparent] = min(low[parent], low[grandparent]) 368 elif stack: # length 1 so grandparent is root 369 root_children += 1 370 if components: 371 ind = edge_stack.index((grandparent, parent)) 372 yield edge_stack[ind:] 373 if not components: 374 # root node is articulation point if it has more than 1 child 375 if root_children > 1: 376 yield start 377