graph_advanced/
kosaraju_scc.rs

1use graph_core::{Graph, NodeId};
2use std::collections::{HashMap, HashSet};
3
4/// Finds all **Strongly Connected Components** (SCCs) using Kosaraju's algorithm.
5///
6/// Kosaraju's algorithm uses two DFS passes:
7/// 1. Run DFS on the **original** graph, recording nodes in finish order.
8/// 2. Run DFS on the **transposed** graph in reverse finish order — each DFS
9///    tree in this pass is one SCC.
10///
11/// # Returns
12///
13/// A `Vec` of SCCs, each SCC being a `Vec<NodeId>`. SCCs are returned in
14/// **topological order** of the condensed DAG (the first SCC has no incoming
15/// edges from other SCCs in the condensed graph).
16///
17/// # Complexity
18///
19/// O(V + E) — two DFS passes plus one graph transposition.
20///
21/// # Examples
22///
23/// ```
24/// use graph_core::{AdjacencyList, Graph};
25/// use graph_advanced::kosaraju_scc;
26///
27/// // 0 → 1 → 0  (cycle),  1 → 2  (singleton)
28/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
29/// let n: Vec<_> = (0..3).map(|_| g.add_node(())).collect();
30/// g.add_edge(n[0], n[1], 1.0).unwrap();
31/// g.add_edge(n[1], n[0], 1.0).unwrap();
32/// g.add_edge(n[1], n[2], 1.0).unwrap();
33///
34/// let sccs = kosaraju_scc(&g);
35/// assert_eq!(sccs.len(), 2);
36/// ```
37pub fn kosaraju_scc<G>(graph: &G) -> Vec<Vec<NodeId>>
38where
39    G: Graph<Weight = f64>,
40{
41    // ── Pass 1: DFS on original graph, record finish order ───────────────────
42    let mut visited: HashSet<NodeId> = HashSet::new();
43    let mut finish_order: Vec<NodeId> = Vec::new();
44
45    for node in graph.nodes() {
46        if !visited.contains(&node) {
47            dfs_finish(graph, node, &mut visited, &mut finish_order);
48        }
49    }
50
51    // ── Build transposed graph ────────────────────────────────────────────────
52    // Map each NodeId to a dense index for the transpose adjacency list.
53    let node_list: Vec<NodeId> = graph.nodes().collect();
54    let index_of: HashMap<NodeId, usize> = node_list
55        .iter()
56        .enumerate()
57        .map(|(i, &id)| (id, i))
58        .collect();
59    let n = node_list.len();
60
61    // transpose[i] = list of nodes that have an edge TO node_list[i].
62    let mut transpose: Vec<Vec<usize>> = vec![Vec::new(); n];
63    for &u in &node_list {
64        for (v, _) in graph.neighbors(u) {
65            let ui = index_of[&u];
66            let vi = index_of[&v];
67            transpose[vi].push(ui); // edge u→v in original becomes v→u in transpose
68        }
69    }
70
71    // ── Pass 2: DFS on transposed graph in reverse finish order ──────────────
72    let mut visited2: HashSet<usize> = HashSet::new();
73    let mut result: Vec<Vec<NodeId>> = Vec::new();
74
75    for node in finish_order.into_iter().rev() {
76        let idx = index_of[&node];
77        if !visited2.contains(&idx) {
78            let mut scc_indices: Vec<usize> = Vec::new();
79            dfs_transpose(idx, &transpose, &mut visited2, &mut scc_indices);
80            let scc = scc_indices.iter().map(|&i| node_list[i]).collect();
81            result.push(scc);
82        }
83    }
84
85    result
86}
87
88/// DFS on the original graph; appends nodes to `finish_order` in post-order.
89fn dfs_finish<G>(
90    graph: &G,
91    node: NodeId,
92    visited: &mut HashSet<NodeId>,
93    finish_order: &mut Vec<NodeId>,
94) where
95    G: Graph<Weight = f64>,
96{
97    if !visited.insert(node) {
98        return;
99    }
100    for (neighbour, _) in graph.neighbors(node) {
101        dfs_finish(graph, neighbour, visited, finish_order);
102    }
103    finish_order.push(node);
104}
105
106/// DFS on the transposed graph (stored as index-based adjacency list).
107fn dfs_transpose(
108    node: usize,
109    transpose: &[Vec<usize>],
110    visited: &mut HashSet<usize>,
111    scc: &mut Vec<usize>,
112) {
113    if !visited.insert(node) {
114        return;
115    }
116    scc.push(node);
117    for &neighbour in &transpose[node] {
118        dfs_transpose(neighbour, transpose, visited, scc);
119    }
120}
graph_advanced/kosaraju_scc.rs

graph_advanced/
kosaraju_scc.rs
