search

easbar / fast_paths

Fast shortest path calculations for Rust
Apache License 2.0
271 stars 25 forks source link

Add a way to get all nodes in a radius #5

Open Eh2406 opened 5 years ago

Eh2406 commented 5 years ago

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.

easbar commented 5 years ago

Starting from some node p you want to find all nodes q such that the weight of the shortest path p->q is less than some threshold ?

Eh2406 commented 5 years ago

Yes. That is what I had in mind.

Eh2406 commented 5 years ago

Now that I think about it we could have an iterator that returns q's sorted by the shortest path p->q. If you want a k nearest: iterator.take(k). If you want all in a range iterator.take_while(|p| p->q < range).

If you have some pointers I may be able to give this a try.

easbar commented 5 years ago

Ok yes the trivial way of doing this is calculating all paths p->q, then sorting by distance and taking only those up to some limit. Do you think this should be included here (it can easily be done using the existing API) ?

This can also be done more efficiently, but currently this is not supported. Btw in the context of routing networks this is sometimes called isochrone calculation.

Eh2406 commented 5 years ago

Only when it can be done more efficiently than the alternatives. Do Contraction Hierarchies help make it more efficient than a Dijkstra's on an unprepared Graph? If so then yes it should be here. If not then I need talk to the pandana team about why they do it this way. :-P

easbar commented 5 years ago

Yes it can be more efficient. Even the trivial way we lined out above might be faster (on small maps at least).

why they do it this way

You mean they are doing this already ? How would implementing it here help with Pandana ?

Eh2406 commented 5 years ago

It is a C++ python Library, it has in the past caused our entire model to segfault. I spent today trying to diagnose a regression in performance, our model is now taking an additional 16 hours to run. As someone who doesn't know C++... let's just say I would like the rust alternatives to be as ready to be a drop-in replacement as possible.