networkx 2.8.2 Pypi GitHub Homepage
Other Docs
NotesParametersRaisesReturnsBackRef
is_biconnected(G)

A graph is biconnected if, and only if, it cannot be disconnected by removing only one node (and all edges incident on that node). If removing a node increases the number of disconnected components in the graph, that node is called an articulation point, or cut vertex. A biconnected graph has no articulation points.

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 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.

Parameters

G : NetworkX Graph

An undirected graph.

Raises

NetworkXNotImplemented

If the input graph is not undirected.

Returns

biconnected : bool

True if the graph is biconnected, False otherwise.

Returns True if the graph is biconnected, False otherwise.

See Also

articulation_points
biconnected_component_edges
biconnected_components
is_connected
is_semiconnected
is_strongly_connected
is_weakly_connected

Examples

>>> G = nx.path_graph(4)
... print(nx.is_biconnected(G)) False
>>> G.add_edge(0, 3)
... print(nx.is_biconnected(G)) True
See :

Back References

The following pages refer to to this document either explicitly or contain code examples using this.

networkx.algorithms.components.strongly_connected.is_strongly_connected networkx.algorithms.components.biconnected.biconnected_component_edges networkx.algorithms.components.biconnected.articulation_points networkx.algorithms.components.connected.is_connected networkx.algorithms.components.biconnected.is_biconnected networkx.algorithms.components.semiconnected.is_semiconnected networkx.algorithms.components.biconnected.biconnected_components networkx.algorithms.components.weakly_connected.is_weakly_connected

Local connectivity graph

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


GitHub : /networkx/algorithms/components/biconnected.py#13
type: <class 'function'>
Commit: