h3ron_graph/algorithm/
path.rs

1use std::cmp::Ordering;
2
3use geo_types::LineString;
4use serde::{Deserialize, Serialize};
5
6use h3ron::to_geo::{ToLineString, ToMultiLineString};
7use h3ron::{H3Cell, H3DirectedEdge, Index};
8
9use crate::error::Error;
10
11/// [DirectedEdgePath] describes a path between a cell and another.
12#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
13pub enum DirectedEdgePath {
14    /// path is empty as origin and destination are the same.
15    OriginIsDestination(H3Cell),
16
17    /// a sequence of edges describing the path.
18    ///
19    /// The edges in the vec are expected to be consecutive.
20    ///
21    /// The cost is the total cost summed for all of the edges.
22    DirectedEdgeSequence(Vec<H3DirectedEdge>),
23}
24
25impl DirectedEdgePath {
26    pub fn is_empty(&self) -> bool {
27        match self {
28            Self::OriginIsDestination(_) => true,
29            Self::DirectedEdgeSequence(edges) => edges.is_empty(),
30        }
31    }
32
33    /// Length of the path in number of edges
34    pub fn len(&self) -> usize {
35        match self {
36            Self::OriginIsDestination(_) => 0,
37            Self::DirectedEdgeSequence(edges) => edges.len(),
38        }
39    }
40
41    pub fn origin_cell(&self) -> Result<H3Cell, Error> {
42        match self {
43            Self::OriginIsDestination(cell) => Ok(*cell),
44            Self::DirectedEdgeSequence(edges) => {
45                if let Some(edge) = edges.first() {
46                    Ok(edge.origin_cell()?)
47                } else {
48                    Err(Error::EmptyPath)
49                }
50            }
51        }
52    }
53
54    pub fn destination_cell(&self) -> Result<H3Cell, Error> {
55        match self {
56            Self::OriginIsDestination(cell) => Ok(*cell),
57            Self::DirectedEdgeSequence(edges) => {
58                if let Some(edge) = edges.last() {
59                    Ok(edge.destination_cell()?)
60                } else {
61                    Err(Error::EmptyPath)
62                }
63            }
64        }
65    }
66
67    pub fn to_linestring(&self) -> Result<LineString<f64>, Error> {
68        match self {
69            Self::OriginIsDestination(_) => Err(Error::InsufficientNumberOfEdges),
70            Self::DirectedEdgeSequence(edges) => match edges.len() {
71                0 => Err(Error::InsufficientNumberOfEdges),
72                1 => Ok(edges[0].to_linestring()?),
73                _ => {
74                    let mut multilinesstring = edges.to_multilinestring()?;
75                    match multilinesstring.0.len() {
76                        0 => Err(Error::InsufficientNumberOfEdges),
77                        1 => Ok(multilinesstring.0.remove(0)),
78                        _ => Err(Error::SegmentedPath),
79                    }
80                }
81            },
82        }
83    }
84
85    pub fn edges(&self) -> &[H3DirectedEdge] {
86        match self {
87            Self::DirectedEdgeSequence(edges) => edges.as_slice(),
88            Self::OriginIsDestination(_) => &[],
89        }
90    }
91
92    /// return a vec of all [`H3Cell`] the path passes through.
93    pub fn cells(&self) -> Result<Vec<H3Cell>, Error> {
94        match self {
95            Self::OriginIsDestination(cell) => Ok(vec![*cell]),
96            Self::DirectedEdgeSequence(edges) => {
97                let mut cells = Vec::with_capacity(edges.len() * 2);
98                for edge in edges.iter() {
99                    cells.push(edge.origin_cell()?);
100                    cells.push(edge.destination_cell()?);
101                }
102                cells.dedup();
103                cells.shrink_to_fit();
104                Ok(cells)
105            }
106        }
107    }
108
109    /// calculate the length of the path in meters using the exact length of the
110    /// contained edges
111    pub fn length_m(&self) -> Result<f64, Error> {
112        match self {
113            Self::OriginIsDestination(_) => Ok(0.0),
114            Self::DirectedEdgeSequence(edges) => {
115                let mut length_m = 0.0;
116                for edge in edges {
117                    length_m += edge.length_m()?;
118                }
119                Ok(length_m)
120            }
121        }
122    }
123}
124
125/// [Path] describes a path between a cell and another with an associated cost
126#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
127pub struct Path<W> {
128    /// The cell the path starts at.
129    ///
130    /// This is the cell the path was calculated from. The actual start cell of the
131    /// path may differ in case `origin_cell` is not directly connected to the graph
132    pub origin_cell: H3Cell,
133
134    /// The cell the path ends at.
135    ///
136    /// This is the cell the path was calculated to. The actual end cell of the
137    /// path may differ in case `destination_cell` is not directly connected to the graph
138    pub destination_cell: H3Cell,
139
140    pub cost: W,
141
142    /// describes the path
143    pub directed_edge_path: DirectedEdgePath,
144}
145
146impl<W> Path<W> {
147    #[inline]
148    pub fn is_empty(&self) -> bool {
149        self.directed_edge_path.is_empty()
150    }
151
152    #[inline]
153    pub fn len(&self) -> usize {
154        self.directed_edge_path.len()
155    }
156}
157
158impl<W> TryFrom<(DirectedEdgePath, W)> for Path<W> {
159    type Error = Error;
160
161    fn try_from((path_directed_edges, cost): (DirectedEdgePath, W)) -> Result<Self, Self::Error> {
162        let origin_cell = path_directed_edges.origin_cell()?;
163        let destination_cell = path_directed_edges.destination_cell()?;
164        Ok(Self {
165            origin_cell,
166            destination_cell,
167            cost,
168            directed_edge_path: path_directed_edges,
169        })
170    }
171}
172
173impl PartialOrd<Self> for DirectedEdgePath {
174    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
175        Some(self.cmp(other))
176    }
177}
178
179impl Ord for DirectedEdgePath {
180    fn cmp(&self, other: &Self) -> Ordering {
181        let cmp_origin = index_or_zero(self.origin_cell()).cmp(&index_or_zero(other.origin_cell()));
182        if cmp_origin == Ordering::Equal {
183            index_or_zero(self.destination_cell()).cmp(&index_or_zero(other.destination_cell()))
184        } else {
185            cmp_origin
186        }
187    }
188}
189
190/// order by cost, origin index and destination_index.
191///
192/// This ordering can used to bring `Vec`s of routes in a deterministic order to make them
193/// comparable
194impl<W> Ord for Path<W>
195where
196    W: Ord,
197{
198    fn cmp(&self, other: &Self) -> Ordering {
199        let cmp_cost = self.cost.cmp(&other.cost);
200        if cmp_cost == Ordering::Equal {
201            self.directed_edge_path.cmp(&other.directed_edge_path)
202        } else {
203            cmp_cost
204        }
205    }
206}
207
208impl<W> PartialOrd for Path<W>
209where
210    W: Ord,
211{
212    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
213        Some(self.cmp(other))
214    }
215}
216
217#[inline]
218fn index_or_zero(cell: Result<H3Cell, Error>) -> u64 {
219    cell.map(|c| c.h3index()).unwrap_or(0)
220}
221
222#[cfg(test)]
223mod tests {
224    use h3ron::{H3DirectedEdge, Index};
225
226    use super::{DirectedEdgePath, Path};
227
228    #[test]
229    fn pathdirectededges_deterministic_ordering() {
230        let r1 =
231            DirectedEdgePath::DirectedEdgeSequence(vec![H3DirectedEdge::new(0x1176b49474ffffff)]);
232        let r2 =
233            DirectedEdgePath::DirectedEdgeSequence(vec![H3DirectedEdge::new(0x1476b49474ffffff)]);
234        let mut paths = vec![r2.clone(), r1.clone()];
235        paths.sort_unstable();
236        assert_eq!(paths[0], r1);
237        assert_eq!(paths[1], r2);
238    }
239
240    #[test]
241    fn paths_deterministic_ordering() {
242        let r1: Path<_> = (
243            DirectedEdgePath::DirectedEdgeSequence(vec![H3DirectedEdge::new(0x1176b49474ffffff)]),
244            1,
245        )
246            .try_into()
247            .unwrap();
248        let r2: Path<_> = (
249            DirectedEdgePath::DirectedEdgeSequence(vec![H3DirectedEdge::new(0x1476b49474ffffff)]),
250            3,
251        )
252            .try_into()
253            .unwrap();
254        let r3: Path<_> = (
255            DirectedEdgePath::DirectedEdgeSequence(vec![H3DirectedEdge::new(0x1476b4b2c2ffffff)]),
256            3,
257        )
258            .try_into()
259            .unwrap();
260        let mut paths = vec![r3.clone(), r1.clone(), r2.clone()];
261        paths.sort_unstable();
262        assert_eq!(paths[0], r1);
263        assert_eq!(paths[1], r2);
264        assert_eq!(paths[2], r3);
265    }
266}
h3ron_graph/algorithm/path.rs

h3ron_graph/algorithm/
path.rs
