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@lists.osgeo.org
>>> wrote:
>>>>
>>>> Message: 1
>>>> Date: Tue, 07 Jun 2011 12:37:09 +0200
>>>> From: Mayeul KAUFFMANN<mayeul.kauffmann@jrc.ec.europa.eu>
>>>> Subject: [pgrouting-users] improve performance of isoline
>>>> computation
>>>> To: pgrouting-users@lists.osgeo.org
>>>> Message-ID:<1307443029.10348.130.camel@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
(Office: building 26b, 1st floor, room 140. TP: 267)