oxicuda_graphalg/traversal/
bfs.rs

1//! Breadth-First Search.
2
3use std::collections::VecDeque;
4
5use crate::error::{GraphalgError, GraphalgResult};
6use crate::repr::adjacency_list::AdjacencyList;
7
8/// BFS levels from `source`. Unreachable nodes have level `usize::MAX`.
9pub fn bfs_levels(g: &AdjacencyList, source: usize) -> GraphalgResult<Vec<usize>> {
10    if source >= g.n {
11        return Err(GraphalgError::SourceOutOfRange {
12            node: source,
13            n: g.n,
14        });
15    }
16    let mut level = vec![usize::MAX; g.n];
17    level[source] = 0;
18    let mut q: VecDeque<usize> = VecDeque::new();
19    q.push_back(source);
20    while let Some(u) = q.pop_front() {
21        let lvl = level[u];
22        for &v in g.neighbors(u)? {
23            if level[v] == usize::MAX {
24                level[v] = lvl + 1;
25                q.push_back(v);
26            }
27        }
28    }
29    Ok(level)
30}
31
32/// BFS predecessors from `source`. `parent[source]` is `source` itself; unreachable -> `usize::MAX`.
33pub fn bfs_parents(g: &AdjacencyList, source: usize) -> GraphalgResult<Vec<usize>> {
34    if source >= g.n {
35        return Err(GraphalgError::SourceOutOfRange {
36            node: source,
37            n: g.n,
38        });
39    }
40    let mut parent = vec![usize::MAX; g.n];
41    parent[source] = source;
42    let mut q: VecDeque<usize> = VecDeque::new();
43    q.push_back(source);
44    while let Some(u) = q.pop_front() {
45        for &v in g.neighbors(u)? {
46            if parent[v] == usize::MAX {
47                parent[v] = u;
48                q.push_back(v);
49            }
50        }
51    }
52    Ok(parent)
53}
54
55/// Reconstruct a shortest path from `source` to `target` from a parents vector.
56pub fn reconstruct_path(
57    parents: &[usize],
58    source: usize,
59    target: usize,
60) -> GraphalgResult<Vec<usize>> {
61    if target >= parents.len() {
62        return Err(GraphalgError::IndexOutOfBounds {
63            index: target,
64            len: parents.len(),
65        });
66    }
67    if parents[target] == usize::MAX {
68        return Err(GraphalgError::NoSolution(format!(
69            "node {target} unreachable from source {source}"
70        )));
71    }
72    let mut path = Vec::new();
73    let mut cur = target;
74    loop {
75        path.push(cur);
76        if cur == source {
77            break;
78        }
79        let p = parents[cur];
80        if p == cur || p == usize::MAX {
81            return Err(GraphalgError::NoSolution(format!(
82                "path reconstruction failed at {cur}"
83            )));
84        }
85        cur = p;
86    }
87    path.reverse();
88    Ok(path)
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    fn line(n: usize) -> AdjacencyList {
96        let mut g = AdjacencyList::new(n);
97        for i in 0..n - 1 {
98            g.add_undirected_edge(i, i + 1).expect("ok");
99        }
100        g
101    }
102
103    #[test]
104    fn bfs_line_levels() {
105        let g = line(5);
106        let lv = bfs_levels(&g, 0).expect("ok");
107        assert_eq!(lv, vec![0, 1, 2, 3, 4]);
108    }
109
110    #[test]
111    fn bfs_source_oob() {
112        let g = line(3);
113        assert!(bfs_levels(&g, 99).is_err());
114    }
115
116    #[test]
117    fn bfs_parents_line() {
118        let g = line(4);
119        let p = bfs_parents(&g, 0).expect("ok");
120        assert_eq!(p, vec![0, 0, 1, 2]);
121    }
122
123    #[test]
124    fn bfs_unreachable() {
125        let mut g = AdjacencyList::new(4);
126        g.add_undirected_edge(0, 1).expect("ok");
127        g.add_undirected_edge(2, 3).expect("ok");
128        let lv = bfs_levels(&g, 0).expect("ok");
129        assert_eq!(lv[2], usize::MAX);
130        assert_eq!(lv[3], usize::MAX);
131    }
132
133    #[test]
134    fn reconstruct_simple_path() {
135        let g = line(5);
136        let p = bfs_parents(&g, 0).expect("ok");
137        let path = reconstruct_path(&p, 0, 4).expect("ok");
138        assert_eq!(path, vec![0, 1, 2, 3, 4]);
139    }
140}
oxicuda_graphalg/traversal/bfs.rs

oxicuda_graphalg/traversal/
bfs.rs
