Crate cch 

cch

Pure-Rust Customizable Contraction Hierarchies (CCH) for fast road routing — the full pipeline in safe Rust, with no C++ or FFI in the published library.

Build a contraction order (degree_order) and CCH structure (Cch::build), customize per metric (Cch::customize), serialize to mmappable .cch-struct / .cch-metric bundles (Cch::save_struct / Metric::save), then serve zero-copy: open bundles (CchBundle / MetricBundle) and answer shortest-path distance / distance-matrix queries (distance_matrix) with shortcut path-unpacking (node_path). The construction and bundle format are bit-identical to RoutingKit, so bundles interoperate with existing artifacts.

Customization runs in parallel internally (via rayon). For a one-off metric, Cch::customize is a thin wrapper that is all you need. For repeated re-customization of the same structure — e.g. re-solving for many weight profiles, or refreshing live traffic weights — build a Customizer once with Cch::customizer and call Customizer::customize_into on each new weight vector: it reuses the output buffers (no allocation once they’re sized) and the precomputed elimination-tree level partition, producing output bit-identical to Cch::customize.

Two contraction-order heuristics are provided: a lightweight degree order (degree_order) and inertial-flow (geometric) nested dissection (inertial_order), which yields far higher-quality hierarchies on road networks.

Example

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. Compute a 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 this per weight profile).
let metric = cch.customize(&graph.weight);

// 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

Derives from RoutingKit (BSD-2-Clause); see NOTICE.

Re-exports

pub use bundle::CchBundle;

pub use bundle::CchView;

pub use bundle::MetricBundle;

pub use bundle::MetricView;

pub use customize::Customizer;

pub use customize::Metric;

pub use order::degree_order;

pub use order::inertial_order;

pub use path::PathQuery;

pub use path::node_path;

pub use query::ElimTreeQuery;

pub use query::distance;

pub use query::distance_matrix;

pub use query::distances_from;

pub use structure::Cch;

Modules

bundle

Zero-copy, mmap-backed readers for .cch-struct and .cch-metric bundles.

customize

Per-metric CCH customization — a faithful port of the single-threaded CustomizableContractionHierarchyMetric::customize() from RoutingKit (oracle/routingkit-cch/RoutingKit/src/customizable_contraction_hierarchy.cpp).

graph

Input graph type in Compressed-Sparse-Row (CSR) format.

order

Contraction order heuristics for CCH construction.

path

Shortcut path unpacking — node-path reconstruction after a CCH query.

query

Elimination-tree distance computation and full distance-matrix.

structure

CCH structure building — a faithful port of the structure-building half of RoutingKit’s CustomizableContractionHierarchy constructor.

Constants

INF_WEIGHT

RoutingKit’s inf_weight sentinel for “unreachable”.