ch-router

Crates.ioch-router
lib.rsch-router
version
sourcesrc
created_at2025-02-02 01:41:08.669246
updated_at2025-02-02 01:41:08.669246
descriptionA router based on Contraction Hierarchies with optional path unfolding and "hot groups"
homepage
repositoryhttps://github.com/tBuLi12/ch-router
max_upload_size
id1539143
Cargo.toml error:TOML parse error at line 18, column 1 | 18 | autolib = false | ^^^^^^^ unknown field `autolib`, expected one of `name`, `version`, `edition`, `authors`, `description`, `readme`, `license`, `repository`, `homepage`, `documentation`, `build`, `resolver`, `links`, `default-run`, `default_dash_run`, `rust-version`, `rust_dash_version`, `rust_version`, `license-file`, `license_dash_file`, `license_file`, `licenseFile`, `license_capital_file`, `forced-target`, `forced_dash_target`, `autobins`, `autotests`, `autoexamples`, `autobenches`, `publish`, `metadata`, `keywords`, `categories`, `exclude`, `include`
size0
(tBuLi12)

documentation

README

ch-router

A router based on Contraction Hierarchies with optional path unfolding and "hot groups".

CH creation

To create the Contraction Hierarchies you need to provide a list of nodes and edges:

let nodes = [Node { x: 0.0, y: 0.0 }, ...];

let edges = [
    Edge {
        from: 0,
        to: 1,
        weight: 2.0,
    },
    ...
];

let max_speed = 30.0; // pass f32::MAX if unknown

let ch = ContractionHierarchy::new(&nodes, &edges, max_speed);

Routing

Basic routing is done with the route mehtod:

let Route { path, distance } = router.route(0, 1).unwrap();

If you don't need the actual path, you can use the distance method (it is recommended to disable the path-unfolding feature in this case):

let distance = router.distance(0, 1).unwrap();

Both methods are also available on the Router struct, which will reuse allocations, so it may be faster for multiple queries:

let mut router = Router::new(&ch);

let distance = router.distance(0, 1).unwrap();
let route = router.route(0, 1).unwrap();

Hot groups

Hot groups are a way to greatly accelerate routing queries for a subset of nodes. This comes at a much larger memory cost per node, because it caches the bidirectional dijkstra results, but will yield about 100x faster queries. Hot groups can be created with the create_hot_group method by passing the desired subset of nodes:

let hot_group = ch.create_hot_group(&[0, 1, 2]);

Distance can then be queried within the group:

let distance = hot_group.distance(0, 1).unwrap();

Path routing is not supported for hot groups for now.

[!IMPORTANT] The node indices passed to hot_group.distance refer to the nodes' indices within the slice passed to create_hot_group, not the indices of the nodes in the original contraction hierarchy.

Saving and loading

Contraction hierarchies can be saved and loaded from disk:

let ch = ContractionHierarchy::new(&nodes, &edges, max_speed);

ch.save("poland.ch").unwrap();

let ch = ContractionHierarchy::load("poland.ch").unwrap();
Commit count: 4

cargo fmt