cch-rs

A practical, high-performance Customizable Contraction Hierarchy (CCH) implementation in Rust.

cch-rs is designed for real-world routing applications where graph topology can change, and edge weights (e.g., traffic data) update frequently. It provides a robust, stack-efficient architecture that integrates graph partitioning directly into the build process.

Key Features

• Batteries-Included Partitioning: Built-in METIS-based separator decomposition (via metis-sys). No need for external graph processing tools or complex pre-processing pipelines.
• Dynamic Topology: Supports both full graph rebuilding and incremental topology updates. Efficiently handle graph changes (adding nodes/edges) without complete re-computation.
• Stack Efficient: Unlike many recursive separator-based CCH implementations that require massive stack sizes for large graphs, cch-rs is optimized for low stack overhead, making it stable on standard thread configurations.
• High Availability & Concurrency: Built on ArcSwap, ensuring wait-free reads during updates. You can safely run queries on one thread while updating weights or topology on another, with zero downtime and consistent snapshots.
• Fast Customization: Update edge weights without rebuilding the contraction hierarchy structure.
• Incremental Weight Updates: Apply sparse (edge_index, new_weight) changes with update_weights_partial, so single-edge or small-batch traffic changes do not require a full re-customization pass.
• High Performance:
  • Parallelized customization using rayon.
  • Optimized memory layout for cache efficiency.
  • Orders of magnitude faster than standard Dijkstra/A* for long-distance queries.

Installation

Add this to your Cargo.toml:

[dependencies]
cch-rs = "0.2.0"

Note: This crate requires metis-sys, which depends on the METIS library.

Usage Example

use cch_rs::{CchEngine, CchGraph, PathResult};
use rustc_hash::FxHashMap;

// 1. Define your graph (implementing the CchGraph trait)
struct MyGraph { /* ... */ }
impl CchGraph for MyGraph { /* ... */ }

fn main() {
    let graph = MyGraph::new();
    
    // 2. Define weight profiles (e.g., "distance", "time", "traffic")
    let mut profile_weights = FxHashMap::default();
    let distance_weights: Vec<f32> = /* ... */;
    profile_weights.insert("distance", distance_weights);

    // 3. Initialize the Engine (automatically handles METIS ordering & contraction)
    let engine = CchEngine::new(&graph, &profile_weights);

    // 4. Query a shortest path
    if let Some(result) = engine.query_path("distance", start_node, end_node) {
        println!("Distance: {}, Path: {:?}", result.distance, result.path);
    }

    // 5. Re-customize the full profile after a large weight change set
    let new_weights: Vec<f32> = /* ... */;
    engine.update_weights("distance", &new_weights);

    // 6. Apply sparse weight updates in the base graph's CSR edge order
    // Useful for real-time traffic changes affecting only a few edges
    let updates = vec![
        (17usize, 42.0),
        (29usize, 18.5),
    ];
    engine.update_weights_partial("distance", &updates);
    
    // 7. Incremental Topology Update
    // Efficiently update the graph structure when nodes are added
    let new_nodes = vec![/* ... */];
    let modified_old_nodes = vec![/* ... */];
    engine.update_topology(&graph, &modified_old_nodes, &new_nodes, &profile_weights);
}

Choosing an Update Path

• Use update_weights(profile, new_weights) when most weights changed or you already have a full replacement vector.
• Use update_weights_partial(profile, updates) when only a small subset of original graph edges changed.
• updates must be expressed in the original graph's CSR edge order as (edge_index, new_weight).
• Partial updates keep the same topology and only recompute affected hierarchy arcs and dependents.

Reusing a Partial-Update Context

If you are working directly with Cch and ProfileData instead of CchEngine, you can cache the partial-update context and reuse it across many updates:

use cch_rs::{Cch, CchGraph};

fn apply_many_updates<G: CchGraph + Sync>(graph: &G, initial_weights: &[f32], batches: &[Vec<(usize, f32)>]) {
    let cch = Cch::new(graph);
    let mut profile = cch.build_profile(initial_weights);
    let update_ctx = cch.build_partial_update_context();

    for updates in batches {
        cch.customize_profile_partial_with_context(&mut profile, &update_ctx, updates);
    }
}

This avoids rebuilding the auxiliary reverse indices needed for incremental customization.

Performance and Testing

Benchmarks below were run on tests/data/USA-road-t.COL.gr + USA-road-d.COL.co (435,666 nodes / 1,042,400 arcs).

Operation	cch-rs	RoutingKit	Notes
Initialization	1.3249 s	2.4328 s	Includes ordering/build/first customization
Single-pair query with path extraction	20.368 us	52.285 us	cch-rs uses Criterion estimate, RoutingKit uses benchmark average
Full weight re-customization after one-edge change	24.739 ms	33.730 ms	Rebuilds metric/customization state after a weight change
Partial single-edge customization	6.630 us	8.960 us	Incremental update for one modified arc
Incremental topology update	87.994 ms	N/A	Not provided by RoutingKit benchmark

cch-rs numbers come from cargo bench --bench cch_bench -- --noplot using the Criterion point estimate. RoutingKit numbers come from .\benches\routingkit\build\routingkit_cch_bench.exe --gr tests\data\USA-road-t.COL.gr --co tests\data\USA-road-d.COL.co using the reported RESULT averages.

License

Dual-licensed under MIT or Apache-2.0.