[pgrouting-users] TSP and how to contribute

[Emre Koc]

On Fri, Jan 14, 2011 at 5:09 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:

> 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.
>


Thats the feature I need and I am sure it will be very useful for a lot of
scenarios.  For instance I want to write a partial edge selection for
driving distance's outmost edges. So it will be very easy to do that with
the data you mentioned.



>
> -Steve
>
> _______________________________________________
> 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/a9a187bf/attachment.html