oxicuda_graphalg/connectivity/
articulation_points.rs

1//! Articulation points (cut vertices) via Tarjan's low-link algorithm.
2
3use crate::error::GraphalgResult;
4use crate::repr::adjacency_list::AdjacencyList;
5
6const UNVISITED: usize = usize::MAX;
7
8pub fn articulation_points(g: &AdjacencyList) -> GraphalgResult<Vec<usize>> {
9    let n = g.n;
10    let mut disc = vec![UNVISITED; n];
11    let mut low = vec![0usize; n];
12    let mut parent = vec![UNVISITED; n];
13    let mut child_count = vec![0usize; n];
14    let mut is_ap = vec![false; n];
15    let mut time = 0usize;
16    for start in 0..n {
17        if disc[start] != UNVISITED {
18            continue;
19        }
20        disc[start] = time;
21        low[start] = time;
22        time += 1;
23        parent[start] = start;
24        let mut stack: Vec<(usize, usize)> = vec![(start, 0)];
25        while let Some(&(u, i)) = stack.last() {
26            let adj = g.neighbors(u)?;
27            if i < adj.len() {
28                let v = adj[i];
29                let last = stack.len() - 1;
30                stack[last].1 = i + 1;
31                if disc[v] == UNVISITED {
32                    parent[v] = u;
33                    disc[v] = time;
34                    low[v] = time;
35                    time += 1;
36                    child_count[u] += 1;
37                    stack.push((v, 0));
38                } else if v != parent[u] {
39                    low[u] = low[u].min(disc[v]);
40                }
41            } else {
42                let par = parent[u];
43                if par != u {
44                    low[par] = low[par].min(low[u]);
45                    if par != start && low[u] >= disc[par] {
46                        is_ap[par] = true;
47                    }
48                }
49                stack.pop();
50            }
51        }
52        if child_count[start] > 1 {
53            is_ap[start] = true;
54        }
55    }
56    Ok((0..n).filter(|&i| is_ap[i]).collect())
57}
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn ap_line_middle() {
65        let mut g = AdjacencyList::new(5);
66        for i in 0..4 {
67            g.add_undirected_edge(i, i + 1).expect("ok");
68        }
69        let ap = articulation_points(&g).expect("ok");
70        assert_eq!(ap, vec![1, 2, 3]);
71    }
72
73    #[test]
74    fn ap_triangle_none() {
75        let mut g = AdjacencyList::new(3);
76        g.add_undirected_edge(0, 1).expect("ok");
77        g.add_undirected_edge(1, 2).expect("ok");
78        g.add_undirected_edge(0, 2).expect("ok");
79        let ap = articulation_points(&g).expect("ok");
80        assert!(ap.is_empty());
81    }
82}
oxicuda_graphalg/connectivity/articulation_points.rs

oxicuda_graphalg/connectivity/
articulation_points.rs
