Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/components/attracting.py: 55%
22 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Attracting components."""
2import networkx as nx
3from networkx.utils.decorators import not_implemented_for
5__all__ = [
6 "number_attracting_components",
7 "attracting_components",
8 "is_attracting_component",
9]
12@not_implemented_for("undirected")
13@nx._dispatch
14def attracting_components(G):
15 """Generates the attracting components in `G`.
17 An attracting component in a directed graph `G` is a strongly connected
18 component with the property that a random walker on the graph will never
19 leave the component, once it enters the component.
21 The nodes in attracting components can also be thought of as recurrent
22 nodes. If a random walker enters the attractor containing the node, then
23 the node will be visited infinitely often.
25 To obtain induced subgraphs on each component use:
26 ``(G.subgraph(c).copy() for c in attracting_components(G))``
28 Parameters
29 ----------
30 G : DiGraph, MultiDiGraph
31 The graph to be analyzed.
33 Returns
34 -------
35 attractors : generator of sets
36 A generator of sets of nodes, one for each attracting component of G.
38 Raises
39 ------
40 NetworkXNotImplemented
41 If the input graph is undirected.
43 See Also
44 --------
45 number_attracting_components
46 is_attracting_component
48 """
49 scc = list(nx.strongly_connected_components(G))
50 cG = nx.condensation(G, scc)
51 for n in cG:
52 if cG.out_degree(n) == 0:
53 yield scc[n]
56@not_implemented_for("undirected")
57@nx._dispatch
58def number_attracting_components(G):
59 """Returns the number of attracting components in `G`.
61 Parameters
62 ----------
63 G : DiGraph, MultiDiGraph
64 The graph to be analyzed.
66 Returns
67 -------
68 n : int
69 The number of attracting components in G.
71 Raises
72 ------
73 NetworkXNotImplemented
74 If the input graph is undirected.
76 See Also
77 --------
78 attracting_components
79 is_attracting_component
81 """
82 return sum(1 for ac in attracting_components(G))
85@not_implemented_for("undirected")
86@nx._dispatch
87def is_attracting_component(G):
88 """Returns True if `G` consists of a single attracting component.
90 Parameters
91 ----------
92 G : DiGraph, MultiDiGraph
93 The graph to be analyzed.
95 Returns
96 -------
97 attracting : bool
98 True if `G` has a single attracting component. Otherwise, False.
100 Raises
101 ------
102 NetworkXNotImplemented
103 If the input graph is undirected.
105 See Also
106 --------
107 attracting_components
108 number_attracting_components
110 """
111 ac = list(attracting_components(G))
112 if len(ac) == 1:
113 return len(ac[0]) == len(G)
114 return False