has_bridges

has_bridges(G, root=None)

Decide whether a graph has any bridges.

A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase.

Parameters:

Gundirected graph

rootnode (optional)

A node in the graph G. If specified, only the bridges in the connected component containing this node will be considered.

Returns:

bool

Whether the graph (or the connected component containing root) has any bridges.

Raises:

NodeNotFound

If root is not in the graph G.

NetworkXNotImplemented

If G is a directed graph.

Notes

This implementation uses the networkx.bridges() function, so it shares its worst-case time complexity, \(O(m + n)\), ignoring polylogarithmic factors, where \(n\) is the number of nodes in the graph and \(m\) is the number of edges.

Examples

The barbell graph with parameter zero has a single bridge:

>>> G = nx.barbell_graph(10, 0)
>>> nx.has_bridges(G)
True

On the other hand, the cycle graph has no bridges:

>>> G = nx.cycle_graph(5)
>>> nx.has_bridges(G)
False