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 ships the simplest variant: from one root, returning the visit
5//! order. Full callback-driven BFS (vids/layers/parents/dist/order/pred/succ)
6//! lands in `ALGO-TR-001`.
7
8use std::collections::VecDeque;
9
10use crate::core::{Graph, IgraphResult, VertexId};
11
12/// Visit order of vertices reachable from `root`, in BFS order.
13///
14/// Vertices unreachable from `root` are not included. Errors if `root` is not
15/// a valid vertex.
16///
17/// # Examples
18///
19/// ```
20/// use rust_igraph::{Graph, bfs};
21///
22/// // 0 - 1 - 3
23/// // |
24/// // 2
25/// let mut g = Graph::with_vertices(4);
26/// g.add_edge(0, 1).unwrap();
27/// g.add_edge(0, 2).unwrap();
28/// g.add_edge(1, 3).unwrap();
29///
30/// let order = bfs(&g, 0).unwrap();
31/// assert_eq!(order, vec![0, 1, 2, 3]);
32/// ```
33pub fn bfs(graph: &Graph, root: VertexId) -> IgraphResult<Vec<VertexId>> {
34    // Validate root via the neighbor lookup; this surfaces VertexOutOfRange.
35    graph.neighbors(root)?;
36
37    let n = graph.vcount();
38    let mut visited = vec![false; n as usize];
39    let mut order: Vec<VertexId> = Vec::with_capacity(n as usize);
40    let mut queue: VecDeque<VertexId> = VecDeque::new();
41
42    visited[root as usize] = true;
43    order.push(root);
44    queue.push_back(root);
45
46    while let Some(v) = queue.pop_front() {
47        for &w in graph.neighbors(v)? {
48            if !visited[w as usize] {
49                visited[w as usize] = true;
50                order.push(w);
51                queue.push_back(w);
52            }
53        }
54    }
55
56    Ok(order)
57}
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    fn path_graph(n: u32) -> Graph {
64        let mut g = Graph::with_vertices(n);
65        for i in 0..n.saturating_sub(1) {
66            g.add_edge(i, i + 1).unwrap();
67        }
68        g
69    }
70
71    #[test]
72    fn empty_graph_errors_on_any_root() {
73        let g = Graph::with_vertices(0);
74        let err = bfs(&g, 0).unwrap_err();
75        assert!(matches!(
76            err,
77            crate::core::IgraphError::VertexOutOfRange { id: 0, n: 0 }
78        ));
79    }
80
81    #[test]
82    fn single_vertex_visits_self() {
83        let g = Graph::with_vertices(1);
84        assert_eq!(bfs(&g, 0).unwrap(), vec![0]);
85    }
86
87    #[test]
88    fn path_visits_in_order() {
89        let g = path_graph(5);
90        assert_eq!(bfs(&g, 0).unwrap(), vec![0, 1, 2, 3, 4]);
91    }
92
93    #[test]
94    fn bfs_layers_breadth_first_not_depth_first() {
95        // 0 -- 1 -- 3
96        // |
97        // 2
98        let mut g = Graph::with_vertices(4);
99        g.add_edge(0, 1).unwrap();
100        g.add_edge(0, 2).unwrap();
101        g.add_edge(1, 3).unwrap();
102        // BFS order from 0 must visit both 1 and 2 before 3.
103        let order = bfs(&g, 0).unwrap();
104        assert_eq!(order[0], 0);
105        let pos_3 = order.iter().position(|&x| x == 3).unwrap();
106        let pos_1 = order.iter().position(|&x| x == 1).unwrap();
107        let pos_2 = order.iter().position(|&x| x == 2).unwrap();
108        assert!(pos_3 > pos_1 && pos_3 > pos_2);
109    }
110
111    #[test]
112    fn unreachable_vertex_excluded() {
113        let mut g = Graph::with_vertices(3);
114        g.add_edge(0, 1).unwrap();
115        // vertex 2 is isolated.
116        let order = bfs(&g, 0).unwrap();
117        assert_eq!(order, vec![0, 1]);
118    }
119
120    #[test]
121    fn invalid_root_errors() {
122        let g = Graph::with_vertices(2);
123        let err = bfs(&g, 5).unwrap_err();
124        match err {
125            crate::core::IgraphError::VertexOutOfRange { id, n } => {
126                assert_eq!(id, 5);
127                assert_eq!(n, 2);
128            }
129            other => panic!("unexpected error: {other:?}"),
130        }
131    }
132}
rust_igraph/algorithms/traversal/bfs.rs

rust_igraph/algorithms/traversal/
bfs.rs
