osmnxr_core/
simplify.rs

1//! Topology simplification and intersection consolidation primitives.
2//!
3//! These functions work purely on graph topology (node indices); the R layer
4//! is responsible for rebuilding `sf` geometry from the returned node chains
5//! and component labels.
6
7use std::collections::HashSet;
8
9/// Distinct-neighbour undirected adjacency. Self-loops are ignored.
10fn undirected_adjacency(from: &[usize], to: &[usize], n_nodes: usize) -> Vec<Vec<usize>> {
11    let mut sets: Vec<HashSet<usize>> = vec![HashSet::new(); n_nodes];
12    for i in 0..from.len() {
13        if from[i] != to[i] {
14            sets[from[i]].insert(to[i]);
15            sets[to[i]].insert(from[i]);
16        }
17    }
18    sets.into_iter()
19        .map(|s| {
20            let mut v: Vec<usize> = s.into_iter().collect();
21            v.sort_unstable();
22            v
23        })
24        .collect()
25}
26
27/// A node is a topological endpoint (kept after simplification) when it does
28/// not have exactly two distinct neighbours, i.e. it is a dead-end, an
29/// intersection, or isolated.
30fn is_endpoint(adj: &[Vec<usize>], node: usize) -> bool {
31    adj[node].len() != 2
32}
33
34/// Find simplified chains: every maximal path of interstitial (degree-2) nodes
35/// between two endpoints. Each chain is returned once as an ordered vector of
36/// node indices `[endpoint, ..interstitial.., endpoint]`.
37pub fn simplify_paths(from: &[usize], to: &[usize], n_nodes: usize) -> Vec<Vec<usize>> {
38    let adj = undirected_adjacency(from, to, n_nodes);
39    let mut paths: Vec<Vec<usize>> = Vec::new();
40    // Directed first-steps already consumed, to record each chain only once.
41    let mut seen: HashSet<(usize, usize)> = HashSet::new();
42
43    for u in 0..n_nodes {
44        if !is_endpoint(&adj, u) {
45            continue;
46        }
47        for &start in &adj[u] {
48            if seen.contains(&(u, start)) {
49                continue;
50            }
51            let mut path = vec![u];
52            let mut prev = u;
53            let mut cur = start;
54            loop {
55                path.push(cur);
56                if is_endpoint(&adj, cur) || cur == u {
57                    break;
58                }
59                let nbrs = &adj[cur];
60                let next = if nbrs[0] == prev { nbrs[1] } else { nbrs[0] };
61                prev = cur;
62                cur = next;
63            }
64            let last = path[path.len() - 1];
65            let before_last = path[path.len() - 2];
66            seen.insert((u, start));
67            seen.insert((last, before_last));
68            paths.push(path);
69        }
70    }
71    paths
72}
73
74/// Union-find root of `x` with path compression.
75fn find(parent: &mut [usize], x: usize) -> usize {
76    let mut root = x;
77    while parent[root] != root {
78        root = parent[root];
79    }
80    let mut cur = x;
81    while parent[cur] != root {
82        let next = parent[cur];
83        parent[cur] = root;
84        cur = next;
85    }
86    root
87}
88
89/// Connected-component label (the 0-based root node index) for each of `n`
90/// nodes, given undirected `a`--`b` adjacency pairs.
91pub fn connected_components(a: &[usize], b: &[usize], n: usize) -> Vec<i32> {
92    let mut parent: Vec<usize> = (0..n).collect();
93    for i in 0..a.len() {
94        let ra = find(&mut parent, a[i]);
95        let rb = find(&mut parent, b[i]);
96        if ra != rb {
97            parent[ra] = rb;
98        }
99    }
100    (0..n).map(|i| find(&mut parent, i) as i32).collect()
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn collapses_degree_two_chain() {
109        // 0 -- 1 -- 2 -- 3 with 1,2 interstitial: one chain [0,1,2,3].
110        let from = vec![0, 1, 2];
111        let to = vec![1, 2, 3];
112        let paths = simplify_paths(&from, &to, 4);
113        assert_eq!(paths.len(), 1);
114        assert_eq!(paths[0], vec![0, 1, 2, 3]);
115    }
116
117    #[test]
118    fn keeps_intersection_nodes() {
119        // A plus/cross: node 0 connects to 1,2,3,4 (all dead-ends).
120        let from = vec![0, 0, 0, 0];
121        let to = vec![1, 2, 3, 4];
122        let paths = simplify_paths(&from, &to, 5);
123        // four chains, each of length 2
124        assert_eq!(paths.len(), 4);
125        assert!(paths.iter().all(|p| p.len() == 2));
126    }
127
128    #[test]
129    fn components_group_connected_nodes() {
130        // pairs (0,1) and (2,3); 4 alone -> 3 components
131        let comp = connected_components(&[0, 2], &[1, 3], 5);
132        assert_eq!(comp[0], comp[1]);
133        assert_eq!(comp[2], comp[3]);
134        assert_ne!(comp[0], comp[2]);
135        assert_ne!(comp[4], comp[0]);
136    }
137}
osmnxr_core/simplify.rs

osmnxr_core/
simplify.rs
