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//! - [`bfs_simple`]: mode-aware BFS with layer boundaries. Counterpart
8//!   of `igraph_bfs_simple` from `references/igraph/src/graph/visitors.c`.
9
10use std::collections::VecDeque;
11
12use crate::core::{Graph, IgraphResult, VertexId};
13
14/// Result of a multi-output BFS scan from a single root. Returned by
15/// [`bfs_tree`].
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct BfsTree {
18    /// Vertices reachable from the root, in BFS visit order.
19    pub order: Vec<VertexId>,
20    /// `distances[v] == Some(d)` if `v` is reachable from the root in
21    /// `d` edges (`d == 0` for the root); `None` if unreachable.
22    pub distances: Vec<Option<u32>>,
23    /// `parents[v] == Some(p)` if `v` was BFS-discovered via `p`; `None`
24    /// for the root and for unreachable vertices.
25    pub parents: Vec<Option<VertexId>>,
26}
27
28/// Multi-output BFS from `root`. Returns visit order, per-vertex
29/// distances, and per-vertex BFS-tree parent in a single pass.
30///
31/// Counterpart of `igraph_bfs(_, root, _, _, &order, _, &father, &dist, _, _)`
32/// — the common subset of the upstream callback-driven variant.
33///
34/// For directed graphs traversal follows out-edges (matching upstream's
35/// `IGRAPH_OUT` mode default). Errors if `root` is out of range.
36///
37/// # Examples
38///
39/// ```
40/// use rust_igraph::{Graph, bfs_tree};
41///
42/// // Tree:
43/// //     0
44/// //    / \
45/// //   1   2
46/// //   |
47/// //   3
48/// let mut g = Graph::with_vertices(4);
49/// g.add_edge(0, 1).unwrap();
50/// g.add_edge(0, 2).unwrap();
51/// g.add_edge(1, 3).unwrap();
52///
53/// let r = bfs_tree(&g, 0).unwrap();
54/// assert_eq!(r.order, vec![0, 1, 2, 3]);
55/// assert_eq!(r.distances, vec![Some(0), Some(1), Some(1), Some(2)]);
56/// assert_eq!(r.parents, vec![None, Some(0), Some(0), Some(1)]);
57/// ```
58pub fn bfs_tree(graph: &Graph, root: VertexId) -> IgraphResult<BfsTree> {
59    graph.neighbors_iter(root)?; // validate root vertex
60
61    let n = graph.vcount();
62    let n_us = n as usize;
63    let mut distances: Vec<Option<u32>> = vec![None; n_us];
64    let mut parents: Vec<Option<VertexId>> = vec![None; n_us];
65    let mut order: Vec<VertexId> = Vec::with_capacity(n_us);
66    let mut queue: VecDeque<VertexId> = VecDeque::new();
67
68    distances[root as usize] = Some(0);
69    order.push(root);
70    queue.push_back(root);
71
72    while let Some(v) = queue.pop_front() {
73        let v_dist = distances[v as usize].ok_or(crate::core::IgraphError::Internal(
74            "dequeued vertex has no distance",
75        ))?;
76        let next_dist = v_dist
77            .checked_add(1)
78            .ok_or(crate::core::IgraphError::Internal(
79                "BFS distance overflow (graph diameter exceeds u32::MAX)",
80            ))?;
81        for w in graph.neighbors_iter(v)? {
82            if distances[w as usize].is_none() {
83                distances[w as usize] = Some(next_dist);
84                parents[w as usize] = Some(v);
85                order.push(w);
86                queue.push_back(w);
87            }
88        }
89    }
90
91    Ok(BfsTree {
92        order,
93        distances,
94        parents,
95    })
96}
97
98/// Visit order of vertices reachable from `root`, in BFS order.
99///
100/// Vertices unreachable from `root` are not included. Errors if `root` is not
101/// a valid vertex.
102///
103/// # Examples
104///
105/// ```
106/// use rust_igraph::{Graph, bfs};
107///
108/// // 0 - 1 - 3
109/// // |
110/// // 2
111/// let mut g = Graph::with_vertices(4);
112/// g.add_edge(0, 1).unwrap();
113/// g.add_edge(0, 2).unwrap();
114/// g.add_edge(1, 3).unwrap();
115///
116/// let order = bfs(&g, 0).unwrap();
117/// assert_eq!(order, vec![0, 1, 2, 3]);
118/// ```
119pub fn bfs(graph: &Graph, root: VertexId) -> IgraphResult<Vec<VertexId>> {
120    graph.neighbors_iter(root)?; // validate root
121
122    let n = graph.vcount();
123    let mut visited = vec![false; n as usize];
124    let mut order: Vec<VertexId> = Vec::with_capacity(n as usize);
125    let mut queue: VecDeque<VertexId> = VecDeque::new();
126
127    visited[root as usize] = true;
128    order.push(root);
129    queue.push_back(root);
130
131    while let Some(v) = queue.pop_front() {
132        for w in graph.neighbors_iter(v)? {
133            if !visited[w as usize] {
134                visited[w as usize] = true;
135                order.push(w);
136                queue.push_back(w);
137            }
138        }
139    }
140
141    Ok(order)
142}
143
144/// Direction mode for [`bfs_simple`].
145#[derive(Debug, Clone, Copy, PartialEq, Eq)]
146pub enum BfsMode {
147    /// Follow outgoing edges (default for directed graphs).
148    Out,
149    /// Follow incoming edges.
150    In,
151    /// Ignore edge direction (always used for undirected graphs).
152    All,
153}
154
155/// Result of [`bfs_simple`].
156#[derive(Debug, Clone, PartialEq, Eq)]
157pub struct BfsSimple {
158    /// Vertices visited during the traversal, in BFS order.
159    pub order: Vec<VertexId>,
160    /// Layer boundary indices into [`order`](Self::order). Vertices at
161    /// distance `d` from the root are `order[layers[d]..layers[d+1]]`.
162    /// The length is `max_distance + 2`.
163    pub layers: Vec<usize>,
164    /// `parents[v] == Some(p)` if vertex `v` was discovered via `p`;
165    /// `parents[root] == None` (root has no parent).
166    /// `parents[v] == None` for unreachable vertices as well.
167    /// To distinguish root from unreachable, check `order[0] == v`.
168    pub parents: Vec<Option<VertexId>>,
169}
170
171/// Mode-aware BFS from a single root, returning visit order, layer
172/// boundaries, and BFS-tree parents.
173///
174/// Counterpart of `igraph_bfs_simple` from
175/// `references/igraph/src/graph/visitors.c`.
176///
177/// For undirected graphs the `mode` parameter is ignored (edges are
178/// always treated as bidirectional). For directed graphs, [`BfsMode::Out`]
179/// follows outgoing edges, [`BfsMode::In`] follows incoming edges, and
180/// [`BfsMode::All`] ignores direction.
181///
182/// # Examples
183///
184/// ```
185/// use rust_igraph::{Graph, BfsMode, bfs_simple};
186///
187/// let mut g = Graph::new(4, true).unwrap();
188/// g.add_edge(0, 1).unwrap();
189/// g.add_edge(0, 2).unwrap();
190/// g.add_edge(1, 3).unwrap();
191///
192/// let r = bfs_simple(&g, 0, BfsMode::Out).unwrap();
193/// assert_eq!(r.order, vec![0, 1, 2, 3]);
194/// assert_eq!(r.layers, vec![0, 1, 3, 4]);
195/// assert_eq!(r.parents[3], Some(1));
196/// ```
197pub fn bfs_simple(graph: &Graph, root: VertexId, mode: BfsMode) -> IgraphResult<BfsSimple> {
198    graph.neighbors_iter(root)?; // validate root
199
200    let n = graph.vcount() as usize;
201    let use_mode = if graph.is_directed() {
202        mode
203    } else {
204        BfsMode::All
205    };
206
207    let mut visited = vec![false; n];
208    let mut parents: Vec<Option<VertexId>> = vec![None; n];
209    let mut order: Vec<VertexId> = Vec::with_capacity(n);
210    let mut layers: Vec<usize> = Vec::new();
211
212    // Queue stores (vertex, distance) pairs.
213    let mut queue: VecDeque<(VertexId, u32)> = VecDeque::new();
214    let mut last_layer: Option<u32> = None;
215
216    visited[root as usize] = true;
217    order.push(root);
218    layers.push(0); // layer 0 starts at index 0
219    queue.push_back((root, 0));
220
221    while let Some((v, dist)) = queue.pop_front() {
222        let neis = match use_mode {
223            BfsMode::Out => graph.out_neighbors_vec(v)?,
224            BfsMode::In => graph.in_neighbors_vec(v)?,
225            BfsMode::All => {
226                if graph.is_directed() {
227                    let mut combined = graph.out_neighbors_vec(v)?;
228                    combined.extend(graph.in_neighbors_vec(v)?);
229                    combined
230                } else {
231                    graph.neighbors(v)?
232                }
233            }
234        };
235        let next_dist = dist
236            .checked_add(1)
237            .ok_or(crate::core::IgraphError::Internal(
238                "BFS distance overflow (graph diameter exceeds u32::MAX)",
239            ))?;
240        for w in neis {
241            if !visited[w as usize] {
242                visited[w as usize] = true;
243                parents[w as usize] = Some(v);
244                queue.push_back((w, next_dist));
245                if last_layer != Some(next_dist) {
246                    layers.push(order.len());
247                    last_layer = Some(next_dist);
248                }
249                order.push(w);
250            }
251        }
252    }
253
254    // Sentinel: final layer boundary = total visited count.
255    layers.push(order.len());
256
257    Ok(BfsSimple {
258        order,
259        layers,
260        parents,
261    })
262}
263
264#[cfg(test)]
265mod tests {
266    use super::*;
267
268    fn path_graph(n: u32) -> Graph {
269        let mut g = Graph::with_vertices(n);
270        for i in 0..n.saturating_sub(1) {
271            g.add_edge(i, i + 1).unwrap();
272        }
273        g
274    }
275
276    #[test]
277    fn empty_graph_errors_on_any_root() {
278        let g = Graph::with_vertices(0);
279        let err = bfs(&g, 0).unwrap_err();
280        assert!(matches!(
281            err,
282            crate::core::IgraphError::VertexOutOfRange { id: 0, n: 0 }
283        ));
284    }
285
286    #[test]
287    fn single_vertex_visits_self() {
288        let g = Graph::with_vertices(1);
289        assert_eq!(bfs(&g, 0).unwrap(), vec![0]);
290    }
291
292    #[test]
293    fn path_visits_in_order() {
294        let g = path_graph(5);
295        assert_eq!(bfs(&g, 0).unwrap(), vec![0, 1, 2, 3, 4]);
296    }
297
298    #[test]
299    fn bfs_layers_breadth_first_not_depth_first() {
300        // 0 -- 1 -- 3
301        // |
302        // 2
303        let mut g = Graph::with_vertices(4);
304        g.add_edge(0, 1).unwrap();
305        g.add_edge(0, 2).unwrap();
306        g.add_edge(1, 3).unwrap();
307        // BFS order from 0 must visit both 1 and 2 before 3.
308        let order = bfs(&g, 0).unwrap();
309        assert_eq!(order[0], 0);
310        let pos_3 = order.iter().position(|&x| x == 3).unwrap();
311        let pos_1 = order.iter().position(|&x| x == 1).unwrap();
312        let pos_2 = order.iter().position(|&x| x == 2).unwrap();
313        assert!(pos_3 > pos_1 && pos_3 > pos_2);
314    }
315
316    #[test]
317    fn unreachable_vertex_excluded() {
318        let mut g = Graph::with_vertices(3);
319        g.add_edge(0, 1).unwrap();
320        // vertex 2 is isolated.
321        let order = bfs(&g, 0).unwrap();
322        assert_eq!(order, vec![0, 1]);
323    }
324
325    #[test]
326    fn invalid_root_errors() {
327        let g = Graph::with_vertices(2);
328        let err = bfs(&g, 5).unwrap_err();
329        match err {
330            crate::core::IgraphError::VertexOutOfRange { id, n } => {
331                assert_eq!(id, 5);
332                assert_eq!(n, 2);
333            }
334            other => panic!("unexpected error: {other:?}"),
335        }
336    }
337
338    #[test]
339    fn bfs_tree_returns_full_state_for_a_tree() {
340        // Star centred at 0, leaves 1, 2, 3.
341        let mut g = Graph::with_vertices(4);
342        g.add_edge(0, 1).unwrap();
343        g.add_edge(0, 2).unwrap();
344        g.add_edge(0, 3).unwrap();
345        let r = bfs_tree(&g, 0).unwrap();
346        assert_eq!(r.order, vec![0, 1, 2, 3]);
347        assert_eq!(r.distances, vec![Some(0), Some(1), Some(1), Some(1)]);
348        assert_eq!(r.parents, vec![None, Some(0), Some(0), Some(0)]);
349    }
350
351    #[test]
352    fn bfs_tree_path_5_is_chain() {
353        let g = path_graph(5);
354        let r = bfs_tree(&g, 0).unwrap();
355        assert_eq!(r.order, vec![0, 1, 2, 3, 4]);
356        assert_eq!(
357            r.distances,
358            vec![Some(0), Some(1), Some(2), Some(3), Some(4)]
359        );
360        assert_eq!(r.parents, vec![None, Some(0), Some(1), Some(2), Some(3)]);
361    }
362
363    #[test]
364    fn bfs_tree_unreachable_vertices_have_none() {
365        let mut g = Graph::with_vertices(4);
366        g.add_edge(0, 1).unwrap();
367        // 2 and 3 isolated.
368        let r = bfs_tree(&g, 0).unwrap();
369        assert_eq!(r.order, vec![0, 1]);
370        assert_eq!(r.distances, vec![Some(0), Some(1), None, None]);
371        assert_eq!(r.parents, vec![None, Some(0), None, None]);
372    }
373
374    #[test]
375    fn bfs_tree_invalid_root_errors() {
376        let g = Graph::with_vertices(3);
377        assert!(bfs_tree(&g, 7).is_err());
378    }
379
380    #[test]
381    fn bfs_tree_directed_uses_out_edges() {
382        // 0 -> 1 -> 2, 1 -> 3: from 0, all 4 reachable.
383        let mut g = Graph::new(4, true).unwrap();
384        g.add_edge(0, 1).unwrap();
385        g.add_edge(1, 2).unwrap();
386        g.add_edge(1, 3).unwrap();
387        let r = bfs_tree(&g, 0).unwrap();
388        assert_eq!(r.distances, vec![Some(0), Some(1), Some(2), Some(2)]);
389        assert_eq!(r.parents[0], None);
390        assert_eq!(r.parents[1], Some(0));
391        assert_eq!(r.parents[2], Some(1));
392        assert_eq!(r.parents[3], Some(1));
393        // From vertex 2, only 2 is reachable (no out-edges).
394        let r2 = bfs_tree(&g, 2).unwrap();
395        assert_eq!(r2.order, vec![2]);
396    }
397
398    // ── bfs_simple tests ────────────────────────────────────────────
399
400    #[test]
401    fn bfs_simple_undirected_tree() {
402        //     0
403        //    / \
404        //   1   2
405        //   |
406        //   3
407        let mut g = Graph::with_vertices(4);
408        g.add_edge(0, 1).unwrap();
409        g.add_edge(0, 2).unwrap();
410        g.add_edge(1, 3).unwrap();
411
412        let r = bfs_simple(&g, 0, BfsMode::Out).unwrap();
413        assert_eq!(r.order, vec![0, 1, 2, 3]);
414        assert_eq!(r.layers, vec![0, 1, 3, 4]);
415        assert_eq!(r.parents[0], None);
416        assert_eq!(r.parents[1], Some(0));
417        assert_eq!(r.parents[2], Some(0));
418        assert_eq!(r.parents[3], Some(1));
419    }
420
421    #[test]
422    fn bfs_simple_single_vertex() {
423        let g = Graph::with_vertices(1);
424        let r = bfs_simple(&g, 0, BfsMode::All).unwrap();
425        assert_eq!(r.order, vec![0]);
426        assert_eq!(r.layers, vec![0, 1]);
427        assert_eq!(r.parents, vec![None]);
428    }
429
430    #[test]
431    fn bfs_simple_invalid_root() {
432        let g = Graph::with_vertices(2);
433        assert!(bfs_simple(&g, 5, BfsMode::Out).is_err());
434    }
435
436    #[test]
437    fn bfs_simple_directed_out() {
438        // 0 -> 1 -> 2, 0 -> 3
439        let mut g = Graph::new(4, true).unwrap();
440        g.add_edge(0, 1).unwrap();
441        g.add_edge(1, 2).unwrap();
442        g.add_edge(0, 3).unwrap();
443
444        let r = bfs_simple(&g, 0, BfsMode::Out).unwrap();
445        assert_eq!(r.order, vec![0, 1, 3, 2]);
446        assert_eq!(r.layers, vec![0, 1, 3, 4]);
447        assert_eq!(r.parents[1], Some(0));
448        assert_eq!(r.parents[2], Some(1));
449        assert_eq!(r.parents[3], Some(0));
450    }
451
452    #[test]
453    fn bfs_simple_directed_in() {
454        // 1 -> 0, 2 -> 1, 3 -> 0
455        let mut g = Graph::new(4, true).unwrap();
456        g.add_edge(1, 0).unwrap();
457        g.add_edge(2, 1).unwrap();
458        g.add_edge(3, 0).unwrap();
459
460        let r = bfs_simple(&g, 0, BfsMode::In).unwrap();
461        assert_eq!(r.order, vec![0, 1, 3, 2]);
462        assert_eq!(r.layers, vec![0, 1, 3, 4]);
463        assert_eq!(r.parents[1], Some(0));
464        assert_eq!(r.parents[3], Some(0));
465        assert_eq!(r.parents[2], Some(1));
466    }
467
468    #[test]
469    fn bfs_simple_directed_all() {
470        // 0 -> 1, 2 -> 0
471        let mut g = Graph::new(3, true).unwrap();
472        g.add_edge(0, 1).unwrap();
473        g.add_edge(2, 0).unwrap();
474
475        let r = bfs_simple(&g, 0, BfsMode::All).unwrap();
476        assert_eq!(r.order.len(), 3);
477        assert_eq!(r.order[0], 0);
478        // Both 1 and 2 are at distance 1
479        assert_eq!(r.layers, vec![0, 1, 3]);
480    }
481
482    #[test]
483    fn bfs_simple_unreachable_vertices() {
484        let mut g = Graph::with_vertices(4);
485        g.add_edge(0, 1).unwrap();
486        // 2, 3 isolated
487        let r = bfs_simple(&g, 0, BfsMode::All).unwrap();
488        assert_eq!(r.order, vec![0, 1]);
489        assert_eq!(r.layers, vec![0, 1, 2]);
490        assert_eq!(r.parents[2], None);
491        assert_eq!(r.parents[3], None);
492    }
493
494    #[test]
495    fn bfs_simple_mode_ignored_for_undirected() {
496        let mut g = Graph::with_vertices(3);
497        g.add_edge(0, 1).unwrap();
498        g.add_edge(1, 2).unwrap();
499        // BfsMode::In should be ignored for undirected
500        let r = bfs_simple(&g, 0, BfsMode::In).unwrap();
501        assert_eq!(r.order, vec![0, 1, 2]);
502    }
503
504    #[test]
505    fn bfs_simple_layers_match_distances() {
506        let g = path_graph(6);
507        let r = bfs_simple(&g, 0, BfsMode::Out).unwrap();
508        // Path: 0-1-2-3-4-5 => each layer has exactly 1 vertex (except root)
509        assert_eq!(r.layers, vec![0, 1, 2, 3, 4, 5, 6]);
510        for d in 0..6 {
511            let layer_verts = &r.order[r.layers[d]..r.layers[d + 1]];
512            assert_eq!(layer_verts.len(), 1);
513        }
514    }
515}
rust_igraph/algorithms/traversal/bfs.rs

rust_igraph/algorithms/traversal/
bfs.rs
