rapx/analysis/graphs/
scc.rs

1use rustc_data_structures::fx::FxHashSet;
2use std::cmp;
3
4#[derive(Debug, Clone)]
5pub struct SccExit {
6    pub exit: usize,
7    pub to: usize,
8}
9
10impl SccExit {
11    pub fn new(exit: usize, to: usize) -> Self {
12        SccExit { exit, to }
13    }
14}
15
16#[derive(Debug, Clone)]
17pub struct SccInfo {
18    pub enter: usize,
19    pub nodes: Vec<usize>,
20    pub exits: Vec<SccExit>,
21}
22
23impl SccInfo {
24    pub fn new(enter: usize) -> Self {
25        SccInfo {
26            enter,
27            nodes: Vec::<usize>::new(),
28            exits: Vec::<SccExit>::new(),
29        }
30    }
31}
32
33pub trait Scc {
34    fn find_scc(&mut self) {
35        let mut stack = Vec::new();
36        let mut instack = FxHashSet::<usize>::default(); // for fast query only
37        let mut dfn = vec![0; self.get_size()];
38        let mut low = vec![0; self.get_size()];
39        let mut time = 0;
40        self.tarjan(0, &mut stack, &mut instack, &mut dfn, &mut low, &mut time);
41    }
42
43    fn on_scc_found(&mut self, root: usize, scc_components: &[usize]); // callback 
44    fn get_next(&mut self, root: usize) -> FxHashSet<usize>; //
45    fn get_size(&mut self) -> usize; //
46    //
47    fn tarjan(
48        &mut self,
49        index: usize,
50        stack: &mut Vec<usize>,
51        instack: &mut FxHashSet<usize>,
52        dfn: &mut Vec<usize>,
53        low: &mut Vec<usize>,
54        time: &mut usize,
55    ) {
56        dfn[index] = *time;
57        low[index] = *time;
58        *time += 1;
59        stack.push(index);
60        instack.insert(index);
61        let nexts = self.get_next(index);
62        for next in nexts {
63            if dfn[next] == 0 {
64                self.tarjan(next, stack, instack, dfn, low, time);
65                low[index] = cmp::min(low[index], low[next]);
66            } else if instack.contains(&next) {
67                low[index] = cmp::min(low[index], dfn[next]);
68            }
69        }
70        if dfn[index] == low[index] {
71            let mut component = vec![index];
72            while let Some(top) = stack.pop() {
73                instack.remove(&top);
74                if top == index {
75                    break;
76                }
77                component.push(top);
78            }
79            self.on_scc_found(index, &component);
80        }
81    }
82}
rapx/analysis/graphs/scc.rs

rapx/analysis/graphs/
scc.rs
