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.

  • You don't want to use pgRouting? – underdark Nov 16 '10 at 15:42
  • I would use pgRouting, however the algorithm I'm trying to implement is bidirectional a-star and not an off-the-shelf option. – user39901230 Nov 19 '10 at 13:11

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).

  • sorry for the confusion. What I'm actually trying to do is to convert the shapefiles into a postGIS databse using shp2pgsql and then from the the postGIS database to import it in the networkX graph. – user39901230 Nov 19 '10 at 13:15
  • thanks Ben. Just noticed that 5 days ago they closed the ticket and your code has been added to the networkX project. It would have been interesting to see if it would be possible to do the same thing with the features from the postGIS database, but I'll have a look on that over the Christmas holiday. – user39901230 Nov 29 '10 at 11:49
  • since the networkx has included the module but not yet released v1.4 would it be possible to give some samples of using utilitynetwork. So far I've skimmed through the testnetworkload and through your samples found here: gis.stackexchange.com/questions/210/alternatives-to-pgrouting/… – user39901230 Jan 3 '11 at 17:41
  • There is still a bit of work to do on this, which is why I haven't put it on pypi. I've made the wiki public now, it should contain the best working samples: bitbucket.org/gallipoli/utilitynetwork/wiki/Home – bwreilly Jan 3 '11 at 19:52
  • since I'm planning to include this in my final undergraduate year project, would it be possible for me to also contribute? – user39901230 Jan 3 '11 at 22:03

Have you looked into using pgRouting?


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!.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.