Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/components/strongly_connected.py: 23%
90 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Strongly connected components."""
2import networkx as nx
3from networkx.utils.decorators import not_implemented_for
5__all__ = [
6 "number_strongly_connected_components",
7 "strongly_connected_components",
8 "is_strongly_connected",
9 "strongly_connected_components_recursive",
10 "kosaraju_strongly_connected_components",
11 "condensation",
12]
15@not_implemented_for("undirected")
16@nx._dispatch
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[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[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._dispatch
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 Returns
125 -------
126 comp : generator of sets
127 A generator of sets of nodes, one for each strongly connected
128 component of G.
130 Raises
131 ------
132 NetworkXNotImplemented
133 If G is undirected.
135 Examples
136 --------
137 Generate a sorted list of strongly connected components, largest first.
139 >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
140 >>> nx.add_cycle(G, [10, 11, 12])
141 >>> [
142 ... len(c)
143 ... for c in sorted(
144 ... nx.kosaraju_strongly_connected_components(G), key=len, reverse=True
145 ... )
146 ... ]
147 [4, 3]
149 If you only want the largest component, it's more efficient to
150 use max instead of sort.
152 >>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len)
154 See Also
155 --------
156 strongly_connected_components
158 Notes
159 -----
160 Uses Kosaraju's algorithm.
162 """
163 post = list(nx.dfs_postorder_nodes(G.reverse(copy=False), source=source))
165 seen = set()
166 while post:
167 r = post.pop()
168 if r in seen:
169 continue
170 c = nx.dfs_preorder_nodes(G, r)
171 new = {v for v in c if v not in seen}
172 seen.update(new)
173 yield new
176@not_implemented_for("undirected")
177@nx._dispatch
178def strongly_connected_components_recursive(G):
179 """Generate nodes in strongly connected components of graph.
181 .. deprecated:: 3.2
183 This function is deprecated and will be removed in a future version of
184 NetworkX. Use `strongly_connected_components` instead.
186 Recursive version of algorithm.
188 Parameters
189 ----------
190 G : NetworkX Graph
191 A directed graph.
193 Returns
194 -------
195 comp : generator of sets
196 A generator of sets of nodes, one for each strongly connected
197 component of G.
199 Raises
200 ------
201 NetworkXNotImplemented
202 If G is undirected.
204 Examples
205 --------
206 Generate a sorted list of strongly connected components, largest first.
208 >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
209 >>> nx.add_cycle(G, [10, 11, 12])
210 >>> [
211 ... len(c)
212 ... for c in sorted(
213 ... nx.strongly_connected_components_recursive(G), key=len, reverse=True
214 ... )
215 ... ]
216 [4, 3]
218 If you only want the largest component, it's more efficient to
219 use max instead of sort.
221 >>> largest = max(nx.strongly_connected_components_recursive(G), key=len)
223 To create the induced subgraph of the components use:
224 >>> S = [G.subgraph(c).copy() for c in nx.weakly_connected_components(G)]
226 See Also
227 --------
228 connected_components
230 Notes
231 -----
232 Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_.
234 References
235 ----------
236 .. [1] Depth-first search and linear graph algorithms, R. Tarjan
237 SIAM Journal of Computing 1(2):146-160, (1972).
239 .. [2] On finding the strongly connected components in a directed graph.
240 E. Nuutila and E. Soisalon-Soinen
241 Information Processing Letters 49(1): 9-14, (1994)..
243 """
244 import warnings
246 warnings.warn(
247 (
248 "\n\nstrongly_connected_components_recursive is deprecated and will be\n"
249 "removed in the future. Use strongly_connected_components instead."
250 ),
251 category=DeprecationWarning,
252 stacklevel=2,
253 )
255 yield from strongly_connected_components(G)
258@not_implemented_for("undirected")
259@nx._dispatch
260def number_strongly_connected_components(G):
261 """Returns number of strongly connected components in graph.
263 Parameters
264 ----------
265 G : NetworkX graph
266 A directed graph.
268 Returns
269 -------
270 n : integer
271 Number of strongly connected components
273 Raises
274 ------
275 NetworkXNotImplemented
276 If G is undirected.
278 Examples
279 --------
280 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0), (2, 3), (4, 5), (3, 4), (5, 6), (6, 3), (6, 7)])
281 >>> nx.number_strongly_connected_components(G)
282 3
284 See Also
285 --------
286 strongly_connected_components
287 number_connected_components
288 number_weakly_connected_components
290 Notes
291 -----
292 For directed graphs only.
293 """
294 return sum(1 for scc in strongly_connected_components(G))
297@not_implemented_for("undirected")
298@nx._dispatch
299def is_strongly_connected(G):
300 """Test directed graph for strong connectivity.
302 A directed graph is strongly connected if and only if every vertex in
303 the graph is reachable from every other vertex.
305 Parameters
306 ----------
307 G : NetworkX Graph
308 A directed graph.
310 Returns
311 -------
312 connected : bool
313 True if the graph is strongly connected, False otherwise.
315 Examples
316 --------
317 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4), (4, 2)])
318 >>> nx.is_strongly_connected(G)
319 True
320 >>> G.remove_edge(2, 3)
321 >>> nx.is_strongly_connected(G)
322 False
324 Raises
325 ------
326 NetworkXNotImplemented
327 If G is undirected.
329 See Also
330 --------
331 is_weakly_connected
332 is_semiconnected
333 is_connected
334 is_biconnected
335 strongly_connected_components
337 Notes
338 -----
339 For directed graphs only.
340 """
341 if len(G) == 0:
342 raise nx.NetworkXPointlessConcept(
343 """Connectivity is undefined for the null graph."""
344 )
346 return len(next(strongly_connected_components(G))) == len(G)
349@not_implemented_for("undirected")
350@nx._dispatch
351def condensation(G, scc=None):
352 """Returns the condensation of G.
354 The condensation of G is the graph with each of the strongly connected
355 components contracted into a single node.
357 Parameters
358 ----------
359 G : NetworkX DiGraph
360 A directed graph.
362 scc: list or generator (optional, default=None)
363 Strongly connected components. If provided, the elements in
364 `scc` must partition the nodes in `G`. If not provided, it will be
365 calculated as scc=nx.strongly_connected_components(G).
367 Returns
368 -------
369 C : NetworkX DiGraph
370 The condensation graph C of G. The node labels are integers
371 corresponding to the index of the component in the list of
372 strongly connected components of G. C has a graph attribute named
373 'mapping' with a dictionary mapping the original nodes to the
374 nodes in C to which they belong. Each node in C also has a node
375 attribute 'members' with the set of original nodes in G that
376 form the SCC that the node in C represents.
378 Raises
379 ------
380 NetworkXNotImplemented
381 If G is undirected.
383 Examples
384 --------
385 Contracting two sets of strongly connected nodes into two distinct SCC
386 using the barbell graph.
388 >>> G = nx.barbell_graph(4, 0)
389 >>> G.remove_edge(3, 4)
390 >>> G = nx.DiGraph(G)
391 >>> H = nx.condensation(G)
392 >>> H.nodes.data()
393 NodeDataView({0: {'members': {0, 1, 2, 3}}, 1: {'members': {4, 5, 6, 7}}})
394 >>> H.graph['mapping']
395 {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1}
397 Contracting a complete graph into one single SCC.
399 >>> G = nx.complete_graph(7, create_using=nx.DiGraph)
400 >>> H = nx.condensation(G)
401 >>> H.nodes
402 NodeView((0,))
403 >>> H.nodes.data()
404 NodeDataView({0: {'members': {0, 1, 2, 3, 4, 5, 6}}})
406 Notes
407 -----
408 After contracting all strongly connected components to a single node,
409 the resulting graph is a directed acyclic graph.
411 """
412 if scc is None:
413 scc = nx.strongly_connected_components(G)
414 mapping = {}
415 members = {}
416 C = nx.DiGraph()
417 # Add mapping dict as graph attribute
418 C.graph["mapping"] = mapping
419 if len(G) == 0:
420 return C
421 for i, component in enumerate(scc):
422 members[i] = component
423 mapping.update((n, i) for n in component)
424 number_of_components = i + 1
425 C.add_nodes_from(range(number_of_components))
426 C.add_edges_from(
427 (mapping[u], mapping[v]) for u, v in G.edges() if mapping[u] != mapping[v]
428 )
429 # Add a list of members (ie original nodes) to each node (ie scc) in C.
430 nx.set_node_attributes(C, members, "members")
431 return C