networkx.algorithms.components.biconnected_components¶
-
biconnected_components
(G)[source]¶ Returns a generator of sets of nodes, one set for each biconnected component of the graph
Biconnected components are maximal subgraphs such that the removal of a node (and all edges incident on that node) will not disconnect the subgraph. Note that nodes may be part of more than one biconnected component. Those nodes are articulation points, or cut vertices. The removal of articulation points will increase the number of connected components of the graph.
Notice that by convention a dyad is considered a biconnected component.
- Parameters
G (NetworkX Graph) – An undirected graph.
- Returns
nodes – Generator of sets of nodes, one set for each biconnected component.
- Return type
generator
- Raises
NetworkXNotImplemented – If the input graph is not undirected.
See also
k_components()
this function is a special case where k=2
bridge_components()
similar to this function, but is defined using 2-edge-connectivity instead of 2-node-connectivity.
Examples
>>> G = nx.lollipop_graph(5, 1) >>> print(nx.is_biconnected(G)) False >>> bicomponents = list(nx.biconnected_components(G)) >>> len(bicomponents) 2 >>> G.add_edge(0, 5) >>> print(nx.is_biconnected(G)) True >>> bicomponents = list(nx.biconnected_components(G)) >>> len(bicomponents) 1
You can generate a sorted list of biconnected components, largest first, using sort.
>>> G.remove_edge(0, 5) >>> [len(c) for c in sorted(nx.biconnected_components(G), key=len, reverse=True)] [5, 2]
If you only want the largest connected component, it’s more efficient to use max instead of sort.
>>> Gc = max(nx.biconnected_components(G), key=len)
To create the components as subgraphs use:
(G.subgraph(c).copy() for c in biconnected_components(G))
Notes
The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node
n
is an articulation point if, and only if, there exists a subtree rooted atn
such that there is no back edge from any successor ofn
that links to a predecessor ofn
in the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points.References
- 1
Hopcroft, J.; Tarjan, R. (1973). “Efficient algorithms for graph manipulation”. Communications of the ACM 16: 372–378. doi:10.1145/362248.362272