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