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 in milliseconds (e.g., for real-time traffic updates) without rebuilding the contraction hierarchy structure.
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.1.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. Update weights dynamically (e.g., traffic update)
    let new_weights: Vec<f32> = /* ... */;
    engine.update_weights("distance", &new_weights);
    
    // 6. 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);
}

Performance and Testing

Benchmarks run on a USA-road-t.COL graph (approx. 435k nodes, 1M edges).

Engine Initialization: ~1.4s (includes METIS partitioning & full contraction)
Shortest Path Query: ~21 µs (orders of magnitude faster than Dijkstra)
Weight Update: ~24 ms (update global edge weights)
Incremental Topology Update: ~87 ms (handle graph structural changes)

cch-rs is designed to be competitive with state-of-the-art routing engines.

The comprehensive road network tests require the DIMACS USA dataset. Please download it from 9th DIMACS Implementation Challenge - Shortest Paths and place it in tests/data/cch/ to run full tests and benchmarks.

License