Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.57 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: Aric Hagberg (hagberg@lanl.gov)
10
#          Christopher Ellison
11
"""Weakly connected components."""
12
import warnings as _warnings
13
import networkx as nx
14
from networkx.utils.decorators import not_implemented_for
15

    
16
__all__ = [
17
    'number_weakly_connected_components',
18
    'weakly_connected_components',
19
    'weakly_connected_component_subgraphs',
20
    'is_weakly_connected',
21
]
22

    
23

    
24
@not_implemented_for('undirected')
25
def weakly_connected_components(G):
26
    """Generate weakly connected components of G.
27

28
    Parameters
29
    ----------
30
    G : NetworkX graph
31
        A directed graph
32

33
    Returns
34
    -------
35
    comp : generator of sets
36
        A generator of sets of nodes, one for each weakly connected
37
        component of G.
38

39
    Raises
40
    ------
41
    NetworkXNotImplemented:
42
        If G is undirected.
43

44
    Examples
45
    --------
46
    Generate a sorted list of weakly connected components, largest first.
47

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

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

57
    >>> largest_cc = max(nx.weakly_connected_components(G), key=len)
58

59
    See Also
60
    --------
61
    connected_components
62
    strongly_connected_components
63

64
    Notes
65
    -----
66
    For directed graphs only.
67

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

    
76

    
77
@not_implemented_for('undirected')
78
def number_weakly_connected_components(G):
79
    """Returns the number of weakly connected components in G.
80

81
    Parameters
82
    ----------
83
    G : NetworkX graph
84
        A directed graph.
85

86
    Returns
87
    -------
88
    n : integer
89
        Number of weakly connected components
90

91
    Raises
92
    ------
93
    NetworkXNotImplemented:
94
        If G is undirected.
95

96
    See Also
97
    --------
98
    weakly_connected_components
99
    number_connected_components
100
    number_strongly_connected_components
101

102
    Notes
103
    -----
104
    For directed graphs only.
105

106
    """
107
    return sum(1 for wcc in weakly_connected_components(G))
108

    
109

    
110
@not_implemented_for('undirected')
111
def weakly_connected_component_subgraphs(G, copy=True):
112
    """DEPRECATED: Use ``(G.subgraph(c) for c in weakly_connected_components(G))``
113

114
           Or ``(G.subgraph(c).copy() for c in weakly_connected_components(G))``
115
    """
116
    msg = "weakly_connected_component_subgraphs is deprecated and will be removed in 2.2" \
117
        "use (G.subgraph(c).copy() for c in weakly_connected_components(G))"
118
    _warnings.warn(msg, DeprecationWarning)
119
    for c in weakly_connected_components(G):
120
        if copy:
121
            yield G.subgraph(c).copy()
122
        else:
123
            yield G.subgraph(c)
124

    
125

    
126
@not_implemented_for('undirected')
127
def is_weakly_connected(G):
128
    """Test directed graph for weak connectivity.
129

130
    A directed graph is weakly connected if and only if the graph
131
    is connected when the direction of the edge between nodes is ignored.
132

133
    Note that if a graph is strongly connected (i.e. the graph is connected
134
    even when we account for directionality), it is by definition weakly
135
    connected as well.
136

137
    Parameters
138
    ----------
139
    G : NetworkX Graph
140
        A directed graph.
141

142
    Returns
143
    -------
144
    connected : bool
145
        True if the graph is weakly connected, False otherwise.
146

147
    Raises
148
    ------
149
    NetworkXNotImplemented:
150
        If G is undirected.
151

152
    See Also
153
    --------
154
    is_strongly_connected
155
    is_semiconnected
156
    is_connected
157
    is_biconnected
158
    weakly_connected_components
159

160
    Notes
161
    -----
162
    For directed graphs only.
163

164
    """
165
    if len(G) == 0:
166
        raise nx.NetworkXPointlessConcept(
167
            """Connectivity is undefined for the null graph.""")
168

    
169
    return len(list(weakly_connected_components(G))[0]) == len(G)
170

    
171

    
172
def _plain_bfs(G, source):
173
    """A fast BFS node generator
174

175
    The direction of the edge between nodes is ignored.
176

177
    For directed graphs only.
178

179
    """
180
    Gsucc = G.succ
181
    Gpred = G.pred
182

    
183
    seen = set()
184
    nextlevel = {source}
185
    while nextlevel:
186
        thislevel = nextlevel
187
        nextlevel = set()
188
        for v in thislevel:
189
            if v not in seen:
190
                yield v
191
                seen.add(v)
192
                nextlevel.update(Gsucc[v])
193
                nextlevel.update(Gpred[v])