reddb_server/storage/engine/pathfinding/
bfs_impl.rs

1use super::*;
2
3impl BFS {
4    /// Find shortest path (by hop count) from source to target
5    pub fn shortest_path(graph: &GraphStore, source: &str, target: &str) -> ShortestPathResult {
6        if source == target {
7            return ShortestPathResult {
8                path: Some(Path::start(source)),
9                nodes_visited: 1,
10            };
11        }
12
13        let mut visited: HashSet<String> = HashSet::new();
14        let mut queue: VecDeque<Path> = VecDeque::new();
15        let mut nodes_visited = 0;
16
17        queue.push_back(Path::start(source));
18        visited.insert(source.to_string());
19
20        while let Some(current_path) = queue.pop_front() {
21            let current = current_path.nodes.last().unwrap();
22            nodes_visited += 1;
23
24            for (edge_type, neighbor, weight) in graph.outgoing_edges(current) {
25                if neighbor == target {
26                    return ShortestPathResult {
27                        path: Some(current_path.extend(&neighbor, edge_type, weight as f64)),
28                        nodes_visited,
29                    };
30                }
31
32                if !visited.contains(&neighbor) {
33                    visited.insert(neighbor.clone());
34                    queue.push_back(current_path.extend(&neighbor, edge_type, weight as f64));
35                }
36            }
37        }
38
39        ShortestPathResult {
40            path: None,
41            nodes_visited,
42        }
43    }
44
45    /// Find all nodes reachable from source within max_depth hops
46    pub fn reachable(graph: &GraphStore, source: &str, max_depth: usize) -> Vec<(String, usize)> {
47        let mut visited: HashMap<String, usize> = HashMap::new();
48        let mut queue: VecDeque<(String, usize)> = VecDeque::new();
49
50        queue.push_back((source.to_string(), 0));
51        visited.insert(source.to_string(), 0);
52
53        while let Some((current, depth)) = queue.pop_front() {
54            if depth >= max_depth {
55                continue;
56            }
57
58            for (_, neighbor, _) in graph.outgoing_edges(&current) {
59                if !visited.contains_key(&neighbor) {
60                    visited.insert(neighbor.clone(), depth + 1);
61                    queue.push_back((neighbor, depth + 1));
62                }
63            }
64        }
65
66        let mut result: Vec<_> = visited.into_iter().collect();
67        result.sort_by_key(|(_, depth)| *depth);
68        result
69    }
70
71    /// BFS traversal returning all nodes in BFS order
72    pub fn traverse(graph: &GraphStore, source: &str) -> Vec<String> {
73        let mut visited: HashSet<String> = HashSet::new();
74        let mut queue: VecDeque<String> = VecDeque::new();
75        let mut result: Vec<String> = Vec::new();
76
77        queue.push_back(source.to_string());
78        visited.insert(source.to_string());
79
80        while let Some(current) = queue.pop_front() {
81            result.push(current.clone());
82
83            for (_, neighbor, _) in graph.outgoing_edges(&current) {
84                if !visited.contains(&neighbor) {
85                    visited.insert(neighbor.clone());
86                    queue.push_back(neighbor);
87                }
88            }
89        }
90
91        result
92    }
93}
reddb_server/storage/engine/pathfinding/bfs_impl.rs

reddb_server/storage/engine/pathfinding/
bfs_impl.rs
