Using the PgRouting driving_distance function can we see the edges?

Question

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.

Answer 1

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.

Answer 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?