Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.39 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: Christopher Ellison
10
"""Attracting components."""
11
import warnings as _warnings
12
import networkx as nx
13
from networkx.utils.decorators import not_implemented_for
14

    
15
__all__ = ['number_attracting_components',
16
           'attracting_components',
17
           'is_attracting_component',
18
           'attracting_component_subgraphs',
19
           ]
20

    
21

    
22
@not_implemented_for('undirected')
23
def attracting_components(G):
24
    """Generates the attracting components in `G`.
25

26
    An attracting component in a directed graph `G` is a strongly connected
27
    component with the property that a random walker on the graph will never
28
    leave the component, once it enters the component.
29

30
    The nodes in attracting components can also be thought of as recurrent
31
    nodes.  If a random walker enters the attractor containing the node, then
32
    the node will be visited infinitely often.
33

34
    Parameters
35
    ----------
36
    G : DiGraph, MultiDiGraph
37
        The graph to be analyzed.
38

39
    Returns
40
    -------
41
    attractors : generator of sets
42
        A generator of sets of nodes, one for each attracting component of G.
43

44
    Raises
45
    ------
46
    NetworkXNotImplemented :
47
        If the input graph is undirected.
48

49
    See Also
50
    --------
51
    number_attracting_components
52
    is_attracting_component
53

54
    """
55
    scc = list(nx.strongly_connected_components(G))
56
    cG = nx.condensation(G, scc)
57
    for n in cG:
58
        if cG.out_degree(n) == 0:
59
            yield scc[n]
60

    
61

    
62
@not_implemented_for('undirected')
63
def number_attracting_components(G):
64
    """Returns the number of attracting components in `G`.
65

66
    Parameters
67
    ----------
68
    G : DiGraph, MultiDiGraph
69
        The graph to be analyzed.
70

71
    Returns
72
    -------
73
    n : int
74
        The number of attracting components in G.
75

76
    Raises
77
    ------
78
    NetworkXNotImplemented :
79
        If the input graph is undirected.
80

81
    See Also
82
    --------
83
    attracting_components
84
    is_attracting_component
85

86
    """
87
    return sum(1 for ac in attracting_components(G))
88

    
89

    
90
@not_implemented_for('undirected')
91
def is_attracting_component(G):
92
    """Returns True if `G` consists of a single attracting component.
93

94
    Parameters
95
    ----------
96
    G : DiGraph, MultiDiGraph
97
        The graph to be analyzed.
98

99
    Returns
100
    -------
101
    attracting : bool
102
        True if `G` has a single attracting component. Otherwise, False.
103

104
    Raises
105
    ------
106
    NetworkXNotImplemented :
107
        If the input graph is undirected.
108

109
    See Also
110
    --------
111
    attracting_components
112
    number_attracting_components
113

114
    """
115
    ac = list(attracting_components(G))
116
    if len(ac) == 1:
117
        return len(ac[0]) == len(G)
118
    return False
119

    
120

    
121
@not_implemented_for('undirected')
122
def attracting_component_subgraphs(G, copy=True):
123
    """DEPRECATED: Use ``(G.subgraph(c) for c in attracting_components(G))``
124

125
           Or ``(G.subgraph(c).copy() for c in attracting_components(G))``
126
    """
127
    msg = "attracting_component_subgraphs is deprecated and will be removed" \
128
        "in 2.2. Use (G.subgraph(c).copy() for c in attracting_components(G))"
129
    _warnings.warn(msg, DeprecationWarning)
130
    for c in attracting_components(G):
131
        if copy:
132
            yield G.subgraph(c).copy()
133
        else:
134
            yield G.subgraph(c)