[pgrouting-dev] APSP Implementation

[Jay Mahadeokar]

On Thu, Dec 2, 2010 at 10:54 AM, Daniel Kastl <daniel at georepublic.de> wrote:

> Let me make some proposal how the APSP function could look like.
> (I mostly copy from Dijkstra:
> http://www.pgrouting.org/docs/1.x/dijkstra.html)
>
> CREATE OR REPLACE FUNCTION apsp(
>                                 *sql* text,
>                                 *n_ids* text,
>                                 *m_ids* text,
>                                 directed boolean,
>                                 has_reverse_cost boolean)
>         RETURNS SETOF <???>
>
> With *sql* as ...
>
> SELECT id, source, target, cost FROM edge_table
>
> ... like for Dijkstra, and *n_ids/m_ids* as ...
>
> SELECT id FROM edge_table
>
> to select the relevant points for the n-m distance matrix.
>
> With a select (instead of a list of ID's you can also select relevant
> points by attribute, update timestamp or whatever.
>
> I can also think of an APSP that calculates all distances from 1 point to n
> points only. That's why I added n_ids/m_ids.
> In that case you could update an existing distance matrix (that you stored
> in some table for example) if only one or a few points changed.
>
>
Hey.. The dijextras algo should be able to provide solution for single
source shortest paths to all other points (1 to n points). The boost doc
here:
http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html
states that: "If you provide a distance property map through the
distance_map() parameter then the shortest distance from the source vertex
to every other vertex in the graph will be recorded in the distance map.
Also you can record the shortest paths tree in a predecessor map: for each
vertex *u in V*, *p[u]* will be the predecessor of *u* in the shortest paths
tree "

So, I think there is no need for doing APSP / Warshall O(n^3) time for this
purpose, Dijextra will do that in O(m+nlog n). I am not fully aware of the
pgRouting dijextra implementation, does it provide above functionality?


*One more thing:* Can we have a wiki page or something like that where we
can put up our ideas, and we can keep on modifying the draft as the ideas
are refined? I guess there are too many ideas in this thread and I am
finding some difficulty to keep track of all of them all..  Just a
suggestion :)



>
>> I think the library should ensure that when you make a query it reads the
>> network data available at that time. If the query for processing a huge
>> distance matrix takes one hour for example, but makes steadily new requests
>> to the database, it could happen that some attributes change over time.
>> Whether this is problematic for an application or not depends on the
>> application. In most cases it probably isn't, that's true. But pgRouting
>> isn't limited to road networks, so who knows what kind of applications will
>> make use of it.
>>
>>
>>
>>>     * It might be slower to later run single shortest path queries again
>>>>      independently
>>>>
>>>
>>> It would be interesting to enhance our single shortest path to be able to
>>> extract multiple single shortest paths based on a single graph build. So
>>> input might be something like
>>>
>>
>> This would be the same as k-Shortest Path, right?
>> http://www.pgrouting.org/rfc/rfc-04.html
>> <http://www.pgrouting.org/rfc/rfc-04.html>
>>
>> Daniel
>>
>>
>>
>> --
>> Georepublic UG & Georepublic Japan
>> eMail: daniel.kastl at georepublic.de
>> Web: http://georepublic.de
>>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> Web: http://georepublic.de
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>


-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20101202/d34f346a/attachment.html