[pgrouting-users] TSP and how to contribute

[Stephen Woodbridge]

On 1/14/2011 6:21 AM, Daniel Kastl wrote:
>
>         Sorry, I was wrong ... it's the right function you're using.
>         Somehow read driving directions somewhere before.
>         Driving directions does what you need, except that it returns
>         you a list of vertices you can reach and the edges column
>         doesn't return anything useful.
>
>         This custom wrapper function takes the vertices and calculates a
>         polygon that contains all of them:
>         https://github.com/pgRouting/pgrouting/blob/master/extra/driving_distance/sql/routing_dd_wrappers.sql#L78
>
>
>     Yes this creates a polygon consisting all vertices but I want to
>     display a road network that show how to go from source to outlying
>     vertices. Actually I think driving distance's edge info should give
>     that info since it calculates a distance from source. If that
>     function know how distant is the vertice it should know the path am
>     I wrong on this ?
>
>     As I wrote, calculating shortest path for each vertex from source
>     does not seem feasible. Can we make driving distance to show edge
>     info ? I am willing to conribute in that sense but I don't want to
>     redo what is done before.
>
>
> Driving Distance function uses Dijkstra algorithm:
> https://github.com/pgRouting/pgrouting/blob/master/extra/driving_distance/src/drivedist.c#L341
> Dijkstra only goes from vertex to vertex.
>
> @Anton: do you have some hint?

Daniel,

This is why we need a function that returns the solved dijkstra tree like:

node_id, cost, parent_node_id

for all nodes in the solution. You can then retrieve the 
edge(parent_node_id, node_id). cost is the accumulated cost to get to 
node_id from the start node. parent_node_id should be NULL or -1 to 
indicate the node_id is the start node.

This allows anyone to do a Dijkstra solution and get back the full 
results of that solution. One of the goal of pgRouting is to better 
support arbitrary graph analysis within the database and this would 
greatly help in this area. We need the high level wrapper functions like 
we already have because they are convenient, but we currently hide 
access to the underlying graph solutions so people can not use it to do 
things like Emre is trying to do.

Look at the image on my home page: http://imaptools.com/

This shows and example of just displaying the polygons, but I was also 
able to display the roads segments colored the distance ranges. These 
were NOT done with pgRouting.

Also if you did a driving distance calculation for say 30 mins and got 
back the solution above, it would be possible to post process that into 
multiple 5 min polygons, (maybe that is possible with the current code). 
There are other useful needs for this kind of data.

-Steve