1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//! # 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](https://docs.rs/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](https://github.com/RoutingKit/RoutingKit) (BSD-2-Clause);
//! see `NOTICE`.
/// `RoutingKit`'s `inf_weight` sentinel for "unreachable".
///
/// Matches `routingkit/include/routingkit/constants.h:7` (`inf_weight = 2_147_483_647 = i32::MAX`).
/// This is the crate-wide sentinel emitted by [`distance_matrix`] for unreachable pairs.
/// Note: the oracle's C++ `cch_compute_distance_matrix` uses `u32::MAX` instead — callers
/// comparing against oracle output must treat the two as equivalent.
pub const INF_WEIGHT: u32 = 2_147_483_647;
pub use ;
pub use ;
pub use ;
pub use ;
pub use ;
pub use Cch;