Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.algorithms.bridges.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
  • G (undirected graph)

  • with_span (bool) – If True, yield a 3-tuple (u, v, span)

  • weight (function, 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

e (edge) – 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.

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