[pgrouting-users] Re: improve performance of isoline computation

[Stephen Woodbridge]

Ok, so a little graph theory background for those that might need it.
The Dijkstra shortest path basically takes a graph directed or not and a 
source node and creates a tree of the shortest paths expanding out from 
the source node. The tree is the nodes for the shortest paths. So if you 
are at a random node in the tree call it A then the edge that got you to 
this node is this nodes parent or predecessor and so forth up the tree 
until the parent is the node itself which indicates you are at the 
source node or the top of the tree.

In addition to this basics, you can do things like request a cut-off 
distance where the solves stops build the tree at some maximum distance 
along each path. Or you might supply a target node where the algorithm 
will stop when it find the target node and then return just the path 
from the source to the target.

For pgRouting, the general process is as follows:

1. create a query that selects some subset of the edges based on 
bounding box
2. request a Dijkstra solution providing a source node and a cut-off 
distance or target node.
3. we run the query and call methods to create a graph and add the edges 
to the graph
4. we run the dijkstra solution
5. we copy the results into a record set that gets return to postgresql 
depending on the analysis requested.

Ideally, what we want to get back a record set, something like:

node | predecessor_node | cost_at_node

We current get back:

node | edge_id | cost_at_node

We can actually use this because the predecessor_node is the edge_id's 
source or target that is not equal to node, but it is easier to deal 
with if we just get the predecessor to start with.

Oh and one big issue I ran into is that I was using the driving_distance 
code and there appears to be a bug in that code where all edges are not 
returned in the results so you can not reconstruct the tree, you in fact 
get multiple disconnected trees that would be connected if the missing 
edges were included. I do not think this damages the driving distance 
because you have all the nodes and that is what is used to create the 
alpha shape.

So what I ended up doing was to recode the dijkstra solver using boost 
outside of the postgresql server environment. I query the server using 
the libpq-fe.h interface, read the edges, build the graph solve it copy 
the results into C structs, reconstruct the tree in C and then play with 
that. It would probably be more efficient if I did it all in C++, but 
I'm a C programmer so I stay with my comfort zone :)

You might look at:

./core/src/boost_wrapper.cpp
./extra/driving_distance/src/boost_drivedist.cpp

It would be pretty easy to clone one of these and return the predecessor 
instead of (or in addition to) the edge_id and create a new wrapper 
function to return the results.

You could also just look at the existing wrapper function for dijkstra 
or driving_distance and clone that and return just the raw results which 
would look like:

node | edge_id | cost_at_node

So if you can reconstruct the tree, then do a depth first search on that 
tree, then every time to get to a terminal leaf node, ie: one with no 
additional descendants then you can collect the the predecessors back to 
the source node and this is one of the shortest paths. The costs at each 
node is the total cost to get to that node from the source. The 
cost_of_A - cost_of_B is the cost of edge_id.

If you want to create multiple isolines, for say 5, 10, 15, 20, 25 cost 
units, the you take all the nodes in the solution and create a 3D 
Deluany triangulated surface using X, Y of the node and Z = cost, then 
you slice the surface with planes at Z = 5, 10, 15, 20, 25 and for each 
Z value you collect the edges and create polygons from them.

So you should be able to see how one Dijkstra solution can be used to 
extract a lot of information depending on how you want to use it.

Hope this helps someones understanding of how this works.

   -Steve

On 6/7/2011 9:41 AM, Stephen Woodbridge wrote:
> You can compute the cost to all nodes in the network connected to the
> start node in a single pass. I have been able to do this with some
> simple modes to the pgRouting code. Basically you want to do a Dijkstra
> solution then extract all the node in the graph. if you want the actual
> path to each of these node it is relatively trivial to reconstruct the
> the solved tree using the predecessor map. I have to run out the door at
> the moment but I will try to post more on this tonight.
>
> -Steve
>
> On 6/7/2011 9:22 AM, Mayeul KAUFFMANN wrote:
>> Hi Jaak,
>> Thanks for your answer! At the end I need to know the time FROM (almost)
>> every single cross in the network TO each one of a few point. The
>> computation is very close to computing several complete sets of
>> isolines, then searching on which isolines a single point lies, this is
>> why I asked my question this way.
>> About your answer "Pgrouting can find one isoline, this is the result of
>> driving_distance", do you mean that you are using a similar approach to
>> the link below to compute isolines?
>>
>> http://underdark.wordpress.com/2011/05/13/catchment-areas-with-pgrouting-driving_distance/
>>
>>
>> Thanks again!
>> Mayeul
>>
>> PS: your link just shows a pin called "Start" in the middle of the
>> Indian Ocean, on Google maps (using Firefox).
>>
>>
>> El mar, 07-06-2011 a las 15:19 +0300, Jaak Laineste escribió:
>>> Hello,.
>>> Pgrouting can find one isoline, this is the result of
>>> driving_distance. This gives number of points, if you connect them
>>> you'll get isoline. If you need many isolines, then you should call it
>>> many times, like for 5,10,20 minutes, for same point(s) etc. It is
>>> sub-optimal this way also, but it is fast, below second for single
>>> iteration, and for most uses sufficient.
>>>
>>>
>>> My recent test with it (isolines from certain point in certain
>>> distances, in KML
>>> format):
>>> http://maps.google.com/?q=http://46.51.131.48/dd/index.php?lat=59.43475%26lon=24.74786%26dist=1,2,3,4,5
>>>
>>>
>>>
>>> Or maybe I misunderstood what exactly do you mean by isoline here?
>>>
>>>
>>> Jaak
>>>
>>>
>>>
>>> On 07.06.2011, at 19:00, pgrouting-users-request at lists.osgeo.org
>>> wrote:
>>>>
>>>> Message: 1
>>>> Date: Tue, 07 Jun 2011 12:37:09 +0200
>>>> From: Mayeul KAUFFMANN<mayeul.kauffmann at jrc.ec.europa.eu>
>>>> Subject: [pgrouting-users] improve performance of isoline
>>>> computation
>>>> To: pgrouting-users at lists.osgeo.org
>>>> Message-ID:<1307443029.10348.130.camel at ISFLXMK2>
>>>> Content-Type: text/plain; CHARSET=US-ASCII
>>>>
>>>> Hi,
>>>>
>>>> 1. I've seen at http://www.pgrouting.org/ that "pgRouting provides
>>>> functions for [...] Driving Distance calculation (Isolines)".
>>>> But I could not find any documentation on this (or I misunderstood
>>>> "isolines")
>>>>
>>>> In the past I have been doing this using pgrouting with this
>>>> iterative
>>>> algorithm (written in bash and allowing parallelism) which is quite
>>>> costly:
>>>> To compute isoline with departure from A, compute travel time
>>>> between A
>>>> and any point of the network.
>>>>
>>>> This is quite similar to this:
>>>> http://underdark.wordpress.com/2011/02/09/creating-catchment-areas-with-pgrouting-and-qgis/
>>>>
>>>>
>>>> http://underdark.wordpress.com/2011/05/13/catchment-areas-with-pgrouting-driving_distance/
>>>>
>>>>
>>>>
>>>> This is costly because some parts of the network get traversed many
>>>> time
>>>> by the algorithm. If point B is between A and C, then once you have
>>>> computed the cost from A to B, you can use this piece of information
>>>> to
>>>> find the shortest path from A to C.
>>>>
>>>>
>>>>
>>>> I searched for documentation here:
>>>> http://www.pgrouting.org/docs/foss4g2010/index.html
>>>>
>>>> Searching on Google:
>>>> site:lists.osgeo.org/pipermail/pgrouting-users/ isolines
>>>> site:lists.osgeo.org/pipermail/pgrouting-dev/ isolines
>>>> gave no result either
>>>>
>>>>
>>>> Are there any other solution to the isoline problem that I'm not
>>>> aware?
>>>>
>>>> 2. Finally, my ultimate goal is as follows:
>>>> given a set of many departure points d1 to d1000, for each of them,
>>>> find
>>>> which of the arrival points (A, B, C, D, E) is the shortest one.
>>>>
>>>> My idea would be to use the following approach, but modified:
>>>> http://underdark.wordpress.com/2011/05/13/catchment-areas-with-pgrouting-driving_distance/
>>>>
>>>>
>>>> with modification as follows: after finding the best path from d1 to
>>>> A,
>>>> if this costs 100, you can search the best path from d1 to B
>>>> stopping
>>>> the search when the cost is larger than 100.
>>>>
>>>> Is any of the two above problems already implemented in compiled
>>>> code,
>>>> or the best I can do is to write my own code based on
>>>> shortest_path() or
>>>> driving_distance() ?
>>>>
>>>> Thanks for any help!!
>>>> Mayeul
>>>>
>>>>
>>>> PS: for those who wonder: this is to study the impact of
>>>> transportation
>>>> disturbance (in countries currently at war) on access to health
>>>> infrastructure, hence: how to go to the closest hospital.
>>>>
>>>> --
>>>> Dr. Mayeul KAUFFMANN, Conflict Specialist
>>>> European Commission, Joint Research Centre (JRC)
>>>> Institute for the Protection and Security of the Citizen (IPSC)
>>>> Global Security and Crisis Management - ISFEREA
>>>> Via E. Fermi 2749 - I-21027 Ispra (VA), ITALY
>>>> Phone: (+39) 033278 5071
>>>> http://isferea.jrc.ec.europa.eu/Staff/Pages/Kauffmann-Mayeul.aspx
>>>>
>>>> (Office: building 26b, 1st floor, room 140. TP: 267)