oxicuda_graphalg/connectivity/
biconnected.rs

1//! Biconnected components (edge-disjoint blocks of an undirected graph).
2
3use crate::error::GraphalgResult;
4use crate::repr::adjacency_list::AdjacencyList;
5
6const UNVISITED: usize = usize::MAX;
7
8pub fn biconnected_components(g: &AdjacencyList) -> GraphalgResult<Vec<Vec<(usize, 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 edge_stack: Vec<(usize, usize)> = Vec::new();
14    let mut bcc: Vec<Vec<(usize, usize)>> = Vec::new();
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                    edge_stack.push((u.min(v), u.max(v)));
37                    stack.push((v, 0));
38                } else if v != parent[u] && disc[v] < disc[u] {
39                    edge_stack.push((u.min(v), u.max(v)));
40                    low[u] = low[u].min(disc[v]);
41                }
42            } else {
43                let par = parent[u];
44                if par != u {
45                    low[par] = low[par].min(low[u]);
46                    if low[u] >= disc[par] {
47                        let mut cur = Vec::new();
48                        while let Some(e) = edge_stack.pop() {
49                            let target = (par.min(u), par.max(u));
50                            cur.push(e);
51                            if e == target {
52                                break;
53                            }
54                        }
55                        if !cur.is_empty() {
56                            bcc.push(cur);
57                        }
58                    }
59                }
60                stack.pop();
61            }
62        }
63    }
64    Ok(bcc)
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn bcc_single_triangle() {
73        let mut g = AdjacencyList::new(3);
74        g.add_undirected_edge(0, 1).expect("ok");
75        g.add_undirected_edge(1, 2).expect("ok");
76        g.add_undirected_edge(0, 2).expect("ok");
77        let bcc = biconnected_components(&g).expect("ok");
78        assert_eq!(bcc.len(), 1);
79    }
80
81    #[test]
82    fn bcc_two_triangles_joined() {
83        // 0-1-2-0 and 2-3-4-2 share vertex 2
84        let mut g = AdjacencyList::new(5);
85        g.add_undirected_edge(0, 1).expect("ok");
86        g.add_undirected_edge(1, 2).expect("ok");
87        g.add_undirected_edge(0, 2).expect("ok");
88        g.add_undirected_edge(2, 3).expect("ok");
89        g.add_undirected_edge(3, 4).expect("ok");
90        g.add_undirected_edge(2, 4).expect("ok");
91        let bcc = biconnected_components(&g).expect("ok");
92        assert_eq!(bcc.len(), 2);
93    }
94}
oxicuda_graphalg/connectivity/biconnected.rs

oxicuda_graphalg/connectivity/
biconnected.rs
