Comments (7)
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 ?
from fast_paths.
Yes. That is what I had in mind.
from fast_paths.
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.
from fast_paths.
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.
from fast_paths.
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
from fast_paths.
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 ?
from fast_paths.
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.
from fast_paths.
Related Issues (20)
- usize does not work well for de/serialization. HOT 4
- CH improve amount of created shortcuts HOT 9
- bidijkstra stall-on-demand HOT 21
- Possible perf regression with Rust 1.45 HOT 4
- Extremely high memory usage when generating fast graph HOT 8
- Why not more object oriented? HOT 5
- Copy and Clone Traits HOT 3
- Rust 1.51.0 warning: panic message is not a string literal HOT 1
- ShortestPath PartialEq ignores nodes
- Improve preparation time
- Why does the preparation time vary so much for different maps? HOT 13
- Possibly wrong path? HOT 3
- What would it take to support tiled routing graphs? HOT 3
- format of datasets such as New York HOT 6
- method calc_path_multiple_sources_and_targets not found in `PathCalculator` HOT 5
- Program hangs with a large (>2200) edge set HOT 2
- The dijkstra's implementation should be bidirectional HOT 2
- Document how to run the benchmarks HOT 6
- Huge performance difference in terms of running time HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from fast_paths.