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"""Strongly connected components."""
3import networkx as nx
4from networkx.utils.decorators import not_implemented_for
6__all__ = [
7 "number_strongly_connected_components",
8 "strongly_connected_components",
9 "is_strongly_connected",
10 "kosaraju_strongly_connected_components",
11 "condensation",
12]
15@not_implemented_for("undirected")
16@nx._dispatchable
17def strongly_connected_components(G):
18 """Generate nodes in strongly connected components of graph.
20 Parameters
21 ----------
22 G : NetworkX Graph
23 A directed graph.
25 Returns
26 -------
27 comp : generator of sets
28 A generator of sets of nodes, one for each strongly connected
29 component of G.
31 Raises
32 ------
33 NetworkXNotImplemented
34 If G is undirected.
36 Examples
37 --------
38 Generate a sorted list of strongly connected components, largest first.
40 >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
41 >>> nx.add_cycle(G, [10, 11, 12])
42 >>> [
43 ... len(c)
44 ... for c in sorted(nx.strongly_connected_components(G), key=len, reverse=True)
45 ... ]
46 [4, 3]
48 If you only want the largest component, it's more efficient to
49 use max instead of sort.
51 >>> largest = max(nx.strongly_connected_components(G), key=len)
53 See Also
54 --------
55 connected_components
56 weakly_connected_components
57 kosaraju_strongly_connected_components
59 Notes
60 -----
61 Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_.
62 Nonrecursive version of algorithm.
64 References
65 ----------
66 .. [1] Depth-first search and linear graph algorithms, R. Tarjan
67 SIAM Journal of Computing 1(2):146-160, (1972).
69 .. [2] On finding the strongly connected components in a directed graph.
70 E. Nuutila and E. Soisalon-Soinen
71 Information Processing Letters 49(1): 9-14, (1994)..
73 """
74 preorder = {}
75 lowlink = {}
76 scc_found = set()
77 scc_queue = []
78 i = 0 # Preorder counter
79 neighbors = {v: iter(G._adj[v]) for v in G}
80 for source in G:
81 if source not in scc_found:
82 queue = [source]
83 while queue:
84 v = queue[-1]
85 if v not in preorder:
86 i = i + 1
87 preorder[v] = i
88 done = True
89 for w in neighbors[v]:
90 if w not in preorder:
91 queue.append(w)
92 done = False
93 break
94 if done:
95 lowlink[v] = preorder[v]
96 for w in G._adj[v]:
97 if w not in scc_found:
98 if preorder[w] > preorder[v]:
99 lowlink[v] = min([lowlink[v], lowlink[w]])
100 else:
101 lowlink[v] = min([lowlink[v], preorder[w]])
102 queue.pop()
103 if lowlink[v] == preorder[v]:
104 scc = {v}
105 while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
106 k = scc_queue.pop()
107 scc.add(k)
108 scc_found.update(scc)
109 yield scc
110 else:
111 scc_queue.append(v)
114@not_implemented_for("undirected")
115@nx._dispatchable
116def kosaraju_strongly_connected_components(G, source=None):
117 """Generate nodes in strongly connected components of graph.
119 Parameters
120 ----------
121 G : NetworkX Graph
122 A directed graph.
124 source : node, optional (default=None)
125 Specify a node from which to start the depth-first search.
126 If not provided, the algorithm will start from an arbitrary node.
128 Yields
129 ------
130 set
131 A set of all nodes in a strongly connected component of `G`.
133 Raises
134 ------
135 NetworkXNotImplemented
136 If `G` is undirected.
138 NetworkXError
139 If `source` is not a node in `G`.
141 Examples
142 --------
143 Generate a list of strongly connected components of a graph:
145 >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
146 >>> nx.add_cycle(G, [10, 11, 12])
147 >>> sorted(nx.kosaraju_strongly_connected_components(G), key=len, reverse=True)
148 [{0, 1, 2, 3}, {10, 11, 12}]
150 If you only want the largest component, it's more efficient to
151 use `max()` instead of `sorted()`.
153 >>> max(nx.kosaraju_strongly_connected_components(G), key=len)
154 {0, 1, 2, 3}
156 See Also
157 --------
158 strongly_connected_components
160 Notes
161 -----
162 Uses Kosaraju's algorithm.
163 """
164 post = list(nx.dfs_postorder_nodes(G.reverse(copy=False), source=source))
165 n = len(post)
166 seen = set()
167 while post and len(seen) < n:
168 r = post.pop()
169 if r in seen:
170 continue
171 new = {r}
172 seen.add(r)
173 stack = [r]
174 while stack and len(seen) < n:
175 v = stack.pop()
176 for w in G._adj[v]:
177 if w not in seen:
178 new.add(w)
179 seen.add(w)
180 stack.append(w)
181 yield new
184@not_implemented_for("undirected")
185@nx._dispatchable
186def number_strongly_connected_components(G):
187 """Returns number of strongly connected components in graph.
189 Parameters
190 ----------
191 G : NetworkX graph
192 A directed graph.
194 Returns
195 -------
196 n : integer
197 Number of strongly connected components
199 Raises
200 ------
201 NetworkXNotImplemented
202 If G is undirected.
204 Examples
205 --------
206 >>> G = nx.DiGraph(
207 ... [(0, 1), (1, 2), (2, 0), (2, 3), (4, 5), (3, 4), (5, 6), (6, 3), (6, 7)]
208 ... )
209 >>> nx.number_strongly_connected_components(G)
210 3
212 See Also
213 --------
214 strongly_connected_components
215 number_connected_components
216 number_weakly_connected_components
218 Notes
219 -----
220 For directed graphs only.
221 """
222 return sum(1 for scc in strongly_connected_components(G))
225@not_implemented_for("undirected")
226@nx._dispatchable
227def is_strongly_connected(G):
228 """Test directed graph for strong connectivity.
230 A directed graph is strongly connected if and only if every vertex in
231 the graph is reachable from every other vertex.
233 Parameters
234 ----------
235 G : NetworkX Graph
236 A directed graph.
238 Returns
239 -------
240 connected : bool
241 True if the graph is strongly connected, False otherwise.
243 Examples
244 --------
245 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4), (4, 2)])
246 >>> nx.is_strongly_connected(G)
247 True
248 >>> G.remove_edge(2, 3)
249 >>> nx.is_strongly_connected(G)
250 False
252 Raises
253 ------
254 NetworkXNotImplemented
255 If G is undirected.
257 See Also
258 --------
259 is_weakly_connected
260 is_semiconnected
261 is_connected
262 is_biconnected
263 strongly_connected_components
265 Notes
266 -----
267 For directed graphs only.
268 """
269 if len(G) == 0:
270 raise nx.NetworkXPointlessConcept(
271 """Connectivity is undefined for the null graph."""
272 )
274 return len(next(strongly_connected_components(G))) == len(G)
277@not_implemented_for("undirected")
278@nx._dispatchable(returns_graph=True)
279def condensation(G, scc=None):
280 """Returns the condensation of G.
282 The condensation of G is the graph with each of the strongly connected
283 components contracted into a single node.
285 Parameters
286 ----------
287 G : NetworkX DiGraph
288 A directed graph.
290 scc: list or generator (optional, default=None)
291 Strongly connected components. If provided, the elements in
292 `scc` must partition the nodes in `G`. If not provided, it will be
293 calculated as scc=nx.strongly_connected_components(G).
295 Returns
296 -------
297 C : NetworkX DiGraph
298 The condensation graph C of G. The node labels are integers
299 corresponding to the index of the component in the list of
300 strongly connected components of G. C has a graph attribute named
301 'mapping' with a dictionary mapping the original nodes to the
302 nodes in C to which they belong. Each node in C also has a node
303 attribute 'members' with the set of original nodes in G that
304 form the SCC that the node in C represents.
306 Raises
307 ------
308 NetworkXNotImplemented
309 If G is undirected.
311 Examples
312 --------
313 Contracting two sets of strongly connected nodes into two distinct SCC
314 using the barbell graph.
316 >>> G = nx.barbell_graph(4, 0)
317 >>> G.remove_edge(3, 4)
318 >>> G = nx.DiGraph(G)
319 >>> H = nx.condensation(G)
320 >>> H.nodes.data()
321 NodeDataView({0: {'members': {0, 1, 2, 3}}, 1: {'members': {4, 5, 6, 7}}})
322 >>> H.graph["mapping"]
323 {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1}
325 Contracting a complete graph into one single SCC.
327 >>> G = nx.complete_graph(7, create_using=nx.DiGraph)
328 >>> H = nx.condensation(G)
329 >>> H.nodes
330 NodeView((0,))
331 >>> H.nodes.data()
332 NodeDataView({0: {'members': {0, 1, 2, 3, 4, 5, 6}}})
334 Notes
335 -----
336 After contracting all strongly connected components to a single node,
337 the resulting graph is a directed acyclic graph.
339 """
340 if scc is None:
341 scc = nx.strongly_connected_components(G)
342 mapping = {}
343 members = {}
344 C = nx.DiGraph()
345 # Add mapping dict as graph attribute
346 C.graph["mapping"] = mapping
347 if len(G) == 0:
348 return C
349 for i, component in enumerate(scc):
350 members[i] = component
351 mapping.update((n, i) for n in component)
352 number_of_components = i + 1
353 C.add_nodes_from(range(number_of_components))
354 C.add_edges_from(
355 (mapping[u], mapping[v]) for u, v in G.edges() if mapping[u] != mapping[v]
356 )
357 # Add a list of members (ie original nodes) to each node (ie scc) in C.
358 nx.set_node_attributes(C, members, "members")
359 return C