local_bridges(G, with_span=True, weight=None)[source]

Iterate over local bridges of G optionally computing the span

A local bridge is an edge whose endpoints have no common neighbors. That is, the edge is not part of a triangle in the graph.

The span of a local bridge is the shortest path length between the endpoints if the local bridge is removed.

Gundirected graph

If True, yield a 3-tuple (u, v, span)

weightfunction, string or None (default: None)

If function, used to compute edge weights for the span. If string, the edge data attribute used in calculating span. If None, all edges have weight 1.


The local bridges as an edge 2-tuple of nodes (u, v) or as a 3-tuple (u, v, span) when with_span is True.


A cycle graph has every edge a local bridge with span N-1.

>>> G = nx.cycle_graph(9)
>>> (0, 8, 8) in set(nx.local_bridges(G))