solverforge_maps/routing/
matrix.rs

1//! Matrix computation for road networks.
2
3use rayon::prelude::*;
4use std::collections::HashMap;
5use tokio::sync::mpsc::{self, Sender};
6
7use super::algo::dijkstra_with_secondary;
8use super::coord::Coord;
9use super::graph::NodeIdx;
10use super::network::{RoadNetwork, SnappedCoord};
11use super::progress::RoutingProgress;
12
13pub const UNREACHABLE: i64 = i64::MAX;
14
15#[derive(Debug, Clone, Default)]
16pub struct TravelTimeMatrix {
17    data: Vec<i64>,
18    distance_data: Vec<i64>,
19    size: usize,
20    locations: Vec<SnappedCoord>,
21}
22
23impl TravelTimeMatrix {
24    pub(crate) fn new(
25        data: Vec<i64>,
26        distance_data: Vec<i64>,
27        size: usize,
28        locations: Vec<SnappedCoord>,
29    ) -> Self {
30        debug_assert_eq!(data.len(), size * size);
31        debug_assert_eq!(distance_data.len(), size * size);
32        debug_assert_eq!(locations.len(), size);
33        Self {
34            data,
35            distance_data,
36            size,
37            locations,
38        }
39    }
40
41    /// Get the travel time from one location to another.
42    ///
43    /// Returns `None` if indices are out of bounds.
44    /// Returns `Some(UNREACHABLE)` if the pair is not reachable.
45    #[inline]
46    pub fn get(&self, from: usize, to: usize) -> Option<i64> {
47        if from < self.size && to < self.size {
48            Some(self.data[from * self.size + to])
49        } else {
50            None
51        }
52    }
53
54    #[inline]
55    pub fn is_reachable(&self, from: usize, to: usize) -> bool {
56        self.get(from, to)
57            .map(|v| v != UNREACHABLE)
58            .unwrap_or(false)
59    }
60
61    /// Get the route distance in meters from one location to another.
62    ///
63    /// Returns `None` if indices are out of bounds.
64    /// Returns `Some(UNREACHABLE)` if the pair is not reachable.
65    #[inline]
66    pub fn distance_meters(&self, from: usize, to: usize) -> Option<i64> {
67        if from < self.size && to < self.size {
68            Some(self.distance_data[from * self.size + to])
69        } else {
70            None
71        }
72    }
73
74    #[inline]
75    pub fn size(&self) -> usize {
76        self.size
77    }
78
79    #[inline]
80    pub fn locations(&self) -> &[SnappedCoord] {
81        &self.locations
82    }
83
84    #[inline]
85    pub fn row(&self, i: usize) -> Option<&[i64]> {
86        if i < self.size {
87            let start = i * self.size;
88            Some(&self.data[start..start + self.size])
89        } else {
90            None
91        }
92    }
93
94    #[inline]
95    pub fn row_distances(&self, i: usize) -> Option<&[i64]> {
96        if i < self.size {
97            let start = i * self.size;
98            Some(&self.distance_data[start..start + self.size])
99        } else {
100            None
101        }
102    }
103
104    pub fn min(&self) -> Option<i64> {
105        let mut min_val = None;
106        for i in 0..self.size {
107            for j in 0..self.size {
108                if i == j {
109                    continue;
110                }
111                let val = self.data[i * self.size + j];
112                if val != UNREACHABLE {
113                    min_val = Some(min_val.map(|m: i64| m.min(val)).unwrap_or(val));
114                }
115            }
116        }
117        min_val
118    }
119
120    pub fn max(&self) -> Option<i64> {
121        let mut max_val = None;
122        for i in 0..self.size {
123            for j in 0..self.size {
124                if i == j {
125                    continue;
126                }
127                let val = self.data[i * self.size + j];
128                if val != UNREACHABLE {
129                    max_val = Some(max_val.map(|m: i64| m.max(val)).unwrap_or(val));
130                }
131            }
132        }
133        max_val
134    }
135
136    pub fn mean(&self) -> Option<f64> {
137        let mut sum = 0i64;
138        let mut count = 0usize;
139        for i in 0..self.size {
140            for j in 0..self.size {
141                if i == j {
142                    continue;
143                }
144                let val = self.data[i * self.size + j];
145                if val != UNREACHABLE {
146                    sum = sum.saturating_add(val);
147                    count += 1;
148                }
149            }
150        }
151        if count > 0 {
152            Some(sum as f64 / count as f64)
153        } else {
154            None
155        }
156    }
157
158    pub fn reachability_ratio(&self) -> f64 {
159        if self.size <= 1 {
160            return 1.0;
161        }
162        let total_pairs = self.size * (self.size - 1);
163        let reachable = self.count_reachable();
164        reachable as f64 / total_pairs as f64
165    }
166
167    fn count_reachable(&self) -> usize {
168        let mut count = 0;
169        for i in 0..self.size {
170            for j in 0..self.size {
171                if i != j && self.data[i * self.size + j] != UNREACHABLE {
172                    count += 1;
173                }
174            }
175        }
176        count
177    }
178
179    pub fn unreachable_pairs(&self) -> Vec<(usize, usize)> {
180        let mut pairs = Vec::new();
181        for i in 0..self.size {
182            for j in 0..self.size {
183                if i != j && self.data[i * self.size + j] == UNREACHABLE {
184                    pairs.push((i, j));
185                }
186            }
187        }
188        pairs
189    }
190
191    pub fn as_slice(&self) -> &[i64] {
192        &self.data
193    }
194
195    pub fn distances_as_slice(&self) -> &[i64] {
196        &self.distance_data
197    }
198}
199
200impl RoadNetwork {
201    pub async fn compute_matrix(
202        &self,
203        locations: &[Coord],
204        progress: Option<&Sender<RoutingProgress>>,
205    ) -> TravelTimeMatrix {
206        let n = locations.len();
207        if n == 0 {
208            return TravelTimeMatrix::new(vec![], vec![], 0, vec![]);
209        }
210
211        let node_snapped: Vec<Option<SnappedCoord>> = locations
212            .iter()
213            .map(|&coord| self.snap_to_road_detailed(coord).ok())
214            .collect();
215
216        let snapped_locations: Vec<SnappedCoord> = locations
217            .iter()
218            .zip(node_snapped.iter())
219            .map(|(&coord, edge_snap)| {
220                if let Some(snapped) = edge_snap {
221                    *snapped
222                } else {
223                    SnappedCoord {
224                        original: coord,
225                        snapped: coord,
226                        snap_distance_m: f64::INFINITY,
227                        node_index: NodeIdx::new(0),
228                    }
229                }
230            })
231            .collect();
232
233        let row_progress = progress.map(|tx| {
234            let (progress_tx, mut progress_rx) = mpsc::unbounded_channel::<usize>();
235            let tx = tx.clone();
236            let handle = tokio::spawn(async move {
237                let mut completed_rows = 0usize;
238                while progress_rx.recv().await.is_some() {
239                    completed_rows += 1;
240                    let percent = 55 + ((completed_rows * 44) / n.max(1)) as u8;
241                    let _ = tx
242                        .send(RoutingProgress::ComputingMatrix {
243                            percent,
244                            row: completed_rows,
245                            total: n,
246                        })
247                        .await;
248                }
249            });
250            (progress_tx, handle)
251        });
252
253        // Compute rows in parallel via rayon - each row runs Dijkstra from source endpoints
254        let graph = &self.graph;
255        let progress_tx = row_progress.as_ref().map(|(tx, _)| tx.clone());
256        let rows: Vec<(Vec<i64>, Vec<i64>)> = (0..n)
257            .into_par_iter()
258            .map(|i| {
259                let mut row = vec![0i64; n];
260                let mut distance_row = vec![0i64; n];
261
262                let Some(from) = &node_snapped[i] else {
263                    for (j, cell) in row.iter_mut().enumerate() {
264                        if i != j {
265                            *cell = UNREACHABLE;
266                            distance_row[j] = UNREACHABLE;
267                        }
268                    }
269                    if let Some(tx) = &progress_tx {
270                        let _ = tx.send(i);
271                    }
272                    return (row, distance_row);
273                };
274
275                let costs = dijkstra_with_secondary(
276                    graph,
277                    from.node_index,
278                    None,
279                    |e| e.travel_time_s,
280                    |e| e.distance_m,
281                );
282
283                for j in 0..n {
284                    if i == j {
285                        continue;
286                    }
287
288                    let Some(to) = &node_snapped[j] else {
289                        row[j] = UNREACHABLE;
290                        distance_row[j] = UNREACHABLE;
291                        continue;
292                    };
293
294                    if let Some(&(duration, distance)) = costs.get(&to.node_index) {
295                        row[j] = duration.round() as i64;
296                        distance_row[j] = distance.round() as i64;
297                    } else {
298                        row[j] = UNREACHABLE;
299                        distance_row[j] = UNREACHABLE;
300                    }
301                }
302
303                if let Some(tx) = &progress_tx {
304                    let _ = tx.send(i);
305                }
306                (row, distance_row)
307            })
308            .collect();
309
310        if let Some((progress_tx, handle)) = row_progress {
311            drop(progress_tx);
312            let _ = handle.await;
313        }
314
315        if let Some(tx) = progress {
316            let _ = tx.send(RoutingProgress::Complete).await;
317        }
318
319        let mut data = Vec::with_capacity(n * n);
320        let mut distance_data = Vec::with_capacity(n * n);
321        for (row, distance_row) in rows {
322            data.extend(row);
323            distance_data.extend(distance_row);
324        }
325        TravelTimeMatrix::new(data, distance_data, n, snapped_locations)
326    }
327
328    pub async fn compute_geometries(
329        &self,
330        locations: &[Coord],
331        progress: Option<&Sender<RoutingProgress>>,
332    ) -> HashMap<(usize, usize), Vec<Coord>> {
333        let n = locations.len();
334        let total_pairs = n * (n - 1);
335        let mut geometries = HashMap::new();
336        let mut pair_count = 0usize;
337
338        for i in 0..n {
339            for j in 0..n {
340                if i == j {
341                    continue;
342                }
343                if let Ok(result) = self.route(locations[i], locations[j]) {
344                    geometries.insert((i, j), result.geometry);
345                }
346                pair_count += 1;
347
348                if let Some(tx) = progress {
349                    if pair_count.is_multiple_of(10) || pair_count == total_pairs {
350                        let percent = 80 + (pair_count * 15 / total_pairs.max(1)) as u8;
351                        let _ = tx
352                            .send(RoutingProgress::ComputingGeometries {
353                                percent,
354                                pair: pair_count,
355                                total: total_pairs,
356                            })
357                            .await;
358                    }
359                }
360            }
361        }
362
363        if let Some(tx) = progress {
364            let _ = tx.send(RoutingProgress::Complete).await;
365        }
366
367        geometries
368    }
369}
solverforge_maps/routing/matrix.rs

solverforge_maps/routing/
matrix.rs
