rshyper_algo/
dijkstra.rs

1/*
2    appellation: dijkstra <module>
3    authors: @FL03
4*/
5//! this module implements Dijkstra's shortest-path algorithm for hypergraphs
6#[doc(inline)]
7pub use self::queue_node::QueueNode;
8
9mod queue_node;
10
11use crate::error::{Error, Result};
12use crate::traits::{PathFinder, Search, Traversal};
13
14use alloc::collections::BinaryHeap;
15use core::hash::{BuildHasher, Hash};
16use hashbrown::{DefaultHashBuilder, HashMap, HashSet};
17use num_traits::bounds::UpperBounded;
18use num_traits::{FromPrimitive, Num};
19use rshyper::idx::{HyperIndex, RawIndex, VertexId, VertexSet};
20use rshyper::rel::RawLayout;
21use rshyper::{GraphProps, HyperGraph, HyperGraphIter};
22
23/// a type alias for a map of distances for vertices in the graph
24pub(crate) type Distances<K, V = f64, S = DefaultHashBuilder> = HashMap<VertexId<K>, V, S>;
25/// a type alias for the history of previous vertices in the graph, maps vertices to vertices
26pub(crate) type PreviousHistory<K, S = DefaultHashBuilder> = HashMap<VertexId<K>, VertexId<K>, S>;
27
28/// Dijkstra's shortest path algorithm for hypergraphs
29pub struct Dijkstra<'a, N, E, A, H, S = DefaultHashBuilder>
30where
31    A: GraphProps,
32    H: HyperGraph<N, E, A>,
33{
34    pub(crate) graph: &'a H,
35    pub(crate) distances: Distances<A::Ix, E, S>,
36    pub(crate) previous: PreviousHistory<A::Ix, S>,
37    pub(crate) visited: VertexSet<A::Ix, S>,
38    _marker: core::marker::PhantomData<(N, E)>,
39}
40
41impl<'a, N, E, A, H, S> Dijkstra<'a, N, E, A, H, S>
42where
43    A: GraphProps,
44    H: HyperGraph<N, E, A>,
45    S: BuildHasher,
46    A::Ix: RawIndex,
47{
48    /// Create a new Dijkstra instance
49    pub fn new(graph: &'a H) -> Self
50    where
51        S: Default,
52    {
53        Self {
54            graph,
55            distances: Distances::default(),
56            previous: PreviousHistory::default(),
57            visited: VertexSet::default(),
58            _marker: core::marker::PhantomData::<(N, E)>,
59        }
60    }
61    /// returns a reference to the graph
62    pub const fn graph(&self) -> &H {
63        self.graph
64    }
65    /// returns a reference to the distances
66    pub const fn distances(&self) -> &Distances<A::Ix, E, S> {
67        &self.distances
68    }
69    /// returns a mutable reference to the distances
70    pub const fn distances_mut(&mut self) -> &mut Distances<A::Ix, E, S> {
71        &mut self.distances
72    }
73    /// returns a reference to the previous history
74    pub const fn previous(&self) -> &PreviousHistory<A::Ix, S> {
75        &self.previous
76    }
77    /// returns a mutable reference to the previous history
78    pub const fn previous_mut(&mut self) -> &mut PreviousHistory<A::Ix, S> {
79        &mut self.previous
80    }
81    /// returns a reference to the visited vertices
82    pub const fn visited(&self) -> &VertexSet<A::Ix, S> {
83        &self.visited
84    }
85    /// returns a mutable reference to the visited vertices
86    pub const fn visited_mut(&mut self) -> &mut VertexSet<A::Ix, S> {
87        &mut self.visited
88    }
89    /// update the distances and returns a mutable reference to the instance
90    pub fn set_distances(&mut self, distances: Distances<A::Ix, E, S>) -> &mut Self {
91        *self.distances_mut() = distances;
92        self
93    }
94    /// update the previous history and returns a mutable reference to the instance
95    pub fn set_previous(&mut self, previous: PreviousHistory<A::Ix, S>) -> &mut Self {
96        *self.previous_mut() = previous;
97        self
98    }
99    /// update the visited vertices and returns a mutable reference to the instance
100    pub fn set_visited(&mut self, visited: VertexSet<A::Ix, S>) -> &mut Self {
101        *self.visited_mut() = visited;
102        self
103    }
104    /// add a new node to the distances
105    pub fn add_distance(&mut self, vertex: VertexId<A::Ix>, distance: E) -> &mut Self
106    where
107        A::Ix: Eq + Hash,
108    {
109        self.distances_mut().insert(vertex, distance);
110        self
111    }
112    /// add a vertex to the previous history
113    pub fn add_previous(&mut self, vertex: VertexId<A::Ix>, previous: VertexId<A::Ix>) -> &mut Self
114    where
115        A::Ix: Eq + Hash,
116    {
117        self.previous_mut().insert(vertex, previous);
118        self
119    }
120    /// record a vertex as visited
121    pub fn add_visited(&mut self, vertex: VertexId<A::Ix>) -> &mut Self
122    where
123        A::Ix: Eq + Hash,
124    {
125        self.visited_mut().insert(vertex);
126        self
127    }
128    /// Find the shortest path from `start` to `goal`
129    pub fn find_path(
130        &mut self,
131        start: VertexId<A::Ix>,
132        dest: VertexId<A::Ix>,
133    ) -> Result<<Self as PathFinder<A::Ix>>::Path>
134    where
135        Self: PathFinder<A::Ix>,
136    {
137        PathFinder::find_path(self, start, dest)
138    }
139    /// search for a path starting from `start` to the vertex with the largest ID
140    pub fn search(
141        &mut self,
142        start: VertexId<A::Ix>,
143    ) -> Result<<Self as Search<VertexId<A::Ix>>>::Output>
144    where
145        Self: Search<VertexId<A::Ix>>,
146    {
147        Search::search(self, start)
148    }
149    /// returns true if the vertex is visited
150    pub fn has_visited<Q>(&self, vertex: &Q) -> bool
151    where
152        Q: ?Sized + Eq + Hash,
153        A::Ix: Eq + Hash,
154        VertexId<A::Ix>: core::borrow::Borrow<Q>,
155    {
156        self.visited().contains(vertex)
157    }
158    /// Reset the state for reuse
159    pub fn reset(&mut self) -> &mut Self {
160        self.distances_mut().clear();
161        self.previous_mut().clear();
162        self.visited_mut().clear();
163        self
164    }
165}
166
167impl<'a, N, E, A, H, S> PathFinder<A::Ix> for Dijkstra<'a, N, E, A, H, S>
168where
169    E: Copy + Default + PartialOrd + FromPrimitive + Num + UpperBounded,
170    A: GraphProps,
171    H: HyperGraph<N, E, A>,
172    S: BuildHasher,
173    A::Ix: HyperIndex,
174    <H::Edge<E> as RawLayout>::Store: Clone + IntoIterator<Item = VertexId<A::Ix>>,
175{
176    type Path = Vec<VertexId<A::Ix>>;
177
178    fn find_path(&mut self, src: VertexId<A::Ix>, dest: VertexId<A::Ix>) -> Result<Self::Path> {
179        self.reset();
180
181        if !self.graph.contains_node(&src) {
182            return Err(rshyper::Error::NodeNotFound.into());
183        }
184        if !self.graph.contains_node(&dest) {
185            return Err(rshyper::Error::NodeNotFound.into());
186        }
187
188        let mut heap: BinaryHeap<QueueNode<A::Ix, E>> = BinaryHeap::new();
189        self.add_distance(src, E::zero());
190        heap.push(QueueNode::from_vertex(src));
191
192        while let Some(QueueNode {
193            vertex: u,
194            cost: u_cost,
195        }) = heap.pop()
196        {
197            // Only mark as visited when popping from the heap
198            if self.has_visited(&u) {
199                continue;
200            }
201            self.add_visited(u);
202
203            if u == dest {
204                return Ok(self.reconstruct_path(dest));
205            }
206
207            // For each neighbor via hyperedges
208            for edge_id in self.graph.find_edges_with_node(&u) {
209                // load the weight of the edge
210                let weight = self
211                    .graph
212                    .get_edge_weight(edge_id)
213                    .expect("no weight for the edge")
214                    .view();
215                // visit each node within the hyperedge
216                for v in self
217                    .graph
218                    .get_edge_domain(edge_id)
219                    .expect("empty hyperedge")
220                    .clone()
221                {
222                    if v == u {
223                        continue;
224                    }
225                    let alt = u_cost + **weight;
226                    if alt < *self.distances().get(&v).unwrap_or(&E::max_value()) {
227                        self.add_distance(v, alt).add_previous(v, u);
228                        heap.push(QueueNode::new(alt, v));
229                    }
230                }
231            }
232        }
233        Err(Error::PathNotFound)
234    }
235
236    fn reconstruct_path(&self, mut goal: VertexId<A::Ix>) -> Vec<VertexId<A::Ix>> {
237        // initialize a new path buffer
238        let mut path = Vec::new();
239        // add the target
240        path.push(goal);
241        // reconstruct the path by following the previous vertices
242        while let Some(&prev) = self.previous().get(&goal) {
243            path.push(prev);
244            goal = prev;
245        }
246        // reverse the path
247        path.reverse();
248        // return the reconstructed path
249        path
250    }
251}
252
253impl<'a, N, E, A, H, S> Traversal<VertexId<A::Ix>> for Dijkstra<'a, N, E, A, H, S>
254where
255    A: GraphProps,
256    H: HyperGraph<N, E, A>,
257    S: BuildHasher,
258    A::Ix: Eq + Hash,
259{
260    type Store<I2> = HashSet<I2, S>;
261
262    fn has_visited(&self, vertex: &VertexId<A::Ix>) -> bool {
263        self.visited().contains(vertex)
264    }
265
266    fn visited(&self) -> &Self::Store<VertexId<A::Ix>> {
267        &self.visited
268    }
269}
270
271impl<'a, N, E, A, H> Search<VertexId<A::Ix>> for Dijkstra<'a, N, E, A, H>
272where
273    E: Copy + Default + PartialOrd + FromPrimitive + Num + UpperBounded,
274    A: GraphProps,
275    H: HyperGraphIter<N, E, A>,
276    A::Ix: HyperIndex,
277    <H::Edge<E> as RawLayout>::Store: Clone + IntoIterator<Item = VertexId<A::Ix>>,
278{
279    type Output = Vec<VertexId<A::Ix>>;
280
281    fn search(&mut self, start: VertexId<A::Ix>) -> Result<Self::Output> {
282        // Use the vertex with the largest ID as a pseudo-goal if not specified
283        let max_vertex_id = match self.graph.vertices().max() {
284            Some(&id) => id,
285            None => {
286                #[cfg(feature = "tracing")]
287                tracing::warn!("Graph is empty, returning an empty path.");
288                return Ok(Vec::new());
289            }
290        };
291        // use the path-finding algorithm to find the path
292        let path = self.find_path(start, max_vertex_id)?;
293        #[cfg(feature = "tracing")]
294        tracing::info!("found path: {:?}", path);
295        Ok(path)
296    }
297}
rshyper_algo/dijkstra.rs

rshyper_algo/
dijkstra.rs
