graphrust_algos/
bfs.rs

1//! Breadth-First Search (BFS) algorithm implementation.
2//!
3//! Provides functions for graph traversal, distance calculation, and path reconstruction.
4
5use graphrust_core::{Graph, NodeId};
6use std::collections::{HashMap, VecDeque};
7
8/// Returns nodes in BFS visit order from the start node.
9///
10/// # Arguments
11/// * `graph` - The graph to traverse
12/// * `start_node` - The starting node
13///
14/// # Returns
15/// Vector of nodes in the order they are visited
16pub fn bfs_traverse(graph: &Graph, start_node: NodeId) -> Vec<NodeId> {
17    let mut visited = vec![false; graph.num_nodes() as usize];
18    let mut queue = VecDeque::new();
19    let mut order = Vec::new();
20
21    queue.push_back(start_node);
22    visited[start_node.as_usize()] = true;
23
24    while let Some(node) = queue.pop_front() {
25        order.push(node);
26
27        for &neighbor in graph.neighbors(node) {
28            if !visited[neighbor.as_usize()] {
29                visited[neighbor.as_usize()] = true;
30                queue.push_back(neighbor);
31            }
32        }
33    }
34
35    order
36}
37
38/// Returns distances from the start node to all reachable nodes.
39///
40/// # Arguments
41/// * `graph` - The graph
42/// * `start_node` - The starting node
43///
44/// # Returns
45/// HashMap mapping node IDs to their distance from start_node
46pub fn bfs_distances(graph: &Graph, start_node: NodeId) -> HashMap<NodeId, u32> {
47    let mut distances = HashMap::new();
48    let mut queue = VecDeque::new();
49
50    distances.insert(start_node, 0);
51    queue.push_back(start_node);
52
53    while let Some(node) = queue.pop_front() {
54        let current_distance = distances[&node];
55
56        for &neighbor in graph.neighbors(node) {
57            if !distances.contains_key(&neighbor) {
58                distances.insert(neighbor, current_distance + 1);
59                queue.push_back(neighbor);
60            }
61        }
62    }
63
64    distances
65}
66
67/// Returns predecessor map for path reconstruction.
68///
69/// # Arguments
70/// * `graph` - The graph
71/// * `start_node` - The starting node
72///
73/// # Returns
74/// HashMap mapping each reachable node to its predecessor in the BFS tree
75pub fn bfs_predecessors(graph: &Graph, start_node: NodeId) -> HashMap<NodeId, NodeId> {
76    let mut predecessors = HashMap::new();
77    let mut queue = VecDeque::new();
78
79    queue.push_back(start_node);
80
81    while let Some(node) = queue.pop_front() {
82        for &neighbor in graph.neighbors(node) {
83            if !predecessors.contains_key(&neighbor) && neighbor != start_node {
84                predecessors.insert(neighbor, node);
85                queue.push_back(neighbor);
86            }
87        }
88    }
89
90    predecessors
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96    use graphrust_core::GraphBuilder;
97
98    fn create_test_graph() -> Graph {
99        // Create a simple graph: 0-1-2, 0-3
100        GraphBuilder::new(4)
101            .add_edge(NodeId(0), NodeId(1))
102            .add_edge(NodeId(1), NodeId(2))
103            .add_edge(NodeId(0), NodeId(3))
104            .build()
105    }
106
107    #[test]
108    fn test_bfs_traverse() {
109        let graph = create_test_graph();
110        let order = bfs_traverse(&graph, NodeId(0));
111        assert_eq!(order[0], NodeId(0));
112        assert!(order.contains(&NodeId(1)));
113        assert!(order.contains(&NodeId(3)));
114        assert!(order.contains(&NodeId(2)));
115    }
116
117    #[test]
118    fn test_bfs_distances() {
119        let graph = create_test_graph();
120        let distances = bfs_distances(&graph, NodeId(0));
121
122        assert_eq!(distances.get(&NodeId(0)), Some(&0));
123        assert_eq!(distances.get(&NodeId(1)), Some(&1));
124        assert_eq!(distances.get(&NodeId(3)), Some(&1));
125        assert_eq!(distances.get(&NodeId(2)), Some(&2));
126    }
127
128    #[test]
129    fn test_bfs_predecessors() {
130        let graph = create_test_graph();
131        let predecessors = bfs_predecessors(&graph, NodeId(0));
132
133        assert_eq!(predecessors.get(&NodeId(1)), Some(&NodeId(0)));
134        assert_eq!(predecessors.get(&NodeId(3)), Some(&NodeId(0)));
135        assert_eq!(predecessors.get(&NodeId(2)), Some(&NodeId(1)));
136    }
137}
graphrust_algos/bfs.rs

graphrust_algos/
bfs.rs
