Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Attracting components."""
3import networkx as nx
4from networkx.utils.decorators import not_implemented_for
6__all__ = [
7 "number_attracting_components",
8 "attracting_components",
9 "is_attracting_component",
10]
13@not_implemented_for("undirected")
14@nx._dispatchable
15def attracting_components(G):
16 """Generates the attracting components in `G`.
18 An attracting component in a directed graph `G` is a strongly connected
19 component with the property that a random walker on the graph will never
20 leave the component, once it enters the component.
22 The nodes in attracting components can also be thought of as recurrent
23 nodes. If a random walker enters the attractor containing the node, then
24 the node will be visited infinitely often.
26 To obtain induced subgraphs on each component use:
27 ``(G.subgraph(c).copy() for c in attracting_components(G))``
29 Parameters
30 ----------
31 G : DiGraph, MultiDiGraph
32 The graph to be analyzed.
34 Returns
35 -------
36 attractors : generator of sets
37 A generator of sets of nodes, one for each attracting component of G.
39 Raises
40 ------
41 NetworkXNotImplemented
42 If the input graph is undirected.
44 See Also
45 --------
46 number_attracting_components
47 is_attracting_component
49 """
50 scc = list(nx.strongly_connected_components(G))
51 cG = nx.condensation(G, scc)
52 for n in cG:
53 if cG.out_degree(n) == 0:
54 yield scc[n]
57@not_implemented_for("undirected")
58@nx._dispatchable
59def number_attracting_components(G):
60 """Returns the number of attracting components in `G`.
62 Parameters
63 ----------
64 G : DiGraph, MultiDiGraph
65 The graph to be analyzed.
67 Returns
68 -------
69 n : int
70 The number of attracting components in G.
72 Raises
73 ------
74 NetworkXNotImplemented
75 If the input graph is undirected.
77 See Also
78 --------
79 attracting_components
80 is_attracting_component
82 """
83 return sum(1 for ac in attracting_components(G))
86@not_implemented_for("undirected")
87@nx._dispatchable
88def is_attracting_component(G):
89 """Returns True if `G` consists of a single attracting component.
91 Parameters
92 ----------
93 G : DiGraph, MultiDiGraph
94 The graph to be analyzed.
96 Returns
97 -------
98 attracting : bool
99 True if `G` has a single attracting component. Otherwise, False.
101 Raises
102 ------
103 NetworkXNotImplemented
104 If the input graph is undirected.
106 See Also
107 --------
108 attracting_components
109 number_attracting_components
111 """
112 ac = list(attracting_components(G))
113 if len(ac) == 1:
114 return len(ac[0]) == len(G)
115 return False