Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/components/connected.py: 38%
42 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Connected components."""
2import networkx as nx
3from networkx.utils.decorators import not_implemented_for
5from ...utils import arbitrary_element
7__all__ = [
8 "number_connected_components",
9 "connected_components",
10 "is_connected",
11 "node_connected_component",
12]
15@not_implemented_for("directed")
16@nx._dispatch
17def connected_components(G):
18 """Generate connected components.
20 Parameters
21 ----------
22 G : NetworkX graph
23 An undirected graph
25 Returns
26 -------
27 comp : generator of sets
28 A generator of sets of nodes, one for each component of G.
30 Raises
31 ------
32 NetworkXNotImplemented
33 If G is directed.
35 Examples
36 --------
37 Generate a sorted list of connected components, largest first.
39 >>> G = nx.path_graph(4)
40 >>> nx.add_path(G, [10, 11, 12])
41 >>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
42 [4, 3]
44 If you only want the largest connected component, it's more
45 efficient to use max instead of sort.
47 >>> largest_cc = max(nx.connected_components(G), key=len)
49 To create the induced subgraph of each component use:
51 >>> S = [G.subgraph(c).copy() for c in nx.connected_components(G)]
53 See Also
54 --------
55 strongly_connected_components
56 weakly_connected_components
58 Notes
59 -----
60 For undirected graphs only.
62 """
63 seen = set()
64 for v in G:
65 if v not in seen:
66 c = _plain_bfs(G, v)
67 seen.update(c)
68 yield c
71@nx._dispatch
72def number_connected_components(G):
73 """Returns the number of connected components.
75 Parameters
76 ----------
77 G : NetworkX graph
78 An undirected graph.
80 Returns
81 -------
82 n : integer
83 Number of connected components
85 Examples
86 --------
87 >>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
88 >>> nx.number_connected_components(G)
89 3
91 See Also
92 --------
93 connected_components
94 number_weakly_connected_components
95 number_strongly_connected_components
97 Notes
98 -----
99 For undirected graphs only.
101 """
102 return sum(1 for cc in connected_components(G))
105@not_implemented_for("directed")
106@nx._dispatch
107def is_connected(G):
108 """Returns True if the graph is connected, False otherwise.
110 Parameters
111 ----------
112 G : NetworkX Graph
113 An undirected graph.
115 Returns
116 -------
117 connected : bool
118 True if the graph is connected, false otherwise.
120 Raises
121 ------
122 NetworkXNotImplemented
123 If G is directed.
125 Examples
126 --------
127 >>> G = nx.path_graph(4)
128 >>> print(nx.is_connected(G))
129 True
131 See Also
132 --------
133 is_strongly_connected
134 is_weakly_connected
135 is_semiconnected
136 is_biconnected
137 connected_components
139 Notes
140 -----
141 For undirected graphs only.
143 """
144 if len(G) == 0:
145 raise nx.NetworkXPointlessConcept(
146 "Connectivity is undefined ", "for the null graph."
147 )
148 return sum(1 for node in _plain_bfs(G, arbitrary_element(G))) == len(G)
151@not_implemented_for("directed")
152@nx._dispatch
153def node_connected_component(G, n):
154 """Returns the set of nodes in the component of graph containing node n.
156 Parameters
157 ----------
158 G : NetworkX Graph
159 An undirected graph.
161 n : node label
162 A node in G
164 Returns
165 -------
166 comp : set
167 A set of nodes in the component of G containing node n.
169 Raises
170 ------
171 NetworkXNotImplemented
172 If G is directed.
174 Examples
175 --------
176 >>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
177 >>> nx.node_connected_component(G, 0) # nodes of component that contains node 0
178 {0, 1, 2}
180 See Also
181 --------
182 connected_components
184 Notes
185 -----
186 For undirected graphs only.
188 """
189 return _plain_bfs(G, n)
192def _plain_bfs(G, source):
193 """A fast BFS node generator"""
194 adj = G._adj
195 n = len(adj)
196 seen = {source}
197 nextlevel = [source]
198 while nextlevel:
199 thislevel = nextlevel
200 nextlevel = []
201 for v in thislevel:
202 for w in adj[v]:
203 if w not in seen:
204 seen.add(w)
205 nextlevel.append(w)
206 if len(seen) == n:
207 return seen
208 return seen