Crates.io | ch-router |
lib.rs | ch-router |
version | |
source | src |
created_at | 2025-02-02 01:41:08.669246 |
updated_at | 2025-02-02 01:41:08.669246 |
description | A router based on Contraction Hierarchies with optional path unfolding and "hot groups" |
homepage | |
repository | https://github.com/tBuLi12/ch-router |
max_upload_size | |
id | 1539143 |
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` |
size | 0 |
A router based on Contraction Hierarchies with optional path unfolding and "hot groups".
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);
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 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 tocreate_hot_group
, not the indices of the nodes in the original contraction hierarchy.
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();