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