three_edge_connected/
state.rs

1use crate::graph::FxMapGraph;
2
3#[derive(Default, Debug, Clone)]
4pub struct State {
5    pub degrees: Vec<isize>,
6    pub next_sigma: Vec<usize>,
7    pub next_on_path: Vec<usize>,
8    pub visited: Vec<bool>,
9    pub pre: Vec<usize>,
10    pub lowpt: Vec<usize>,
11    pub count: usize,
12    pub num_descendants: Vec<usize>,
13    pub path_u: usize,
14    pub sigma: Vec<Vec<usize>>,
15}
16
17impl State {
18    pub fn initialize(graph: &FxMapGraph) -> State {
19        let num_nodes = graph.len();
20
21        State {
22            count: 1,
23            next_sigma: vec![0; num_nodes],
24            next_on_path: vec![0; num_nodes],
25            pre: vec![0; num_nodes],
26            lowpt: vec![0; num_nodes],
27            num_descendants: vec![1; num_nodes],
28            degrees: vec![0; num_nodes],
29            visited: vec![false; num_nodes],
30            sigma: Vec::new(),
31            path_u: 0,
32        }
33    }
34
35    pub fn mut_recur(&mut self, w: usize) {
36        assert!(w < self.visited.len());
37        unsafe {
38            *self.visited.get_unchecked_mut(w) = true;
39            *self.next_sigma.get_unchecked_mut(w) = w;
40            *self.next_on_path.get_unchecked_mut(w) = w;
41            *self.pre.get_unchecked_mut(w) = self.count;
42            *self.lowpt.get_unchecked_mut(w) = self.count;
43        }
44        self.count += 1;
45    }
46
47    pub fn components(&self) -> &Vec<Vec<usize>> {
48        &self.sigma
49    }
50
51    pub fn is_back_edge(&self, u: usize, v: usize) -> bool {
52        self.pre[u] > self.pre[v]
53    }
54
55    pub fn is_null_path(&self, u: usize) -> bool {
56        self.next_on_path[u] == u
57    }
58
59    pub fn absorb_path(
60        &mut self,
61        root: usize,
62        path: usize,
63        end: Option<usize>,
64    ) {
65        if Some(root) != end {
66            let mut current = root;
67            let mut step = path;
68            while current != step {
69                unsafe {
70                    *self.degrees.get_unchecked_mut(root) +=
71                        *self.degrees.get_unchecked_mut(step) - 2;
72                    self.next_sigma.swap(root, step);
73                    current = step;
74                    if Some(step) != end {
75                        step = *self.next_on_path.get_unchecked(step);
76                    }
77                    // self.degrees[root] += self.degrees[step] - 2;
78                    // self.next_sigma.swap(root, step);
79                    // current = step;
80                    // if Some(step) != end {
81                    //     step = self.next_on_path[step];
82                    // }
83                }
84            }
85        }
86    }
87
88    pub fn sigma_iter(&self, start: usize) -> SigmaIter<'_> {
89        SigmaIter::new(self, start)
90    }
91
92    pub fn add_component(&mut self, start: usize) {
93        self.sigma.push(self.sigma_iter(start).collect());
94    }
95}
96
97// Struct representing an iterator over a node's sigma set
98pub struct SigmaIter<'a> {
99    start: usize,
100    current: usize,
101    next_sigma: &'a [usize],
102    done: bool,
103}
104
105impl<'a> SigmaIter<'a> {
106    fn new(state: &'a State, node: usize) -> SigmaIter<'a> {
107        let next_sigma = &state.next_sigma;
108        SigmaIter {
109            start: node,
110            current: next_sigma[node],
111            next_sigma,
112            done: false,
113        }
114    }
115}
116
117impl<'a> Iterator for SigmaIter<'a> {
118    type Item = usize;
119
120    fn next(&mut self) -> Option<usize> {
121        if self.done {
122            None
123        } else {
124            if self.current == self.start {
125                self.done = true;
126            }
127
128            self.current = self.next_sigma[self.current];
129            Some(self.current)
130        }
131    }
132}
three_edge_connected/state.rs

three_edge_connected/
state.rs
