aoclib_rs/
dijkstra.rs

1use std::{
2    cmp::{Ordering, Reverse},
3    collections::BinaryHeap,
4    ops::Add,
5};
6
7/// An object on which we can run Dijkstra's algorithm to retrieve the multiple shortest paths.
8pub trait Dijkstrable {
9    /// "Point", "node", or "vertex" type.
10    type Point: Copy;
11
12    /// Type for the bounds of the search (useful if searching in a `Vec` or similar rather than a
13    /// graph proper). This is only used in the implementation of `neighbours()`, so it can be
14    /// effectively ignored if it's not relevant for that particular implementation.
15    type Bounds: ?Sized + Copy;
16
17    /// Type for the distance.
18    type Dist: Copy + Add<Output = Self::Dist>;
19
20    /// Type for the elements of a priority queue structure. `PqElement` is often a good choice.
21    type PQE: PriorityQueueElement<Point = Self::Point, Dist = Self::Dist>;
22
23    /// Returns an iterator to all the neighbours (or "adjacent points") of the provided `Point`.
24    /// Implementations can ignore the `Bounds` if it's not relevant.
25    fn neighbours(
26        _: Self::Point,
27        _: Self::Bounds,
28    ) -> impl Iterator<Item = (Self::Point, Self::Dist)>;
29
30    /// Returns whether it is impossible to get to the destination from the current `Point`.
31    fn is_impossible(&self, _: Self::Point) -> bool;
32
33    /// Returns the distance between the destination and the current `Point`, or `None` if it has
34    /// not been computed yet or is impossible.
35    fn dist(&self, _: Self::Point) -> Option<Self::Dist>;
36
37    /// Sets the distance between the destination and the current `Point`. If the destination and
38    /// the current `Point` are not connected, `None` will be passed in.
39    fn set_dist(&mut self, _: Self::Point, _: Option<Self::Dist>);
40
41    /// Performs Dijkstra's algorithm. The result is the ending `dist()` value for the starting
42    /// point.
43    fn dijkstra(&mut self, start: Self::Point, start_dist: Self::Dist, bounds: Self::Bounds) {
44        let mut q = BinaryHeap::new();
45        q.push(Reverse(Self::PQE::init(start, start_dist)));
46
47        while !q.is_empty() {
48            let curr = q.pop().unwrap();
49
50            for n in Self::neighbours(curr.0.point(), bounds) {
51                let d = if self.is_impossible(n.0) {
52                    None
53                } else {
54                    Some(curr.0.dist() + n.1)
55                };
56                if let Some(dval) = d
57                    && self.dist(n.0).is_none()
58                {
59                    self.set_dist(n.0, d);
60                    q.push(Reverse(Self::PQE::init(n.0, dval)));
61                }
62            }
63        }
64    }
65}
66
67/// Element of a priority queue.
68pub trait PriorityQueueElement: Ord + Copy + Sized {
69    /// "Point", "node", or "vertex" type.
70    type Point;
71
72    /// Type for the distance or "value" of the point.
73    type Dist: Add<Output = Self::Dist>;
74
75    fn init(_: Self::Point, _: Self::Dist) -> Self;
76    fn point(&self) -> Self::Point;
77    fn dist(&self) -> Self::Dist;
78}
79
80/// Concrete implementation of `PriorityQueueElement`. Comparison and equality operations only care
81/// about `val`.
82#[derive(Copy, Clone)]
83pub struct PqElement<Point, Value>
84where
85    Point: Copy,
86    Value: Copy + Add<Output = Value> + Ord,
87{
88    point: Point,
89    val: Value,
90}
91
92impl<Point, Value> Ord for PqElement<Point, Value>
93where
94    Point: Copy,
95    Value: Copy + Add<Output = Value> + Ord,
96{
97    fn cmp(&self, other: &Self) -> Ordering {
98        self.val.cmp(&other.val)
99    }
100}
101
102impl<Point, Value> PartialOrd for PqElement<Point, Value>
103where
104    Point: Copy,
105    Value: Copy + Add<Output = Value> + Ord,
106{
107    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
108        Some(self.cmp(other))
109    }
110}
111
112impl<Point, Value> PartialEq for PqElement<Point, Value>
113where
114    Point: Copy,
115    Value: Copy + Add<Output = Value> + Ord,
116{
117    fn eq(&self, other: &Self) -> bool {
118        self.val == other.val
119    }
120}
121
122impl<Point, Value> Eq for PqElement<Point, Value>
123where
124    Point: Copy,
125    Value: Copy + Add<Output = Value> + Ord,
126{
127}
128
129impl<Point, Value> PriorityQueueElement for PqElement<Point, Value>
130where
131    Point: Copy,
132    Value: Copy + Add<Output = Value> + Ord,
133{
134    type Point = Point;
135    type Dist = Value;
136
137    fn init(p: Self::Point, d: Self::Dist) -> Self {
138        PqElement { point: p, val: d }
139    }
140
141    fn point(&self) -> Self::Point {
142        self.point
143    }
144
145    fn dist(&self) -> Self::Dist {
146        self.val
147    }
148}
aoclib_rs/dijkstra.rs

aoclib_rs/
dijkstra.rs
