prepona/algo/shortest_path/
dijkstra.rs

1use magnitude::Magnitude;
2use num_traits::{Unsigned, Zero};
3use std::collections::HashMap;
4use std::{any::Any, collections::HashSet};
5
6use crate::provide::{Edges, Graph, Vertices};
7use crate::{
8    graph::{subgraph::ShortestPathSubgraph, Edge, EdgeDir},
9    prelude::Neighbors,
10};
11
12/// Finds shortest path from a single source to all other vertices using dijkstra algorithm.
13///
14/// # Examples
15/// ```
16/// use prepona::prelude::*;
17/// use prepona::storage::DiMat;
18/// use prepona::graph::MatGraph;
19/// use prepona::algo::Dijkstra;
20///
21/// // Given: Graph
22/// //          6       1
23/// //      a  -->  b  <--  c ---
24/// //    1 |       |           |
25/// //      |  2 /`````\ 2      |
26/// //      |````       ````|   |
27/// //      v               v   | 1
28/// //      d  ---------->  e --'
29/// //              1
30/// let mut graph = MatGraph::init(DiMat::<usize>::init());
31/// let a = graph.add_vertex(); // 0
32/// let b = graph.add_vertex(); // 1
33/// let c = graph.add_vertex(); // 2
34/// let d = graph.add_vertex(); // 3
35/// let e = graph.add_vertex(); // 4
36///
37/// graph.add_edge_unchecked(a, b, 6.into());
38/// let ad = graph.add_edge_unchecked(a, d, 1.into());
39/// graph.add_edge_unchecked(b, d, 2.into());
40/// graph.add_edge_unchecked(b, e, 2.into());
41/// let cb = graph.add_edge_unchecked(c, b, 1.into());
42/// let ec = graph.add_edge_unchecked(e, c, 1.into());
43/// let de = graph.add_edge_unchecked(d, e, 1.into());
44///
45/// // When: Performing Dijkstra algorithm.
46/// let sp_subgraph = Dijkstra::init(&graph).execute(&graph, a);
47///
48/// // Then:
49/// assert_eq!(sp_subgraph.vertex_count(), 5);
50/// assert_eq!(sp_subgraph.edges_count(), 4);
51/// assert!(vec![a, b, c, d, e]
52///     .iter()
53///     .all(|vertex_id| sp_subgraph.vertices().contains(vertex_id)));
54/// assert!(vec![ad, cb, ec, de]
55///     .into_iter()
56///     .all(|edge_id| sp_subgraph.edge(edge_id).is_ok()));
57/// assert_eq!(sp_subgraph.distance_to(a).unwrap(), 0.into());
58/// assert_eq!(sp_subgraph.distance_to(b).unwrap(), 4.into());
59/// assert_eq!(sp_subgraph.distance_to(c).unwrap(), 3.into());
60/// assert_eq!(sp_subgraph.distance_to(d).unwrap(), 1.into());
61/// assert_eq!(sp_subgraph.distance_to(e).unwrap(), 2.into());
62/// ```
63pub struct Dijkstra<W> {
64    visited: Vec<bool>,
65    dist: Vec<Magnitude<W>>,
66    prev: Vec<Magnitude<usize>>,
67}
68
69impl<W: Copy + Ord + Zero + Any + Unsigned> Dijkstra<W> {
70    /// Initializes the structure.
71    pub fn init<E, Ty, G>(graph: &G) -> Self
72    where
73        E: Edge<W>,
74        Ty: EdgeDir,
75        G: Edges<W, E> + Vertices + Graph<W, E, Ty>,
76    {
77        let vertex_count = graph.vertex_count();
78
79        Dijkstra {
80            visited: vec![false; vertex_count],
81            dist: vec![Magnitude::PosInfinite; vertex_count],
82            prev: vec![Magnitude::PosInfinite; vertex_count],
83        }
84    }
85
86    fn next_id(&self) -> Option<usize> {
87        self.dist
88            .iter()
89            .enumerate()
90            .filter(|(virt_id, dist)| dist.is_finite() && self.visited[*virt_id] == false)
91            .min_by(|(_, dist1), (_, dist2)| dist1.cmp(dist2))
92            .and_then(|(v_id, _)| Some(v_id))
93    }
94
95    /// Finds shortest path from a single source to all other vertices.
96    ///
97    /// # Arguments
98    /// * `graph`: Graph to search for the shortest paths in.
99    /// * `src_id`: Id of the source vertex(Shortest path will be calculated from this vertex to all other vertices)
100    ///
101    /// # Returns
102    /// The shortest path as a subgraph of the original graph.
103    /// You can query shortest path from source to each destination using api provided by `ShortestPathSubgraph`.
104    pub fn execute<E, Ty, G>(
105        mut self,
106        graph: &G,
107        src_id: usize,
108    ) -> ShortestPathSubgraph<W, E, Ty, G>
109    where
110        E: Edge<W>,
111        Ty: EdgeDir,
112        G: Edges<W, E> + Neighbors + Vertices + Graph<W, E, Ty>,
113    {
114        let mut edges = vec![];
115
116        let id_map = graph.continuos_id_map();
117
118        let src_virt_id = id_map.virt_id_of(src_id);
119
120        self.dist[src_virt_id] = W::zero().into();
121
122        while let Some(virt_id) = self.next_id() {
123            self.visited[virt_id] = true;
124
125            let real_id = id_map.real_id_of(virt_id);
126
127            for (n_id, edge) in graph.edges_from_unchecked(real_id) {
128                let n_virt_id = id_map.virt_id_of(n_id);
129
130                let alt = self.dist[virt_id] + *edge.get_weight();
131                if alt < self.dist[n_virt_id] {
132                    self.dist[n_virt_id] = alt;
133                    self.prev[n_virt_id] = virt_id.into();
134
135                    edges.retain(|(_, dst_id, _)| *dst_id != n_id); // remove edge to neighbor
136                    edges.push((real_id, n_id, edge.get_id())); // add new edge
137                }
138            }
139        }
140
141        let mut distance_map = HashMap::new();
142        for virt_id in 0..graph.vertex_count() {
143            let real_id = id_map.real_id_of(virt_id);
144            distance_map.insert(real_id, self.dist[virt_id]);
145        }
146
147        let vertices = edges
148            .iter()
149            .flat_map(|(src_id, dst_id, _)| vec![*src_id, *dst_id])
150            .chain(std::iter::once(src_id))
151            .collect::<HashSet<usize>>();
152
153        ShortestPathSubgraph::init(graph, edges, vertices, distance_map)
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use super::*;
160    use crate::graph::MatGraph;
161    use crate::storage::{DiMat, Mat};
162
163    #[test]
164    fn one_vertex_undirected_graph() {
165        // Given: Graph
166        //
167        //      a
168        //
169        let mut graph = MatGraph::init(Mat::<usize>::init());
170        let a = graph.add_vertex();
171
172        let sp_subgraph = Dijkstra::init(&graph).execute(&graph, a);
173
174        // assert_eq!(sp_subgraph.keys().len(), 1);
175        // assert_eq!(*sp_subgraph.get(&(a, a)).unwrap(), 0.into());
176        assert_eq!(sp_subgraph.distance_to(a).unwrap(), 0.into());
177        assert_eq!(sp_subgraph.vertex_count(), 1);
178        assert_eq!(sp_subgraph.vertices()[0], a);
179        assert_eq!(sp_subgraph.edges_count(), 0);
180    }
181
182    #[test]
183    fn one_vertex_directed_graph() {
184        // Given: Graph
185        //
186        //      a
187        //
188        let mut graph = MatGraph::init(DiMat::<usize>::init());
189        let a = graph.add_vertex();
190
191        let sp_subgraph = Dijkstra::init(&graph).execute(&graph, a);
192
193        assert_eq!(sp_subgraph.distance_to(a).unwrap(), 0.into());
194        assert_eq!(sp_subgraph.vertex_count(), 1); // how to add vertex? without edge? problem with Subgraph definition.
195        assert_eq!(sp_subgraph.vertices()[0], a);
196        assert_eq!(sp_subgraph.edges_count(), 0);
197    }
198
199    #[test]
200    fn trivial_undirected_graph() {
201        // Given: Graph
202        //          6       5
203        //      a  ---  b  ---  c
204        //    1 |       |       | 5
205        //      |  2 /`````\ 2  |
206        //      |````       ````|
207        //      d  -----------  e
208        //              1
209        let mut graph = MatGraph::init(Mat::<usize>::init());
210        let a = graph.add_vertex();
211        let b = graph.add_vertex();
212        let c = graph.add_vertex();
213        let d = graph.add_vertex();
214        let e = graph.add_vertex();
215
216        graph.add_edge_unchecked(a, b, 6.into());
217        let ad = graph.add_edge_unchecked(a, d, 1.into());
218        let bd = graph.add_edge_unchecked(b, d, 2.into());
219        graph.add_edge_unchecked(b, c, 5.into());
220        graph.add_edge_unchecked(b, e, 2.into());
221        let ce = graph.add_edge_unchecked(c, e, 5.into());
222        let de = graph.add_edge_unchecked(d, e, 1.into());
223
224        // When: Performing Dijkstra algorithm.
225        let sp_subgraph = Dijkstra::init(&graph).execute(&graph, a);
226
227        // Then:
228        assert_eq!(sp_subgraph.vertex_count(), 5);
229        assert_eq!(sp_subgraph.edges_count(), 4);
230        assert!(vec![a, b, c, d, e]
231            .iter()
232            .all(|vertex_id| sp_subgraph.vertices().contains(vertex_id)));
233        assert!(vec![ad, bd, ce, de]
234            .into_iter()
235            .all(|edge_id| sp_subgraph.edge(edge_id).is_ok()));
236        assert_eq!(sp_subgraph.distance_to(a).unwrap(), 0.into());
237        assert_eq!(sp_subgraph.distance_to(b).unwrap(), 3.into());
238        assert_eq!(sp_subgraph.distance_to(c).unwrap(), 7.into());
239        assert_eq!(sp_subgraph.distance_to(d).unwrap(), 1.into());
240        assert_eq!(sp_subgraph.distance_to(e).unwrap(), 2.into());
241    }
242
243    #[test]
244    fn trivial_directed_graph() {
245        // Given: Graph
246        //          6       1
247        //      a  -->  b  <--  c ---
248        //    1 |       |           |
249        //      |  2 /`````\ 2      |
250        //      |````       ````|   |
251        //      v               v   | 1
252        //      d  ---------->  e --'
253        //              1
254        let mut graph = MatGraph::init(DiMat::<usize>::init());
255        let a = graph.add_vertex(); // 0
256        let b = graph.add_vertex(); // 1
257        let c = graph.add_vertex(); // 2
258        let d = graph.add_vertex(); // 3
259        let e = graph.add_vertex(); // 4
260
261        graph.add_edge_unchecked(a, b, 6.into());
262        let ad = graph.add_edge_unchecked(a, d, 1.into());
263        graph.add_edge_unchecked(b, d, 2.into());
264        graph.add_edge_unchecked(b, e, 2.into());
265        let cb = graph.add_edge_unchecked(c, b, 1.into());
266        let ec = graph.add_edge_unchecked(e, c, 1.into());
267        let de = graph.add_edge_unchecked(d, e, 1.into());
268
269        // When: Performing Dijkstra algorithm.
270        let sp_subgraph = Dijkstra::init(&graph).execute(&graph, a);
271
272        // Then:
273        assert_eq!(sp_subgraph.vertex_count(), 5);
274        assert_eq!(sp_subgraph.edges_count(), 4);
275        assert!(vec![a, b, c, d, e]
276            .iter()
277            .all(|vertex_id| sp_subgraph.vertices().contains(vertex_id)));
278        assert!(vec![ad, cb, ec, de]
279            .into_iter()
280            .all(|edge_id| sp_subgraph.edge(edge_id).is_ok()));
281        assert_eq!(sp_subgraph.distance_to(a).unwrap(), 0.into());
282        assert_eq!(sp_subgraph.distance_to(b).unwrap(), 4.into());
283        assert_eq!(sp_subgraph.distance_to(c).unwrap(), 3.into());
284        assert_eq!(sp_subgraph.distance_to(d).unwrap(), 1.into());
285        assert_eq!(sp_subgraph.distance_to(e).unwrap(), 2.into());
286    }
287}
prepona/algo/shortest_path/dijkstra.rs

prepona/algo/shortest_path/
dijkstra.rs
