rust_igraph/algorithms/connectivity/bridges.rs
1//! Bridges (ALGO-CC-014).
2//!
3//! Counterpart of `igraph_bridges()` from
4//! `references/igraph/src/connectivity/components.c:1400-1504`.
5//!
6//! A *bridge* is an edge whose removal increases the number of (weakly)
7//! connected components in the graph. The algorithm is Tarjan-style:
8//! one iterative DFS per weak component, tracking each vertex's
9//! discovery time `vis[v]` and low-link `low[v]` (the lowest discovery
10//! time reachable from `v`'s DFS subtree). When a child's `low > vis[parent]`
11//! the parent-child edge is a bridge.
12//!
13//! To support multigraphs we track the *incoming edge id* for each
14//! vertex (rather than the parent vertex id), so a parallel edge back
15//! to the parent correctly counts as a back-edge. This mirrors
16//! upstream's note at `components.c:1402-1406`.
17
18use crate::core::graph::EdgeId;
19use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
20
21/// Bridges of `graph` — edges whose removal would increase the number
22/// of (weakly) connected components.
23///
24/// Counterpart of `igraph_bridges()`. On directed graphs the input is
25/// treated as undirected (matches upstream's `IGRAPH_ALL` mode default
26/// at `components.c:1417`). Returns edge ids.
27///
28/// # Examples
29///
30/// ```
31/// use rust_igraph::{Graph, bridges};
32///
33/// // Two triangles sharing a single bridge edge: 0-1-2-0, 3-4-5-3, 2-3.
34/// // Only edge id 6 (the 2-3 link) is a bridge.
35/// let mut g = Graph::with_vertices(6);
36/// g.add_edge(0, 1).unwrap(); // edge 0
37/// g.add_edge(1, 2).unwrap(); // edge 1
38/// g.add_edge(2, 0).unwrap(); // edge 2
39/// g.add_edge(3, 4).unwrap(); // edge 3
40/// g.add_edge(4, 5).unwrap(); // edge 4
41/// g.add_edge(5, 3).unwrap(); // edge 5
42/// g.add_edge(2, 3).unwrap(); // edge 6 — bridge
43///
44/// assert_eq!(bridges(&g).unwrap(), vec![6]);
45/// ```
46pub fn bridges(graph: &Graph) -> IgraphResult<Vec<EdgeId>> {
47 let n = graph.vcount();
48 if n == 0 {
49 return Ok(Vec::new());
50 }
51 let n_us = n as usize;
52
53 let mut visited: Vec<bool> = vec![false; n_us];
54 let mut vis: Vec<u32> = vec![0; n_us];
55 let mut low: Vec<u32> = vec![0; n_us];
56 // `incoming_edge[v] = Some(eid)` if v was reached via that edge in
57 // the DFS tree; `None` for roots (and unvisited). Using Option matches
58 // upstream's `incoming_edge[v] = -1` sentinel.
59 let mut incoming_edge: Vec<Option<EdgeId>> = vec![None; n_us];
60
61 // The DFS state is two parallel stacks: `su` (vertex on top of the
62 // "active" stack), `si` (the index into u's incident-edge list to
63 // process next). Mirrors upstream `components.c:1428-1490`.
64 let mut su: Vec<VertexId> = Vec::new();
65 let mut si: Vec<usize> = Vec::new();
66 let mut time: u32 = 0;
67
68 // Pre-cache incident edges (parity with upstream's
69 // `igraph_inclist_init(_, _, IGRAPH_ALL, IGRAPH_LOOPS_TWICE)`).
70 let mut inc: Vec<Vec<EdgeId>> = Vec::with_capacity(n_us);
71 for v in 0..n {
72 inc.push(graph.incident(v)?);
73 }
74
75 let mut bridges_out: Vec<EdgeId> = Vec::new();
76
77 for start in 0..n {
78 if visited[start as usize] {
79 continue;
80 }
81 su.push(start);
82 si.push(0);
83
84 while let Some(u) = su.pop() {
85 let Some(i) = si.pop() else {
86 return Err(IgraphError::Internal("si/su stack invariant broken"));
87 };
88 let u_us = u as usize;
89
90 if i == 0 {
91 visited[u_us] = true;
92 time = time
93 .checked_add(1)
94 .ok_or(IgraphError::Internal("DFS time counter overflow"))?;
95 vis[u_us] = time;
96 low[u_us] = time;
97 }
98
99 let edges = &inc[u_us];
100 if i < edges.len() {
101 // Re-push (u, i+1) so we resume after handling this edge,
102 // then push (v, 0) to descend into the neighbour.
103 su.push(u);
104 si.push(i + 1);
105
106 let edge = edges[i];
107 let v = graph.edge_other(edge, u)?;
108
109 if !visited[v as usize] {
110 incoming_edge[v as usize] = Some(edge);
111 su.push(v);
112 si.push(0);
113 } else if Some(edge) != incoming_edge[u_us] {
114 // Back-edge (not the edge we entered u through).
115 // Update u's low-link to the discovery time of v.
116 if vis[v as usize] < low[u_us] {
117 low[u_us] = vis[v as usize];
118 }
119 }
120 } else {
121 // Done with u — propagate low-link up and check bridge condition.
122 if let Some(edge) = incoming_edge[u_us] {
123 let w = graph.edge_other(edge, u)?; // parent of u in DFS tree
124 let w_us = w as usize;
125 if low[u_us] < low[w_us] {
126 low[w_us] = low[u_us];
127 }
128 if low[u_us] > vis[w_us] {
129 bridges_out.push(edge);
130 }
131 }
132 }
133 }
134 }
135
136 Ok(bridges_out)
137}
138
139#[cfg(test)]
140mod tests {
141 use super::*;
142
143 fn brsorted(g: &Graph) -> Vec<EdgeId> {
144 let mut b = bridges(g).unwrap();
145 b.sort_unstable();
146 b
147 }
148
149 #[test]
150 fn empty_graph_has_no_bridges() {
151 let g = Graph::with_vertices(0);
152 assert!(bridges(&g).unwrap().is_empty());
153 }
154
155 #[test]
156 fn isolated_vertices_have_no_bridges() {
157 let g = Graph::with_vertices(5);
158 assert!(bridges(&g).unwrap().is_empty());
159 }
160
161 #[test]
162 fn cycle_has_no_bridges() {
163 let mut g = Graph::with_vertices(4);
164 g.add_edge(0, 1).unwrap();
165 g.add_edge(1, 2).unwrap();
166 g.add_edge(2, 3).unwrap();
167 g.add_edge(3, 0).unwrap();
168 assert!(bridges(&g).unwrap().is_empty());
169 }
170
171 #[test]
172 fn path_every_edge_is_a_bridge() {
173 // Path 0-1-2-3-4: every one of the 4 edges is a bridge.
174 let mut g = Graph::with_vertices(5);
175 for i in 0..4 {
176 g.add_edge(i, i + 1).unwrap();
177 }
178 assert_eq!(brsorted(&g), vec![0, 1, 2, 3]);
179 }
180
181 #[test]
182 fn cycle_with_pendant_bridges_are_pendant_edges() {
183 // 0-1-2-0 (cycle) + 2-3-4 (pendant): edge 3 (2-3) and edge 4 (3-4) are bridges.
184 let mut g = Graph::with_vertices(5);
185 g.add_edge(0, 1).unwrap(); // 0
186 g.add_edge(1, 2).unwrap(); // 1
187 g.add_edge(2, 0).unwrap(); // 2
188 g.add_edge(2, 3).unwrap(); // 3
189 g.add_edge(3, 4).unwrap(); // 4
190 assert_eq!(brsorted(&g), vec![3, 4]);
191 }
192
193 #[test]
194 fn parallel_edges_make_neither_a_bridge() {
195 // Three parallel edges 0-1: no single edge is a bridge.
196 let mut g = Graph::with_vertices(2);
197 g.add_edge(0, 1).unwrap();
198 g.add_edge(0, 1).unwrap();
199 g.add_edge(0, 1).unwrap();
200 assert!(bridges(&g).unwrap().is_empty());
201 }
202
203 #[test]
204 fn self_loop_is_not_a_bridge() {
205 // 0-self + 0-1: only edge 1 (0-1) is a bridge. Self-loop ignored.
206 let mut g = Graph::with_vertices(2);
207 g.add_edge(0, 0).unwrap(); // 0
208 g.add_edge(0, 1).unwrap(); // 1
209 assert_eq!(brsorted(&g), vec![1]);
210 }
211
212 #[test]
213 fn two_components_each_contributes_independently() {
214 // Path 0-1-2 and Path 3-4-5: every edge is a bridge.
215 let mut g = Graph::with_vertices(6);
216 g.add_edge(0, 1).unwrap();
217 g.add_edge(1, 2).unwrap();
218 g.add_edge(3, 4).unwrap();
219 g.add_edge(4, 5).unwrap();
220 assert_eq!(brsorted(&g), vec![0, 1, 2, 3]);
221 }
222
223 #[test]
224 fn two_triangles_joined_by_bridge() {
225 // Triangle {0,1,2} + triangle {3,4,5} + edge 2-3 (the bridge).
226 let mut g = Graph::with_vertices(6);
227 g.add_edge(0, 1).unwrap();
228 g.add_edge(1, 2).unwrap();
229 g.add_edge(2, 0).unwrap();
230 g.add_edge(3, 4).unwrap();
231 g.add_edge(4, 5).unwrap();
232 g.add_edge(5, 3).unwrap();
233 g.add_edge(2, 3).unwrap(); // edge 6 — bridge
234 assert_eq!(brsorted(&g), vec![6]);
235 }
236
237 #[test]
238 fn star_every_edge_is_a_bridge() {
239 // Centre 0, leaves 1..4: 4 bridges.
240 let mut g = Graph::with_vertices(5);
241 for v in 1..5 {
242 g.add_edge(0, v).unwrap();
243 }
244 assert_eq!(brsorted(&g), vec![0, 1, 2, 3]);
245 }
246}