Crate routingkit_cch 

routingkit-cch

Rust/Python bindings for the Customizable Contraction Hierarchies (CCH) implementation from RoutingKit. CCH is a three‑phase shortest path acceleration technique for large directed graphs (e.g. road networks) that allows fast re-weighting while keeping very low query latency.

Why CCH?

CustomizableContractionHierarchies (CCH) are an index-based speedup technique for shortest paths in directed graphs that can quickly be adapted to new weights. CCHs use, contrary to regulars CHs, a three phase setup:

1. Preprocessing
2. Customization
3. Query

The preprocessing is slow but does not rely on the arc weights. The Customization introduces the weights and is reasonably fast. Finally, the actual paths are computed in the query phase. A common setup consists of doing the preprocessing once and the customization per user upon login. Further one can use a customization to incorporate live-traffic updates.

Features

• Safe ergonomic Rust API on top of proven C++ core via cxx.
• Build indices from raw edge lists (tail/head arrays).
• Ordering helpers: nested dissection (inertial separator heuristic) and degree fallback.
• Sequential & parallel customization, and partial weight update afterwards.
• Reusable query object supporting multi-source / multi-target searches.
• Path extraction: node sequence & original arc id sequence.
• Thread-safe sharing of immutable structures (CCH, CCHMetric).

Installation

---

Rust stable release from crates.io:

[dependencies]
routingkit-cch = "0.1"

Or track the repository:

[dependencies]
routingkit-cch = { git = "https://github.com/HellOwhatAs/routingkit-cch" }

---

Python stable release from pypi:

pip install routingkit-cch

Or track the repository:

pip install git+https://github.com/HellOwhatAs/routingkit-cch

---

For the git form ensure the RoutingKit submodule is present:

git submodule update --init --recursive

Requirements: C++17 compiler (MSVC / gcc / clang). OpenMP is enabled automatically by the build script; ensure your toolchain provides an OpenMP runtime (e.g. install libomp on macOS). Without it the build may fail when CCHMetric::parallel_new is called.

Quick Start

For a python example, see examples/draft.py.

use routingkit_cch::{CCH, CCHMetric, CCHQuery, compute_order_degree};

// Small toy graph: 0 -> 1 -> 2 -> 3
let tail = vec![0, 1, 2];
let head = vec![1, 2, 3];
let weights = vec![10, 5, 7]; // total 22 from 0 to 3
let node_count = 4u32;

// 1) Compute a (cheap) order; for real data prefer compute_order_inertial (requires lat,lon).
let order = compute_order_degree(node_count, &tail, &head);
let cch = CCH::new(&order, &tail, &head, |_| {}, false);

// 2) Bind weights & customize (done inside CCHMetric::new here).
let metric = CCHMetric::new(&cch, weights.clone());

// 3) Run a shortest path query 0 -> 3.
let mut q = CCHQuery::new(&metric);
q.add_source(0, 0);
q.add_target(3, 0);
let res = q.run();
assert_eq!(res.distance(), Some(22));
let node_path = res.node_path();
assert_eq!(node_path, vec![0, 1, 2, 3]);
let arc_path = res.arc_path();
assert_eq!(arc_path, vec![0, 1, 2]);

Building an Order

For production use prefer the inertial nested dissection based order:

use routingkit_cch::compute_order_inertial;
let order = compute_order_inertial(node_count, &tail, &head, &latitude, &longitude);

Better separators -> faster customization & queries. External advanced orderers (e.g. FlowCutter) could be integrated offline; you only need to supply the permutation.

(Parallel) Customization

use routingkit_cch::{CCH, CCHMetric};
let metric = CCHMetric::new(&cch, weights.clone()); // single thread
let metric = CCHMetric::parallel_new(&cch, weights.clone(), 0); // 0 -> auto threads

Use when graphs are large enough; for tiny graphs overhead may outweigh benefit.

Incremental (Partial) Weight Updates

If only a small subset of arc weights change (e.g. traffic incidents), you can avoid a full re-customization:

let mut metric = CCHMetric::parallel_new(&cch, weights.clone(), 0);
let mut updater = CCHMetricPartialUpdater::new(&cch);
// ... run queries ...
// Update two arcs (id 12 -> 900, id 77 -> 450)
updater.apply(&mut metric, &BTreeMap::from_iter([(12, 900), (77, 450)]));
// New queries now see updated weights.

Query

let mut q = CCHQuery::new(&metric);
q.add_source(0, 0);
q.add_target(3, 0);
{
    let res = q.run();
    printf("{:?}", res.distance());
} // drop res before reusing q since res takes &mut q
q.add_source(2, 0);
q.add_target(5, 0);
{
    let res = q.run();
    // ...
}

CCHQuery is not thread-safe; create one instance per thread and reuse it is far cheaper than constructing a new one.

Path Reconstruction

After run() -> CCHQueryResult:

• CCHQueryResult::distance() -> Option<u32> (None = unreachable)
• CCHQueryResult::node_path() -> Vec<node_id> (empty = unreachable)
• CCHQueryResult::arc_path() -> Vec<original_arc_id> (empty = unreachable)

Thread Safety

Type	Send	Sync	Notes
CCH	yes	yes	Immutable after build
CCHMetric	yes	yes	Read-only after customization / partial-update
CCHQuery	yes	no	Internal mutable labels; reuse it within thread
CCHQueryResult	yes	no	Runned state of CCHQuery, actually &mut of it
CCHMetricPartialUpdater	no	no	Should have nothing to do with parallel

Create separate queries per thread for parallel batch querying.

Modules

ffi

shp_utils

Structs

CCH

Immutable Customizable Contraction Hierarchy index.

CCHMetric

A customized metric (weight binding) for a given CCH. Keeps ownership of the weight vector so it can be mutated for partial updates. Thread-safety: Send + Sync; read-only for queries.

CCHMetricPartialUpdater

Reusable partial customization helper. Construct once if you perform many small incremental weight updates; this avoids reallocating O(m) internal buffers each call.

CCHQuery

A reusable shortest-path query object bound to a given CCHMetric. Thread-safety: Send but not Sync; holds mutable per-query state.

CCHQueryResult

The result of a single execution of a CCHQuery. Holds a mutable reference to the query to ensure it is not reset or reused while the result is still alive. So you need to drop the result before reusing the query. When the result is dropped, the query is automatically reset.

Functions

compute_order_degree

Lightweight fill-in reducing order heuristic: sort nodes by (degree, id) ascending. Fast but lower quality than nested dissection. Use if no coordinates or other data available. Panics if tail/head have inconsistent lengths or contain invalid node ids.

compute_order_inertial

High-quality nested dissection order using inertial flow separators. Requires per-node coordinates (latitude/longitude) as input. Panics if tail/head have inconsistent lengths or contain invalid node ids, or if latitude/longitude lengths do not match node_count.