Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have a directed graph and am using PgRouting's driving_distance function. My application needs it (or a related PostreSQL procedure) to return a full set of EDGES emanating out of the source, and not the just the VERTICES.

The Drivetime function (the essential "Dijkstra algorithm") returns the following columns:

  • Vertex_id

  • CostToSource (from that vertex)

  • Edge_id (where edge.source = vertex_id )

Of course a vertex can have several edges associated with it and only one edge per vertex is returned in this table (for some reason).

Qu: Can anybody think of a way to relate the above information with the network so that I can get what I need, which is:

  • Related Pair ( Vertex_ID, Edge_ID)

  • CostToSource (From vertex_id)

Hint: the obvious problem with joining vertex_id to the "source" in the network table is that some of the links do not belong in the result set. Any link heading back to the source should be excluded.

Thanks all.

share|improve this question

2 Answers 2

it's not an answer but I don't have enough points to comment your entries.
I'm a noob at postGIS (and have some basic knowledge of SQL), can you explain me more how to do passes 3-5?

share|improve this answer
    
Sorry about the terribly late reply. I left this field for a while. I cannot really remember. I gave up and started using a Dijkstra algorithm directly with the python language. The routine returns the distance (or time cost, if that is how you weight the links/edges) of every visited node back to the source as well as every nodes predecessor node. i.e.code.activestate.com/recipes/… –  John Steedman May 10 '13 at 19:01

I have found one way to do this now. It is a little involved and adds an inefficiency but works on my 2000 node network.

For a driving distance analysis from A_SOURCE...

  1. Join the driving_distance table d back to the network/graph table nw on d.vertex_id == nw.TARGET. PostGIS returns table RES_TABLE

    Column selection should include

    nw.SOURCE (alias edgeSource)

    nw.thegeom

  2. Sort this table by d.cost (FromSource)

  3. Now create a list VISITED which will contain vertices

    Push SOURCE_ID onto VISITED

  4. for each RECORD in RES_TABLE if RES.edgeSource in VISITED then

    discard this RECORD
    

    else

    push RES.VERTEX_ID into VISITED
    
  5. Now RES should contain

    -vertex_id with a cost to SOURCE_ID

    -data relating to an edge which points BACK from the vertex_id towards

    SOURCE_ID

Note:

It would be VERY helpful if PgRouting could return information about the PREDECESSOR (edge or vertex) rather than some random edge. In fact the Dijkstra algorithm is supposed to return both costToSource and prior vertex.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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