diff env/lib/python3.9/site-packages/networkx/algorithms/bridges.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/bridges.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,181 @@
+"""Bridge-finding algorithms."""
+from itertools import chain
+
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+__all__ = ["bridges", "has_bridges", "local_bridges"]
+
+
+@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 if and only if 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
+
+
+@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")