Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / bridges.py @ 5cef0f13

History | View | Annotate | Download (5.38 KB)

1
# -*- coding: utf-8 -*-
2
# bridges.py - bridge-finding algorithms
3
#
4
# Copyright 2004-2019 NetworkX developers.
5
#
6
# This file is part of NetworkX.
7
#
8
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
9
# information.
10
"""Bridge-finding algorithms."""
11
from itertools import chain
12

    
13
import networkx as nx
14
from networkx.utils import not_implemented_for
15

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

    
18

    
19
@not_implemented_for('multigraph')
20
@not_implemented_for('directed')
21
def bridges(G, root=None):
22
    """Generate all bridges in a graph.
23

24
    A *bridge* in a graph is an edge whose removal causes the number of
25
    connected components of the graph to increase.  Equivalently, a bridge is an
26
    edge that does not belong to any cycle.
27

28
    Parameters
29
    ----------
30
    G : undirected graph
31

32
    root : node (optional)
33
       A node in the graph `G`. If specified, only the bridges in the
34
       connected component containing this node will be returned.
35

36
    Yields
37
    ------
38
    e : edge
39
       An edge in the graph whose removal disconnects the graph (or
40
       causes the number of connected components to increase).
41

42
    Raises
43
    ------
44
    NodeNotFound
45
       If `root` is not in the graph `G`.
46

47
    Examples
48
    --------
49
    The barbell graph with parameter zero has a single bridge:
50

51
    >>> G = nx.barbell_graph(10, 0)
52
    >>> list(nx.bridges(G))
53
    [(9, 10)]
54

55
    Notes
56
    -----
57
    This is an implementation of the algorithm described in _[1].  An edge is a
58
    bridge if and only if it is not contained in any chain. Chains are found
59
    using the :func:`networkx.chain_decomposition` function.
60

61
    Ignoring polylogarithmic factors, the worst-case time complexity is the
62
    same as the :func:`networkx.chain_decomposition` function,
63
    $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is
64
    the number of edges.
65

66
    References
67
    ----------
68
    .. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-Finding_with_Chain_Decompositions
69
    """
70
    chains = nx.chain_decomposition(G, root=root)
71
    chain_edges = set(chain.from_iterable(chains))
72
    for u, v in G.edges():
73
        if (u, v) not in chain_edges and (v, u) not in chain_edges:
74
            yield u, v
75

    
76

    
77
@not_implemented_for('multigraph')
78
@not_implemented_for('directed')
79
def has_bridges(G, root=None):
80
    """Decide whether a graph has any bridges.
81

82
    A *bridge* in a graph is an edge whose removal causes the number of
83
    connected components of the graph to increase.
84

85
    Parameters
86
    ----------
87
    G : undirected graph
88

89
    root : node (optional)
90
       A node in the graph `G`. If specified, only the bridges in the
91
       connected component containing this node will be considered.
92

93
    Returns
94
    -------
95
    bool
96
       Whether the graph (or the connected component containing `root`)
97
       has any bridges.
98

99
    Raises
100
    ------
101
    NodeNotFound
102
       If `root` is not in the graph `G`.
103

104
    Examples
105
    --------
106
    The barbell graph with parameter zero has a single bridge::
107

108
        >>> G = nx.barbell_graph(10, 0)
109
        >>> nx.has_bridges(G)
110
        True
111

112
    On the other hand, the cycle graph has no bridges::
113

114
        >>> G = nx.cycle_graph(5)
115
        >>> nx.has_bridges(G)
116
        False
117

118
    Notes
119
    -----
120
    This implementation uses the :func:`networkx.bridges` function, so
121
    it shares its worst-case time complexity, $O(m + n)$, ignoring
122
    polylogarithmic factors, where $n$ is the number of nodes in the
123
    graph and $m$ is the number of edges.
124

125
    """
126
    try:
127
        next(bridges(G))
128
    except StopIteration:
129
        return False
130
    else:
131
        return True
132

    
133

    
134
@not_implemented_for('multigraph')
135
@not_implemented_for('directed')
136
def local_bridges(G, with_span=True, weight=None):
137
    """Iterate over local bridges of `G` optionally computing the span
138

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

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

145
    Parameters
146
    ----------
147
    G : undirected graph
148

149
    with_span : bool
150
        If True, yield a 3-tuple `(u, v, span)`
151

152
    weight : function, string or None (default: None)
153
        If function, used to compute edge weights for the span.
154
        If string, the edge data attribute used in calculating span.
155
        If None, all edges have weight 1.
156

157
    Yields
158
    ------
159
    e : edge
160
        The local bridges as an edge 2-tuple of nodes `(u, v)` or
161
        as a 3-tuple `(u, v, span)` when `with_span is True`.
162

163
    Examples
164
    --------
165
    A cycle graph has every edge a local bridge with span N-1.
166

167
       >>> G = nx.cycle_graph(9)
168
       >>> (0, 8, 8) in set(nx.local_bridges(G))
169
       True
170
    """
171
    if with_span is not True:
172
        for u, v in G.edges:
173
            if not (set(G[u]) & set(G[v])):
174
                yield u, v
175
    else:
176
        wt = nx.weighted._weight_function(G, weight)
177
        for u, v in G.edges:
178
            if not (set(G[u]) & set(G[v])):
179
                enodes = {u, v}
180

    
181
                def hide_edge(n, nbr, d):
182
                    if n not in enodes or nbr not in enodes:
183
                        return wt(n, nbr, d)
184
                    return None
185

    
186
                try:
187
                    span = nx.shortest_path_length(G, u, v, weight=hide_edge)
188
                    yield u, v, span
189
                except nx.NetworkXNoPath:
190
                    yield u, v, float('inf')