[pgrouting-dev] APSP Implementation

[Daniel Kastl]

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.

One big question is what to return as a result.
And another question is if it will be possible to chose between Dijkstra,
A-Star or Shooting*.

Daniel


2010/12/2 Daniel Kastl <daniel at georepublic.de>

>
>>> I think there will be both cases. DARP/TSP might only need the matrix at
>>> first. But when you got your optimized tour result you had to run again
>>> the shortest path search to retrieve a path, which causes two problems:
>>>
>>>    * The network (conditions) might have changed if you run those path
>>>      queries later.
>>>
>>
>> I guess this assumes the you are getting live feed data for traffic or
>> something like that. What are you think here? Also be aware that the
>> algorithms can select any of equal distance alternatives and the later if
>> you single shortest path it might pick a different path, which may or may
>> not be problematic.
>>
>>
> I actually don't assume live feed data but the fact that pgRouting keeps
> the network in a database and it's possible to change attributes for
> example, that are part of your cost parameter, at any time. Or maybe road
> links become unavailable during a long APSP query.
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20101202/79ff75a3/attachment.html