oxihuman_core/
shortest_path_bfs.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! BFS shortest path on an unweighted directed/undirected graph.
6
7use std::collections::VecDeque;
8
9/// An unweighted adjacency-list graph.
10pub struct BfsGraph {
11    pub n: usize,
12    pub adj: Vec<Vec<usize>>,
13}
14
15impl BfsGraph {
16    pub fn new(n: usize) -> Self {
17        BfsGraph {
18            n,
19            adj: vec![Vec::new(); n],
20        }
21    }
22}
23
24/// Create a new BFS graph with `n` nodes.
25pub fn new_bfs_graph(n: usize) -> BfsGraph {
26    BfsGraph::new(n)
27}
28
29/// Add a directed edge `u -> v`.
30pub fn bfs_add_edge(g: &mut BfsGraph, u: usize, v: usize) {
31    if u < g.n && v < g.n {
32        g.adj[u].push(v);
33    }
34}
35
36/// Add an undirected edge between `u` and `v`.
37pub fn bfs_add_undirected(g: &mut BfsGraph, u: usize, v: usize) {
38    bfs_add_edge(g, u, v);
39    bfs_add_edge(g, v, u);
40}
41
42/// Return the shortest-path distance from `src` to every reachable node.
43/// Unreachable nodes have distance `usize::MAX`.
44pub fn bfs_distances(g: &BfsGraph, src: usize) -> Vec<usize> {
45    let mut dist = vec![usize::MAX; g.n];
46    if src >= g.n {
47        return dist;
48    }
49    dist[src] = 0;
50    let mut queue = VecDeque::new();
51    queue.push_back(src);
52    while let Some(u) = queue.pop_front() {
53        for &v in &g.adj[u] {
54            if dist[v] == usize::MAX {
55                dist[v] = dist[u] + 1;
56                queue.push_back(v);
57            }
58        }
59    }
60    dist
61}
62
63/// Return the shortest path from `src` to `dst` as a vector of node indices,
64/// or `None` if unreachable.
65pub fn bfs_shortest_path(g: &BfsGraph, src: usize, dst: usize) -> Option<Vec<usize>> {
66    if src >= g.n || dst >= g.n {
67        return None;
68    }
69    let mut prev = vec![usize::MAX; g.n];
70    let mut dist = vec![usize::MAX; g.n];
71    dist[src] = 0;
72    let mut queue = VecDeque::new();
73    queue.push_back(src);
74    while let Some(u) = queue.pop_front() {
75        if u == dst {
76            break;
77        }
78        for &v in &g.adj[u] {
79            if dist[v] == usize::MAX {
80                dist[v] = dist[u] + 1;
81                prev[v] = u;
82                queue.push_back(v);
83            }
84        }
85    }
86    if dist[dst] == usize::MAX {
87        return None;
88    }
89    /* reconstruct path by walking prev[] from dst back to src.
90     * prev[src] == usize::MAX (never assigned), so the loop terminates naturally. */
91    let mut path = Vec::new();
92    let mut cur = dst;
93    while cur != usize::MAX {
94        path.push(cur);
95        cur = prev[cur];
96    }
97    path.reverse();
98    Some(path)
99}
100
101/// Return the hop count from `src` to `dst`, or `None` if unreachable.
102pub fn bfs_distance(g: &BfsGraph, src: usize, dst: usize) -> Option<usize> {
103    let dists = bfs_distances(g, src);
104    if dst < g.n && dists[dst] != usize::MAX {
105        Some(dists[dst])
106    } else {
107        None
108    }
109}
110
111/// Return `true` if `dst` is reachable from `src`.
112pub fn bfs_reachable(g: &BfsGraph, src: usize, dst: usize) -> bool {
113    bfs_distance(g, src, dst).is_some()
114}
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119
120    #[test]
121    fn test_simple_path() {
122        /* 0 -> 1 -> 2 -> 3 */
123        let mut g = new_bfs_graph(4);
124        bfs_add_edge(&mut g, 0, 1);
125        bfs_add_edge(&mut g, 1, 2);
126        bfs_add_edge(&mut g, 2, 3);
127        assert_eq!(bfs_distance(&g, 0, 3), Some(3));
128    }
129
130    #[test]
131    fn test_unreachable() {
132        let mut g = new_bfs_graph(3);
133        bfs_add_edge(&mut g, 0, 1);
134        /* 2 is isolated */
135        assert_eq!(bfs_distance(&g, 0, 2), None);
136    }
137
138    #[test]
139    fn test_path_reconstruction() {
140        let mut g = new_bfs_graph(4);
141        bfs_add_edge(&mut g, 0, 1);
142        bfs_add_edge(&mut g, 1, 3);
143        bfs_add_edge(&mut g, 0, 2);
144        bfs_add_edge(&mut g, 2, 3);
145        let path = bfs_shortest_path(&g, 0, 3).expect("should succeed");
146        assert_eq!(path[0], 0);
147        assert_eq!(*path.last().expect("should succeed"), 3);
148        assert_eq!(path.len(), 3); /* 0 -> 1 -> 3 or 0 -> 2 -> 3 */
149    }
150
151    #[test]
152    fn test_same_src_dst() {
153        let mut g = new_bfs_graph(3);
154        bfs_add_edge(&mut g, 0, 1);
155        assert_eq!(bfs_distance(&g, 1, 1), Some(0));
156    }
157
158    #[test]
159    fn test_reachable_true() {
160        let mut g = new_bfs_graph(5);
161        for i in 0..4 {
162            bfs_add_edge(&mut g, i, i + 1);
163        }
164        assert!(bfs_reachable(&g, 0, 4));
165    }
166
167    #[test]
168    fn test_reachable_false() {
169        let mut g = new_bfs_graph(3);
170        bfs_add_edge(&mut g, 0, 1);
171        assert!(!bfs_reachable(&g, 2, 0));
172    }
173
174    #[test]
175    fn test_undirected_distances() {
176        let mut g = new_bfs_graph(4);
177        bfs_add_undirected(&mut g, 0, 1);
178        bfs_add_undirected(&mut g, 1, 2);
179        bfs_add_undirected(&mut g, 2, 3);
180        let d = bfs_distances(&g, 3);
181        assert_eq!(d[0], 3);
182        assert_eq!(d[1], 2);
183    }
184
185    #[test]
186    fn test_bfs_distances_length() {
187        let g = new_bfs_graph(5);
188        let d = bfs_distances(&g, 0);
189        assert_eq!(d.len(), 5);
190    }
191
192    #[test]
193    fn test_path_none_when_unreachable() {
194        let g = new_bfs_graph(3);
195        assert!(bfs_shortest_path(&g, 0, 2).is_none());
196    }
197}
oxihuman_core/shortest_path_bfs.rs

oxihuman_core/
shortest_path_bfs.rs
