Comments (8)
UPDATE: I've come to a solution that serves my needs for the time being, so this is not a time-critical issue for me. Although if it is implemented, I would look into switching over.
It is a bit tangential, but in case anyone is interested, here are some of the tools that I've used or looked into:
I am using the DTA Anway classes (https://code.google.com/p/dta/) to store my networks. This is derived from a dynamic traffic assignment project, but gives me a package to read networks in a couple of different formats, and deal with intersection control, centroid connectors and such things. I originally used an SP algorithm implemented in this package, but I was naively re-calculating the paths with each call, so it was slow.
To speed things up, I considered: pandana, networkX, aequilibrae, and scipy. Of those, I found:
- pandana doesn't currently have the SP functionality exposed, although it looks promising when that happens.
- networkX seemed to struggle with the size of my network (~15,000 nodes), and I got feedback that it's SP was slow.
- aequilibrae looks promising as a traffic assignment/travel modelling package. It's SP method is based on scipy, so for my purposes I opted to go directly to the source.
- It turns out that scipy has some pretty good SP implementations. You specify the network in a sparse matrix format, and it gives back 1) a matrix containing the impedance between each node pair, and 2) a matrix containing the predecessor nodes in the shortest paths, which allows you to re-construct the path. In my case, I can just calculate the paths once, and then re-trace what I need for each GPS point using the predessor matrix. This improved my runtime by 2 orders fo magnitude, so I'm happy. The downside is that it does it for every node pair, so the resulting matrices can be quite large in terms of their memory footprint, but it works ok for me.
My bottlneck is currently in matching points to the N nearest links, but that is another topic.
from pandana.
Thanks for the summary Gregory. As you mentioned, the SP in Pandana does exist on the C++ side but hasn't yet been exposed in Python, and it shouldn't be too much work to do so. It's always been on our roadmap but it's good to know that there's interest so that we can prioritize it. Since the underlying SP implementation uses contraction hierarchies (we use older code from the OSRM project), this should be quite fast, although if you use scipy to do the all pairs shortest path I think that should be efficient as well. I think that approach would fail for very large networks - like 200k edges, which is what we typically use for the 9 county Bay Area local street network. Will let you know as we make progress!
from pandana.
Thanks, Fletcher.
Yeah, I'm currently using a City of SF network that has about 30k edges, so I can imagine 200k making it blow up due to having to store the return matrices in memory.
from pandana.
Hey Greg, (hi from London!) if you specifically need high performance (via C++ bindings and multiprocessor support) then have a look at graph-tool. Not sure how it fares in Windows, though worked quite well for me on Ubuntu. (When running natively on Mac then it isn't able to utilise all processor cores.) You can also do some interesting things by moving the data to and from numpy and you can load / save to graphML format.
from pandana.
wanted to vote +1 on this. We'd be really interested to use pandana for network-based spatial weights in pysal and this would be an easy way to get there
from pandana.
It looks like this was implemented in #48 and included in the v0.4.0 release, actually, but left out of the change log.
https://github.com/UDST/pandana/blob/master/pandana/network.py#L174-L203
Does this provide what you need?
from pandana.
oh awesome! though as fletcher mentioned,
a nice extension of this would be to get a dataframe of shortest paths, in parallel
which would be ideal
from pandana.
for my part, this is essentially the same request as #120 and #56
from pandana.
Related Issues (20)
- Support for M1 Macs HOT 3
- [Question] How to get different Key|Value combinations in osm.node_query
- [Feature Request] Aggreggation queries to subset of nodes
- Binary incompatibility error with older versions of NumPy HOT 1
- Shortest path length exists but shortest path is empty HOT 5
- shortest path distance between non connected nodes
- Allow specifying mapping distance for POIs
- Issue: the POI Accessibility computation is taking forever
- OSM loader - POIs that are ways in OSM HOT 1
- Pandana network initiation slow for large network HOT 4
- how to increase the performance of the aggregate when impedance is changed to time?
- net.shortest_paths doesn't work with multiprocessing
- tables sub-dependency versions conflict with python 3.10 compatibility when installing with pip HOT 1
- incorrect shortest paths solutions when impendance values are particularly small or large HOT 1
- Plotting with Pandana does not render title HOT 1
- osm.pdna_network_from_bbox error HOT 6
- Pulling network object from OSM bugged HOT 2
- New release ?
- Google Colab install pandana error HOT 1
- query the OSM API for the street network within the specified bounding box error 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 pandana.