lowlink/
lib.rs

1use std::marker::PhantomData;
2
3pub struct Lowlink<V, I, D> {
4    low: Vec<usize>,
5    ord: Vec<usize>,
6    par_ord: Vec<usize>,
7    index: I,
8    delta: D,
9    _phd: PhantomData<(fn(&V) -> I, fn(&V) -> D)>,
10}
11
12impl<V, I, D, J> Lowlink<V, I, D>
13where
14    V: Eq + Clone,
15    I: Fn(&V) -> usize + Copy,
16    D: Fn(&V) -> J + Copy,
17    J: Iterator<Item = V>,
18{
19    pub fn new(
20        vertices: impl Iterator<Item = V>,
21        len: usize,
22        index: I,
23        delta: D,
24    ) -> Self
25    where
26        D: Fn(&V) -> J + Copy,
27        I: Fn(&V) -> usize + Copy,
28        J: Iterator<Item = V>,
29    {
30        struct State {
31            ord: Vec<usize>,
32            low: Vec<usize>,
33            par_ord: Vec<usize>,
34            is_ancestor: Vec<bool>,
35            index: usize,
36        }
37
38        fn dfs<V, I, D, J>(v: &V, index: I, delta: D, state: &mut State)
39        where
40            D: Fn(&V) -> J + Copy,
41            I: Fn(&V) -> usize + Copy,
42            J: Iterator<Item = V>,
43        {
44            let n = state.ord.len();
45            let vi = index(v);
46            state.ord[vi] = state.index;
47            state.low[vi] = state.index;
48            state.index += 1;
49            state.is_ancestor[vi] = true;
50            for nv in delta(v) {
51                let nvi = index(&nv);
52                if state.ord[nvi] == n {
53                    dfs(&nv, index, delta, state);
54                    state.par_ord[nvi] = vi;
55                    state.low[vi] = state.low[vi].min(state.low[nvi]);
56                } else if state.is_ancestor[nvi] {
57                    state.low[vi] = state.low[vi].min(state.ord[nvi]);
58                }
59            }
60            state.is_ancestor[vi] = false;
61        }
62
63        let mut state = State {
64            ord: vec![len; len],
65            low: vec![len; len],
66            par_ord: vec![len; len],
67            index: 0,
68            is_ancestor: vec![false; len],
69        };
70
71        for v in vertices {
72            if state.ord[index(&v)] == len {
73                dfs(&v, index, delta, &mut state);
74            }
75        }
76
77        let State { ord, low, par_ord, .. } = state;
78        Self {
79            ord,
80            low,
81            par_ord,
82            index,
83            delta,
84            _phd: PhantomData,
85        }
86    }
87
88    pub fn low(&self, v: &V) -> usize { self.low[(self.index)(v)] }
89    pub fn ord(&self, v: &V) -> usize { self.ord[(self.index)(v)] }
90    pub fn par_ord(&self, v: &V) -> usize { self.par_ord[(self.index)(v)] }
91
92    // the difference of the number of connected components on the removal of the vertex
93    pub fn cc_rm_v(&self, v: &V) -> isize {
94        let len = self.ord.len();
95        let vi = (self.index)(v);
96        let count = if self.par_ord[vi] == len {
97            // (!) multiple edges?
98            (self.delta)(v)
99                .map(|nv| (self.index)(&nv))
100                .filter(|&nvi| self.par_ord[nvi] == vi)
101                .count()
102        } else {
103            (self.delta)(v)
104                .map(|nv| (self.index)(&nv))
105                .filter(|&nvi| self.par_ord[nvi] == vi)
106                .filter(|&nvi| self.ord[vi] <= self.low[nvi])
107                .count()
108                + 1
109        };
110        count as isize - 1
111    }
112}
lowlink/lib.rs

lowlink/
lib.rs
