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.

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