reddb_server/storage/engine/pathfinding/
all_shortest_impl.rs

1use super::*;
2
3impl AllShortestPaths {
4    /// Find all paths with minimum length from source to target
5    pub fn find(graph: &GraphStore, source: &str, target: &str) -> AllPathsResult {
6        if source == target {
7            return AllPathsResult {
8                paths: vec![Path::start(source)],
9                nodes_visited: 1,
10            };
11        }
12
13        // First, find minimum distance using BFS
14        let first_result = BFS::shortest_path(graph, source, target);
15        let min_distance = match &first_result.path {
16            Some(p) => p.len(),
17            None => {
18                return AllPathsResult {
19                    paths: Vec::new(),
20                    nodes_visited: first_result.nodes_visited,
21                }
22            }
23        };
24
25        // Then find all paths with that exact length
26        let mut paths: Vec<Path> = Vec::new();
27        let mut nodes_visited = 0;
28
29        fn find_all(
30            graph: &GraphStore,
31            current_path: Path,
32            target: &str,
33            remaining_depth: usize,
34            visited_in_path: &mut HashSet<String>,
35            paths: &mut Vec<Path>,
36            nodes_visited: &mut usize,
37        ) {
38            let current = current_path.nodes.last().unwrap().clone();
39            *nodes_visited += 1;
40
41            if remaining_depth == 0 {
42                if current == target {
43                    paths.push(current_path);
44                }
45                return;
46            }
47
48            for (edge_type, neighbor, weight) in graph.outgoing_edges(&current) {
49                if !visited_in_path.contains(&neighbor) {
50                    visited_in_path.insert(neighbor.clone());
51                    let new_path = current_path.extend(&neighbor, edge_type, weight as f64);
52                    find_all(
53                        graph,
54                        new_path,
55                        target,
56                        remaining_depth - 1,
57                        visited_in_path,
58                        paths,
59                        nodes_visited,
60                    );
61                    visited_in_path.remove(&neighbor);
62                }
63            }
64        }
65
66        let mut visited_in_path: HashSet<String> = HashSet::new();
67        visited_in_path.insert(source.to_string());
68        find_all(
69            graph,
70            Path::start(source),
71            target,
72            min_distance,
73            &mut visited_in_path,
74            &mut paths,
75            &mut nodes_visited,
76        );
77
78        AllPathsResult {
79            paths,
80            nodes_visited,
81        }
82    }
83}
reddb_server/storage/engine/pathfinding/all_shortest_impl.rs

reddb_server/storage/engine/pathfinding/
all_shortest_impl.rs
