Expose shortest path functionality

[gregerhardt]

Can the underlying shortest path functionality in pananda be exposed so it can be called using a python method? Given a node pair A-B, I want to get back 1) the impedance from A to B, and 2) the sequence of node or link IDs that define the shortest path from A to B. Doing this for a list of node pairs is even better.

My specific use case is that I am matching probe vehicle GPS points to the a network. Since they are only collected every 60 seconds, I need to impute the path between points, so I end up building many "short" shortest paths to do so. My current implementation works, but is slow, and I'm hoping your multi-threaded C++ implementation can speed things up.

pandana looks like it could turn into a nice general purpose networks container for transportation modelling/analysis, and I think exposing more of this functionality would help in that regard. Many thanks!

[gregerhardt]

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.

[fscottfoti]

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!

[gregerhardt]

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.

[songololo]

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.

[knaaptime]

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

[smmaurer]

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?

[knaaptime]

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

[knaaptime]

for my part, this is essentially the same request as #120 and #56