README.md
1# Fast Paths
2
3The most famous algorithms used to calculate shortest paths are probably Dijkstra's algorithm and A*. However, shortest path calculation can be done much faster by preprocessing the graph.
4
5*Fast Paths* uses *Contraction Hierarchies*, one of the best known speed-up techniques for shortest path calculation. It is especially suited to calculate shortest paths in road networks, but can be used for any directed graph with positive, non-zero edge weights.
6
7### Installation
8
9In `Cargo.toml`
10
11```toml
12[dependencies]
13fast_paths = "0.1.0"
14
15```
16### Basic usage
17
18```rust
19// begin with an empty graph
20let mut input_graph = InputGraph::new();
21
22// add an edge between nodes with ID 0 and 6, the weight of the edge is 12.
23// Note that the node IDs should be consecutive, if your graph has N nodes use 0...N-1 as node IDs,
24// otherwise performance will degrade.
25input_graph.add_edge(0, 6, 12);
26// ... add many more edges here
27
28// freeze the graph before using it (you cannot add more edges afterwards, unless you call thaw() first)
29input_graph.freeze();
30
31// prepare the graph for fast shortest path calculations. note that you have to do this again if you want to change the
32// graph topology or any of the edge weights
33let fast_graph = fast_paths::prepare(&input_graph);
34
35// calculate the shortest path between nodes with ID 8 and 6
36let shortest_path = fast_paths::calc_path(&fast_graph, 8, 6);
37
38match shortest_path {
39 Some(p) => {
40 // the weight of the shortest path
41 let weight = p.get_weight();
42
43 // all nodes of the shortest path (including source and target)
44 let nodes = p.get_nodes();
45 },
46 None => {
47 // no path has been found (nodes are not connected in this graph)
48 }
49}
50
51
52```
53
54### Batch-wise shortest path calculation
55
56For batch-wise calculation of shortest paths the method described above is inefficient. You should keep the `PathCalculator` object to execute multiple queries instead:
57
58```rust
59// ... see above
60// create a path calculator (note: not thread-safe, use a separate object per thread)
61let mut path_calculator = fast_paths::create_calculator(&fast_graph);
62let shortest_path = path_calculator.calc_path(&fast_graph, 8, 6);
63```
64
65### Serializing the prepared graph
66
67`FastGraph` implements standard [Serde](https://serde.rs/) serialization.
68
69To be able to use the graph in a 32bit WebAssembly environment, it needs to be transformed to a 32bit representation when preparing it on a 64bit system. This can be achieved with the following two methods, but it will only work for graphs that do not exceed the 32bit limit, i.e. the number of nodes and edges and all weights must be below 2^32.
70
71```rust
72use fast_paths::{deserialize_32, serialize_32, FastGraph};
73
74#[derive(Serialize, Deserialize)]
75struct YourData {
76 #[serde(serialize_with = "serialize_32", deserialize_with = "deserialize_32")]
77 graph: FastGraph,
78 // the rest of your struct
79}
80```
81
82### Preparing the graph after changes
83
84The graph preparation can be done much faster using a fixed node ordering, which is just a permutation of node ids. This can be done like this:
85
86```rust
87let fast_graph = fast_paths::prepare(&input_graph);
88let node_ordering = fast_graph.get_node_ordering();
89
90let another_fast_graph = fast_paths::prepare_with_order(&another_input_graph, &node_ordering);
91```
92
93For this to work `another_input_graph` must have the same number of nodes as `input_graph`, otherwise `prepare_with_order` will return an error. Also performance will only be acceptable if `input_graph` and `another_input_graph` are similar to each other, say you only changed a few edge weights.
94
95### Benchmarks
96
97*FastPaths* was run on a single core on a consumer-grade laptop using the road networks provided for the [DIMACS implementation challenge graphs](http://users.diag.uniroma1.it/challenge9/download.shtml). The following graphs were used for the benchmark:
98
99|area|number of nodes|number of edges|
100|-|-|-|
101|New York|264.346|733.846|
102|California&Nevada|1.890.815|4.630.444|
103|USA|23.947.347|57.708.624|
104
105|graph|metric|preparation time|average query time (micros)|
106|-|-|-|-|
107|NY city|distance|24 s|162|
108|CAL&NV|distance|100 s|430|
109|USA|distance|35 min|3980|
110|NY city|time|14 s|77|
111|CAL&NV|time|62 s|222|
112|USA|time|13 min|1086|
113
114The shortest path calculation time was averaged over 100k random routing queries.
115
116There are also some benchmarks using smaller maps included in the test suite. You can run them like this:
117```shell
118export RUST_TEST_THREADS=1; cargo test --release -- --ignored --nocapture
119```
120
121### Graph limitations
122
123- loop-edges (from node A to node A) will be ignored, because since we are only considering positive non-zero edge-weights they cannot be part of a shortest path
124- in case the graph has duplicate edges (multiple edges from node A to node B) only the edge with the lowest weight will be considered
125
126### Special Thanks
127
128Thanks to [Dustin Carlino](http://github.com/dabreegster) from [A/B Street](http://github.com/dabreegster/abstreet)!
129
130
131#### License
132
133This project is licensed under either of
134
135 * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or
136 http://www.apache.org/licenses/LICENSE-2.0)
137 * MIT license ([LICENSE-MIT](LICENSE-MIT) or
138 http://opensource.org/licenses/MIT)
139
140at your option.
141
142#### Contribution
143
144Unless you explicitly state otherwise, any contribution intentionally submitted
145for inclusion in fast_paths by you, as defined in the Apache-2.0 license, shall be
146dual licensed as above, without any additional terms or conditions.
147