h3ron_graph/algorithm/
within_weight_threshold.rs

1use std::borrow::Borrow;
2use std::ops::Add;
3
4use num_traits::Zero;
5use rayon::prelude::*;
6
7use h3ron::collections::hashbrown::hash_map::Entry;
8use h3ron::collections::H3CellMap;
9use h3ron::H3Cell;
10
11use crate::algorithm::dijkstra::edge_dijkstra_weight_threshold;
12use crate::error::Error;
13use crate::graph::GetCellEdges;
14
15/// Find all cells connected to the graph around a origin cell within a given threshold
16pub trait WithinWeightThreshold<W> {
17    /// Find all cells connected to the graph within a given `weight_threshold` around the
18    /// given `origin_cell`
19    fn cells_within_weight_threshold(
20        &self,
21        origin_cell: H3Cell,
22        weight_threshold: W,
23    ) -> Result<H3CellMap<W>, Error>;
24}
25
26impl<W, G> WithinWeightThreshold<W> for G
27where
28    G: GetCellEdges<EdgeWeightType = W>,
29    W: Zero + Ord + Copy + Add,
30{
31    fn cells_within_weight_threshold(
32        &self,
33        origin_cell: H3Cell,
34        weight_threshold: W,
35    ) -> Result<H3CellMap<W>, Error> {
36        edge_dijkstra_weight_threshold(self, &origin_cell, weight_threshold)
37    }
38}
39
40/// Find all cells connected to the graph around a origin cell within a given threshold
41pub trait WithinWeightThresholdMany<W> {
42    /// Find all cells connected to the graph within a given `weight_threshold` around the
43    /// given `origin_cells`.
44    ///
45    /// The weights for cells which are traversed from multiple `origin_cells` are aggregated using
46    /// `agg_fn`. This can be used - for example - to find the minimum or maximum weight for a cell.
47    fn cells_within_weight_threshold_many<I, AGG>(
48        &self,
49        origin_cells: I,
50        weight_threshold: W,
51        agg_fn: AGG,
52    ) -> Result<H3CellMap<W>, Error>
53    where
54        I: IntoParallelIterator,
55        I::Item: Borrow<H3Cell>,
56        AGG: Fn(&mut W, W) + Sync;
57}
58
59impl<W, G> WithinWeightThresholdMany<W> for G
60where
61    G: GetCellEdges<EdgeWeightType = W> + WithinWeightThreshold<W> + Sync,
62    W: Zero + Ord + Copy + Add + Send + Sync,
63{
64    fn cells_within_weight_threshold_many<I, AGG>(
65        &self,
66        origin_cells: I,
67        weight_threshold: W,
68        agg_fn: AGG,
69    ) -> Result<H3CellMap<W>, Error>
70    where
71        I: IntoParallelIterator,
72        I::Item: Borrow<H3Cell>,
73        AGG: Fn(&mut W, W) + Sync,
74    {
75        origin_cells
76            .into_par_iter()
77            .map(|item| self.cells_within_weight_threshold(*item.borrow(), weight_threshold))
78            .try_reduce_with(|cellmap1, cellmap2| {
79                // select the source and target maps, to move the contents of the map with fewer elements, to the map
80                // with more elements. This should save quite a few hashing operations.
81                let (source_cellmap, mut target_cellmap) = if cellmap1.len() < cellmap2.len() {
82                    (cellmap1, cellmap2)
83                } else {
84                    (cellmap2, cellmap1)
85                };
86
87                for (cell, weight) in source_cellmap {
88                    match target_cellmap.entry(cell) {
89                        Entry::Occupied(mut entry) => {
90                            agg_fn(entry.get_mut(), weight);
91                        }
92                        Entry::Vacant(entry) => {
93                            entry.insert(weight);
94                        }
95                    };
96                }
97                Ok(target_cellmap)
98            })
99            .unwrap_or_else(|| Ok(Default::default()))
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use std::collections::HashMap;
106    use std::convert::TryInto;
107
108    use geo_types::{Geometry, Line};
109
110    use h3ron::iter::continuous_cells_to_edges;
111    use h3ron::{H3Cell, ToH3Cells};
112
113    use crate::algorithm::{WithinWeightThreshold, WithinWeightThresholdMany};
114    use crate::graph::{GetStats, H3EdgeGraph, PreparedH3EdgeGraph};
115
116    /// a simple graph consisting of a single line
117    fn line_graph(default_weight: u32) -> (Vec<H3Cell>, PreparedH3EdgeGraph<u32>) {
118        let h3_resolution = 4;
119        let cell_sequence: Vec<_> = Geometry::Line(Line {
120            start: (10.0f64, 20.0f64).into(),
121            end: (20., 20.).into(),
122        })
123        .to_h3_cells(h3_resolution)
124        .unwrap()
125        .iter()
126        .collect();
127
128        let mut g = H3EdgeGraph::new(h3_resolution);
129        for edge_result in continuous_cells_to_edges(&cell_sequence) {
130            g.add_edge(edge_result.unwrap(), default_weight).unwrap();
131        }
132        (cell_sequence, g.try_into().unwrap())
133    }
134
135    #[test]
136    fn test_cells_within_weight_threshold() {
137        let (cell_sequence, prepared_graph) = line_graph(10);
138        assert!(prepared_graph.get_stats().unwrap().num_edges > 10);
139        let within_threshold = prepared_graph
140            .cells_within_weight_threshold(cell_sequence[0], 30)
141            .unwrap();
142        assert_eq!(within_threshold.len(), 4);
143        let weights: Vec<_> = within_threshold.values().copied().collect();
144        assert!(weights.contains(&0));
145        assert!(weights.contains(&10));
146        assert!(weights.contains(&20));
147        assert!(weights.contains(&30));
148    }
149
150    #[test]
151    fn test_cells_within_weight_threshold_many() {
152        let (cell_sequence, prepared_graph) = line_graph(10);
153        assert!(prepared_graph.get_stats().unwrap().num_edges > 20);
154
155        let origin_cells = vec![
156            cell_sequence[0],
157            cell_sequence[1], // overlaps with the previous cell
158            cell_sequence[10],
159        ];
160
161        let within_threshold = prepared_graph
162            .cells_within_weight_threshold_many(
163                origin_cells,
164                30,
165                // use the minimum weight encountered
166                |existing, new| {
167                    if new < *existing {
168                        *existing = new
169                    }
170                },
171            )
172            .unwrap();
173        assert_eq!(within_threshold.len(), 9);
174        let weights_freq = within_threshold
175            .iter()
176            .fold(HashMap::new(), |mut agg, (_, weight)| {
177                agg.entry(weight).and_modify(|c| *c += 1).or_insert(1u32);
178                agg
179            });
180        assert_eq!(weights_freq[&0], 3);
181        assert_eq!(weights_freq[&10], 2);
182        assert_eq!(weights_freq[&20], 2);
183        assert_eq!(weights_freq[&30], 2);
184    }
185}
h3ron_graph/algorithm/within_weight_threshold.rs

h3ron_graph/algorithm/
within_weight_threshold.rs
