graph_traversal/
paths.rs

1use graph_core::NodeId;
2use std::collections::HashMap;
3
4/// Reconstructs the path from `start` to `end` using a parent map produced
5/// by BFS or DFS.
6///
7/// Returns `Some(path)` where `path[0] == start` and `path[last] == end`,
8/// or `None` if `end` is not reachable from `start` in the parent map.
9///
10/// # Examples
11///
12/// ```
13/// use graph_core::NodeId;
14/// use graph_traversal::reconstruct_path;
15/// use std::collections::HashMap;
16///
17/// let a = NodeId::new(0);
18/// let b = NodeId::new(1);
19/// let c = NodeId::new(2);
20///
21/// let mut parent = HashMap::new();
22/// parent.insert(b, a);
23/// parent.insert(c, b);
24///
25/// let path = reconstruct_path(&parent, a, c).unwrap();
26/// assert_eq!(path, vec![a, b, c]);
27/// ```
28pub fn reconstruct_path(
29    parent: &HashMap<NodeId, NodeId>,
30    start: NodeId,
31    end: NodeId,
32) -> Option<Vec<NodeId>> {
33    if start == end {
34        return Some(vec![start]);
35    }
36
37    let mut path = vec![end];
38    let mut current = end;
39
40    loop {
41        let prev = *parent.get(&current)?;
42        path.push(prev);
43        if prev == start {
44            break;
45        }
46        current = prev;
47    }
48
49    path.reverse();
50    Some(path)
51}
graph_traversal/paths.rs

graph_traversal/
paths.rs
