1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
# -*- coding: utf-8 -*-
"""
Attracting components.
"""
# Copyright (C) 2004-2011 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
import networkx as nx
__authors__ = "\n".join(['Christopher Ellison'])
__all__ = ['number_attracting_components',
'attracting_components',
'is_attracting_component',
'attracting_component_subgraphs',
]
def attracting_components(G):
"""Returns a list of attracting components in `G`.
An attracting component in a directed graph `G` is a strongly connected
component with the property that a random walker on the graph will never
leave the component, once it enters the component.
The nodes in attracting components can also be thought of as recurrent
nodes. If a random walker enters the attractor containing the node, then
the node will be visited infinitely often.
Parameters
----------
G : DiGraph, MultiDiGraph
The graph to be analyzed.
Returns
-------
attractors : list
The list of attracting components, sorted from largest attracting
component to smallest attracting component.
See Also
--------
number_attracting_components
is_attracting_component
attracting_component_subgraphs
"""
scc = nx.strongly_connected_components(G)
cG = nx.condensation(G, scc)
attractors = [scc[n] for n in cG if cG.out_degree(n) == 0]
attractors.sort(key=len,reverse=True)
return attractors
def number_attracting_components(G):
"""Returns the number of attracting components in `G`.
Parameters
----------
G : DiGraph, MultiDiGraph
The graph to be analyzed.
Returns
-------
n : int
The number of attracting components in G.
See Also
--------
attracting_components
is_attracting_component
attracting_component_subgraphs
"""
n = len(attracting_components(G))
return n
def is_attracting_component(G):
"""Returns True if `G` consists of a single attracting component.
Parameters
----------
G : DiGraph, MultiDiGraph
The graph to be analyzed.
Returns
-------
attracting : bool
True if `G` has a single attracting component. Otherwise, False.
See Also
--------
attracting_components
number_attracting_components
attracting_component_subgraphs
"""
ac = attracting_components(G)
if len(ac[0]) == len(G):
attracting = True
else:
attracting = False
return attracting
def attracting_component_subgraphs(G):
"""Returns a list of attracting component subgraphs from `G`.
Parameters
----------
G : DiGraph, MultiDiGraph
The graph to be analyzed.
Returns
-------
subgraphs : list
A list of node-induced subgraphs of the attracting components of `G`.
Notes
-----
Graph, node, and edge attributes are copied to the subgraphs.
See Also
--------
attracting_components
number_attracting_components
is_attracting_component
"""
subgraphs = [G.subgraph(ac).copy() for ac in attracting_components(G)]
return subgraphs
|
