Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/components/attracting.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Attracting components."""
2 import networkx as nx
3 from networkx.utils.decorators import not_implemented_for
4
5 __all__ = [
6 "number_attracting_components",
7 "attracting_components",
8 "is_attracting_component",
9 ]
10
11
12 @not_implemented_for("undirected")
13 def attracting_components(G):
14 """Generates the attracting components in `G`.
15
16 An attracting component in a directed graph `G` is a strongly connected
17 component with the property that a random walker on the graph will never
18 leave the component, once it enters the component.
19
20 The nodes in attracting components can also be thought of as recurrent
21 nodes. If a random walker enters the attractor containing the node, then
22 the node will be visited infinitely often.
23
24 To obtain induced subgraphs on each component use:
25 ``(G.subgraph(c).copy() for c in attracting_components(G))``
26
27 Parameters
28 ----------
29 G : DiGraph, MultiDiGraph
30 The graph to be analyzed.
31
32 Returns
33 -------
34 attractors : generator of sets
35 A generator of sets of nodes, one for each attracting component of G.
36
37 Raises
38 ------
39 NetworkXNotImplemented
40 If the input graph is undirected.
41
42 See Also
43 --------
44 number_attracting_components
45 is_attracting_component
46
47 """
48 scc = list(nx.strongly_connected_components(G))
49 cG = nx.condensation(G, scc)
50 for n in cG:
51 if cG.out_degree(n) == 0:
52 yield scc[n]
53
54
55 @not_implemented_for("undirected")
56 def number_attracting_components(G):
57 """Returns the number of attracting components in `G`.
58
59 Parameters
60 ----------
61 G : DiGraph, MultiDiGraph
62 The graph to be analyzed.
63
64 Returns
65 -------
66 n : int
67 The number of attracting components in G.
68
69 Raises
70 ------
71 NetworkXNotImplemented
72 If the input graph is undirected.
73
74 See Also
75 --------
76 attracting_components
77 is_attracting_component
78
79 """
80 return sum(1 for ac in attracting_components(G))
81
82
83 @not_implemented_for("undirected")
84 def is_attracting_component(G):
85 """Returns True if `G` consists of a single attracting component.
86
87 Parameters
88 ----------
89 G : DiGraph, MultiDiGraph
90 The graph to be analyzed.
91
92 Returns
93 -------
94 attracting : bool
95 True if `G` has a single attracting component. Otherwise, False.
96
97 Raises
98 ------
99 NetworkXNotImplemented
100 If the input graph is undirected.
101
102 See Also
103 --------
104 attracting_components
105 number_attracting_components
106
107 """
108 ac = list(attracting_components(G))
109 if len(ac) == 1:
110 return len(ac[0]) == len(G)
111 return False