# 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`:

```toml
[dependencies]
cch-rs = "0.2.0"
```

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

## Usage Example

```rust
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:

```rust
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.
