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 The connected components of an undirected graph partition the graph into
22 disjoint sets of nodes. Each of these sets induces a subgraph of graph
23 `G` that is connected and not part of any larger connected subgraph.
25 A graph is connected (:func:`is_connected`) if, for every pair of distinct
26 nodes, there is a path between them. If there is a pair of nodes for
27 which such path does not exist, the graph is not connected (also referred
28 to as "disconnected").
30 A graph consisting of a single node and no edges is connected.
31 Connectivity is undefined for the null graph (graph with no nodes).
33 Parameters
34 ----------
35 G : NetworkX graph
36 An undirected graph
38 Yields
39 ------
40 comp : set
41 A set of nodes in one connected component of the graph.
43 Raises
44 ------
45 NetworkXNotImplemented
46 If G is directed.
48 Examples
49 --------
50 Generate a sorted list of connected components, largest first.
52 >>> G = nx.path_graph(4)
53 >>> nx.add_path(G, [10, 11, 12])
54 >>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
55 [4, 3]
57 If you only want the largest connected component, it's more
58 efficient to use max instead of sort.
60 >>> largest_cc = max(nx.connected_components(G), key=len)
62 To create the induced subgraph of each component use:
64 >>> S = [G.subgraph(c).copy() for c in nx.connected_components(G)]
66 See Also
67 --------
68 number_connected_components
69 is_connected
70 number_weakly_connected_components
71 number_strongly_connected_components
73 Notes
74 -----
75 This function is for undirected graphs only. For directed graphs, use
76 :func:`strongly_connected_components` or
77 :func:`weakly_connected_components`.
79 The algorithm is based on a Breadth-First Search (BFS) traversal and its
80 time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
81 number of edges in the graph.
83 """
84 seen = set()
85 n = len(G) # must be outside the loop to avoid performance hit with graph views
86 for v in G:
87 if v not in seen:
88 c = _plain_bfs(G, n - len(seen), v)
89 seen.update(c)
90 yield c
93@not_implemented_for("directed")
94@nx._dispatchable
95def number_connected_components(G):
96 """Returns the number of connected components.
98 The connected components of an undirected graph partition the graph into
99 disjoint sets of nodes. Each of these sets induces a subgraph of graph
100 `G` that is connected and not part of any larger connected subgraph.
102 A graph is connected (:func:`is_connected`) if, for every pair of distinct
103 nodes, there is a path between them. If there is a pair of nodes for
104 which such path does not exist, the graph is not connected (also referred
105 to as "disconnected").
107 A graph consisting of a single node and no edges is connected.
108 Connectivity is undefined for the null graph (graph with no nodes).
110 Parameters
111 ----------
112 G : NetworkX graph
113 An undirected graph.
115 Returns
116 -------
117 n : integer
118 Number of connected components
120 Raises
121 ------
122 NetworkXNotImplemented
123 If G is directed.
125 Examples
126 --------
127 >>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
128 >>> nx.number_connected_components(G)
129 3
131 See Also
132 --------
133 connected_components
134 is_connected
135 number_weakly_connected_components
136 number_strongly_connected_components
138 Notes
139 -----
140 This function is for undirected graphs only. For directed graphs, use
141 :func:`number_strongly_connected_components` or
142 :func:`number_weakly_connected_components`.
144 The algorithm is based on a Breadth-First Search (BFS) traversal and its
145 time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
146 number of edges in the graph.
148 """
149 return sum(1 for _ in connected_components(G))
152@not_implemented_for("directed")
153@nx._dispatchable
154def is_connected(G):
155 """Returns True if the graph is connected, False otherwise.
157 A graph is connected if, for every pair of distinct nodes, there is a
158 path between them. If there is a pair of nodes for which such path does
159 not exist, the graph is not connected (also referred to as "disconnected").
161 A graph consisting of a single node and no edges is connected.
162 Connectivity is undefined for the null graph (graph with no nodes).
164 Parameters
165 ----------
166 G : NetworkX Graph
167 An undirected graph.
169 Returns
170 -------
171 connected : bool
172 True if the graph is connected, False otherwise.
174 Raises
175 ------
176 NetworkXNotImplemented
177 If G is directed.
179 Examples
180 --------
181 >>> G = nx.path_graph(4)
182 >>> print(nx.is_connected(G))
183 True
185 See Also
186 --------
187 is_strongly_connected
188 is_weakly_connected
189 is_semiconnected
190 is_biconnected
191 connected_components
193 Notes
194 -----
195 This function is for undirected graphs only. For directed graphs, use
196 :func:`is_strongly_connected` or :func:`is_weakly_connected`.
198 The algorithm is based on a Breadth-First Search (BFS) traversal and its
199 time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
200 number of edges in the graph.
202 """
203 n = len(G)
204 if n == 0:
205 raise nx.NetworkXPointlessConcept(
206 "Connectivity is undefined for the null graph."
207 )
208 return len(next(connected_components(G))) == n
211@not_implemented_for("directed")
212@nx._dispatchable
213def node_connected_component(G, n):
214 """Returns the set of nodes in the component of graph containing node n.
216 A connected component is a set of nodes that induces a subgraph of graph
217 `G` that is connected and not part of any larger connected subgraph.
219 A graph is connected (:func:`is_connected`) if, for every pair of distinct
220 nodes, there is a path between them. If there is a pair of nodes for
221 which such path does not exist, the graph is not connected (also referred
222 to as "disconnected").
224 A graph consisting of a single node and no edges is connected.
225 Connectivity is undefined for the null graph (graph with no nodes).
227 Parameters
228 ----------
229 G : NetworkX Graph
230 An undirected graph.
232 n : node label
233 A node in G
235 Returns
236 -------
237 comp : set
238 A set of nodes in the component of G containing node n.
240 Raises
241 ------
242 NetworkXNotImplemented
243 If G is directed.
245 Examples
246 --------
247 >>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
248 >>> nx.node_connected_component(G, 0) # nodes of component that contains node 0
249 {0, 1, 2}
251 See Also
252 --------
253 connected_components
255 Notes
256 -----
257 This function is for undirected graphs only.
259 The algorithm is based on a Breadth-First Search (BFS) traversal and its
260 time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
261 number of edges in the graph.
263 """
264 return _plain_bfs(G, len(G), n)
267def _plain_bfs(G, n, source):
268 """A fast BFS node generator"""
269 adj = G._adj
270 seen = {source}
271 nextlevel = [source]
272 while nextlevel:
273 thislevel = nextlevel
274 nextlevel = []
275 for v in thislevel:
276 for w in adj[v]:
277 if w not in seen:
278 seen.add(w)
279 nextlevel.append(w)
280 if len(seen) == n:
281 return seen
282 return seen