haar_lib/graph/
biconnected.rs

1//! 二重頂点連結分解
2
3pub use crate::graph::lowlink::Lowlink;
4
5type Vertices = Vec<usize>;
6type Edges = Vec<(usize, usize)>;
7
8/// 二重頂点連結分解
9pub fn biconnected(ll: &Lowlink) -> Vec<(Vertices, Edges)> {
10    let n = ll.size;
11
12    let mut check = vec![false; n];
13    let mut ret = vec![];
14    let mut temp = vec![];
15    let mut vcheck = vec![false; n];
16
17    for i in 0..n {
18        if !check[i] {
19            if ll.ch[i].is_empty() && ll.par[i].is_none() {
20                ret.push((vec![i], vec![]));
21            } else {
22                dfs(i, ll, &mut check, &mut vcheck, &mut temp, &mut ret);
23            }
24        }
25    }
26
27    ret
28}
29
30fn dfs(
31    cur: usize,
32    ll: &Lowlink,
33    check: &mut [bool],
34    vcheck: &mut [bool],
35    stack: &mut Vec<(usize, usize)>,
36    ret: &mut Vec<(Vertices, Edges)>,
37) {
38    check[cur] = true;
39
40    for &to in ll.ch[cur].iter().chain(ll.back[cur].iter()) {
41        if !check[to] || ll.ord[to] < ll.ord[cur] {
42            stack.push((cur, to));
43        }
44        if !check[to] {
45            dfs(to, ll, check, vcheck, stack, ret);
46
47            if ll.low[to] >= ll.ord[cur] {
48                let mut es = vec![];
49                let mut vs = vec![];
50
51                while let Some(e) = stack.pop() {
52                    let (u, v) = e;
53                    es.push(e);
54
55                    if !vcheck[u] {
56                        vs.push(u);
57                        vcheck[u] = true;
58                    }
59                    if !vcheck[v] {
60                        vs.push(v);
61                        vcheck[v] = true;
62                    }
63
64                    if u == cur && v == to {
65                        break;
66                    }
67                }
68
69                for &i in &vs {
70                    vcheck[i] = false;
71                }
72
73                ret.push((vs, es));
74            }
75        }
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use super::biconnected;
82    use crate::btreeset;
83    use crate::graph::{lowlink::Lowlink, *};
84    use std::collections::BTreeSet;
85    use std::iter::FromIterator;
86
87    #[test]
88    fn test() {
89        let mut g = Graph::<Undirected, _>::new(4);
90        g.extend(
91            vec![(0, 3), (0, 1), (3, 0), (2, 1), (2, 3)]
92                .into_iter()
93                .map(|(u, v)| Edge::new(u, v, (), ())),
94        );
95
96        assert_eq!(
97            BTreeSet::from_iter(
98                biconnected(&Lowlink::new(&g))
99                    .into_iter()
100                    .map(|(v, _)| BTreeSet::from_iter(v))
101            ),
102            btreeset! {
103                btreeset!{0, 1, 2, 3}
104            }
105        );
106
107        let mut g = Graph::<Undirected, _>::new(10);
108        g.extend(
109            vec![
110                (0, 6),
111                (0, 8),
112                (1, 2),
113                (1, 6),
114                (2, 6),
115                (3, 6),
116                (3, 9),
117                (4, 9),
118                (4, 7),
119                (5, 6),
120                (5, 9),
121                (6, 8),
122            ]
123            .into_iter()
124            .map(|(u, v)| Edge::new(u, v, (), ())),
125        );
126
127        assert_eq!(
128            BTreeSet::from_iter(
129                biconnected(&Lowlink::new(&g))
130                    .into_iter()
131                    .map(|(v, _)| BTreeSet::from_iter(v))
132            ),
133            btreeset! {
134                btreeset!{0, 6, 8},
135                btreeset!{1, 2, 6},
136                btreeset!{3, 5, 6, 9},
137                btreeset!{4, 7},
138                btreeset!{4, 9}
139            }
140        );
141
142        let mut g = Graph::<Undirected, _>::new(5);
143        g.extend(
144            vec![(0, 1), (1, 0), (0, 1)]
145                .into_iter()
146                .map(|(u, v)| Edge::new(u, v, (), ())),
147        );
148
149        assert_eq!(
150            BTreeSet::from_iter(
151                biconnected(&Lowlink::new(&g))
152                    .into_iter()
153                    .map(|(v, _)| BTreeSet::from_iter(v))
154            ),
155            btreeset! {
156                btreeset!{0, 1},
157                btreeset!{2},
158                btreeset!{3},
159                btreeset!{4}
160            }
161        );
162    }
163}
haar_lib/graph/biconnected.rs

haar_lib/graph/
biconnected.rs
