cch_rs/cch/
order.rs

1//! Node ordering strategies for graph contraction.
2//!
3//! To achieve optimal query performance, the graph must be contracted in an order that
4//! minimizes the introduction of new shortcut edges and keeps the elimination tree shallow.
5//!
6//! This module leverages the METIS graph partitioning library via `metis_sys` to compute
7//! a Nested Dissection ordering. This produces significantly better contraction hierarchies
8//! than simple degree-based heuristics, especially for large, real-world road networks.
9
10use crate::cch::{Cch, CchGraph};
11
12impl Cch {
13    pub fn get_metis_order<G: CchGraph>(graph: &G) -> Vec<u32> {
14        let n = graph.num_nodes();
15        let mut xadj: Vec<metis_sys::idx_t> = Vec::with_capacity(n + 1);
16        let mut adjncy: Vec<metis_sys::idx_t> = Vec::new();
17
18        let mut temp_adj = vec![vec![]; n];
19        for u in 0..n {
20            for v in graph.neighbors(u as u32) {
21                let v = v as usize;
22                if u != v {
23                    temp_adj[u].push(v as metis_sys::idx_t);
24                    temp_adj[v].push(u as metis_sys::idx_t);
25                }
26            }
27        }
28
29        xadj.push(0);
30        for neighbors in temp_adj.iter_mut().take(n) {
31            neighbors.sort_unstable();
32            neighbors.dedup();
33            for &mut v in neighbors {
34                adjncy.push(v);
35            }
36            xadj.push(adjncy.len() as metis_sys::idx_t);
37        }
38
39        let mut perm = vec![0 as metis_sys::idx_t; n];
40        let mut iperm = vec![0 as metis_sys::idx_t; n];
41        let mut nvtxs = n as metis_sys::idx_t;
42
43        if !adjncy.is_empty() {
44            unsafe {
45                metis_sys::METIS_NodeND(
46                    &mut nvtxs,
47                    xadj.as_mut_ptr(),
48                    adjncy.as_mut_ptr(),
49                    std::ptr::null_mut(),
50                    std::ptr::null_mut(),
51                    perm.as_mut_ptr(),
52                    iperm.as_mut_ptr(),
53                );
54            }
55        } else {
56            return (0..n as u32).collect();
57        }
58
59        iperm.into_iter().map(|x| x as u32).collect()
60    }
61}
cch_rs/cch/order.rs

cch_rs/cch/
order.rs
