Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.6 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
#          Ben Edwards (bedwards@cs.unm.edu)
13
"""Strongly connected components."""
14
import warnings as _warnings
15
import networkx as nx
16
from networkx.utils.decorators import not_implemented_for
17

    
18
__all__ = ['number_strongly_connected_components',
19
           'strongly_connected_components',
20
           'strongly_connected_component_subgraphs',
21
           'is_strongly_connected',
22
           'strongly_connected_components_recursive',
23
           'kosaraju_strongly_connected_components',
24
           'condensation']
25

    
26

    
27
@not_implemented_for('undirected')
28
def strongly_connected_components(G):
29
    """Generate nodes in strongly connected components of graph.
30

31
    Parameters
32
    ----------
33
    G : NetworkX Graph
34
        A directed graph.
35

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

42
    Raises
43
    ------
44
    NetworkXNotImplemented :
45
        If G is undirected.
46

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

51
    >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
52
    >>> nx.add_cycle(G, [10, 11, 12])
53
    >>> [len(c) for c in sorted(nx.strongly_connected_components(G),
54
    ...                         key=len, reverse=True)]
55
    [4, 3]
56

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

60
    >>> largest = max(nx.strongly_connected_components(G), key=len)
61

62
    See Also
63
    --------
64
    connected_components
65
    weakly_connected_components
66
    kosaraju_strongly_connected_components
67

68
    Notes
69
    -----
70
    Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_.
71
    Nonrecursive version of algorithm.
72

73
    References
74
    ----------
75
    .. [1] Depth-first search and linear graph algorithms, R. Tarjan
76
       SIAM Journal of Computing 1(2):146-160, (1972).
77

78
    .. [2] On finding the strongly connected components in a directed graph.
79
       E. Nuutila and E. Soisalon-Soinen
80
       Information Processing Letters 49(1): 9-14, (1994)..
81

82
    """
83
    nbrs = {}
84
    preorder = {}
85
    lowlink = {}
86
    scc_found = {}
87
    scc_queue = []
88
    i = 0     # Preorder counter
89
    for source in G:
90
        if source not in scc_found:
91
            queue = [source]
92
            while queue:
93
                v = queue[-1]
94
                if v not in preorder:
95
                    i = i + 1
96
                    preorder[v] = i
97
                done = 1
98
                if v not in nbrs:
99
                    nbrs[v] = iter(G[v])
100
                v_nbrs = nbrs[v]
101
                for w in v_nbrs:
102
                    if w not in preorder:
103
                        queue.append(w)
104
                        done = 0
105
                        break
106
                if done == 1:
107
                    lowlink[v] = preorder[v]
108
                    for w in G[v]:
109
                        if w not in scc_found:
110
                            if preorder[w] > preorder[v]:
111
                                lowlink[v] = min([lowlink[v], lowlink[w]])
112
                            else:
113
                                lowlink[v] = min([lowlink[v], preorder[w]])
114
                    queue.pop()
115
                    if lowlink[v] == preorder[v]:
116
                        scc_found[v] = True
117
                        scc = {v}
118
                        while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
119
                            k = scc_queue.pop()
120
                            scc_found[k] = True
121
                            scc.add(k)
122
                        yield scc
123
                    else:
124
                        scc_queue.append(v)
125

    
126

    
127
@not_implemented_for('undirected')
128
def kosaraju_strongly_connected_components(G, source=None):
129
    """Generate nodes in strongly connected components of graph.
130

131
    Parameters
132
    ----------
133
    G : NetworkX Graph
134
        A directed graph.
135

136
    Returns
137
    -------
138
    comp : generator of sets
139
        A genrator of sets of nodes, one for each strongly connected
140
        component of G.
141

142
    Raises
143
    ------
144
    NetworkXNotImplemented:
145
        If G is undirected.
146

147
    Examples
148
    --------
149
    Generate a sorted list of strongly connected components, largest first.
150

151
    >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
152
    >>> nx.add_cycle(G, [10, 11, 12])
153
    >>> [len(c) for c in sorted(nx.kosaraju_strongly_connected_components(G),
154
    ...                         key=len, reverse=True)]
155
    [4, 3]
156

157
    If you only want the largest component, it's more efficient to
158
    use max instead of sort.
159

160
    >>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len)
161

162
    See Also
163
    --------
164
    strongly_connected_components
165

166
    Notes
167
    -----
168
    Uses Kosaraju's algorithm.
169

170
    """
171
    with nx.utils.reversed(G):
172
        post = list(nx.dfs_postorder_nodes(G, source=source))
173

    
174
    seen = set()
175
    while post:
176
        r = post.pop()
177
        if r in seen:
178
            continue
179
        c = nx.dfs_preorder_nodes(G, r)
180
        new = {v for v in c if v not in seen}
181
        yield new
182
        seen.update(new)
183

    
184

    
185
@not_implemented_for('undirected')
186
def strongly_connected_components_recursive(G):
187
    """Generate nodes in strongly connected components of graph.
188

189
    Recursive version of algorithm.
190

191
    Parameters
192
    ----------
193
    G : NetworkX Graph
194
        A directed graph.
195

196
    Returns
197
    -------
198
    comp : generator of sets
199
        A generator of sets of nodes, one for each strongly connected
200
        component of G.
201

202
    Raises
203
    ------
204
    NetworkXNotImplemented :
205
        If G is undirected.
206

207
    Examples
208
    --------
209
    Generate a sorted list of strongly connected components, largest first.
210

211
    >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
212
    >>> nx.add_cycle(G, [10, 11, 12])
213
    >>> [len(c) for c in sorted(nx.strongly_connected_components_recursive(G),
214
    ...                         key=len, reverse=True)]
215
    [4, 3]
216

217
    If you only want the largest component, it's more efficient to
218
    use max instead of sort.
219

220
    >>> largest = max(nx.strongly_connected_components_recursive(G), key=len)
221

222
    See Also
223
    --------
224
    connected_components
225

226
    Notes
227
    -----
228
    Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_.
229

230
    References
231
    ----------
232
    .. [1] Depth-first search and linear graph algorithms, R. Tarjan
233
       SIAM Journal of Computing 1(2):146-160, (1972).
234

235
    .. [2] On finding the strongly connected components in a directed graph.
236
       E. Nuutila and E. Soisalon-Soinen
237
       Information Processing Letters 49(1): 9-14, (1994)..
238

239
    """
240
    def visit(v, cnt):
241
        root[v] = cnt
242
        visited[v] = cnt
243
        cnt += 1
244
        stack.append(v)
245
        for w in G[v]:
246
            if w not in visited:
247
                for c in visit(w, cnt):
248
                    yield c
249
            if w not in component:
250
                root[v] = min(root[v], root[w])
251
        if root[v] == visited[v]:
252
            component[v] = root[v]
253
            tmpc = {v}  # hold nodes in this component
254
            while stack[-1] != v:
255
                w = stack.pop()
256
                component[w] = root[v]
257
                tmpc.add(w)
258
            stack.remove(v)
259
            yield tmpc
260

    
261
    visited = {}
262
    component = {}
263
    root = {}
264
    cnt = 0
265
    stack = []
266
    for source in G:
267
        if source not in visited:
268
            for c in visit(source, cnt):
269
                yield c
270

    
271

    
272
@not_implemented_for('undirected')
273
def strongly_connected_component_subgraphs(G, copy=True):
274
    """DEPRECATED: Use ``(G.subgraph(c) for c in strongly_connected_components(G))``
275

276
         Or ``(G.subgraph(c).copy() for c in strongly_connected_components(G))``
277
    """
278
    msg = "strongly_connected_component_subgraphs is deprecated and will be removed in 2.2" \
279
        "use (G.subgraph(c).copy() for c in strongly_connected_components(G))"
280
    _warnings.warn(msg, DeprecationWarning)
281
    for c in strongly_connected_components(G):
282
        if copy:
283
            yield G.subgraph(c).copy()
284
        else:
285
            yield G.subgraph(c)
286

    
287

    
288
@not_implemented_for('undirected')
289
def number_strongly_connected_components(G):
290
    """Returns number of strongly connected components in graph.
291

292
    Parameters
293
    ----------
294
    G : NetworkX graph
295
       A directed graph.
296

297
    Returns
298
    -------
299
    n : integer
300
       Number of strongly connected components
301

302
    Raises
303
    ------
304
    NetworkXNotImplemented:
305
        If G is undirected.
306

307
    See Also
308
    --------
309
    strongly_connected_components
310
    number_connected_components
311
    number_weakly_connected_components
312

313
    Notes
314
    -----
315
    For directed graphs only.
316
    """
317
    return sum(1 for scc in strongly_connected_components(G))
318

    
319

    
320
@not_implemented_for('undirected')
321
def is_strongly_connected(G):
322
    """Test directed graph for strong connectivity.
323

324
    A directed graph is strongly connected if and only if every vertex in
325
    the graph is reachable from every other vertex.
326

327
    Parameters
328
    ----------
329
    G : NetworkX Graph
330
       A directed graph.
331

332
    Returns
333
    -------
334
    connected : bool
335
      True if the graph is strongly connected, False otherwise.
336

337
    Raises
338
    ------
339
    NetworkXNotImplemented:
340
        If G is undirected.
341

342
    See Also
343
    --------
344
    is_weakly_connected
345
    is_semiconnected
346
    is_connected
347
    is_biconnected
348
    strongly_connected_components
349

350
    Notes
351
    -----
352
    For directed graphs only.
353
    """
354
    if len(G) == 0:
355
        raise nx.NetworkXPointlessConcept(
356
            """Connectivity is undefined for the null graph.""")
357

    
358
    return len(list(strongly_connected_components(G))[0]) == len(G)
359

    
360

    
361
@not_implemented_for('undirected')
362
def condensation(G, scc=None):
363
    """Returns the condensation of G.
364

365
    The condensation of G is the graph with each of the strongly connected
366
    components contracted into a single node.
367

368
    Parameters
369
    ----------
370
    G : NetworkX DiGraph
371
       A directed graph.
372

373
    scc:  list or generator (optional, default=None)
374
       Strongly connected components. If provided, the elements in
375
       `scc` must partition the nodes in `G`. If not provided, it will be
376
       calculated as scc=nx.strongly_connected_components(G).
377

378
    Returns
379
    -------
380
    C : NetworkX DiGraph
381
       The condensation graph C of G.  The node labels are integers
382
       corresponding to the index of the component in the list of
383
       strongly connected components of G.  C has a graph attribute named
384
       'mapping' with a dictionary mapping the original nodes to the
385
       nodes in C to which they belong.  Each node in C also has a node
386
       attribute 'members' with the set of original nodes in G that
387
       form the SCC that the node in C represents.
388

389
    Raises
390
    ------
391
    NetworkXNotImplemented:
392
        If G is undirected.
393

394
    Notes
395
    -----
396
    After contracting all strongly connected components to a single node,
397
    the resulting graph is a directed acyclic graph.
398

399
    """
400
    if scc is None:
401
        scc = nx.strongly_connected_components(G)
402
    mapping = {}
403
    members = {}
404
    C = nx.DiGraph()
405
    # Add mapping dict as graph attribute
406
    C.graph['mapping'] = mapping
407
    if len(G) == 0:
408
        return C
409
    for i, component in enumerate(scc):
410
        members[i] = component
411
        mapping.update((n, i) for n in component)
412
    number_of_components = i + 1
413
    C.add_nodes_from(range(number_of_components))
414
    C.add_edges_from((mapping[u], mapping[v]) for u, v in G.edges()
415
                     if mapping[u] != mapping[v])
416
    # Add a list of members (ie original nodes) to each node (ie scc) in C.
417
    nx.set_node_attributes(C, members, 'members')
418
    return C