uni_algo/algo/algorithms/
bidirectional_dijkstra.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Bidirectional Dijkstra Algorithm.
5//!
6//! Performs Dijkstra's algorithm from both source and target simultaneously.
7//! Requires `include_reverse` in GraphProjection.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use std::cmp::Reverse;
12use std::collections::BinaryHeap;
13use uni_common::core::id::Vid;
14
15pub struct BidirectionalDijkstra;
16
17#[derive(Debug, Clone)]
18pub struct BidirectionalDijkstraConfig {
19    pub source: Vid,
20    pub target: Vid,
21}
22
23impl Default for BidirectionalDijkstraConfig {
24    fn default() -> Self {
25        Self {
26            source: Vid::from(0),
27            target: Vid::from(0),
28        }
29    }
30}
31
32pub struct BidirectionalDijkstraResult {
33    pub distance: Option<f64>,
34    // Path reconstruction is more complex for bidirectional, omitted for basic version
35    // but can be added if we store parent pointers.
36    // Let's implement distance first.
37}
38
39impl Algorithm for BidirectionalDijkstra {
40    type Config = BidirectionalDijkstraConfig;
41    type Result = BidirectionalDijkstraResult;
42
43    fn name() -> &'static str {
44        "bidirectional_dijkstra"
45    }
46
47    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
48        if !graph.has_reverse() {
49            // Fallback or error? Usually should error if algorithm requires reverse.
50            // But we can just return None or panic.
51            panic!("Bidirectional Dijkstra requires graph projection with reverse edges");
52        }
53
54        let source_slot = match graph.to_slot(config.source) {
55            Some(s) => s,
56            None => return BidirectionalDijkstraResult { distance: None },
57        };
58        let target_slot = match graph.to_slot(config.target) {
59            Some(s) => s,
60            None => return BidirectionalDijkstraResult { distance: None },
61        };
62
63        if source_slot == target_slot {
64            return BidirectionalDijkstraResult {
65                distance: Some(0.0),
66            };
67        }
68
69        let n = graph.vertex_count();
70        let mut dist_fwd = vec![f64::INFINITY; n];
71        let mut dist_bwd = vec![f64::INFINITY; n];
72
73        let mut heap_fwd = BinaryHeap::new();
74        let mut heap_bwd = BinaryHeap::new();
75
76        dist_fwd[source_slot as usize] = 0.0;
77        heap_fwd.push(Reverse((0.0f64.to_bits(), source_slot)));
78
79        dist_bwd[target_slot as usize] = 0.0;
80        heap_bwd.push(Reverse((0.0f64.to_bits(), target_slot)));
81
82        let mut mu = f64::INFINITY; // Best path cost found so far
83
84        while !heap_fwd.is_empty() && !heap_bwd.is_empty() {
85            // Check termination: top_fwd + top_bwd >= mu
86            let min_fwd = f64::from_bits(heap_fwd.peek().unwrap().0.0);
87            let min_bwd = f64::from_bits(heap_bwd.peek().unwrap().0.0);
88
89            if min_fwd + min_bwd >= mu {
90                break;
91            }
92
93            // Expand smaller frontier or alternate
94            if heap_fwd.len() <= heap_bwd.len() {
95                // Forward step
96                let Reverse((d_bits, u)) = heap_fwd.pop().unwrap();
97                let d = f64::from_bits(d_bits);
98
99                if d > dist_fwd[u as usize] {
100                    continue;
101                }
102
103                for (i, &v) in graph.out_neighbors(u).iter().enumerate() {
104                    let weight = if graph.has_weights() {
105                        graph.out_weight(u, i)
106                    } else {
107                        1.0
108                    };
109                    let new_dist = d + weight;
110                    if new_dist < dist_fwd[v as usize] {
111                        dist_fwd[v as usize] = new_dist;
112                        heap_fwd.push(Reverse((new_dist.to_bits(), v)));
113
114                        // Check connection
115                        if dist_bwd[v as usize] < f64::INFINITY {
116                            mu = mu.min(new_dist + dist_bwd[v as usize]);
117                        }
118                    }
119                }
120            } else {
121                // Backward step
122                let Reverse((d_bits, u)) = heap_bwd.pop().unwrap();
123                let d = f64::from_bits(d_bits);
124
125                if d > dist_bwd[u as usize] {
126                    continue;
127                }
128
129                for &v in graph.in_neighbors(u) {
130                    // For reverse step, weight is edge v->u.
131                    // We need to find weight of v->u.
132                    // GraphProjection in_neighbors doesn't store weights directly?
133                    // We might need to look up v's out_edges to find u.
134                    // This is inefficient.
135                    // GraphProjection should probably store in_weights if needed.
136                    // If no weights, assume 1.0.
137                    let weight = if graph.has_weights() {
138                        // TODO: efficiently get weight for v -> u
139                        // Linear scan of v's out_neighbors
140                        let mut w = 1.0;
141                        // This is O(degree), making backward search slower on dense graphs.
142                        // Ideally GraphProjection stores in_weights.
143                        // For now, assume 1.0 or implement scan.
144                        let neighbors = graph.out_neighbors(v);
145                        for (idx, &n) in neighbors.iter().enumerate() {
146                            if n == u {
147                                w = graph.out_weight(v, idx);
148                                break;
149                            }
150                        }
151                        w
152                    } else {
153                        1.0
154                    };
155
156                    let new_dist = d + weight;
157                    if new_dist < dist_bwd[v as usize] {
158                        dist_bwd[v as usize] = new_dist;
159                        heap_bwd.push(Reverse((new_dist.to_bits(), v)));
160
161                        // Check connection
162                        if dist_fwd[v as usize] < f64::INFINITY {
163                            mu = mu.min(dist_fwd[v as usize] + new_dist);
164                        }
165                    }
166                }
167            }
168        }
169
170        BidirectionalDijkstraResult {
171            distance: if mu < f64::INFINITY { Some(mu) } else { None },
172        }
173    }
174}
175
176#[cfg(test)]
177mod tests {
178    use super::*;
179    use crate::algo::{GraphProjection, IdMap};
180
181    fn build_graph_with_reverse(vids: Vec<Vid>, edges: Vec<(Vid, Vid)>) -> GraphProjection {
182        // Custom builder to ensure in_neighbors are populated
183        // Reusing test_utils logic but adding in_neighbors
184        let mut id_map = IdMap::with_capacity(vids.len());
185        for vid in &vids {
186            id_map.insert(*vid);
187        }
188        let vertex_count = id_map.len();
189
190        let mut out_adj: Vec<Vec<u32>> = vec![Vec::new(); vertex_count];
191        let mut in_adj: Vec<Vec<u32>> = vec![Vec::new(); vertex_count];
192
193        for (src, dst) in &edges {
194            let u = id_map.to_slot(*src).unwrap();
195            let v = id_map.to_slot(*dst).unwrap();
196            out_adj[u as usize].push(v);
197            in_adj[v as usize].push(u);
198        }
199
200        let mut out_offsets = vec![0u32; vertex_count + 1];
201        let mut out_neighbors = Vec::new();
202        for i in 0..vertex_count {
203            out_offsets[i + 1] = out_offsets[i] + out_adj[i].len() as u32;
204            out_neighbors.extend_from_slice(&out_adj[i]);
205        }
206
207        let mut in_offsets = vec![0u32; vertex_count + 1];
208        let mut in_neighbors = Vec::new();
209        for i in 0..vertex_count {
210            in_offsets[i + 1] = in_offsets[i] + in_adj[i].len() as u32;
211            in_neighbors.extend_from_slice(&in_adj[i]);
212        }
213
214        GraphProjection {
215            vertex_count,
216            out_offsets,
217            out_neighbors,
218            in_offsets,
219            in_neighbors,
220            out_weights: None,
221            id_map,
222            _node_labels: Vec::new(),
223            _edge_types: Vec::new(),
224        }
225    }
226
227    #[test]
228    fn test_bi_dijkstra_simple() {
229        // 0 -> 1 -> 2
230        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
231        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
232        let graph = build_graph_with_reverse(vids, edges);
233
234        let config = BidirectionalDijkstraConfig {
235            source: Vid::from(0),
236            target: Vid::from(2),
237        };
238
239        let result = BidirectionalDijkstra::run(&graph, config);
240        assert_eq!(result.distance, Some(2.0));
241    }
242}
uni_algo/algo/algorithms/bidirectional_dijkstra.rs

uni_algo/algo/algorithms/
bidirectional_dijkstra.rs
