osmnxr_core/
graph.rs

1//! Compressed-sparse-row (CSR) directed graph built from edge lists.
2//!
3//! Node identifiers are 0-based contiguous indices; the R layer is responsible
4//! for mapping OSM node ids to and from these indices.
5
6/// A directed, weighted graph in CSR form.
7pub struct Graph {
8    /// `offsets[i] .. offsets[i + 1]` is the slice of out-edges of node `i`.
9    pub offsets: Vec<usize>,
10    /// Destination node of each out-edge, grouped by source node.
11    pub targets: Vec<usize>,
12    /// Weight (e.g. length or travel time) of each out-edge.
13    pub weights: Vec<f64>,
14    /// Number of nodes.
15    pub n_nodes: usize,
16}
17
18impl Graph {
19    /// Build a CSR graph from parallel `from`/`to`/`weight` edge vectors.
20    ///
21    /// `n_nodes` is the number of distinct node indices; every value in
22    /// `from`/`to` must be in `0 .. n_nodes`.
23    pub fn from_edges(from: &[usize], to: &[usize], weight: &[f64], n_nodes: usize) -> Self {
24        let m = from.len();
25        let mut degree = vec![0usize; n_nodes + 1];
26        for &u in from {
27            degree[u + 1] += 1;
28        }
29        for i in 0..n_nodes {
30            degree[i + 1] += degree[i];
31        }
32        let offsets = degree; // now a prefix-sum offset array
33        let mut targets = vec![0usize; m];
34        let mut weights = vec![0.0f64; m];
35        let mut cursor = offsets.clone();
36        for e in 0..m {
37            let u = from[e];
38            let pos = cursor[u];
39            targets[pos] = to[e];
40            weights[pos] = weight[e];
41            cursor[u] += 1;
42        }
43        Graph {
44            offsets,
45            targets,
46            weights,
47            n_nodes,
48        }
49    }
50
51    /// Out-edges of `node` as `(target, weight)` pairs.
52    pub fn neighbors(&self, node: usize) -> impl Iterator<Item = (usize, f64)> + '_ {
53        let start = self.offsets[node];
54        let end = self.offsets[node + 1];
55        (start..end).map(move |e| (self.targets[e], self.weights[e]))
56    }
57
58    /// Number of directed edges.
59    pub fn n_edges(&self) -> usize {
60        self.targets.len()
61    }
62}
osmnxr_core/graph.rs

osmnxr_core/
graph.rs
