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"""Weakly connected components."""
3import networkx as nx
4from networkx.utils.decorators import not_implemented_for
6__all__ = [
7 "number_weakly_connected_components",
8 "weakly_connected_components",
9 "is_weakly_connected",
10]
13@not_implemented_for("undirected")
14@nx._dispatchable
15def weakly_connected_components(G):
16 """Generate weakly connected components of G.
18 Parameters
19 ----------
20 G : NetworkX graph
21 A directed graph
23 Returns
24 -------
25 comp : generator of sets
26 A generator of sets of nodes, one for each weakly connected
27 component of G.
29 Raises
30 ------
31 NetworkXNotImplemented
32 If G is undirected.
34 Examples
35 --------
36 Generate a sorted list of weakly connected components, largest first.
38 >>> G = nx.path_graph(4, create_using=nx.DiGraph())
39 >>> nx.add_path(G, [10, 11, 12])
40 >>> [
41 ... len(c)
42 ... for c in sorted(nx.weakly_connected_components(G), key=len, reverse=True)
43 ... ]
44 [4, 3]
46 If you only want the largest component, it's more efficient to
47 use max instead of sort:
49 >>> largest_cc = max(nx.weakly_connected_components(G), key=len)
51 See Also
52 --------
53 connected_components
54 strongly_connected_components
56 Notes
57 -----
58 For directed graphs only.
60 """
61 seen = set()
62 n = len(G) # must be outside the loop to avoid performance hit with graph views
63 for v in G:
64 if v not in seen:
65 c = set(_plain_bfs(G, n - len(seen), v))
66 seen.update(c)
67 yield c
70@not_implemented_for("undirected")
71@nx._dispatchable
72def number_weakly_connected_components(G):
73 """Returns the number of weakly connected components in G.
75 Parameters
76 ----------
77 G : NetworkX graph
78 A directed graph.
80 Returns
81 -------
82 n : integer
83 Number of weakly connected components
85 Raises
86 ------
87 NetworkXNotImplemented
88 If G is undirected.
90 Examples
91 --------
92 >>> G = nx.DiGraph([(0, 1), (2, 1), (3, 4)])
93 >>> nx.number_weakly_connected_components(G)
94 2
96 See Also
97 --------
98 weakly_connected_components
99 number_connected_components
100 number_strongly_connected_components
102 Notes
103 -----
104 For directed graphs only.
106 """
107 return sum(1 for wcc in weakly_connected_components(G))
110@not_implemented_for("undirected")
111@nx._dispatchable
112def is_weakly_connected(G):
113 """Test directed graph for weak connectivity.
115 A directed graph is weakly connected if and only if the graph
116 is connected when the direction of the edge between nodes is ignored.
118 Note that if a graph is strongly connected (i.e. the graph is connected
119 even when we account for directionality), it is by definition weakly
120 connected as well.
122 Parameters
123 ----------
124 G : NetworkX Graph
125 A directed graph.
127 Returns
128 -------
129 connected : bool
130 True if the graph is weakly connected, False otherwise.
132 Raises
133 ------
134 NetworkXNotImplemented
135 If G is undirected.
137 Examples
138 --------
139 >>> G = nx.DiGraph([(0, 1), (2, 1)])
140 >>> G.add_node(3)
141 >>> nx.is_weakly_connected(G) # node 3 is not connected to the graph
142 False
143 >>> G.add_edge(2, 3)
144 >>> nx.is_weakly_connected(G)
145 True
147 See Also
148 --------
149 is_strongly_connected
150 is_semiconnected
151 is_connected
152 is_biconnected
153 weakly_connected_components
155 Notes
156 -----
157 For directed graphs only.
159 """
160 if len(G) == 0:
161 raise nx.NetworkXPointlessConcept(
162 """Connectivity is undefined for the null graph."""
163 )
165 return len(next(weakly_connected_components(G))) == len(G)
168def _plain_bfs(G, n, source):
169 """A fast BFS node generator
171 The direction of the edge between nodes is ignored.
173 For directed graphs only.
175 """
176 Gsucc = G._succ
177 Gpred = G._pred
178 seen = {source}
179 nextlevel = [source]
181 yield source
182 while nextlevel:
183 thislevel = nextlevel
184 nextlevel = []
185 for v in thislevel:
186 for w in Gsucc[v]:
187 if w not in seen:
188 seen.add(w)
189 nextlevel.append(w)
190 yield w
191 for w in Gpred[v]:
192 if w not in seen:
193 seen.add(w)
194 nextlevel.append(w)
195 yield w
196 if len(seen) == n:
197 return