Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.59 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Eben Kenah
10
#          Aric Hagberg (hagberg@lanl.gov)
11
#          Christopher Ellison
12
"""Connected components."""
13
import warnings as _warnings
14
import networkx as nx
15
from networkx.utils.decorators import not_implemented_for
16
from ...utils import arbitrary_element
17

    
18
__all__ = [
19
    'number_connected_components',
20
    'connected_components',
21
    'connected_component_subgraphs',
22
    'is_connected',
23
    'node_connected_component',
24
]
25

    
26

    
27
@not_implemented_for('directed')
28
def connected_components(G):
29
    """Generate connected components.
30

31
    Parameters
32
    ----------
33
    G : NetworkX graph
34
       An undirected graph
35

36
    Returns
37
    -------
38
    comp : generator of sets
39
       A generator of sets of nodes, one for each component of G.
40

41
    Raises
42
    ------
43
    NetworkXNotImplemented:
44
        If G is directed.
45

46
    Examples
47
    --------
48
    Generate a sorted list of connected components, largest first.
49

50
    >>> G = nx.path_graph(4)
51
    >>> nx.add_path(G, [10, 11, 12])
52
    >>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
53
    [4, 3]
54

55
    If you only want the largest connected component, it's more
56
    efficient to use max instead of sort.
57

58
    >>> largest_cc = max(nx.connected_components(G), key=len)
59

60
    See Also
61
    --------
62
    strongly_connected_components
63
    weakly_connected_components
64

65
    Notes
66
    -----
67
    For undirected graphs only.
68

69
    """
70
    seen = set()
71
    for v in G:
72
        if v not in seen:
73
            c = set(_plain_bfs(G, v))
74
            yield c
75
            seen.update(c)
76

    
77

    
78
@not_implemented_for('directed')
79
def connected_component_subgraphs(G, copy=True):
80
    """DEPRECATED: Use ``(G.subgraph(c) for c in connected_components(G))``
81

82
           Or ``(G.subgraph(c).copy() for c in connected_components(G))``
83
    """
84
    msg = "connected_component_subgraphs is deprecated and will be removed" \
85
          "in 2.2. Use (G.subgraph(c).copy() for c in connected_components(G))"
86
    _warnings.warn(msg, DeprecationWarning)
87
    for c in connected_components(G):
88
        if copy:
89
            yield G.subgraph(c).copy()
90
        else:
91
            yield G.subgraph(c)
92

    
93

    
94
def number_connected_components(G):
95
    """Returns the number of connected components.
96

97
    Parameters
98
    ----------
99
    G : NetworkX graph
100
       An undirected graph.
101

102
    Returns
103
    -------
104
    n : integer
105
       Number of connected components
106

107
    See Also
108
    --------
109
    connected_components
110
    number_weakly_connected_components
111
    number_strongly_connected_components
112

113
    Notes
114
    -----
115
    For undirected graphs only.
116

117
    """
118
    return sum(1 for cc in connected_components(G))
119

    
120

    
121
@not_implemented_for('directed')
122
def is_connected(G):
123
    """Returns True if the graph is connected, False otherwise.
124

125
    Parameters
126
    ----------
127
    G : NetworkX Graph
128
       An undirected graph.
129

130
    Returns
131
    -------
132
    connected : bool
133
      True if the graph is connected, false otherwise.
134

135
    Raises
136
    ------
137
    NetworkXNotImplemented:
138
        If G is directed.
139

140
    Examples
141
    --------
142
    >>> G = nx.path_graph(4)
143
    >>> print(nx.is_connected(G))
144
    True
145

146
    See Also
147
    --------
148
    is_strongly_connected
149
    is_weakly_connected
150
    is_semiconnected
151
    is_biconnected
152
    connected_components
153

154
    Notes
155
    -----
156
    For undirected graphs only.
157

158
    """
159
    if len(G) == 0:
160
        raise nx.NetworkXPointlessConcept('Connectivity is undefined ',
161
                                          'for the null graph.')
162
    return sum(1 for node in _plain_bfs(G, arbitrary_element(G))) == len(G)
163

    
164

    
165
@not_implemented_for('directed')
166
def node_connected_component(G, n):
167
    """Returns the set of nodes in the component of graph containing node n.
168

169
    Parameters
170
    ----------
171
    G : NetworkX Graph
172
       An undirected graph.
173

174
    n : node label
175
       A node in G
176

177
    Returns
178
    -------
179
    comp : set
180
       A set of nodes in the component of G containing node n.
181

182
    Raises
183
    ------
184
    NetworkXNotImplemented:
185
        If G is directed.
186

187
    See Also
188
    --------
189
    connected_components
190

191
    Notes
192
    -----
193
    For undirected graphs only.
194

195
    """
196
    return set(_plain_bfs(G, n))
197

    
198

    
199
def _plain_bfs(G, source):
200
    """A fast BFS node generator"""
201
    G_adj = G.adj
202
    seen = set()
203
    nextlevel = {source}
204
    while nextlevel:
205
        thislevel = nextlevel
206
        nextlevel = set()
207
        for v in thislevel:
208
            if v not in seen:
209
                yield v
210
                seen.add(v)
211
                nextlevel.update(G_adj[v])