|
|
"""Strongly connected components.""" |
|
|
|
|
|
import networkx as nx |
|
|
from networkx.utils.decorators import not_implemented_for |
|
|
|
|
|
__all__ = [ |
|
|
"number_strongly_connected_components", |
|
|
"strongly_connected_components", |
|
|
"is_strongly_connected", |
|
|
"kosaraju_strongly_connected_components", |
|
|
"condensation", |
|
|
] |
|
|
|
|
|
|
|
|
@not_implemented_for("undirected") |
|
|
@nx._dispatchable |
|
|
def strongly_connected_components(G): |
|
|
"""Generate nodes in strongly connected components of graph. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : NetworkX Graph |
|
|
A directed graph. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
comp : generator of sets |
|
|
A generator of sets of nodes, one for each strongly connected |
|
|
component of G. |
|
|
|
|
|
Raises |
|
|
------ |
|
|
NetworkXNotImplemented |
|
|
If G is undirected. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
Generate a sorted list of strongly connected components, largest first. |
|
|
|
|
|
>>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) |
|
|
>>> nx.add_cycle(G, [10, 11, 12]) |
|
|
>>> [ |
|
|
... len(c) |
|
|
... for c in sorted(nx.strongly_connected_components(G), key=len, reverse=True) |
|
|
... ] |
|
|
[4, 3] |
|
|
|
|
|
If you only want the largest component, it's more efficient to |
|
|
use max instead of sort. |
|
|
|
|
|
>>> largest = max(nx.strongly_connected_components(G), key=len) |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
connected_components |
|
|
weakly_connected_components |
|
|
kosaraju_strongly_connected_components |
|
|
|
|
|
Notes |
|
|
----- |
|
|
Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_. |
|
|
Nonrecursive version of algorithm. |
|
|
|
|
|
References |
|
|
---------- |
|
|
.. [1] Depth-first search and linear graph algorithms, R. Tarjan |
|
|
SIAM Journal of Computing 1(2):146-160, (1972). |
|
|
|
|
|
.. [2] On finding the strongly connected components in a directed graph. |
|
|
E. Nuutila and E. Soisalon-Soinen |
|
|
Information Processing Letters 49(1): 9-14, (1994).. |
|
|
|
|
|
""" |
|
|
preorder = {} |
|
|
lowlink = {} |
|
|
scc_found = set() |
|
|
scc_queue = [] |
|
|
i = 0 |
|
|
neighbors = {v: iter(G[v]) for v in G} |
|
|
for source in G: |
|
|
if source not in scc_found: |
|
|
queue = [source] |
|
|
while queue: |
|
|
v = queue[-1] |
|
|
if v not in preorder: |
|
|
i = i + 1 |
|
|
preorder[v] = i |
|
|
done = True |
|
|
for w in neighbors[v]: |
|
|
if w not in preorder: |
|
|
queue.append(w) |
|
|
done = False |
|
|
break |
|
|
if done: |
|
|
lowlink[v] = preorder[v] |
|
|
for w in G[v]: |
|
|
if w not in scc_found: |
|
|
if preorder[w] > preorder[v]: |
|
|
lowlink[v] = min([lowlink[v], lowlink[w]]) |
|
|
else: |
|
|
lowlink[v] = min([lowlink[v], preorder[w]]) |
|
|
queue.pop() |
|
|
if lowlink[v] == preorder[v]: |
|
|
scc = {v} |
|
|
while scc_queue and preorder[scc_queue[-1]] > preorder[v]: |
|
|
k = scc_queue.pop() |
|
|
scc.add(k) |
|
|
scc_found.update(scc) |
|
|
yield scc |
|
|
else: |
|
|
scc_queue.append(v) |
|
|
|
|
|
|
|
|
@not_implemented_for("undirected") |
|
|
@nx._dispatchable |
|
|
def kosaraju_strongly_connected_components(G, source=None): |
|
|
"""Generate nodes in strongly connected components of graph. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : NetworkX Graph |
|
|
A directed graph. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
comp : generator of sets |
|
|
A generator of sets of nodes, one for each strongly connected |
|
|
component of G. |
|
|
|
|
|
Raises |
|
|
------ |
|
|
NetworkXNotImplemented |
|
|
If G is undirected. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
Generate a sorted list of strongly connected components, largest first. |
|
|
|
|
|
>>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) |
|
|
>>> nx.add_cycle(G, [10, 11, 12]) |
|
|
>>> [ |
|
|
... len(c) |
|
|
... for c in sorted( |
|
|
... nx.kosaraju_strongly_connected_components(G), key=len, reverse=True |
|
|
... ) |
|
|
... ] |
|
|
[4, 3] |
|
|
|
|
|
If you only want the largest component, it's more efficient to |
|
|
use max instead of sort. |
|
|
|
|
|
>>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len) |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
strongly_connected_components |
|
|
|
|
|
Notes |
|
|
----- |
|
|
Uses Kosaraju's algorithm. |
|
|
|
|
|
""" |
|
|
post = list(nx.dfs_postorder_nodes(G.reverse(copy=False), source=source)) |
|
|
|
|
|
seen = set() |
|
|
while post: |
|
|
r = post.pop() |
|
|
if r in seen: |
|
|
continue |
|
|
c = nx.dfs_preorder_nodes(G, r) |
|
|
new = {v for v in c if v not in seen} |
|
|
seen.update(new) |
|
|
yield new |
|
|
|
|
|
|
|
|
@not_implemented_for("undirected") |
|
|
@nx._dispatchable |
|
|
def number_strongly_connected_components(G): |
|
|
"""Returns number of strongly connected components in graph. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : NetworkX graph |
|
|
A directed graph. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
n : integer |
|
|
Number of strongly connected components |
|
|
|
|
|
Raises |
|
|
------ |
|
|
NetworkXNotImplemented |
|
|
If G is undirected. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
>>> G = nx.DiGraph( |
|
|
... [(0, 1), (1, 2), (2, 0), (2, 3), (4, 5), (3, 4), (5, 6), (6, 3), (6, 7)] |
|
|
... ) |
|
|
>>> nx.number_strongly_connected_components(G) |
|
|
3 |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
strongly_connected_components |
|
|
number_connected_components |
|
|
number_weakly_connected_components |
|
|
|
|
|
Notes |
|
|
----- |
|
|
For directed graphs only. |
|
|
""" |
|
|
return sum(1 for scc in strongly_connected_components(G)) |
|
|
|
|
|
|
|
|
@not_implemented_for("undirected") |
|
|
@nx._dispatchable |
|
|
def is_strongly_connected(G): |
|
|
"""Test directed graph for strong connectivity. |
|
|
|
|
|
A directed graph is strongly connected if and only if every vertex in |
|
|
the graph is reachable from every other vertex. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : NetworkX Graph |
|
|
A directed graph. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
connected : bool |
|
|
True if the graph is strongly connected, False otherwise. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
>>> G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4), (4, 2)]) |
|
|
>>> nx.is_strongly_connected(G) |
|
|
True |
|
|
>>> G.remove_edge(2, 3) |
|
|
>>> nx.is_strongly_connected(G) |
|
|
False |
|
|
|
|
|
Raises |
|
|
------ |
|
|
NetworkXNotImplemented |
|
|
If G is undirected. |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
is_weakly_connected |
|
|
is_semiconnected |
|
|
is_connected |
|
|
is_biconnected |
|
|
strongly_connected_components |
|
|
|
|
|
Notes |
|
|
----- |
|
|
For directed graphs only. |
|
|
""" |
|
|
if len(G) == 0: |
|
|
raise nx.NetworkXPointlessConcept( |
|
|
"""Connectivity is undefined for the null graph.""" |
|
|
) |
|
|
|
|
|
return len(next(strongly_connected_components(G))) == len(G) |
|
|
|
|
|
|
|
|
@not_implemented_for("undirected") |
|
|
@nx._dispatchable(returns_graph=True) |
|
|
def condensation(G, scc=None): |
|
|
"""Returns the condensation of G. |
|
|
|
|
|
The condensation of G is the graph with each of the strongly connected |
|
|
components contracted into a single node. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : NetworkX DiGraph |
|
|
A directed graph. |
|
|
|
|
|
scc: list or generator (optional, default=None) |
|
|
Strongly connected components. If provided, the elements in |
|
|
`scc` must partition the nodes in `G`. If not provided, it will be |
|
|
calculated as scc=nx.strongly_connected_components(G). |
|
|
|
|
|
Returns |
|
|
------- |
|
|
C : NetworkX DiGraph |
|
|
The condensation graph C of G. The node labels are integers |
|
|
corresponding to the index of the component in the list of |
|
|
strongly connected components of G. C has a graph attribute named |
|
|
'mapping' with a dictionary mapping the original nodes to the |
|
|
nodes in C to which they belong. Each node in C also has a node |
|
|
attribute 'members' with the set of original nodes in G that |
|
|
form the SCC that the node in C represents. |
|
|
|
|
|
Raises |
|
|
------ |
|
|
NetworkXNotImplemented |
|
|
If G is undirected. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
Contracting two sets of strongly connected nodes into two distinct SCC |
|
|
using the barbell graph. |
|
|
|
|
|
>>> G = nx.barbell_graph(4, 0) |
|
|
>>> G.remove_edge(3, 4) |
|
|
>>> G = nx.DiGraph(G) |
|
|
>>> H = nx.condensation(G) |
|
|
>>> H.nodes.data() |
|
|
NodeDataView({0: {'members': {0, 1, 2, 3}}, 1: {'members': {4, 5, 6, 7}}}) |
|
|
>>> H.graph["mapping"] |
|
|
{0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1} |
|
|
|
|
|
Contracting a complete graph into one single SCC. |
|
|
|
|
|
>>> G = nx.complete_graph(7, create_using=nx.DiGraph) |
|
|
>>> H = nx.condensation(G) |
|
|
>>> H.nodes |
|
|
NodeView((0,)) |
|
|
>>> H.nodes.data() |
|
|
NodeDataView({0: {'members': {0, 1, 2, 3, 4, 5, 6}}}) |
|
|
|
|
|
Notes |
|
|
----- |
|
|
After contracting all strongly connected components to a single node, |
|
|
the resulting graph is a directed acyclic graph. |
|
|
|
|
|
""" |
|
|
if scc is None: |
|
|
scc = nx.strongly_connected_components(G) |
|
|
mapping = {} |
|
|
members = {} |
|
|
C = nx.DiGraph() |
|
|
|
|
|
C.graph["mapping"] = mapping |
|
|
if len(G) == 0: |
|
|
return C |
|
|
for i, component in enumerate(scc): |
|
|
members[i] = component |
|
|
mapping.update((n, i) for n in component) |
|
|
number_of_components = i + 1 |
|
|
C.add_nodes_from(range(number_of_components)) |
|
|
C.add_edges_from( |
|
|
(mapping[u], mapping[v]) for u, v in G.edges() if mapping[u] != mapping[v] |
|
|
) |
|
|
|
|
|
nx.set_node_attributes(C, members, "members") |
|
|
return C |
|
|
|
