Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.algorithms.bridges

# -*- coding: utf-8 -*-
# bridges.py - bridge-finding algorithms
#
# Copyright 2004-2017 NetworkX developers.
#
# This file is part of NetworkX.
#
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
# information.
"""Bridge-finding algorithms."""
from itertools import chain

import networkx as nx
from networkx.utils import not_implemented_for

__all__ = ['bridges', 'has_bridges', 'local_bridges']


[docs]@not_implemented_for('multigraph') @not_implemented_for('directed') def bridges(G, root=None): """Generate all bridges in a graph. A *bridge* in a graph is an edge whose removal causes the number of connected components of the graph to increase. Equivalently, a bridge is an edge that does not belong to any cycle. Parameters ---------- G : undirected graph root : node (optional) A node in the graph `G`. If specified, only the bridges in the connected component containing this node will be returned. Yields ------ e : edge An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase). Raises ------ NodeNotFound If `root` is not in the graph `G`. Examples -------- The barbell graph with parameter zero has a single bridge: >>> G = nx.barbell_graph(10, 0) >>> list(nx.bridges(G)) [(9, 10)] Notes ----- This is an implementation of the algorithm described in _[1]. An edge is a bridge iff it is not contained in any chain. Chains are found using the :func:`networkx.chain_decomposition` function. Ignoring polylogarithmic factors, the worst-case time complexity is the same as the :func:`networkx.chain_decomposition` function, $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is the number of edges. References ---------- .. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-Finding_with_Chain_Decompositions """ chains = nx.chain_decomposition(G, root=root) chain_edges = set(chain.from_iterable(chains)) for u, v in G.edges(): if (u, v) not in chain_edges and (v, u) not in chain_edges: yield u, v
[docs]@not_implemented_for('multigraph') @not_implemented_for('directed') def 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 ---------- G : undirected graph root : node (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`. 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 Notes ----- This implementation uses the :func:`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. """ try: next(bridges(G)) except StopIteration: return False else: return True
@not_implemented_for('multigraph') @not_implemented_for('directed') def local_bridges(G, with_span=True, weight=None): """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 """ if with_span is not True: for u, v in G.edges: if not (set(G[u]) & set(G[v])): yield u, v else: wt = nx.weighted._weight_function(G, weight) for u, v in G.edges: if not (set(G[u]) & set(G[v])): enodes = {u, v} def hide_edge(n, nbr, d): if n not in enodes or nbr not in enodes: return wt(n, nbr, d) return None try: span = nx.shortest_path_length(G, u, v, weight=hide_edge) yield u, v, span except nx.NetworkXNoPath: yield u, v, float('inf')