[pgrouting-users] TSP and how to contribute

Emre_Koc · January 14, 2011, 12:29pm

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

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Stephen_Woodbridge1 · January 14, 2011, 3:09pm

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

Emre_Koc · January 14, 2011, 3:33pm

On Fri, Jan 14, 2011 at 5:09 PM, Stephen Woodbridge <woodbri@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Stephen_Woodbridge1 · January 14, 2011, 3:53pm

On 1/14/2011 3:15 AM, Emre Koc wrote:

Steve,

To trick the algorithm can't we switch reverse_cost and cost values in
driving directions ? I think that if driving directions can output a
connected road network that will both cover your 5 min roads to store
and fire-station reachability. Am I wrong about this ?

Yes this might work for the way that pgRouting has implemented this. This only works because the graph is built with edges in both direction. I you eliminated the anti-oneway edges when the graph was built, this would not work. When I implemented, in another program, something similar I did not have edges with high weights on them to indicate a one way street. My graph was a directed graph and I just did not include the edge at all. If you have a lot of oneway streets like in a city, then you get a smaller graph to start with. I have also seen pgRouting actually route the wrong way down one of these high cost edges. I think I would rather it just fail than to silently do that.

-Steve

/emre

On Fri, Jan 14, 2011 at 8:01 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    On 1/13/2011 10:15 PM, Daniel Kastl wrote:

        2011/1/14 Stephen Woodbridge <woodbri@swoodbridge.com
        <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.com>>

            On 1/13/2011 3:18 AM, Emre Koc wrote:

                Hello,

                I am intereted in using TSP functions of pgRouting but I
                couldn't find
                any tutorial or documentation on it. Does anyone have a
                documentation
                for TSP functions ? I am using Dijkstra with a custom
        query. Is it
                possible to use TSP with custom query?

                Also I want to extend pgRouting functionality by
        calculating a
                distance
                network from a point or towards a point. How can I
        integrate my
                source
                to pgRouting ?

            Yes, I asked for this functionality also. I did a little
        research
            into how to do this. I seems that in boost you need to
        reverse the
            graph. We already build the graph but would need to then add
        a step
            to reverse it to change the sense of direction. I think this
        is the
            function that is needed:
        http://www.systomath.com/include/Boost-1_35/libs/graph/doc/reverse_graph.html

        Maybe someone wants to add an RFC for that
        (http://www.pgrouting.org/rfc/index.html).
        Soon there will be GSoC and students will be looking for project
        ideas.

        Recently "SRC" (don't know the real name) wrote some
        bidirectional patch
        for pgRouting. I applied the patch to my fork at GitHub called
        "Two-Way
        A-Star": https://github.com/dkastl/pgrouting
        Is this somehow related?

    Daniel,

    This might apply to this problem, but I have not looked at what he
    did or how it is implemented. On an undirected graph routing from
    A->B is the same as B->A, on a directed graph this does not have to
    be the case.

    For bi-directional routing on a directed graph, you need to reverse
    the graph or otherwise trick the algorithm when it is routing FROM
    the destination toward the start. At the destination you need to ask
    what node could I have come FROM to get here, but at the start you
    have to ask what nodes can I go TO from here. So you need a graph
    and a reverse graph or you need to maintain enough a list of
    outgoing nodes AND a separate list of incoming nodes.

    For drive time analysis, you might want to compute what is the area
    covered by consumers that are willing to drive 20 min to get to my
    store located "here". So "here" is the destination. But if you are a
    municipal planner, you might want to know what coverage area do my
    fire-stations have with a drive time of 5 mins or 10 mins. In this
    case the fire-station is the start point.

    For undirected graphs, there is no difference.

    -Steve

    _______________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.org <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

dkastl · January 15, 2011, 5:20am

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?
Probably we should add some tickets.

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Stephen_Woodbridge1 · January 15, 2011, 3:23pm

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@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users