toolbox_rs/
unidirectional_dijkstra.rs

1/// Implementation of a unidirectional Dijkstra that uses the adresseable heap
2/// as its priority queue.
3///
4/// The main advantage of this implementation is that it stores the entire
5/// search space of each run in its internal structures. From there paths can
6/// be unpacked.
7use crate::{
8    addressable_binary_heap::AddressableHeap,
9    graph::{Graph, NodeID},
10};
11
12use log::debug;
13
14pub struct UnidirectionalDijkstra {
15    queue: AddressableHeap<NodeID, usize, NodeID>,
16    upper_bound: usize,
17}
18
19impl Default for UnidirectionalDijkstra {
20    fn default() -> Self {
21        Self::new()
22    }
23}
24
25impl UnidirectionalDijkstra {
26    pub fn new() -> Self {
27        let queue = AddressableHeap::<NodeID, usize, NodeID>::new();
28        Self {
29            queue,
30            upper_bound: usize::MAX,
31        }
32    }
33
34    /// clears the search space stored in the queue.
35    pub fn clear(&mut self) {
36        self.queue.clear();
37        self.upper_bound = usize::MAX;
38    }
39
40    /// retrieves the number of nodes that were explored (not settled) during
41    /// a search.
42    pub fn search_space_len(&self) -> usize {
43        self.queue.inserted_len()
44    }
45
46    /// run a path computation from s to t on some graph. The object is reusable
47    /// to run consecutive searches, even on different graphs. It is cleared on
48    /// every run, which saves on allocations.
49    pub fn run<G: Graph<usize>>(&mut self, graph: &G, s: NodeID, t: NodeID) -> usize {
50        // clear the search space
51        self.clear();
52
53        debug!("[start] source: {s}, target: {t}");
54
55        // prime queue
56        self.queue.insert(s, 0, s);
57        debug!("[push] {s} at distance {}", self.queue.weight(s));
58
59        // iteratively search the graph
60        while !self.queue.is_empty() && self.upper_bound == usize::MAX {
61            // settle next node from queue
62            let u = self.queue.delete_min();
63            let distance = self.queue.weight(u);
64
65            debug!("[pop] {u} at distance {distance}");
66
67            // check if target is reached
68            if u == t {
69                self.upper_bound = distance;
70                debug!("[done] reached {t} at {distance}");
71                return self.upper_bound;
72            }
73
74            // relax outgoing edges
75            for edge in graph.edge_range(u) {
76                debug!("[relax] edge {edge}");
77                let v = graph.target(edge);
78                let new_distance = distance + *graph.data(edge);
79
80                if !self.queue.inserted(v) {
81                    debug!("[push] node: {v}, weight: {new_distance}, parent: {u}");
82                    // if target not enqued before, do now
83                    self.queue.insert(v, new_distance, u);
84                }
85                if self.queue.contains(v) && self.queue.weight(v) > new_distance {
86                    debug!("[decrease] node: {v}, new weight: {new_distance}, new parent: {u}");
87                    // if lower distance found, update distance and its parent
88                    self.queue.decrease_key_and_update_data(v, new_distance, v);
89                }
90            }
91        }
92
93        self.upper_bound
94    }
95
96    /// retrieve path from the node to the queue according to the search space
97    /// stored in the priority queue. It's stored in reverse node order (from
98    /// target to source) and thus reversed before returning.
99    pub fn retrieve_node_path(&self, target: NodeID) -> Option<Vec<NodeID>> {
100        if self.upper_bound == usize::MAX || !self.queue.inserted(target) {
101            // if no path was found or target was not reached, return None
102            return None;
103        }
104
105        let mut path = vec![target];
106        let mut node = target;
107        loop {
108            // since the target was inserted (as checked above) and the sources
109            // parent is the source node of the search itself, this loop will
110            // terminate.
111            let parent = *self.queue.data(node);
112            if parent == node {
113                // reverse order to go from source to target
114                path.reverse();
115                return Some(path);
116            }
117            path.push(parent);
118            node = parent;
119        }
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use crate::{
126        edge::InputEdge, graph::Graph, static_graph::StaticGraph,
127        unidirectional_dijkstra::UnidirectionalDijkstra,
128    };
129
130    fn create_graph() -> StaticGraph<usize> {
131        let edges = vec![
132            InputEdge::new(0, 1, 3),
133            InputEdge::new(1, 2, 3),
134            InputEdge::new(4, 2, 1),
135            InputEdge::new(2, 3, 6),
136            InputEdge::new(0, 4, 2),
137            InputEdge::new(4, 5, 2),
138            InputEdge::new(5, 3, 7),
139            InputEdge::new(1, 5, 2),
140        ];
141        let graph = StaticGraph::<usize>::new(edges);
142        assert_eq!(6, graph.number_of_nodes());
143        assert_eq!(8, graph.number_of_edges());
144
145        graph
146    }
147
148    #[test]
149    fn simple_graph() {
150        let graph = create_graph();
151
152        let mut dijkstra = UnidirectionalDijkstra::default();
153        let distance = dijkstra.run(&graph, 0, 3);
154        assert_eq!(6, dijkstra.search_space_len());
155        assert_eq!(9, distance);
156    }
157
158    #[test]
159    fn apsp() {
160        let graph = create_graph();
161
162        let no = usize::MAX;
163
164        let results_table = [
165            [0, 3, 3, 9, 2, 4],
166            [no, 0, 3, 9, no, 2],
167            [no, no, 0, 6, no, no],
168            [no, no, no, 0, no, no],
169            [no, no, 1, 7, 0, 2],
170            [no, no, no, 7, no, 0],
171        ];
172
173        let mut dijkstra = UnidirectionalDijkstra::new();
174        for (i, &table) in results_table.iter().enumerate() {
175            for (j, result) in table.iter().enumerate() {
176                let distance = dijkstra.run(&graph, i, j);
177                assert_eq!(*result, distance);
178            }
179        }
180    }
181
182    #[test]
183    fn retrieve_node_path() {
184        let graph = create_graph();
185        let mut dijkstra = UnidirectionalDijkstra::new();
186        let distance = dijkstra.run(&graph, 0, 3);
187        assert_eq!(9, distance);
188        let computed_path = dijkstra.retrieve_node_path(3).unwrap();
189        let expected_path = vec![0, 4, 2, 3];
190
191        assert_eq!(computed_path, expected_path);
192    }
193
194    #[test]
195    fn decrease_key_in_search() {
196        let edges = vec![
197            InputEdge::new(0, 1, 7),
198            InputEdge::new(0, 2, 3),
199            InputEdge::new(1, 2, 1),
200            InputEdge::new(1, 3, 6),
201            InputEdge::new(2, 4, 8),
202            InputEdge::new(3, 5, 2),
203            InputEdge::new(4, 3, 2),
204            InputEdge::new(4, 5, 8),
205        ];
206        let graph = StaticGraph::new(edges);
207
208        let mut dijkstra = UnidirectionalDijkstra::new();
209        let distance = dijkstra.run(&graph, 0, 5);
210        assert_eq!(distance, 15);
211    }
212
213    #[test]
214    fn larger_graph() {
215        // regression test from handling DIMACS data set
216        let edges = vec![
217            InputEdge::new(3, 12, 2852),
218            InputEdge::new(3, 13, 1641),
219            InputEdge::new(3, 26, 1334),
220            InputEdge::new(3, 14, 425),
221            InputEdge::new(3, 27, 1380),
222            InputEdge::new(28, 29, 2713),
223            InputEdge::new(28, 30, 2378),
224            InputEdge::new(28, 31, 1114),
225            InputEdge::new(28, 8, 1013),
226            InputEdge::new(32, 30, 1225),
227            InputEdge::new(32, 33, 892),
228            InputEdge::new(32, 31, 2375),
229            InputEdge::new(34, 33, 2497),
230            InputEdge::new(34, 35, 885),
231            InputEdge::new(34, 31, 1332),
232            InputEdge::new(36, 37, 2886),
233            InputEdge::new(36, 38, 864),
234            InputEdge::new(36, 39, 126),
235            InputEdge::new(37, 36, 2886),
236            InputEdge::new(38, 36, 864),
237            InputEdge::new(38, 40, 3560),
238            InputEdge::new(38, 41, 1770),
239            InputEdge::new(38, 42, 826),
240            InputEdge::new(40, 38, 3560),
241            InputEdge::new(40, 39, 3335),
242            InputEdge::new(40, 43, 2295),
243            InputEdge::new(41, 38, 1770),
244            InputEdge::new(1, 15, 667),
245            InputEdge::new(1, 44, 901),
246            InputEdge::new(1, 9, 1233),
247            InputEdge::new(44, 1, 901),
248            InputEdge::new(45, 46, 1638),
249            InputEdge::new(45, 47, 889),
250            InputEdge::new(45, 48, 2582),
251            InputEdge::new(46, 45, 1638),
252            InputEdge::new(47, 45, 889),
253            InputEdge::new(47, 49, 1311),
254            InputEdge::new(47, 11, 508),
255            InputEdge::new(49, 47, 1311),
256            InputEdge::new(11, 47, 508),
257            InputEdge::new(11, 7, 3106),
258            InputEdge::new(11, 50, 1979),
259            InputEdge::new(11, 16, 1334),
260            InputEdge::new(4, 26, 1917),
261            InputEdge::new(4, 51, 859),
262            InputEdge::new(4, 17, 1140),
263            InputEdge::new(4, 2, 2888),
264            InputEdge::new(4, 52, 1885),
265            InputEdge::new(26, 3, 1334),
266            InputEdge::new(26, 4, 1917),
267            InputEdge::new(26, 51, 1657),
268            InputEdge::new(51, 4, 859),
269            InputEdge::new(51, 26, 1657),
270            InputEdge::new(51, 53, 1253),
271            InputEdge::new(51, 54, 2474),
272            InputEdge::new(27, 3, 1380),
273            InputEdge::new(27, 53, 690),
274            InputEdge::new(27, 8, 3284),
275            InputEdge::new(2, 18, 1249),
276            InputEdge::new(2, 4, 2888),
277            InputEdge::new(2, 55, 1560),
278            InputEdge::new(52, 4, 1885),
279            InputEdge::new(52, 55, 1525),
280            InputEdge::new(52, 56, 2467),
281            InputEdge::new(53, 51, 1253),
282            InputEdge::new(53, 27, 690),
283            InputEdge::new(53, 29, 552),
284            InputEdge::new(29, 28, 2713),
285            InputEdge::new(29, 53, 552),
286            InputEdge::new(29, 57, 1196),
287            InputEdge::new(0, 19, 2224),
288            InputEdge::new(0, 5, 584),
289            InputEdge::new(0, 58, 2113),
290            InputEdge::new(0, 59, 1065),
291            InputEdge::new(5, 20, 491),
292            InputEdge::new(5, 0, 584),
293            InputEdge::new(5, 60, 904),
294            InputEdge::new(60, 5, 904),
295            InputEdge::new(60, 30, 1111),
296            InputEdge::new(60, 8, 2549),
297            InputEdge::new(58, 0, 2113),
298            InputEdge::new(58, 30, 491),
299            InputEdge::new(58, 61, 2112),
300            InputEdge::new(59, 0, 1065),
301            InputEdge::new(59, 62, 983),
302            InputEdge::new(59, 63, 4556),
303            InputEdge::new(30, 28, 2378),
304            InputEdge::new(30, 32, 1225),
305            InputEdge::new(30, 60, 1111),
306            InputEdge::new(30, 58, 491),
307            InputEdge::new(61, 58, 2112),
308            InputEdge::new(61, 33, 573),
309            InputEdge::new(61, 63, 1038),
310            InputEdge::new(61, 64, 3897),
311            InputEdge::new(33, 32, 892),
312            InputEdge::new(33, 34, 2497),
313            InputEdge::new(33, 61, 573),
314            InputEdge::new(62, 59, 983),
315            InputEdge::new(62, 39, 1070),
316            InputEdge::new(62, 65, 5245),
317            InputEdge::new(63, 59, 4556),
318            InputEdge::new(63, 61, 1038),
319            InputEdge::new(63, 65, 1544),
320            InputEdge::new(63, 66, 3563),
321            InputEdge::new(39, 36, 126),
322            InputEdge::new(39, 40, 3335),
323            InputEdge::new(39, 62, 1070),
324            InputEdge::new(42, 38, 826),
325            InputEdge::new(42, 67, 672),
326            InputEdge::new(42, 6, 989),
327            InputEdge::new(67, 42, 672),
328            InputEdge::new(6, 42, 989),
329            InputEdge::new(6, 21, 424),
330            InputEdge::new(55, 2, 1560),
331            InputEdge::new(55, 52, 1525),
332            InputEdge::new(55, 68, 2967),
333            InputEdge::new(56, 52, 2467),
334            InputEdge::new(56, 35, 414),
335            InputEdge::new(56, 54, 1016),
336            InputEdge::new(35, 34, 885),
337            InputEdge::new(35, 56, 414),
338            InputEdge::new(35, 68, 1242),
339            InputEdge::new(48, 45, 2582),
340            InputEdge::new(48, 69, 828),
341            InputEdge::new(48, 64, 1589),
342            InputEdge::new(48, 70, 1657),
343            InputEdge::new(69, 48, 828),
344            InputEdge::new(69, 7, 371),
345            InputEdge::new(69, 71, 861),
346            InputEdge::new(7, 11, 3106),
347            InputEdge::new(7, 69, 371),
348            InputEdge::new(7, 22, 742),
349            InputEdge::new(65, 62, 5245),
350            InputEdge::new(65, 63, 1544),
351            InputEdge::new(65, 43, 1306),
352            InputEdge::new(66, 63, 3563),
353            InputEdge::new(66, 64, 1202),
354            InputEdge::new(66, 10, 997),
355            InputEdge::new(43, 40, 2295),
356            InputEdge::new(43, 65, 1306),
357            InputEdge::new(64, 61, 3897),
358            InputEdge::new(64, 48, 1589),
359            InputEdge::new(64, 66, 1202),
360            InputEdge::new(64, 70, 1667),
361            InputEdge::new(10, 66, 997),
362            InputEdge::new(10, 72, 616),
363            InputEdge::new(10, 23, 1463),
364            InputEdge::new(57, 29, 1196),
365            InputEdge::new(57, 31, 1970),
366            InputEdge::new(57, 54, 508),
367            InputEdge::new(31, 28, 1114),
368            InputEdge::new(31, 32, 2375),
369            InputEdge::new(31, 34, 1332),
370            InputEdge::new(31, 57, 1970),
371            InputEdge::new(54, 51, 2474),
372            InputEdge::new(54, 56, 1016),
373            InputEdge::new(54, 57, 508),
374            InputEdge::new(8, 28, 1013),
375            InputEdge::new(8, 27, 3284),
376            InputEdge::new(8, 60, 2549),
377            InputEdge::new(8, 24, 1003),
378            InputEdge::new(9, 1, 1233),
379            InputEdge::new(9, 25, 1229),
380            InputEdge::new(9, 70, 7863),
381            InputEdge::new(68, 55, 2967),
382            InputEdge::new(68, 35, 1242),
383            InputEdge::new(68, 70, 2667),
384            InputEdge::new(70, 48, 1657),
385            InputEdge::new(70, 64, 1667),
386            InputEdge::new(70, 9, 7863),
387            InputEdge::new(70, 68, 2667),
388            InputEdge::new(71, 69, 861),
389            InputEdge::new(72, 10, 616),
390            InputEdge::new(50, 11, 1979),
391        ];
392        let graph = StaticGraph::new(edges);
393
394        let mut dijkstra = UnidirectionalDijkstra::new();
395        let distance = dijkstra.run(&graph, 1, 19);
396        assert_eq!(distance, 21109);
397    }
398}
toolbox_rs/unidirectional_dijkstra.rs

toolbox_rs/
unidirectional_dijkstra.rs
