biconnected_components(G)
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.
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 at n such that there is no back edge from any successor of n that links to a predecessor of n 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.
An undirected graph.
If the input graph is not undirected.
Generator of sets of nodes, one set for each biconnected component.
Returns a generator of sets of nodes, one set for each biconnected component of the graph
bridge_components
similar to this function, but is defined using 2-edge-connectivity instead of 2-node-connectivity.
k_components
this function is a special case where k=2
>>> 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))
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.connectivity.kcomponents.k_components
networkx.algorithms.components.biconnected.biconnected_component_edges
networkx.algorithms.components.biconnected.articulation_points
networkx.algorithms.components.biconnected.is_biconnected
networkx.algorithms.connectivity.edge_kcomponents.bridge_components
networkx.algorithms.components.biconnected.biconnected_components
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them