[pgrouting-users] TSP and how to contribute

[Stephen Woodbridge]

On 1/15/2011 12:20 AM, Daniel Kastl wrote:
>
>     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.
>
>
> Good point. I agree.
> Since the returned "edge" column is more or less useless, don't you
> think it would fit in the current schema?
> http://www.pgrouting.org/docs/1.x/dd.html
>
> Just replace edge_id column with parent_node_id and cost
> as accumulated cost.
> That said, I unfortunately have no knowledge in C/C++. If someone
> thinks, this isn't difficult, please go ahead!
>
>
>     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.
>
>
> Also agree.
> Do you think this applies also to shortest path functions or are they
> "open" enough?

The shortest path if you are talking about a simple dijkstra solution, 
we have the same issue as driving distance. Both use a Dijkstra solution 
the only difference is when the solution is terminated. Driving distance 
it terminated when all node on the frontier are greater then or equal to 
the cut off distance. For the shortest path, it terminates when the 
graph is solved or when the target node is reached depending on how it 
is coded. Then in both cases, the resulting tree is post-processed to 
extract additional information, ie: the start to end route or the 
driving distance polygons.

So what are the use cases for this:

1. Say you want to do a TSP (not using our existing code). If You had 10 
points, then you could run 10 Dijkstra solutions, one for each point and 
from each solution extract the route and cost to the other nine points. 
This is like a selective all paths solution, I call it some paths 
solution. This is very efficient and lets you collect all the inputs to 
solve the TSP and after you have solved it you already have all the 
routes computed and cached. Also, if you can reuse the graph for each of 
the ten solutions, rather than rebuild the same graph ten times, it is 
significantly faster.

2. We already discussed drive time analysis

3. We talked about the need to reverse the graph for destination drive 
time analysis

4. The obvious on of shortest path between start and end.

I'm sure there are other analysis that need this as it is one of the 
more basic graph analysis, but my brain is not fully awake yet.

So one issue I see in refactoring this, is for example building a graph 
and reusing that graph probably all has to be done inside a single C/C++ 
call or you have to build a mechanism to save the graph to a blob or 
somewhere and then reload it when you later want to use it. So this 
might all need to be wrapped into a single call.

> Probably we should add some tickets.

Yes this would be a good idea, if nothing else to capture the ideas and 
discussion. Or I think you already started some RFCs. This would be a 
better way to document and discuss these issues. tickets should be used 
to document actual work or bugs.

-Steve

>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users