uni_algo/algo/algorithms/
articulation_points.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Articulation Points Algorithm.
5//!
6//! Finds articulation points (cut vertices) in the graph. Removing an articulation point
7//! increases the number of connected components.
8//! This implementation treats the graph as undirected if `include_reverse` was used in projection.
9
10use crate::algo::GraphProjection;
11use crate::algo::algorithms::Algorithm;
12use uni_common::core::id::Vid;
13
14pub struct ArticulationPoints;
15
16#[derive(Debug, Clone, Default)]
17pub struct ArticulationPointsConfig {}
18
19pub struct ArticulationPointsResult {
20    pub points: Vec<Vid>,
21}
22
23impl Algorithm for ArticulationPoints {
24    type Config = ArticulationPointsConfig;
25    type Result = ArticulationPointsResult;
26
27    fn name() -> &'static str {
28        "articulation_points"
29    }
30
31    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
32        let n = graph.vertex_count();
33        if n == 0 {
34            return ArticulationPointsResult { points: Vec::new() };
35        }
36
37        let mut disc = vec![u32::MAX; n];
38        let mut low = vec![u32::MAX; n];
39        let mut time = 0;
40        let mut is_ap = vec![false; n];
41
42        for i in 0..n {
43            if disc[i] == u32::MAX {
44                find_aps(
45                    i as u32,
46                    u32::MAX, // no parent
47                    graph,
48                    &mut disc,
49                    &mut low,
50                    &mut time,
51                    &mut is_ap,
52                );
53            }
54        }
55
56        let points = is_ap
57            .into_iter()
58            .enumerate()
59            .filter(|(_, is_ap)| *is_ap)
60            .map(|(i, _)| graph.to_vid(i as u32))
61            .collect();
62
63        ArticulationPointsResult { points }
64    }
65}
66
67fn find_aps(
68    u: u32,
69    p: u32, // parent
70    graph: &GraphProjection,
71    disc: &mut [u32],
72    low: &mut [u32],
73    time: &mut u32,
74    is_ap: &mut [bool],
75) {
76    let mut children = 0;
77    disc[u as usize] = *time;
78    low[u as usize] = *time;
79    *time += 1;
80
81    let mut process_neighbor = |v: u32| {
82        if v == p {
83            return;
84        }
85        if disc[v as usize] != u32::MAX {
86            low[u as usize] = std::cmp::min(low[u as usize], disc[v as usize]);
87        } else {
88            children += 1;
89            find_aps(v, u, graph, disc, low, time, is_ap);
90            low[u as usize] = std::cmp::min(low[u as usize], low[v as usize]);
91            if p != u32::MAX && low[v as usize] >= disc[u as usize] {
92                is_ap[u as usize] = true;
93            }
94        }
95    };
96
97    // Iterate out neighbors
98    for &v in graph.out_neighbors(u) {
99        process_neighbor(v);
100    }
101
102    // Iterate in neighbors
103    if graph.has_reverse() {
104        for &v in graph.in_neighbors(u) {
105            process_neighbor(v);
106        }
107    }
108
109    if p == u32::MAX && children > 1 {
110        is_ap[u as usize] = true;
111    }
112}
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117    use crate::algo::test_utils::build_test_graph;
118
119    #[test]
120    fn test_articulation_points_line() {
121        // 0 - 1 - 2
122        // 1 is AP.
123        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
124        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
125        let graph = build_test_graph(vids, edges);
126
127        let result = ArticulationPoints::run(&graph, ArticulationPointsConfig::default());
128        assert_eq!(result.points.len(), 1);
129        assert_eq!(result.points[0], Vid::from(1));
130    }
131
132    #[test]
133    fn test_articulation_points_cycle() {
134        // 0 - 1 - 2 - 0
135        // No APs.
136        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
137        let edges = vec![
138            (Vid::from(0), Vid::from(1)),
139            (Vid::from(1), Vid::from(2)),
140            (Vid::from(2), Vid::from(0)),
141        ];
142        let graph = build_test_graph(vids, edges);
143
144        let result = ArticulationPoints::run(&graph, ArticulationPointsConfig::default());
145        assert_eq!(result.points.len(), 0);
146    }
147}
uni_algo/algo/algorithms/articulation_points.rs

uni_algo/algo/algorithms/
articulation_points.rs
