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 i = si.pop().expect("si parallel to su");
86 let u_us = u as usize;
87
88 if i == 0 {
89 visited[u_us] = true;
90 time = time
91 .checked_add(1)
92 .ok_or(IgraphError::Internal("DFS time counter overflow"))?;
93 vis[u_us] = time;
94 low[u_us] = time;
95 }
96
97 let edges = &inc[u_us];
98 if i < edges.len() {
99 // Re-push (u, i+1) so we resume after handling this edge,
100 // then push (v, 0) to descend into the neighbour.
101 su.push(u);
102 si.push(i + 1);
103
104 let edge = edges[i];
105 let v = graph.edge_other(edge, u)?;
106
107 if !visited[v as usize] {
108 incoming_edge[v as usize] = Some(edge);
109 su.push(v);
110 si.push(0);
111 } else if Some(edge) != incoming_edge[u_us] {
112 // Back-edge (not the edge we entered u through).
113 // Update u's low-link to the discovery time of v.
114 if vis[v as usize] < low[u_us] {
115 low[u_us] = vis[v as usize];
116 }
117 }
118 } else {
119 // Done with u — propagate low-link up and check bridge condition.
120 if let Some(edge) = incoming_edge[u_us] {
121 let w = graph.edge_other(edge, u)?; // parent of u in DFS tree
122 let w_us = w as usize;
123 if low[u_us] < low[w_us] {
124 low[w_us] = low[u_us];
125 }
126 if low[u_us] > vis[w_us] {
127 bridges_out.push(edge);
128 }
129 }
130 }
131 }
132 }
133
134 Ok(bridges_out)
135}
136
137#[cfg(test)]
138mod tests {
139 use super::*;
140
141 fn brsorted(g: &Graph) -> Vec<EdgeId> {
142 let mut b = bridges(g).unwrap();
143 b.sort_unstable();
144 b
145 }
146
147 #[test]
148 fn empty_graph_has_no_bridges() {
149 let g = Graph::with_vertices(0);
150 assert!(bridges(&g).unwrap().is_empty());
151 }
152
153 #[test]
154 fn isolated_vertices_have_no_bridges() {
155 let g = Graph::with_vertices(5);
156 assert!(bridges(&g).unwrap().is_empty());
157 }
158
159 #[test]
160 fn cycle_has_no_bridges() {
161 let mut g = Graph::with_vertices(4);
162 g.add_edge(0, 1).unwrap();
163 g.add_edge(1, 2).unwrap();
164 g.add_edge(2, 3).unwrap();
165 g.add_edge(3, 0).unwrap();
166 assert!(bridges(&g).unwrap().is_empty());
167 }
168
169 #[test]
170 fn path_every_edge_is_a_bridge() {
171 // Path 0-1-2-3-4: every one of the 4 edges is a bridge.
172 let mut g = Graph::with_vertices(5);
173 for i in 0..4 {
174 g.add_edge(i, i + 1).unwrap();
175 }
176 assert_eq!(brsorted(&g), vec![0, 1, 2, 3]);
177 }
178
179 #[test]
180 fn cycle_with_pendant_bridges_are_pendant_edges() {
181 // 0-1-2-0 (cycle) + 2-3-4 (pendant): edge 3 (2-3) and edge 4 (3-4) are bridges.
182 let mut g = Graph::with_vertices(5);
183 g.add_edge(0, 1).unwrap(); // 0
184 g.add_edge(1, 2).unwrap(); // 1
185 g.add_edge(2, 0).unwrap(); // 2
186 g.add_edge(2, 3).unwrap(); // 3
187 g.add_edge(3, 4).unwrap(); // 4
188 assert_eq!(brsorted(&g), vec![3, 4]);
189 }
190
191 #[test]
192 fn parallel_edges_make_neither_a_bridge() {
193 // Three parallel edges 0-1: no single edge is a bridge.
194 let mut g = Graph::with_vertices(2);
195 g.add_edge(0, 1).unwrap();
196 g.add_edge(0, 1).unwrap();
197 g.add_edge(0, 1).unwrap();
198 assert!(bridges(&g).unwrap().is_empty());
199 }
200
201 #[test]
202 fn self_loop_is_not_a_bridge() {
203 // 0-self + 0-1: only edge 1 (0-1) is a bridge. Self-loop ignored.
204 let mut g = Graph::with_vertices(2);
205 g.add_edge(0, 0).unwrap(); // 0
206 g.add_edge(0, 1).unwrap(); // 1
207 assert_eq!(brsorted(&g), vec![1]);
208 }
209
210 #[test]
211 fn two_components_each_contributes_independently() {
212 // Path 0-1-2 and Path 3-4-5: every edge is a bridge.
213 let mut g = Graph::with_vertices(6);
214 g.add_edge(0, 1).unwrap();
215 g.add_edge(1, 2).unwrap();
216 g.add_edge(3, 4).unwrap();
217 g.add_edge(4, 5).unwrap();
218 assert_eq!(brsorted(&g), vec![0, 1, 2, 3]);
219 }
220
221 #[test]
222 fn two_triangles_joined_by_bridge() {
223 // Triangle {0,1,2} + triangle {3,4,5} + edge 2-3 (the bridge).
224 let mut g = Graph::with_vertices(6);
225 g.add_edge(0, 1).unwrap();
226 g.add_edge(1, 2).unwrap();
227 g.add_edge(2, 0).unwrap();
228 g.add_edge(3, 4).unwrap();
229 g.add_edge(4, 5).unwrap();
230 g.add_edge(5, 3).unwrap();
231 g.add_edge(2, 3).unwrap(); // edge 6 — bridge
232 assert_eq!(brsorted(&g), vec![6]);
233 }
234
235 #[test]
236 fn star_every_edge_is_a_bridge() {
237 // Centre 0, leaves 1..4: 4 bridges.
238 let mut g = Graph::with_vertices(5);
239 for v in 1..5 {
240 g.add_edge(0, v).unwrap();
241 }
242 assert_eq!(brsorted(&g), vec![0, 1, 2, 3]);
243 }
244}