h3ron_graph/algorithm/
differential_shortest_path.rs

1use std::borrow::Borrow;
2use std::ops::Add;
3
4use num_traits::Zero;
5use serde::{Deserialize, Serialize};
6
7use h3ron::collections::{ContainsIndex, H3CellMap, H3Treemap, HashMap, RandomState};
8use h3ron::{H3Cell, HasH3Resolution, Index};
9
10use crate::algorithm::path::Path;
11use crate::algorithm::shortest_path::{ShortestPathManyToMany, ShortestPathOptions};
12use crate::algorithm::NearestGraphNodes;
13use crate::error::Error;
14use crate::graph::modifiers::ExcludeCells;
15use crate::graph::{GetCellEdges, GetCellNode};
16
17#[derive(Serialize, Deserialize)]
18pub struct ExclusionDiff<T> {
19    /// the results of the shortest-path calculation before the cells have been
20    /// excluded from the graph.
21    pub before_cell_exclusion: Vec<T>,
22
23    /// the results of the shortest-path calculation after the cells have been
24    /// excluded from the graph.
25    pub after_cell_exclusion: Vec<T>,
26}
27
28/// "Differential" routing calculates the shortest path from (multiple) origin cells
29/// to the `N` nearest destinations.
30/// This done once to the un-modified graph, and once the the graph with a set of nodes
31/// being removed, the `exclude_cells` parameter.
32pub trait DifferentialShortestPath<W>
33where
34    W: Send + Sync + Ord + Copy,
35{
36    fn differential_shortest_path<I, OPT>(
37        &self,
38        origin_cells: I,
39        destination_cells: I,
40        exclude_cells: &H3Treemap<H3Cell>,
41        options: &OPT,
42    ) -> Result<HashMap<H3Cell, ExclusionDiff<Path<W>>>, Error>
43    where
44        I: IntoIterator,
45        I::Item: Borrow<H3Cell>,
46        OPT: ShortestPathOptions + Send + Sync,
47    {
48        self.differential_shortest_path_map(
49            origin_cells,
50            destination_cells,
51            exclude_cells,
52            options,
53            Ok,
54        )
55    }
56
57    fn differential_shortest_path_map<I, OPT, PM, O>(
58        &self,
59        origin_cells: I,
60        destination_cells: I,
61        exclude_cells: &H3Treemap<H3Cell>,
62        options: &OPT,
63        path_transform_fn: PM,
64    ) -> Result<HashMap<H3Cell, ExclusionDiff<O>>, Error>
65    where
66        I: IntoIterator,
67        I::Item: Borrow<H3Cell>,
68        OPT: ShortestPathOptions + Send + Sync,
69        O: Send + Ord + Clone,
70        PM: Fn(Path<W>) -> Result<O, Error> + Send + Sync;
71}
72
73impl<G, W> DifferentialShortestPath<W> for G
74where
75    W: PartialOrd + PartialEq + Add + Copy + Send + Ord + Zero + Sync,
76    G: GetCellEdges<EdgeWeightType = W>
77        + GetCellNode
78        + HasH3Resolution
79        + NearestGraphNodes
80        + Sync
81        + ShortestPathManyToMany<W>,
82{
83    fn differential_shortest_path_map<I, OPT, PM, O>(
84        &self,
85        origin_cells: I,
86        destination_cells: I,
87        exclude_cells: &H3Treemap<H3Cell>,
88        options: &OPT,
89        path_transform_fn: PM,
90    ) -> Result<HashMap<H3Cell, ExclusionDiff<O>>, Error>
91    where
92        I: IntoIterator,
93        I::Item: Borrow<H3Cell>,
94        OPT: ShortestPathOptions + Send + Sync,
95        O: Send + Ord + Clone,
96        PM: Fn(Path<W>) -> Result<O, Error> + Send + Sync,
97    {
98        if exclude_cells.is_empty() {
99            return Err(Error::Other("exclude_cells must not be empty".to_string()));
100        };
101        let origin_cells = check_resolution_and_collect(
102            origin_cells.into_iter().filter(|c| {
103                // exclude the cells of the disturbance itself from routing
104                !exclude_cells.contains_index(c.borrow())
105            }),
106            self.h3_resolution(),
107        )?;
108        let destination_cells =
109            check_resolution_and_collect(destination_cells, self.h3_resolution())?;
110
111        let mut paths_before = self.shortest_path_many_to_many_map(
112            &origin_cells,
113            &destination_cells,
114            options,
115            &path_transform_fn,
116        )?;
117
118        let exclude_wrapper = ExcludeCells::new(self, exclude_cells);
119        let mut paths_after = exclude_wrapper.shortest_path_many_to_many_map(
120            &origin_cells,
121            &destination_cells,
122            options,
123            path_transform_fn,
124        )?;
125
126        let mut out_diffs =
127            H3CellMap::with_capacity_and_hasher(paths_before.len(), RandomState::default());
128        for (cell, paths) in paths_before.drain() {
129            out_diffs.insert(
130                cell,
131                ExclusionDiff {
132                    before_cell_exclusion: paths,
133                    after_cell_exclusion: paths_after.remove(&cell).unwrap_or_default(),
134                },
135            );
136        }
137        Ok(out_diffs)
138    }
139}
140
141fn check_resolution_and_collect<I>(in_cells: I, h3_resolution: u8) -> Result<Vec<H3Cell>, Error>
142where
143    I: IntoIterator,
144    I::Item: Borrow<H3Cell>,
145{
146    let mut out_cells = in_cells
147        .into_iter()
148        .map(|cell| {
149            if cell.borrow().resolution() != h3_resolution {
150                Err(Error::MixedH3Resolutions(
151                    h3_resolution,
152                    cell.borrow().resolution(),
153                ))
154            } else {
155                Ok(*cell.borrow())
156            }
157        })
158        .collect::<Result<Vec<_>, _>>()?;
159    out_cells.sort_unstable();
160    out_cells.dedup();
161    Ok(out_cells)
162}
h3ron_graph/algorithm/differential_shortest_path.rs

h3ron_graph/algorithm/
differential_shortest_path.rs
