has_bridges

has_bridges(G, root=None)[source]

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