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

Mayeul KAUFFMANN mayeul.kauffmann at jrc.ec.europa.eu
Wed Jun 8 04:13:00 EDT 2011 

Hi Steve,
Thanks a lot for you answer!
If I understand you correctly, what you are doing is not fully
implemented in current pgRouting code, right?
If so, do you have plan to share a working code?
(Sorry, C is not my comfort zone 8-| )
Ideally, a full tutorial based on some available data (say for instance
monaco.osm from http://download.geofabrik.de/osm/europe/monaco.osm.bz2 )
but I understand this is quite some work.

Anyway, the theory was useful, thanks a lot!

Mayeul

El mié, 08-06-2011 a las 00:33 -0400, Stephen Woodbridge escribió:
> 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)
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users

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

More information about the Pgrouting-users mailing list