local_bridges#

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.

Parameters:
Gundirected graph
with_spanbool

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.

Yields:
eedge

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.

Raises:
NetworkXNotImplemented

If G is a directed graph or multigraph.

Examples

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))
True