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"""Connected components."""
3import networkx as nx
4from networkx.utils.decorators import not_implemented_for
6from ...utils import arbitrary_element
8__all__ = [
9 "number_connected_components",
10 "connected_components",
11 "is_connected",
12 "node_connected_component",
13]
16@not_implemented_for("directed")
17@nx._dispatchable
18def connected_components(G):
19 """Generate connected components.
21 Parameters
22 ----------
23 G : NetworkX graph
24 An undirected graph
26 Returns
27 -------
28 comp : generator of sets
29 A generator of sets of nodes, one for each component of G.
31 Raises
32 ------
33 NetworkXNotImplemented
34 If G is directed.
36 Examples
37 --------
38 Generate a sorted list of connected components, largest first.
40 >>> G = nx.path_graph(4)
41 >>> nx.add_path(G, [10, 11, 12])
42 >>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
43 [4, 3]
45 If you only want the largest connected component, it's more
46 efficient to use max instead of sort.
48 >>> largest_cc = max(nx.connected_components(G), key=len)
50 To create the induced subgraph of each component use:
52 >>> S = [G.subgraph(c).copy() for c in nx.connected_components(G)]
54 See Also
55 --------
56 strongly_connected_components
57 weakly_connected_components
59 Notes
60 -----
61 For undirected graphs only.
63 """
64 seen = set()
65 n = len(G)
66 for v in G:
67 if v not in seen:
68 c = _plain_bfs(G, n - len(seen), v)
69 seen.update(c)
70 yield c
73@not_implemented_for("directed")
74@nx._dispatchable
75def number_connected_components(G):
76 """Returns the number of connected components.
78 Parameters
79 ----------
80 G : NetworkX graph
81 An undirected graph.
83 Returns
84 -------
85 n : integer
86 Number of connected components
88 Raises
89 ------
90 NetworkXNotImplemented
91 If G is directed.
93 Examples
94 --------
95 >>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
96 >>> nx.number_connected_components(G)
97 3
99 See Also
100 --------
101 connected_components
102 number_weakly_connected_components
103 number_strongly_connected_components
105 Notes
106 -----
107 For undirected graphs only.
109 """
110 return sum(1 for _ in connected_components(G))
113@not_implemented_for("directed")
114@nx._dispatchable
115def is_connected(G):
116 """Returns True if the graph is connected, False otherwise.
118 Parameters
119 ----------
120 G : NetworkX Graph
121 An undirected graph.
123 Returns
124 -------
125 connected : bool
126 True if the graph is connected, false otherwise.
128 Raises
129 ------
130 NetworkXNotImplemented
131 If G is directed.
133 Examples
134 --------
135 >>> G = nx.path_graph(4)
136 >>> print(nx.is_connected(G))
137 True
139 See Also
140 --------
141 is_strongly_connected
142 is_weakly_connected
143 is_semiconnected
144 is_biconnected
145 connected_components
147 Notes
148 -----
149 For undirected graphs only.
151 """
152 n = len(G)
153 if n == 0:
154 raise nx.NetworkXPointlessConcept(
155 "Connectivity is undefined for the null graph."
156 )
157 return len(_plain_bfs(G, n, arbitrary_element(G))) == n
160@not_implemented_for("directed")
161@nx._dispatchable
162def node_connected_component(G, n):
163 """Returns the set of nodes in the component of graph containing node n.
165 Parameters
166 ----------
167 G : NetworkX Graph
168 An undirected graph.
170 n : node label
171 A node in G
173 Returns
174 -------
175 comp : set
176 A set of nodes in the component of G containing node n.
178 Raises
179 ------
180 NetworkXNotImplemented
181 If G is directed.
183 Examples
184 --------
185 >>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
186 >>> nx.node_connected_component(G, 0) # nodes of component that contains node 0
187 {0, 1, 2}
189 See Also
190 --------
191 connected_components
193 Notes
194 -----
195 For undirected graphs only.
197 """
198 return _plain_bfs(G, len(G), n)
201def _plain_bfs(G, n, source):
202 """A fast BFS node generator"""
203 adj = G._adj
204 seen = {source}
205 nextlevel = [source]
206 while nextlevel:
207 thislevel = nextlevel
208 nextlevel = []
209 for v in thislevel:
210 for w in adj[v]:
211 if w not in seen:
212 seen.add(w)
213 nextlevel.append(w)
214 if len(seen) == n:
215 return seen
216 return seen