toolbox_rs/
one_to_many_dijkstra.rs

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

toolbox_rs/
one_to_many_dijkstra.rs
