toolbox_rs/
path_based_scc.rs

1/*
2 * Path-based SCC algorithm (Gabow's Algorithm)
3 *
4 * The algorithm numbers SCCs in reverse order of their discovery:
5 * - Initially, component counter starts at n (number of vertices)
6 * - Each time an SCC is found, counter is decremented
7 * - Final numbering is from n-1 down to 0
8 *
9 * This approach serves multiple purposes:
10 * 1. Avoids conflicts with temporary stack indices during processing
11 * 2. Creates a reverse topological ordering of SCCs
12 * 3. Ensures each SCC gets a unique, consecutive number
13 *
14 * Example: In a graph with 5 vertices and 3 SCCs:
15 * - First discovered SCC gets number 4
16 * - Second SCC gets number 3
17 * - Last SCC gets number 2
18 */
19
20use crate::graph::Graph;
21
22#[derive(Clone, Copy)]
23enum DfsState {
24    Visit(usize),            // Knoten zum ersten Mal besuchen
25    ProcessNeighbors(usize), // Nachbarn verarbeiten
26    Finalize(usize),         // SCC finalisieren
27}
28
29pub struct PathBasedScc {
30    scc: Vec<usize>,
31    stack: Vec<usize>,  // Stack S
32    bounds: Vec<usize>, // Stack B
33    component: usize,
34}
35
36impl Default for PathBasedScc {
37    fn default() -> Self {
38        Self::new()
39    }
40}
41
42impl PathBasedScc {
43    pub fn new() -> Self {
44        Self {
45            bounds: Vec::new(),
46            scc: Vec::new(),
47            stack: Vec::new(),
48            component: 0,
49        }
50    }
51
52    pub fn run<T>(&mut self, graph: &(impl Graph<T> + 'static)) -> Vec<usize> {
53        // initialization
54        self.bounds = Vec::new();
55        self.scc.resize(graph.number_of_nodes(), usize::MAX);
56        self.stack = Vec::new();
57        self.component = graph.number_of_nodes();
58
59        // main loop
60        for v in graph.node_range() {
61            if self.scc[v] == usize::MAX {
62                self.dfs_iterative(v, graph);
63            }
64        }
65
66        self.scc.clone()
67    }
68
69    fn dfs_iterative<T>(&mut self, start: usize, graph: &(impl Graph<T> + 'static)) {
70        let mut dfs_stack = vec![DfsState::Visit(start)];
71        let mut edge_indices = vec![0usize; graph.number_of_nodes()];
72
73        while let Some(state) = dfs_stack.pop() {
74            match state {
75                DfsState::Visit(v) => {
76                    // step 1: push v onto S
77                    self.stack.push(v);
78                    self.scc[v] = self.stack.len() - 1;
79                    self.bounds.push(self.scc[v]);
80                    dfs_stack.push(DfsState::ProcessNeighbors(v));
81                }
82
83                DfsState::ProcessNeighbors(v) => {
84                    let edges: Vec<_> = graph.edge_range(v).collect();
85                    if edge_indices[v] < edges.len() {
86                        let e = edges[edge_indices[v]];
87                        edge_indices[v] += 1;
88                        dfs_stack.push(DfsState::ProcessNeighbors(v));
89
90                        let w = graph.target(e);
91                        if self.scc[w] == usize::MAX {
92                            dfs_stack.push(DfsState::Visit(w));
93                        } else {
94                            // contract if necessary
95                            while let Some(&bound) = self.bounds.last() {
96                                if self.scc[w] < bound {
97                                    self.bounds.pop();
98                                } else {
99                                    break;
100                                }
101                            }
102                        }
103                    } else {
104                        dfs_stack.push(DfsState::Finalize(v));
105                    }
106                }
107
108                DfsState::Finalize(v) => {
109                    if Some(&self.scc[v]) == self.bounds.last() {
110                        self.bounds.pop();
111                        self.component -= 1;
112                        while let Some(u) = self.stack.pop() {
113                            self.scc[u] = self.component;
114                            if u == v {
115                                break;
116                            }
117                        }
118                    }
119                }
120            }
121        }
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use crate::edge::InputEdge;
128    use crate::path_based_scc::PathBasedScc;
129    use crate::static_graph::StaticGraph;
130
131    #[test]
132    fn scc_wiki1() {
133        type Graph = StaticGraph<i32>;
134        let edges = vec![
135            InputEdge::new(0, 1, 3),
136            InputEdge::new(1, 2, 3),
137            InputEdge::new(1, 4, 1),
138            InputEdge::new(1, 5, 6),
139            InputEdge::new(2, 3, 2),
140            InputEdge::new(2, 6, 2),
141            InputEdge::new(3, 2, 2),
142            InputEdge::new(3, 7, 2),
143            InputEdge::new(4, 0, 2),
144            InputEdge::new(4, 5, 2),
145            InputEdge::new(5, 6, 2),
146            InputEdge::new(6, 5, 2),
147            InputEdge::new(7, 3, 2),
148            InputEdge::new(7, 6, 2),
149        ];
150        let graph = Graph::new(edges);
151
152        let mut scc = PathBasedScc::new();
153        assert_eq!(vec![5, 5, 6, 6, 5, 7, 7, 6], scc.run(&graph));
154    }
155
156    #[test]
157    fn geekforgeeks() {
158        type Graph = StaticGraph<i32>;
159        let edges = vec![
160            InputEdge::new(1, 0, 3),
161            InputEdge::new(0, 3, 3),
162            InputEdge::new(0, 2, 1),
163            InputEdge::new(2, 1, 6),
164            InputEdge::new(3, 4, 2),
165        ];
166        let graph = Graph::new(edges);
167
168        let mut scc = PathBasedScc::new();
169        assert_eq!(vec![2, 2, 2, 3, 4], scc.run(&graph));
170    }
171
172    #[test]
173    fn stanford2() {
174        type Graph = StaticGraph<i32>;
175        let edges = vec![
176            InputEdge::new(0, 6, 3),
177            InputEdge::new(6, 3, 3),
178            InputEdge::new(3, 0, 1),
179            InputEdge::new(6, 8, 6),
180            InputEdge::new(8, 5, 2),
181            InputEdge::new(5, 2, 2),
182            InputEdge::new(2, 8, 2),
183            InputEdge::new(5, 7, 2),
184            InputEdge::new(7, 1, 2),
185            InputEdge::new(4, 7, 2),
186            InputEdge::new(1, 4, 2),
187        ];
188        let graph = Graph::new(edges);
189
190        let mut scc = PathBasedScc::new();
191        assert_eq!(vec![6, 8, 7, 6, 8, 7, 6, 8, 7], scc.run(&graph));
192    }
193
194    #[test]
195    fn web1() {
196        type Graph = StaticGraph<i32>;
197        let edges = vec![
198            InputEdge::new(0, 1, 3),
199            InputEdge::new(1, 3, 3),
200            InputEdge::new(1, 4, 1),
201            InputEdge::new(1, 2, 6),
202            InputEdge::new(2, 5, 2),
203            InputEdge::new(4, 1, 2),
204            InputEdge::new(4, 5, 2),
205            InputEdge::new(4, 6, 2),
206            InputEdge::new(5, 7, 2),
207            InputEdge::new(6, 7, 2),
208            InputEdge::new(6, 8, 2),
209            InputEdge::new(7, 9, 2),
210            InputEdge::new(9, 10, 2),
211            InputEdge::new(10, 8, 2),
212            InputEdge::new(8, 11, 2),
213            InputEdge::new(11, 6, 2),
214        ];
215        let graph = Graph::new(edges);
216
217        let mut scc = PathBasedScc::default();
218        assert_eq!(
219            vec![6, 7, 9, 8, 7, 10, 11, 11, 11, 11, 11, 11],
220            scc.run(&graph)
221        );
222    }
223}
toolbox_rs/path_based_scc.rs

toolbox_rs/
path_based_scc.rs
