How to populate an undirected graph from PostGIS?

Question

This question is more related to resources that I might not have identified yet, although I've been searching the web for a while.

In the project I'm working at the moment I need to run a shortest-path algorithm on a graph representing office rooms, corridors, stairs, lifts and routes between buildings.

For the presentation layer I thought of using Python scripting with MapServer, but now I'm giving more thought into how to build the graph from the (shapefiles conveted into a) postGIS db generated from OpenEV so that it's easy to add and remove edges or weights or information about the points afterwards.

For Python there's a module called networkX that deals with graphs, and although this issue has been brought up in stackexchange here, the graph I'm trying to build is not a digraph but an undirectional one.

Update: 5 days ago Ben Reilly's utilitynetwork has been added to the networkX project. Utilitynetwork builds a directed graph from shapefile features.
The questions remains open for a similar approach of reading features from the postGIS database.

Answer 1

NetworkX has a method to convert directed graphs into undirected ones.

Additionally, the code to read a shapefile (or directory of shapefiles) doesn't really need to output a directed graph, that's just what I needed at the time. I haven't tried, but replacing the single line:

net = nx.DiGraph()

...might just do the trick.

NetworkX looks like it will support reading shapefiles out of the box (with OGR) in 1.4 (feature).

Answer 2

Have you looked into using pgRouting?
http://www.pgrouting.org/docs/howto/topology.html#graphs-directed-undirected-reverse-costs

Answer 3

Not sure how interested you are in using other frameworks, or if you've gotten this solved already, but the Geodjango project adds real nice ORM features to GIS data models, for a variety of GIS enabled databases, including postgres with the PostGIS bindings installed.

The Geodjango link is here: http://docs.djangoproject.com/en/dev/ref/contrib/gis/install/#overview

Note that Django is a web framework for python, geodjango came about to edit and display GIS data for backend webdevelopment, but it also gives a much more intuitive and powerful set of classes than the direct OGR python bindings (much more 'pythonic' rather than directly 'converted from C syntax', e.g. you can create a django.contrib.gis.geos.linestring.LineString class directly rather than creating an ogr.Geometry class with wkbLineString constant in the constructor).

In the geodjango tutorial located: http://docs.djangoproject.com/en/dev/ref/contrib/gis/tutorial/

The steps needed to configure read/write from your Postgres database are as simple as using other django python models, the headache is setting up your geospatial database. So, to load data into the postgres database, see the anchor #layermapping link in the tutorial above; it is a field mapping between the available data in the shape file to the database columns that are setup for your data model.

At the very least, I'd take 2-3 hours to go through the tutorial and setup the PostGIS bindings and see if this GIS tool is what you're looking for.

Note also, that when you have a GIS enabled database (e.g. PostGIS bindings for pgsql) you can do 'contains' 'within' directly on the database geometry (Lines/Polygons) data using the database stored functions (e.g. ST_Contains(...): see the sample SQL for postgis/pgsql here: http://postgis.refractions.net/docs/ch04.html#id2639062 ... and the best part about Geodjango, is that it is optimized to do these spatial lookups for you!.