petgraph/algo/scc/
kosaraju_scc.rs

1use crate::visit::VisitMap;
2use alloc::vec::Vec;
3
4use crate::visit::{
5    Dfs, DfsPostOrder, IntoNeighborsDirected, IntoNodeIdentifiers, Reversed, Visitable,
6};
7
8/// Renamed to `kosaraju_scc`.
9#[deprecated(note = "renamed to kosaraju_scc")]
10pub fn scc<G>(g: G) -> Vec<Vec<G::NodeId>>
11where
12    G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
13{
14    kosaraju_scc(g)
15}
16
17/// Compute the *strongly connected components* using [Kosaraju's algorithm][1].
18///
19/// This implementation is iterative and does two passes over the nodes.
20///
21/// # Arguments
22/// * `g`: a directed or undirected graph.
23///
24/// # Returns
25/// Return a vector where each element is a strongly connected component (scc).
26/// The order of node ids within each scc is arbitrary, but the order of
27/// the sccs is their postorder (reverse topological sort).
28///
29/// For an undirected graph, the sccs are simply the connected components.
30///
31/// # Complexity
32/// * Time complexity: **O(|V| + |E|)**.
33/// * Auxiliary space: **O(|V|)**.
34///
35/// where **|V|** is the number of nodes and **|E|** is the number of edges.
36///
37/// # Examples
38///
39/// ```rust
40/// use petgraph::Graph;
41/// use petgraph::algo::kosaraju_scc;
42/// use petgraph::prelude::*;
43///
44/// let mut graph: Graph<i32, (), Directed> = Graph::new();
45/// let a = graph.add_node(1);
46/// let b = graph.add_node(2);
47/// let c = graph.add_node(3);
48/// let d = graph.add_node(4);
49/// let e = graph.add_node(5);
50/// let f = graph.add_node(6);
51///
52/// graph.extend_with_edges(&[
53///     (a, b), (b, c), (c, a),  // First SCC: a -> b -> c -> a
54///     (d, e), (e, f), (f, d),  // Second SCC: d -> e -> f -> d
55///     (c, d),                  // Connection between SCCs
56/// ]);
57///
58/// // Graph structure:
59/// // a ---> b       e ---> f
60/// // ↑     ↓       ↑      |
61/// // └---- c --->  d <----┘
62///
63/// let sccs = kosaraju_scc(&graph);
64/// assert_eq!(sccs.len(), 2); // Two strongly connected components
65///
66/// // Each SCC contains 3 nodes
67/// assert_eq!(sccs[0].len(), 3);
68/// assert_eq!(sccs[1].len(), 3);
69/// ```
70///
71/// For a simple directed acyclic graph (DAG):
72///
73/// ```rust
74/// use petgraph::Graph;
75/// use petgraph::algo::kosaraju_scc;
76/// use petgraph::prelude::*;
77///
78/// let mut dag: Graph<&str, (), Directed> = Graph::new();
79/// let a = dag.add_node("A");
80/// let b = dag.add_node("B");
81/// let c = dag.add_node("C");
82///
83/// dag.extend_with_edges(&[(a, b), (b, c)]);
84/// // A -> B -> C
85///
86/// let sccs = kosaraju_scc(&dag);
87/// assert_eq!(sccs.len(), 3); // Each node is its own SCC
88///
89/// // Each SCC contains exactly one node
90/// for scc in &sccs {
91///     assert_eq!(scc.len(), 1);
92/// }
93/// ```
94///
95/// [1]: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
96pub fn kosaraju_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
97where
98    G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
99{
100    let mut dfs = DfsPostOrder::empty(g);
101
102    // First phase, reverse dfs pass, compute finishing times.
103    // http://stackoverflow.com/a/26780899/161659
104    let mut finish_order = Vec::with_capacity(0);
105    for i in g.node_identifiers() {
106        if dfs.discovered.is_visited(&i) {
107            continue;
108        }
109
110        dfs.move_to(i);
111        while let Some(nx) = dfs.next(Reversed(g)) {
112            finish_order.push(nx);
113        }
114    }
115
116    let mut dfs = Dfs::from_parts(dfs.stack, dfs.discovered);
117    dfs.reset(g);
118    let mut sccs = Vec::new();
119
120    // Second phase
121    // Process in decreasing finishing time order
122    for i in finish_order.into_iter().rev() {
123        if dfs.discovered.is_visited(&i) {
124            continue;
125        }
126        // Move to the leader node `i`.
127        dfs.move_to(i);
128        let mut scc = Vec::new();
129        while let Some(nx) = dfs.next(g) {
130            scc.push(nx);
131        }
132        sccs.push(scc);
133    }
134    sccs
135}
petgraph/algo/scc/kosaraju_scc.rs

petgraph/algo/scc/
kosaraju_scc.rs
