How do I apply Dijkstra's algorithm in Python with PostGIS data?

Question

I have currently parsed OSM data, from a PBF file, into a pgRouting database with the use of osm2po, an excellent parsing tool. I don't however want to use the algorithms provided by pgRouting and instead want to have a custom algorithm. But to start off and gain an understanding of how to use the data, I'll attempt to simply apply Dijkstra's algorithm.

My logic so far is to:

1. Determine whether two points are within x distance.
2. Get the two nodes closest to each point.
3. Query the database with a bounding box.

The query to the database will return all nodes, including their: x and y position, target nodes, edge length (km) and the_geom, within the specified bounding box.

The difficulty I have now is, how can I use the data and apply Dijkstra's algorithm such as the algorithm here: http://thomas.pelletier.im/2010/02/dijkstras-algorithm-python-implementation/, as the query won't produce a graph like:

...      graph = {
...     'A': {'B': 10, 'D': 4, 'F': 10},
...     'B': {'E': 5, 'J': 10, 'I': 17},
...     'C': {'A': 4, 'D': 10, 'E': 16},
...     'D': {'F': 12, 'G': 21},
...     'E': {'G': 4},
...     'F': {'H': 3},
...     'G': {'J': 3},
...     'H': {'G': 3, 'J': 5},
...     'I': {},
...     'J': {'I': 8},
...     }

If Dijkstra's algorithm is not suitable for this, what routing algorithm is?

In addition to that, I'm slightly confused how routing algorithms work on parsed data, which has been parsed by any osm parser. From all the parsers I've come across, a node only ever has one target node. Wouldn't this mean that I could only ever move in one direction, that being to the target node, then the next target node and so on?

Thanks to anyone willing to improve my logic.

Answer 1

What you need is a directed graph. The table osm2po creates for pgRouting is not directed. Nevertheless you can derive one forward and one backward edge from each segment (table-row). The result is an adjacency list - a little different from your representation:

graph = {
  'A': {'B': 10, 'D': 4, 'F': 10},
}

osm2po (and I think pgRouting does also) uses this layout:

'A', 10 , 'B'
'A',  4 , 'D'
'A', 10 , 'F'

Answer 2

I have done it the way you are discussing, though I borrowed this algorithm instead of the one you're using.

http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/

I've also processed OSM to make it routeable and can vouch for osm2po. It does work well with Dijksra's algorithm and saves you a lot of time.

A* is an alternative. I believe it is implemented in PgRouting.

Answer 3

I actually figured out how to do this by myself. The first thing that confused me was how can one node only have one target node, hence can only go in one direction. The answer is it doesn't.

Firstly, in the database there can be multiple rows for a single source node, ie one for each edge going out from that node. Secondly, when you build a network using your data, the network will become directed, ie the target node of any edge will also be able to see the edge.

In Python, I easily created a network using the framework NetworkX, here: http://networkx.github.com/, via an algorithm I quickly made. NetworkX is well documented, so anyone should be able to build their own network.

Once you have built your network, you can call the method to_dict_of_dicts on it, which converts the network into a matrix, similar to the one I posted in my question. Now that you have a matrix to work with you can go ahead and implement any type of routing algorithm on it.

It took me a while to figure this out, but I hope this helps anyone who seeks to apply routing algorithms, on OSM parsed data, in the future.

UPDATE: "Any NetworkX graph behaves like a Python dictionary with nodes as primary keys" [source: http://www.cl.cam.ac.uk/~cm542/teaching/2011/stna-pdfs/stna-lecture11.pdf, pg 23]. You therefore do not need to convert the NetworkX graph into a matrix before performing your algorithm on it.