easbar / fast_paths Goto Github PK
View Code? Open in Web Editor NEWFast shortest path calculations for Rust
License: Apache License 2.0
Fast shortest path calculations for Rust
License: Apache License 2.0
I am facing extremely high memory usage when generating a fast graph(>25GB)
I have 873k nodes and 900k edges. My code looks like this:
let mut input_graph = InputGraph::new();
for e in edges {
input_graph.add_edge(e.start_node, e.end_node, e.weight);
}
println!("Freezing graph...");
input_graph.freeze();
println!("Calculating optimized graph...");
let fast_graph = fast_paths::prepare(&input_graph);
println!("Done.\r\nSaving graph...\t");
fast_paths::save_to_disk(&fast_graph, format!("{}.ff", filename).as_ref());
println!("Done.");
It starts swallowing memory at let fast_graph = fast_paths::prepare(&input_graph);
. I tried creating a new params with a ratio of 0.01 and 10.0, which didn't seem to help. (I'm not entirely sure what this value does, which is why I tried a small and large value)
I looked through the benchmark code but it doesn't look like I'm doing anything fundamentally different.
My main use of this algorithm is in pandana ware the common need is to for each knode, calculate summary statistics about all the nodes that are within a thresholded.
Hey! I'm the maintainer of Headway, a self-hostable maps stack. I'm thinking about taking the project in a direction that would allow instances to link together in a federated network that could grow to cover the planet. Doing so presents a number of challenges though. From the routing side of things, an end-user can't simply send a routing query including route endpoints to an untrusted server, because of the privacy implications. Nor can it download a routing graph for the entire planet. Valhalla handles this by dividing up the routing graph into tiles. Do you know if an approach like that could work with fast_paths? If so, what would need to change?
Compiling Valhalla to webassembly seems extremely difficult, and I'd like to evaluate building turn-by-turn on top of fast_paths instead. I'm not sure which would end up being more difficult since both of these ideas sound ridiculously complex, but this option involves less CMake at least and I want to explore it a bit.
I just switched to a new Rust and building the CH is suddenly stalling out. I'll dig in soon and see what's going on.
The code in floyd_warshall.rs is only used in tests at the moment.
Hello!
Could you please share how you ran the benchmarks listed in the README?
The only tests I can see are in the lib.rs, and running cargo test after removing the #[ignore] still compiles the code in unoptimized mode. 'grep'-ing for '#[bench]' also shows nothing.
as seen here, the amount of shortcuts is not optimal.
The current approach as described in the original publication is creating shortcuts, if the contracting node is not part of the shortest path from previous neighbor to the next neighbor. As seen here this can lead to non perfect amount of shortcuts.
A "newer" approach is, to have a distinct set of previous neighbors and another distinct set with following neighbors. Then use Dijkstra and calculate the travel-costs. If the cost is equal to the cost from previous to contracting node to the following neighbor then the path from neighbor to neighbor is the optimal path. Therefore a new shortcut has to be created. Otherwise another better path is available and will create a shortcut in the future.
The path itself does not have to be fully resolved. Only the costs are important. Additional Improvement
i already did an implementation in rust, but with a different data-structure: link
maybe I find some time and could try implement it for your model. Is this wanted? Or do your prefer doing this yourself?
Some of the ideas taken from this discussion: Stunkymonkey/osm_ch#1
Hey, i am using this lib for the current advent of code.
And I got the wrong result for my input. The test input is working and everything else also. Maybe you can verify that the code is working correctly from your point of view?
I got the result of 3019
but it should be 3012
. I rerun the code multiple times and also verified, that the enlarged matrix is correct (it is :/). So I cannot find any issues in my code. My next thought is, that your lib maybe has an issue? :D
Maybe you want/can take a look :)
You can find the code here:
https://github.com/auryn31/aoc_2021/blob/main/day_15/src/main.rs
But there is a solid chance my code is wrong :D
Best
Just wondering why the structs like FastGraph
don't derive Clone
?
It's blocking structs that own one from deriving those traits.
I use the USA-road-d.COL
road network, which contains 435666 nodes and 1042400 edges.
Generally, it costs more than 61300 micros, and it is much slower than you reported benchmark.
I download the dataset from dataset and then clean it (remove duplicated edges; remove loop...).
The cleaned data can be download from google drive
USA-road-d.COL 435666 1042400
0 1 14567
0 46 7059
1 0 14567
1 30 16448
...
I run the experiments on a Windows desktop with i7 8700 CPU, 16 GB memory.
The saved CH file is 80.1MB.
let fast_graph = fast_paths::load_from_disk("fast_graph_col.fp").unwrap();
let start = Instant::now();
let shortest_path = fast_paths::calc_path(&fast_graph, s, t);
let duration = start.elapsed();
println!("Time elapsed in ch_run() is: {:?}", duration.as_micros());
The average query time to answer the shortest from 0
to 1001
is 61303
micros.
I noticed a lot of methods are used like this:
fast_paths::a_method(&graph, a, b, ...)
Whereas a more OO method call would look like this:
graph.a_method(a, b, ...)
Is there any reason the first is used so often? I would like to send in a PR to move over to the second way, but want to make sure it would be accepted.
I am not sure if I understand stall-on-demand fully.
this one will improve query time for sure 😉
i have seen @easbar implemented it for graphhopper
, so i guess you understood everything.
please check my understanding:
the blocking happens before the neighboring nodes are added to the heap. Because adding nodes to the heap is the expensive part.
so we iterate over incoming edges with its neighbors and check if a node with a higher level is already settled. if so we end here.?
if not we iterate as usual over outgoing edges with its neighbors and add them to the heap.
do we have to store something when a node is blocked?
Hi there, could you dual license under MIT or Apache 2.0? This is the standard license used in the Rust community.
The preparation time varies drastically depending on the graph we use. Take for example these graphs (included in this repository), that are similar in size:
name | nodes | edges | edges/nodes | preparation time (ms) | fast_graph edges | fast_graph edges/node | prep per node (μs) | query time (μs) |
---|---|---|---|---|---|---|---|---|
Bremen dist | 40_461 | 85_090 | 2.10 | 429 | 66_520 | 1.64 | 10 | 18 |
Bremen time | 40_461 | 85_090 | 2.10 | 6_868 | 62_518 | 1.54 | 169 | 13 |
Bremen uniform* | 40_461 | 85_090 | 2.10 | 307 | 65_669 | 1.62 | 8 | 15 |
South Seattle | 29_763 | 49_604 | 1.67 | 16_750 | 64_029 | 2.15 | 560 | 32 |
The measurements shown in the table are just the result of running the tests in lib.rs
on my laptop.
*Update: For the Bremen uniform graph I used the Bremen time graph, but set all edge weights to a constant value of 10.
I'd really like to find out where this difference comes from and it would be especially useful to speed up the preparation of the abstreet graphs (South Seattle here) somehow. Also related: #33.
In a table, it shows the consumed time, such as New York.
But where is the dataset? is the format shapefile?
could you pls provide more details?
WASM is 32bit always (afaik).
So if you serialize a FastGraph on a 64bit platform the resulting bytes will not be deserializable in a WASM binary.
Is there a real need for usize
or would you be amenable to a more concrete type? Or do you know of some way to tell serde that usize
should read 8 bytes (u64
) when it's decoding into a u32
?
There are still some perf gains to be had if we switch to a bidirectional dijkstra's implementation for the query phase.
(See https://arxiv.org/pdf/1504.05140.pdf , pages 22-23)
Using Rust 1.51.0 I get:
warning: panic message is not a string literal
--> src/preparation_graph.rs:150:13
|
150 | / format!(
151 | | "invalid node id {}, must be in [0, {}[",
152 | | node, self.num_nodes
153 | | )
| |_____________^
|
= note: `#[warn(non_fmt_panic)]` on by default
= note: this is no longer accepted in Rust 2021
= note: this warning originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
See discussion here:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.