[pgrouting-dev] Driving Directions Revisited

[Stephen Woodbridge]

On 5/17/2011 4:37 PM, Jay Mahadeokar wrote:

[snip]

> I will just guess here, since I am not exactly sure about the internals
> of driving distance.  But, in theory, if the graph is not connected, the
> breadth-first-dijkstra-search algorithm would return multiple trees.
>
> If the dijkstra implementation stops when no more vertices can be
> reached from source, then only single tree should be returned, excluding
> the vertices in other components of graph. But, if b-f-s is continued,
> then multiple search trees would be output.
>
> Is the input graph that is being constructed, connected?
> Would this have something to do with the result? Or if the
> driving_distance implementation search stops when no vertices are
> reachable, then I guess there would be some other issue..

Jay,

Thanks for your thoughts. I had to go back and reread the description here:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/dijkstra_shortest_paths.html

So this does not do a breadth-first search but using dijkstra algorithm.

It should return a single tree with the source node cost=0.0

We also pass a predecessor map which I would like to output also as this 
would aid in reconstructing the tree. In theory I should be able to 
reconstruct the tree from the vertex_id and edge_id because the 
predecessor of vertex_d should be:

    case when b.source=vertex_id then b.target else b.source end as tid

in my query.

What I am concerned about and wondering about if there is a bug that is 
preventing some edges from being return the would link the various trees 
that I was able to reconstruct.

I will do some additional data analysis to try and validate that hypothesis.

-Steve