Returns a generator of lists of edges, one list for each biconnected component of the input 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. However, each edge belongs to one, and only one, biconnected component.
Notice that by convention a dyad is considered a biconnected component.
- GNetworkX Graph
An undirected graph.
- edgesgenerator of lists
Generator of lists of edges, one list for each bicomponent.
If the input graph is not undirected.
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
nis an articulation point if, and only if, there exists a subtree rooted at
nsuch that there is no back edge from any successor of
nthat links to a predecessor of
nin 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.
Hopcroft, J.; Tarjan, R. (1973). “Efficient algorithms for graph manipulation”. Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
>>> G = nx.barbell_graph(4, 2) >>> print(nx.is_biconnected(G)) False >>> bicomponents_edges = list(nx.biconnected_component_edges(G)) >>> len(bicomponents_edges) 5 >>> G.add_edge(2, 8) >>> print(nx.is_biconnected(G)) True >>> bicomponents_edges = list(nx.biconnected_component_edges(G)) >>> len(bicomponents_edges) 1