rust_igraph/algorithms/traversal/
bfs.rs

1//! Breadth-first search.
2//!
3//! Counterpart of `igraph_bfs()` from `references/igraph/src/properties/bfs.c`.
4//! - Phase 0 [`bfs`]: simplest variant, returns the visit order.
5//! - Phase 1 [`bfs_tree`] (ALGO-TR-001): full multi-output variant,
6//!   returns the visit order + per-vertex distance + BFS-tree parent.
7
8use std::collections::VecDeque;
9
10use crate::core::{Graph, IgraphResult, VertexId};
11
12/// Result of a multi-output BFS scan from a single root. Returned by
13/// [`bfs_tree`].
14#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct BfsTree {
16    /// Vertices reachable from the root, in BFS visit order.
17    pub order: Vec<VertexId>,
18    /// `distances[v] == Some(d)` if `v` is reachable from the root in
19    /// `d` edges (`d == 0` for the root); `None` if unreachable.
20    pub distances: Vec<Option<u32>>,
21    /// `parents[v] == Some(p)` if `v` was BFS-discovered via `p`; `None`
22    /// for the root and for unreachable vertices.
23    pub parents: Vec<Option<VertexId>>,
24}
25
26/// Multi-output BFS from `root`. Returns visit order, per-vertex
27/// distances, and per-vertex BFS-tree parent in a single pass.
28///
29/// Counterpart of `igraph_bfs(_, root, _, _, &order, _, &father, &dist, _, _)`
30/// — the common subset of the upstream callback-driven variant.
31///
32/// For directed graphs traversal follows out-edges (matching upstream's
33/// `IGRAPH_OUT` mode default). Errors if `root` is out of range.
34///
35/// # Examples
36///
37/// ```
38/// use rust_igraph::{Graph, bfs_tree};
39///
40/// // Tree:
41/// //     0
42/// //    / \
43/// //   1   2
44/// //   |
45/// //   3
46/// let mut g = Graph::with_vertices(4);
47/// g.add_edge(0, 1).unwrap();
48/// g.add_edge(0, 2).unwrap();
49/// g.add_edge(1, 3).unwrap();
50///
51/// let r = bfs_tree(&g, 0).unwrap();
52/// assert_eq!(r.order, vec![0, 1, 2, 3]);
53/// assert_eq!(r.distances, vec![Some(0), Some(1), Some(1), Some(2)]);
54/// assert_eq!(r.parents, vec![None, Some(0), Some(0), Some(1)]);
55/// ```
56pub fn bfs_tree(graph: &Graph, root: VertexId) -> IgraphResult<BfsTree> {
57    graph.neighbors(root)?; // surface VertexOutOfRange
58
59    let n = graph.vcount();
60    let n_us = n as usize;
61    let mut distances: Vec<Option<u32>> = vec![None; n_us];
62    let mut parents: Vec<Option<VertexId>> = vec![None; n_us];
63    let mut order: Vec<VertexId> = Vec::with_capacity(n_us);
64    let mut queue: VecDeque<VertexId> = VecDeque::new();
65
66    distances[root as usize] = Some(0);
67    order.push(root);
68    queue.push_back(root);
69
70    while let Some(v) = queue.pop_front() {
71        let v_dist = distances[v as usize].expect("dequeued vertex is visited");
72        let next_dist = v_dist
73            .checked_add(1)
74            .ok_or(crate::core::IgraphError::Internal(
75                "BFS distance overflow (graph diameter exceeds u32::MAX)",
76            ))?;
77        for w in graph.neighbors(v)? {
78            if distances[w as usize].is_none() {
79                distances[w as usize] = Some(next_dist);
80                parents[w as usize] = Some(v);
81                order.push(w);
82                queue.push_back(w);
83            }
84        }
85    }
86
87    Ok(BfsTree {
88        order,
89        distances,
90        parents,
91    })
92}
93
94/// Visit order of vertices reachable from `root`, in BFS order.
95///
96/// Vertices unreachable from `root` are not included. Errors if `root` is not
97/// a valid vertex.
98///
99/// # Examples
100///
101/// ```
102/// use rust_igraph::{Graph, bfs};
103///
104/// // 0 - 1 - 3
105/// // |
106/// // 2
107/// let mut g = Graph::with_vertices(4);
108/// g.add_edge(0, 1).unwrap();
109/// g.add_edge(0, 2).unwrap();
110/// g.add_edge(1, 3).unwrap();
111///
112/// let order = bfs(&g, 0).unwrap();
113/// assert_eq!(order, vec![0, 1, 2, 3]);
114/// ```
115pub fn bfs(graph: &Graph, root: VertexId) -> IgraphResult<Vec<VertexId>> {
116    // Validate root via the neighbor lookup; this surfaces VertexOutOfRange.
117    graph.neighbors(root)?;
118
119    let n = graph.vcount();
120    let mut visited = vec![false; n as usize];
121    let mut order: Vec<VertexId> = Vec::with_capacity(n as usize);
122    let mut queue: VecDeque<VertexId> = VecDeque::new();
123
124    visited[root as usize] = true;
125    order.push(root);
126    queue.push_back(root);
127
128    while let Some(v) = queue.pop_front() {
129        // `neighbors` returns Vec<VertexId> on the new indexed-edgelist
130        // backend (ALGO-CORE-001a); a contiguous slice is not free anymore.
131        for w in graph.neighbors(v)? {
132            if !visited[w as usize] {
133                visited[w as usize] = true;
134                order.push(w);
135                queue.push_back(w);
136            }
137        }
138    }
139
140    Ok(order)
141}
142
143#[cfg(test)]
144mod tests {
145    use super::*;
146
147    fn path_graph(n: u32) -> Graph {
148        let mut g = Graph::with_vertices(n);
149        for i in 0..n.saturating_sub(1) {
150            g.add_edge(i, i + 1).unwrap();
151        }
152        g
153    }
154
155    #[test]
156    fn empty_graph_errors_on_any_root() {
157        let g = Graph::with_vertices(0);
158        let err = bfs(&g, 0).unwrap_err();
159        assert!(matches!(
160            err,
161            crate::core::IgraphError::VertexOutOfRange { id: 0, n: 0 }
162        ));
163    }
164
165    #[test]
166    fn single_vertex_visits_self() {
167        let g = Graph::with_vertices(1);
168        assert_eq!(bfs(&g, 0).unwrap(), vec![0]);
169    }
170
171    #[test]
172    fn path_visits_in_order() {
173        let g = path_graph(5);
174        assert_eq!(bfs(&g, 0).unwrap(), vec![0, 1, 2, 3, 4]);
175    }
176
177    #[test]
178    fn bfs_layers_breadth_first_not_depth_first() {
179        // 0 -- 1 -- 3
180        // |
181        // 2
182        let mut g = Graph::with_vertices(4);
183        g.add_edge(0, 1).unwrap();
184        g.add_edge(0, 2).unwrap();
185        g.add_edge(1, 3).unwrap();
186        // BFS order from 0 must visit both 1 and 2 before 3.
187        let order = bfs(&g, 0).unwrap();
188        assert_eq!(order[0], 0);
189        let pos_3 = order.iter().position(|&x| x == 3).unwrap();
190        let pos_1 = order.iter().position(|&x| x == 1).unwrap();
191        let pos_2 = order.iter().position(|&x| x == 2).unwrap();
192        assert!(pos_3 > pos_1 && pos_3 > pos_2);
193    }
194
195    #[test]
196    fn unreachable_vertex_excluded() {
197        let mut g = Graph::with_vertices(3);
198        g.add_edge(0, 1).unwrap();
199        // vertex 2 is isolated.
200        let order = bfs(&g, 0).unwrap();
201        assert_eq!(order, vec![0, 1]);
202    }
203
204    #[test]
205    fn invalid_root_errors() {
206        let g = Graph::with_vertices(2);
207        let err = bfs(&g, 5).unwrap_err();
208        match err {
209            crate::core::IgraphError::VertexOutOfRange { id, n } => {
210                assert_eq!(id, 5);
211                assert_eq!(n, 2);
212            }
213            other => panic!("unexpected error: {other:?}"),
214        }
215    }
216
217    #[test]
218    fn bfs_tree_returns_full_state_for_a_tree() {
219        // Star centred at 0, leaves 1, 2, 3.
220        let mut g = Graph::with_vertices(4);
221        g.add_edge(0, 1).unwrap();
222        g.add_edge(0, 2).unwrap();
223        g.add_edge(0, 3).unwrap();
224        let r = bfs_tree(&g, 0).unwrap();
225        assert_eq!(r.order, vec![0, 1, 2, 3]);
226        assert_eq!(r.distances, vec![Some(0), Some(1), Some(1), Some(1)]);
227        assert_eq!(r.parents, vec![None, Some(0), Some(0), Some(0)]);
228    }
229
230    #[test]
231    fn bfs_tree_path_5_is_chain() {
232        let g = path_graph(5);
233        let r = bfs_tree(&g, 0).unwrap();
234        assert_eq!(r.order, vec![0, 1, 2, 3, 4]);
235        assert_eq!(
236            r.distances,
237            vec![Some(0), Some(1), Some(2), Some(3), Some(4)]
238        );
239        assert_eq!(r.parents, vec![None, Some(0), Some(1), Some(2), Some(3)]);
240    }
241
242    #[test]
243    fn bfs_tree_unreachable_vertices_have_none() {
244        let mut g = Graph::with_vertices(4);
245        g.add_edge(0, 1).unwrap();
246        // 2 and 3 isolated.
247        let r = bfs_tree(&g, 0).unwrap();
248        assert_eq!(r.order, vec![0, 1]);
249        assert_eq!(r.distances, vec![Some(0), Some(1), None, None]);
250        assert_eq!(r.parents, vec![None, Some(0), None, None]);
251    }
252
253    #[test]
254    fn bfs_tree_invalid_root_errors() {
255        let g = Graph::with_vertices(3);
256        assert!(bfs_tree(&g, 7).is_err());
257    }
258
259    #[test]
260    fn bfs_tree_directed_uses_out_edges() {
261        // 0 -> 1 -> 2, 1 -> 3: from 0, all 4 reachable.
262        let mut g = Graph::new(4, true).unwrap();
263        g.add_edge(0, 1).unwrap();
264        g.add_edge(1, 2).unwrap();
265        g.add_edge(1, 3).unwrap();
266        let r = bfs_tree(&g, 0).unwrap();
267        assert_eq!(r.distances, vec![Some(0), Some(1), Some(2), Some(2)]);
268        assert_eq!(r.parents[0], None);
269        assert_eq!(r.parents[1], Some(0));
270        assert_eq!(r.parents[2], Some(1));
271        assert_eq!(r.parents[3], Some(1));
272        // From vertex 2, only 2 is reachable (no out-edges).
273        let r2 = bfs_tree(&g, 2).unwrap();
274        assert_eq!(r2.order, vec![2]);
275    }
276}
rust_igraph/algorithms/traversal/bfs.rs

rust_igraph/algorithms/traversal/
bfs.rs
