uni_algo/algo/algorithms/
bridges.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Bridge Detection Algorithm.
5//!
6//! Finds bridges (cut-edges) in the graph. Removing a bridge increases the number of connected components.
7//! This implementation treats the graph as undirected if `include_reverse` was used in projection.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use uni_common::core::id::Vid;
12
13pub struct Bridges;
14
15#[derive(Debug, Clone, Default)]
16pub struct BridgesConfig {}
17
18pub struct BridgesResult {
19    pub bridges: Vec<(Vid, Vid)>,
20}
21
22impl Algorithm for Bridges {
23    type Config = BridgesConfig;
24    type Result = BridgesResult;
25
26    fn name() -> &'static str {
27        "bridges"
28    }
29
30    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
31        let n = graph.vertex_count();
32        if n == 0 {
33            return BridgesResult {
34                bridges: Vec::new(),
35            };
36        }
37
38        let mut disc = vec![u32::MAX; n];
39        let mut low = vec![u32::MAX; n];
40        let mut time = 0;
41        let mut bridges = Vec::new();
42
43        for i in 0..n {
44            if disc[i] == u32::MAX {
45                find_bridges(
46                    i as u32,
47                    u32::MAX, // no parent
48                    graph,
49                    &mut disc,
50                    &mut low,
51                    &mut time,
52                    &mut bridges,
53                );
54            }
55        }
56
57        let mapped_bridges = bridges
58            .into_iter()
59            .map(|(u, v)| (graph.to_vid(u), graph.to_vid(v)))
60            .collect();
61
62        BridgesResult {
63            bridges: mapped_bridges,
64        }
65    }
66}
67
68fn find_bridges(
69    u: u32,
70    p: u32, // parent
71    graph: &GraphProjection,
72    disc: &mut [u32],
73    low: &mut [u32],
74    time: &mut u32,
75    bridges: &mut Vec<(u32, u32)>,
76) {
77    disc[u as usize] = *time;
78    low[u as usize] = *time;
79    *time += 1;
80
81    // Helper to process neighbor
82    let mut process_neighbor = |v: u32| {
83        if v == p {
84            return;
85        }
86        if disc[v as usize] != u32::MAX {
87            low[u as usize] = std::cmp::min(low[u as usize], disc[v as usize]);
88        } else {
89            find_bridges(v, u, graph, disc, low, time, bridges);
90            low[u as usize] = std::cmp::min(low[u as usize], low[v as usize]);
91            if low[v as usize] > disc[u as usize] {
92                bridges.push((u, v));
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 (if available, treating as undirected)
103    if graph.has_reverse() {
104        for &v in graph.in_neighbors(u) {
105            process_neighbor(v);
106        }
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113    use crate::algo::test_utils::build_test_graph;
114
115    #[test]
116    fn test_bridges_simple() {
117        // 0 - 1 - 2
118        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
119        // Undirected: need both directions for build_test_graph usually,
120        // or ensure algorithm treats directed as undirected.
121        // Our algorithm does treat directed edges.
122        // If we want undirected behavior test, we should provide edges such that graph connects.
123        // 0->1, 1->2.
124        // Bridges: (0,1), (1,2)
125        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
126        let graph = build_test_graph(vids, edges); // directed
127
128        let result = Bridges::run(&graph, BridgesConfig::default());
129        assert_eq!(result.bridges.len(), 2);
130    }
131
132    #[test]
133    fn test_bridges_cycle() {
134        // 0 - 1 - 2 - 0 (Triangle)
135        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
136        let edges = vec![
137            (Vid::from(0), Vid::from(1)),
138            (Vid::from(1), Vid::from(2)),
139            (Vid::from(2), Vid::from(0)),
140        ];
141        let graph = build_test_graph(vids, edges);
142
143        let result = Bridges::run(&graph, BridgesConfig::default());
144        assert_eq!(result.bridges.len(), 0);
145    }
146
147    #[test]
148    fn test_bridges_dumbbell() {
149        // 0-1-2-3, 2-4-5-2 (Loop at end)
150        // 0->1 (bridge)
151        // 1->2 (bridge)
152        // 2->3 (bridge)
153        // 2->4, 4->5, 5->2 (cycle)
154        // Expected bridges: (0,1), (1,2), (2,3)
155        // Note: graph is directed in test utils.
156
157        let vids = (0..6).map(Vid::from).collect();
158        let edges = vec![
159            (Vid::from(0), Vid::from(1)),
160            (Vid::from(1), Vid::from(2)),
161            (Vid::from(2), Vid::from(3)),
162            (Vid::from(2), Vid::from(4)),
163            (Vid::from(4), Vid::from(5)),
164            (Vid::from(5), Vid::from(2)),
165        ];
166        let graph = build_test_graph(vids, edges);
167
168        let result = Bridges::run(&graph, BridgesConfig::default());
169        assert_eq!(result.bridges.len(), 3);
170        // Check contents?
171    }
172}
uni_algo/algo/algorithms/bridges.rs

uni_algo/algo/algorithms/
bridges.rs
