Driving Distance function does not return a useful edge id

[YenTheFirst]

This is brought up tangentially in another issue (https://github.com/pgRouting/pgrouting/issues/51), and alluded to in the 2.0 documentation "id2: edge ID (this is probably not a useful item)", but this really needs to be documented as a specific issue.

The driving distance function should return the ids of edges actually traversed, and the cost to traverse those edges. i.e., the output of pgr_drivingDistance should describe a shortest path tree.

As it is currently, you can only get information on the cost to reach nodes, but not what edges are traversed in reaching those nodes. It returns an edge_id, but this is not actually related to anything.

demonstration of problem, using the sample data network:

the shortest path from node 1 to 6 is along edges 1,4,8:

select * from pgr_dijkstra('SELECT id, source, target, cost FROM edge_table', 1, 6, false, false);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   1 |   1 |    1
   1 |   2 |   4 |    1
   2 |   5 |   8 |    1
   3 |   6 |  -1 |    0

however, doing a driving distance query from node 1:

select * from pgr_drivingdistance('SELECT id, source, target, cost FROM edge_table', 1, 3, false, false);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   1 |   1 |    0
   1 |   2 |   4 |    1
   2 |   5 |  10 |    2
   3 |   6 |   9 |    3
   4 |   8 |   7 |    3
   5 |  10 |  10 |    3

you can see that it does not include edge 8. rather, it includes edge 9, which, while connected to node 6, would not actually be crossed if traveling only 3 distance units from node 1. the expected output should be:

 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   1 |   ? |    0
   1 |   2 |   1 |    1
   2 |   5 |   4 |    2
   3 |   6 |   8 |    3
   4 |   8 |   7 |    3
   5 |  10 |  10 |    3

where the edge id associated with the starting node could be anything, possibly -1 as a marker.

[woodbri]

This is not really a bug it is just how the code was designed. What you are asking for is the full output of the Dijkstra solution. I'll leave this open and see about adding this feature for 2.1 (whenever that is).

[woodbri]

Thank for the pull request. After looking at your changes and rereading your analysis of the problem, It looks like there your fix is very clean and elegant. I guess this is more of a bug than a feature request that has been in the code from the start. I'll merge this into 2.1 and probably into 2.0.1 branch also as soon as I get a chance. Thanks.

[cvvergara]

Work in progress See #278, For the case where there is no edge to traverse, I am returning -1 as suggested, I will have tests with sample data soon.