haar_lib/graph/
lowlink.rs

1//! Lowlink
2use crate::graph::*;
3use std::cmp::min;
4
5/// Lowlink
6#[derive(Debug, Clone)]
7pub struct Lowlink {
8    /// グラフの頂点数
9    pub size: usize,
10    /// DFSで頂点を訪れた順番
11    pub ord: Vec<usize>,
12    /// DFS木を葉方向に0回以上、後退辺を1回以下辿って到達可能な頂点の`ord`の最小値
13    pub low: Vec<usize>,
14    /// DFS木での親ノード
15    pub par: Vec<Option<usize>>,
16    /// DFS木での子ノード
17    pub ch: Vec<Vec<usize>>,
18    /// par, chのどちらにも属さないノード
19    pub back: Vec<Vec<usize>>,
20}
21
22impl Lowlink {
23    /// 無向グラフから[`Lowlink`]を構築する。
24    pub fn new<E: EdgeTrait>(g: &Graph<Undirected, E>) -> Self {
25        let n = g.len();
26        let mut this = Self {
27            size: n,
28            ord: vec![0; n],
29            low: vec![0; n],
30            par: vec![None; n],
31            ch: vec![vec![]; n],
32            back: vec![vec![]; n],
33        };
34
35        let mut index = 0;
36        let mut check = vec![false; n];
37        for i in 0..n {
38            this.dfs(g, i, None, &mut index, &mut check);
39        }
40
41        this
42    }
43
44    fn dfs<E: EdgeTrait>(
45        &mut self,
46        g: &Graph<Undirected, E>,
47        cur: usize,
48        par: Option<usize>,
49        index: &mut usize,
50        check: &mut [bool],
51    ) {
52        if check[cur] {
53            return;
54        }
55        check[cur] = true;
56
57        self.par[cur] = par;
58        self.ord[cur] = *index;
59        self.low[cur] = *index;
60        *index += 1;
61        let mut count_par = 0;
62
63        for e in g.nodes[cur].edges.iter() {
64            let to = e.to();
65            if par.is_some_and(|p| p == to) {
66                count_par += 1;
67                if count_par == 1 {
68                    continue;
69                }
70            }
71
72            if !check[to] {
73                self.ch[cur].push(to);
74                self.dfs(g, to, Some(cur), index, check);
75                self.low[cur] = min(self.low[cur], self.low[to]);
76            } else {
77                self.back[cur].push(to);
78            }
79
80            self.low[cur] = min(self.low[cur], self.ord[to]);
81        }
82    }
83}
haar_lib/graph/lowlink.rs

haar_lib/graph/
lowlink.rs
