easbar / fast_paths Goto Github PK

See discussion here:

20ba810#r53021469

Hi there, could you dual license under MIT or Apache 2.0? This is the standard license used in the Rust community.

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.

Data

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
...

Experiment hardware

I run the experiments on a Windows desktop with i7 8700 CPU, 16 GB memory.

Code of running queries of CH

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.

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?

Just wondering why the structs like FastGraph don't derive Clone?
It's blocking structs that own one from deriving those traits.

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.

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?

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

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?

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.

Some of the ideas taken from this discussion: Stunkymonkey/osm_ch#1

• cancel witness searches after a certain amount of nodes have been explored -> see #37
• use contracted_neighbors heuristic
• use flat array for preparation graph
• parallelization Stunkymonkey/osm_ch#1 (comment)
• contract only a certain fraction of nodes
• find out why abstreet graph preparation is slow compared to e.g. plain OSM maps Stunkymonkey/osm_ch#1 (comment) -> see #37
• clean up query code? Stunkymonkey/osm_ch#1 (comment)

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.

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)

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 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.

The code in floyd_warshall.rs is only used in tests at the moment.

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:

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?

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)

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.