Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/components/weakly_connected.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 """Weakly connected components."""
2 import networkx as nx
3 from networkx.utils.decorators import not_implemented_for
4
5 __all__ = [
6 "number_weakly_connected_components",
7 "weakly_connected_components",
8 "is_weakly_connected",
9 ]
10
11
12 @not_implemented_for("undirected")
13 def weakly_connected_components(G):
14 """Generate weakly connected components of G.
15
16 Parameters
17 ----------
18 G : NetworkX graph
19 A directed graph
20
21 Returns
22 -------
23 comp : generator of sets
24 A generator of sets of nodes, one for each weakly connected
25 component of G.
26
27 Raises
28 ------
29 NetworkXNotImplemented
30 If G is undirected.
31
32 Examples
33 --------
34 Generate a sorted list of weakly connected components, largest first.
35
36 >>> G = nx.path_graph(4, create_using=nx.DiGraph())
37 >>> nx.add_path(G, [10, 11, 12])
38 >>> [
39 ... len(c)
40 ... for c in sorted(nx.weakly_connected_components(G), key=len, reverse=True)
41 ... ]
42 [4, 3]
43
44 If you only want the largest component, it's more efficient to
45 use max instead of sort:
46
47 >>> largest_cc = max(nx.weakly_connected_components(G), key=len)
48
49 See Also
50 --------
51 connected_components
52 strongly_connected_components
53
54 Notes
55 -----
56 For directed graphs only.
57
58 """
59 seen = set()
60 for v in G:
61 if v not in seen:
62 c = set(_plain_bfs(G, v))
63 yield c
64 seen.update(c)
65
66
67 @not_implemented_for("undirected")
68 def number_weakly_connected_components(G):
69 """Returns the number of weakly connected components in G.
70
71 Parameters
72 ----------
73 G : NetworkX graph
74 A directed graph.
75
76 Returns
77 -------
78 n : integer
79 Number of weakly connected components
80
81 Raises
82 ------
83 NetworkXNotImplemented
84 If G is undirected.
85
86 See Also
87 --------
88 weakly_connected_components
89 number_connected_components
90 number_strongly_connected_components
91
92 Notes
93 -----
94 For directed graphs only.
95
96 """
97 return sum(1 for wcc in weakly_connected_components(G))
98
99
100 @not_implemented_for("undirected")
101 def is_weakly_connected(G):
102 """Test directed graph for weak connectivity.
103
104 A directed graph is weakly connected if and only if the graph
105 is connected when the direction of the edge between nodes is ignored.
106
107 Note that if a graph is strongly connected (i.e. the graph is connected
108 even when we account for directionality), it is by definition weakly
109 connected as well.
110
111 Parameters
112 ----------
113 G : NetworkX Graph
114 A directed graph.
115
116 Returns
117 -------
118 connected : bool
119 True if the graph is weakly connected, False otherwise.
120
121 Raises
122 ------
123 NetworkXNotImplemented
124 If G is undirected.
125
126 See Also
127 --------
128 is_strongly_connected
129 is_semiconnected
130 is_connected
131 is_biconnected
132 weakly_connected_components
133
134 Notes
135 -----
136 For directed graphs only.
137
138 """
139 if len(G) == 0:
140 raise nx.NetworkXPointlessConcept(
141 """Connectivity is undefined for the null graph."""
142 )
143
144 return len(list(weakly_connected_components(G))[0]) == len(G)
145
146
147 def _plain_bfs(G, source):
148 """A fast BFS node generator
149
150 The direction of the edge between nodes is ignored.
151
152 For directed graphs only.
153
154 """
155 Gsucc = G.succ
156 Gpred = G.pred
157
158 seen = set()
159 nextlevel = {source}
160 while nextlevel:
161 thislevel = nextlevel
162 nextlevel = set()
163 for v in thislevel:
164 if v not in seen:
165 yield v
166 seen.add(v)
167 nextlevel.update(Gsucc[v])
168 nextlevel.update(Gpred[v])