[pgrouting-users] TSP and how to contribute

[Emre Koc]

On Fri, Jan 14, 2011 at 1:21 PM, Daniel Kastl <daniel at georepublic.de> 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.
>

I know that dijkstra works from vertex to vertex but the shortest path
implementation of dijksta in pgRouting is giving edge id's as an output that
it passed.

Now I found a solution to this problem by marking edges who has source or
target vertex ids that is listed in driving distance query's vertex list.
But this takes 25 seconds to calculate. With a given edge id.

Is there any indexing or configuration to postgre that can speed up driving
distance calculation ? or is there a more noble solution to this edge
selection problem ?

Emre




>
> @Anton: do you have some hint?
>
> Daniel
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> Web: http://georepublic.de
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20110114/33a38ebc/attachment-0001.html