9

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.

Community
  • 1
user39901230
  • 466
  • 5
  • 14

3 Answers3

5

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

bwreilly
  • 874
  • 4
  • 10
  • 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: http://gis.stackexchange.com/questions/210/alternatives-to-pgrouting/789#789 – user39901230 Jan 03 '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: https://bitbucket.org/gallipoli/utilitynetwork/wiki/Home – bwreilly Jan 03 '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 03 '11 at 22:03
  • Happy to have any contributions. DM me (bwreilly) if you have any questions or problems getting started up. – bwreilly Jan 04 '11 at 18:18
  • you're storing the g.GetPoint(0) in a tuple that has 3 elements as floating points - at least that's what I see when I print net.nodes(). What is the 3rd element for? – user39901230 Jan 07 '11 at 21:13
  • figured out. It's for attributes. I'm trying to compare the x, y coordinates of two linestrings and if the end of one is close enough to the start of the other to use the average between the two points to as the ending vertex of one edge in the networkx graph and as the starting in the other. – user39901230 Jan 07 '11 at 22:14
  • I've adjusted the code to detect close starts/ends of linestrings and add them to the graph with edges starting from the point that's the closes to. btw. there's no dm in stackoverflow. How can I contact you, ben? – user39901230 Jan 09 '11 at 19:07
  • Sorry. By DM earlier I meant twitter DM (bwreilly). Prefer to keep my email off the site. Should also be able to message on bitbucket (http://bitbucket.org/gallipoli/) and I have an account on github as well (http://github.com/bwreilly). – bwreilly Jan 10 '11 at 04:02
2

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

Regina Obe
  • 10,503
  • 1
  • 23
  • 28
2

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

tmarthal
  • 401
  • 4
  • 7