algorithms_edu/algo/graph/
tarjan_scc.rs

1//! An implementation of Tarjan's Strongly Connected Components algorithm using an adjacency list.
2//!
3//! - Time complexity: $O(V+E)$
4//!
5//! # Resources
6//!
7//! - [W. Fiset's video](https://www.youtube.com/watch?v=wUgWX0nc4NY&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=23)
8
9use crate::algo::graph::UnweightedAdjacencyList;
10use std::cmp::min;
11
12const UNVISITED: i32 = -1;
13struct SccSolver<'a> {
14    g: &'a UnweightedAdjacencyList,
15    ids: Vec<i32>,
16    stack: Vec<usize>,
17    on_stack: Vec<bool>,
18    id: i32,
19    low_link: Vec<i32>,
20    sccs: Vec<Vec<usize>>,
21}
22
23impl<'a> SccSolver<'a> {
24    fn new(g: &'a UnweightedAdjacencyList) -> Self {
25        let n = g.node_count();
26        Self {
27            g,
28            ids: vec![UNVISITED; n],
29            sccs: Vec::new(),
30            low_link: vec![0; n],
31            id: 0,
32            stack: Vec::new(),
33            on_stack: vec![false; n],
34        }
35    }
36}
37
38impl UnweightedAdjacencyList {
39    pub fn scc(&self) -> SccResult {
40        let n = self.node_count();
41        let mut s = SccSolver::new(self);
42
43        fn _dfs(s: &mut SccSolver, at: usize) {
44            s.low_link[at] = s.id;
45            s.ids[at] = s.id;
46            s.id += 1;
47            s.stack.push(at);
48            s.on_stack[at] = true;
49            // visit all neighbours and min low-link on callback
50            for &neighbour in &s.g[at] {
51                if s.ids[neighbour] == UNVISITED {
52                    _dfs(s, neighbour);
53                }
54                if s.on_stack[neighbour] {
55                    s.low_link[at] = min(s.low_link[at], s.low_link[neighbour])
56                }
57            }
58            // after having visited all the neighbours of `at` if we're at the start of
59            // a SCC empty the seen stack until we're back to the start of the SCC
60            if s.ids[at] == s.low_link[at] {
61                let mut this_scc = Vec::new();
62                while let Some(node) = s.stack.pop() {
63                    s.on_stack[node] = false;
64                    s.low_link[node] = s.ids[at];
65                    this_scc.push(node);
66                    if node == at {
67                        s.sccs.push(this_scc);
68                        break;
69                    }
70                }
71            }
72        }
73        for i in 0..n {
74            if s.ids[i] == UNVISITED {
75                _dfs(&mut s, i);
76            }
77        }
78        let SccSolver { sccs, low_link, .. } = s;
79        SccResult { sccs, low_link }
80    }
81}
82
83#[derive(Debug)]
84pub struct SccResult {
85    sccs: Vec<Vec<usize>>,
86    low_link: Vec<i32>,
87}
88
89impl SccResult {
90    pub fn scc_count(&self) -> usize {
91        self.sccs.len()
92    }
93    pub fn in_same_scc(&self, nodes: &[usize]) -> bool {
94        let id = self.low_link[nodes[0]];
95        nodes.iter().all(|&node| self.low_link[node] == id)
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102    #[test]
103    fn test_tarjan_scc() {
104        let graph = UnweightedAdjacencyList::new_directed(
105            10,
106            &[
107                // SCC 1 with nodes 0,1,2
108                [0, 1],
109                [1, 2],
110                [2, 0],
111                // SCC 2 with nodes 3,4,5,6
112                [5, 4],
113                [5, 6],
114                [3, 5],
115                [4, 3],
116                [4, 5],
117                [6, 4],
118                // SCC 3 with nodes 7,8
119                [7, 8],
120                [8, 7],
121                // SCC 4 is node 9 all alone by itself
122                // Add a few more edges to make things interesting
123                [1, 5],
124                [1, 7],
125                [2, 7],
126                [6, 8],
127                [9, 8],
128                [9, 4],
129            ],
130        );
131        let res = graph.scc();
132        assert_eq!(res.scc_count(), 4);
133        assert!(res.in_same_scc(&[0, 1, 2]));
134        assert!(res.in_same_scc(&[3, 4, 5, 6]));
135        assert!(res.in_same_scc(&[7, 8]));
136        assert!(res.in_same_scc(&[9]));
137        // not in the same scc
138        assert!(!res.in_same_scc(&[8, 9]));
139    }
140}
algorithms_edu/algo/graph/tarjan_scc.rs

algorithms_edu/algo/graph/
tarjan_scc.rs
