cch

Customizable Contraction Hierarchies for fast road routing — the whole pipeline in pure, safe Rust.

cch builds a metric-independent contraction hierarchy from a road graph, customizes it per weight profile (distance, travel-time, …), serializes it to memory-mappable bundles, and answers point-to-point distance, many-to-many distance-matrix, and shortest-path queries — with no C++ and no FFI in the published library.

It is a from-scratch Rust reimplementation of RoutingKit's CCH, validated bit-for-bit against it: same contraction order quality, bit-identical structure and customization arrays, byte-identical on-disk bundles, and identical query results. It was extracted from — and now powers — a production distance-matrix routing service.

[dependencies]
cch = "0.3"

Quick start

use cch::graph::Graph;
use cch::{distance_matrix, degree_order, node_path, Cch};

// Input graph in CSR form: a 4-node path 0—1—2—3 with unit-weight arcs.
// (CCH treats the input as symmetric / undirected internally.)
let graph = Graph {
    first_out: vec![0, 1, 2, 3, 3],
    head: vec![1, 2, 3],
    weight: vec![1, 1, 1],
};

// 1. Contraction order (metric-independent). `degree_order` needs no
//    coordinates; use `inertial_order` for production-quality orders.
let order = degree_order(&graph);

// 2. Build the CCH structure once.
let cch = Cch::build(&graph, &order);

// 3. Customize a metric (cheap — repeat per weight profile).
let metric = cch.customize(&graph.weight);

// For repeated re-customization, reuse buffers:
// let cust = cch.customizer();
// cust.customize_into(&graph.weight, &mut metric);

// 4. Query in memory, via zero-copy views.
let dm = distance_matrix(&cch.view(), &metric.view(), &[0], &[3]);
assert_eq!(dm[0], 3); // shortest distance 0 -> 3

let path = node_path(&cch.view(), &metric.view(), 0, 3);
assert_eq!(path, Some(vec![0, 1, 2, 3])); // unpacked node path

Why CCH?

A Customizable Contraction Hierarchy is a two-phase shortest-path index built for road networks where the topology is fixed but edge weights change often (live traffic, vehicle profiles, time-of-day):

1. Build (once, metric-independent) — pick a contraction order, contract the graph into a chordal supergraph, and record the shortcut structure.
2. Customize (cheap, per metric) — push concrete edge weights through the structure to compute every shortcut's weight.
3. Query (very fast) — answer point-to-point, one-to-many, and many-to-many shortest paths over the customized hierarchy; unpack shortcuts to recover the full node path.

The expensive build is amortized across many cheap customizations, which is exactly what a routing service with frequently-changing weights needs.

Highlights

• Pure Rust, no FFI. The published library has zero C++ in its dependency tree — embed it in a Rust service with no C/C++ toolchain. (Parallel customization uses rayon, also pure Rust. A C++ RoutingKit build is used only as a dev-time differential-test oracle; it is not part of the crate you depend on.)
• The complete pipeline — contraction order, structure build, per-metric customization, bundle reader and writer, distance / distance-matrix / path queries, and shortcut unpacking.
• Parallel, reusable customization. Cch::customizer builds a Customizer once per structure; Customizer::customize_into re-customizes for a new weight profile without reallocating output buffers, with both phases of customization running in parallel — bit-identical to the serial, single-shot Cch::customize.
• Two ordering strategies — a lightweight degree_order, and inertial_order: a full geometric nested-dissection (inertial-flow max-flow / min-cut) that produces hierarchies of the same quality as RoutingKit (identical shortcut counts in testing).
• Zero-copy mmap bundles. Build once, write .cch-struct / .cch-metric files, then serve them memory-mapped — the OS page cache backs the query slices directly, so many regions can be served within a bounded memory budget. The format is byte-compatible with RoutingKit-produced bundles.
• Proven correct. Every stage is gated by a differential test against the C++ oracle (see Correctness).
• 100% line coverage, enforced in CI.

API at a glance

Unreachable distances are reported as cch::INF_WEIGHT (2_147_483_647). Queries take borrowed CchView / MetricViews, so you can query a freshly-built Cch/Metric in memory (.view()) or a memory-mapped bundle (.view() on CchBundle/MetricBundle) through the same functions.

Serving from bundles

Production serving builds once and memory-maps the result:

use cch::{CchBundle, MetricBundle, distance_matrix};

let cch = CchBundle::open("romania.cch-struct".as_ref())?;
let metric = MetricBundle::open("romania.cch-metric-distance".as_ref())?;

// Zero-copy: the slices borrow straight from the mmap'd pages.
let matrix = distance_matrix(&cch.view(), &metric.view(), &sources, &targets);
# Ok::<(), std::io::Error>(())

Bundles are immutable, shareable across processes via the page cache, and let a single host serve many regions without loading them all into heap.

Performance

Indicative numbers, Rust vs the C++ RoutingKit oracle, on a 24×24 bidirectional grid (576 nodes, ~3 000 CCH arcs), measured with Criterion. Both sides use the same contraction order so the comparison is apples-to-apples. Run cargo bench to reproduce on your hardware.

Every operation is at parity with (or faster than) RoutingKit. The query paths reach parity by eliding the per-arc bounds checks in the hot relaxation loops — the elision-able accesses via sliced iterators, and the data-dependent distance-array access via a get_unchecked guarded by a one-time structural validation. (Numbers are indicative; hardware is not standardized — run cargo bench for your own.)

A customize_reuse bench compares a fresh Cch::customize per call against a reused Customizer::customize_into on the same grid; the reused path avoids re-deriving the level partition and re-allocating output buffers, so it is never slower and is typically a few percent faster (cargo bench --bench cch -- customize to reproduce). The gain grows with structure size and call frequency; on this modest 24×24 fixture the parallel overhead largely offsets the savings.

Parallel customization is a large-graph win: on nested-dissection-ordered grids, customize runs ~1.85× faster at 65k nodes and ~2.8× at 656k nodes on 18 cores, with no benefit — and no measurable regression — below ~tens of thousands of nodes. The efficiency is sub-linear in cores: level-synchronized customization has a barrier per elimination-tree level, and the top of the hierarchy has too few nodes to fill many cores. Grids are a pessimistic proxy (worse separators than real road networks), so treat these as a lower bound. Full method and numbers: docs/customize-parallel-scaling.md. On a real road network — Albania, ~6.29M nodes — customize runs 366.87 ms single-threaded and 80.7 ms on 18 threads (~4.55×), a stronger scaling result than the synthetic grids above, consistent with real road networks having better separators than grids.

Correctness

The reference C++ RoutingKit is vendored as a dev-only differential-test oracle, and each stage of the pipeline is gated against it:

• Contraction order — inertial_order produces the same shortcut count as RoutingKit's inertial-flow order (e.g. identical on a 24×24 grid), and yields correct shortest paths.
• Structure — Cch::build is bit-identical to RoutingKit's structure arrays given the same graph + order.
• Customization — customize is bit-identical to RoutingKit's forward/backward shortcut weights.
• Bundles — save_struct / Metric::save produce byte-identical files to RoutingKit's writer, and RoutingKit can load bundles written by cch (and vice-versa).
• Queries — distance-matrix and a 200-pair shortest-path suite match RoutingKit exactly, end-to-end.

The whole crate maintains 100% line coverage, enforced by a CI gate (cargo llvm-cov --fail-under-lines 100), alongside clippy -D warnings and rustfmt.

Status & roadmap

0.1 ships the full pipeline — both orderings, build, customize, bundle read/write, and all query types — validated against RoutingKit. Customization runs in parallel (via rayon) and supports buffer reuse across repeated calls through Cch::customizer / Customizer::customize_into, with no change to the bit-identical output. The API may still evolve before 1.0.

Planned: narrowing the query-path performance gap and broader benchmark coverage on real continental graphs.

Relationship to RoutingKit

RoutingKit (BSD-2-Clause) is the canonical C++ CCH implementation and the basis for this work. cch reimplements its CCH construction, customization, bundle format, and query algorithms in Rust, and is differential-tested against it for exact equivalence. The on-disk bundle format is interoperable with RoutingKit-produced artifacts.

License

MIT. The algorithm and bundle format derive from RoutingKit (BSD-2-Clause); see NOTICE.