[pgrouting-dev] Dijkstra's solution - How to get tree?

pgRouting pgrouting-dev
1

Hi,

If I run a Dijkstra's solution:

Can I run it for some max distance?
How can I get the resulting tree?

I have a problem where I need to pick a start point and solve the graph for some max distance from the start node. I think this is similar to what is done for drive time analysis.

Any hints would be welcome and I'm not shy about hack some code if I know where to start looking.

Thanks,
   -Steve

2

Hi Steve,

Can Driving Distance function give you some hints? It is nothing more
than Dijkstra where a distance (not a target vertex) is a quit
condition. It returns only vertices, but with some hacking you can
make it return a tree. I think.

Cheers,
Anton.

3

Anton Patrushev wrote:

Hi Steve,

Can Driving Distance function give you some hints? It is nothing more
than Dijkstra where a distance (not a target vertex) is a quit
condition. It returns only vertices, but with some hacking you can
make it return a tree. I think.

Cheers,
Anton.

Thanks Anton,

I will look at that tomorrow when its not so late.

I am thinking it would be nice with we could do something like:

select node_id, cost, parent_id
   from dijkstra(start_node_id, max_distance, ....);

or something like that. From these tuples you can easily construct the tree extract the route from to all or any nodes in the tree, etc.

You can also find all terminal nodes because they will not be represented in the parent_id column, like:

select node_id from treetable
except
select parent_id as node_id from treetable;

-Steve

4

Anton Patrushev wrote:

Hi Steve,

Can Driving Distance function give you some hints? It is nothing more
than Dijkstra where a distance (not a target vertex) is a quit
condition. It returns only vertices, but with some hacking you can
make it return a tree. I think.

Cheers,
Anton.

Hi Anton,

So I'm looking at trunk/extra/driving_distance/sql/routing_dd_wrappers.sql

Am I correct in thinking that if I clone FUNCTION driving_distance() and do not call points_as_polygon() that I can basically get that to return me the point tuples of the solution which would be:

routing_ld=# \d path_result
Composite type "public.path_result"
   Column | Type
-----------+------------------
  vertex_id | integer
  edge_id | integer
  cost | double precision

And I assume that parent is source or target which is not vertex_id.

Hmm, but the C code is in $libdir/librouting_dd which is a problem for me because I can not get CGAL to load on Debian so I can't load the extra stuff.

Argh! and to top things off, I am not familiar with hacking CMake.

Any thoughts or help in simplifying this would be appreciated. It seems that boost_drivedist.cpp and drivedist.c could get moved to core and only the CGAL stuff could be left in extra. This would also probably mean moving the corresponding parts of routing_dd.sql to core also.

-Steve