reddb_server/storage/engine/pathfinding/
k_shortest_impl.rs

1use super::*;
2
3impl KShortestPaths {
4    /// Find k shortest paths from source to target
5    pub fn find(graph: &GraphStore, source: &str, target: &str, k: usize) -> Vec<Path> {
6        if k == 0 {
7            return Vec::new();
8        }
9
10        // Find the first shortest path
11        let first = Dijkstra::shortest_path(graph, source, target);
12        let mut result: Vec<Path> = Vec::new();
13
14        if let Some(path) = first.path {
15            result.push(path);
16        } else {
17            return result;
18        }
19
20        // Candidates for the next shortest path
21        let mut candidates: BinaryHeap<PathCandidate> = BinaryHeap::new();
22
23        for i in 1..k {
24            let prev_path = &result[i - 1];
25
26            // For each spur node in the previous path
27            for spur_idx in 0..prev_path.nodes.len() - 1 {
28                let spur_node = &prev_path.nodes[spur_idx];
29                let root_path: Vec<String> = prev_path.nodes[..=spur_idx].to_vec();
30
31                // Edges to exclude (edges used by existing paths at this spur)
32                let mut excluded_edges: HashSet<(String, String)> = HashSet::new();
33                for existing_path in &result {
34                    if existing_path.nodes.len() > spur_idx
35                        && existing_path.nodes[..=spur_idx] == root_path
36                    {
37                        if let Some(next) = existing_path.nodes.get(spur_idx + 1) {
38                            excluded_edges.insert((spur_node.clone(), next.clone()));
39                        }
40                    }
41                }
42
43                // Nodes to exclude (nodes in root path except spur)
44                let excluded_nodes: HashSet<String> =
45                    root_path[..spur_idx].iter().cloned().collect();
46
47                // Find spur path
48                if let Some(spur_path) = Self::dijkstra_with_exclusions(
49                    graph,
50                    spur_node,
51                    target,
52                    &excluded_edges,
53                    &excluded_nodes,
54                ) {
55                    // Combine root path and spur path
56                    let mut total_path = Path {
57                        nodes: root_path.clone(),
58                        total_weight: Self::path_weight_up_to(prev_path, spur_idx),
59                        edge_types: prev_path.edge_types[..spur_idx].to_vec(),
60                    };
61
62                    // Add spur path (skip first node as it's the spur node)
63                    for (j, node) in spur_path.nodes.iter().enumerate().skip(1) {
64                        total_path.nodes.push(node.clone());
65                        total_path.total_weight += spur_path
66                            .edge_types
67                            .get(j - 1)
68                            .map(|_| 1.0) // Simplified weight
69                            .unwrap_or(0.0);
70                        if let Some(et) = spur_path.edge_types.get(j - 1) {
71                            total_path.edge_types.push(et.clone());
72                        }
73                    }
74                    total_path.total_weight =
75                        spur_path.total_weight + Self::path_weight_up_to(prev_path, spur_idx);
76
77                    candidates.push(PathCandidate { path: total_path });
78                }
79            }
80
81            // Get the best candidate
82            while let Some(candidate) = candidates.pop() {
83                // Check if this path is unique
84                let is_duplicate = result.iter().any(|p| p.nodes == candidate.path.nodes);
85                if !is_duplicate {
86                    result.push(candidate.path);
87                    break;
88                }
89            }
90
91            if result.len() <= i {
92                break; // No more paths found
93            }
94        }
95
96        result
97    }
98
99    /// Dijkstra with edge and node exclusions
100    fn dijkstra_with_exclusions(
101        graph: &GraphStore,
102        source: &str,
103        target: &str,
104        excluded_edges: &HashSet<(String, String)>,
105        excluded_nodes: &HashSet<String>,
106    ) -> Option<Path> {
107        let mut dist: HashMap<String, f64> = HashMap::new();
108        let mut heap: BinaryHeap<DijkstraState> = BinaryHeap::new();
109
110        dist.insert(source.to_string(), 0.0);
111        heap.push(DijkstraState {
112            node: source.to_string(),
113            cost: 0.0,
114            path: Path::start(source),
115        });
116
117        while let Some(DijkstraState { node, cost, path }) = heap.pop() {
118            if node == target {
119                return Some(path);
120            }
121
122            if let Some(&d) = dist.get(&node) {
123                if cost > d {
124                    continue;
125                }
126            }
127
128            for (edge_type, neighbor, weight) in graph.outgoing_edges(&node) {
129                // Skip excluded edges and nodes
130                if excluded_edges.contains(&(node.clone(), neighbor.clone())) {
131                    continue;
132                }
133                if excluded_nodes.contains(&neighbor) {
134                    continue;
135                }
136
137                let new_cost = cost + weight as f64;
138
139                if !dist.contains_key(&neighbor) || new_cost < dist[&neighbor] {
140                    dist.insert(neighbor.clone(), new_cost);
141                    heap.push(DijkstraState {
142                        node: neighbor.clone(),
143                        cost: new_cost,
144                        path: path.extend(&neighbor, edge_type, weight as f64),
145                    });
146                }
147            }
148        }
149
150        None
151    }
152
153    /// Calculate path weight up to a given index
154    fn path_weight_up_to(path: &Path, idx: usize) -> f64 {
155        // Simplified: sum of edge weights up to idx
156        // In real implementation, track weights in Path struct
157        idx as f64 // Placeholder
158    }
159}
reddb_server/storage/engine/pathfinding/k_shortest_impl.rs

reddb_server/storage/engine/pathfinding/
k_shortest_impl.rs
