[pgrouting-dev] APSP Implementation

[Jay Mahadeokar]

Hi Stephen,

Thanks for the quick input. Some queries in-line.Greeting Jay,


> It looks like Johnsons algorithm might be a little faster on sparse graphs,
> but I'm not sure if you can extract the path between the pairs if you need
> that and I think that would be a valuable component to the algorithm, so the
> Warshall Algorithm might be better if we support that extraction capability.
>
> I'm not sure how these algorithms work from the point of view that you have
> to extract ALL pairs from the graph, or whether you can just extract
> selected pairs at a reduced cost. The use case for this would be that you
> have 20 locations that you are interested in and you want the APSP between
> those 20 locations and not the whole graph.
>
>
Notations that I have used:
m - edges.
n - vertices.
v - vertices in subset.

Our postgres map data constitutes a planar graph right? If so, then the
number of edges m = O(n). In that case, the dijextra Shortest path algorithm
will take O(m + n log n) that is O(n logn) time.

Now, if we want to find APSP between small subset of vertices v, we can call
dijextra v^2 times to get total complexity O(v^2* n log n). We will have a
good bound until (v^2 log n) < n^2. I guess this will also return the paths
between vertices.

When (v^2 log n) > n^2 we can use Warshall algo. Extracting paths will be
complicated task.


> I think some thought needs to go into:
>
> 1. what are the results? just a V^2 table of costs?
>
> 2. can we extract the paths? In pgRouting, this has some additional
> implications beyond is it physically possible to extract paths from the
> algorithm.
>  a. typically queries do not store results, they only return sets
>  b. extracting paths, implies computing assembling a graph, computing the
> results and holding the results for additional queries against them to
> extract paths.
>  c. while this is potentially possible using temp tables, we do not
> currently do that
>
>
I did not properly understand point b above.

I am not sure if the boost implementation of Warshall returns a path matrix,
http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/floyd_warshall_shortest.html
says that it will just return the distance matrix.

In theory, we can simultaneously create a n^2 path matrix along with the
distance matrix and use that to extract paths. Pseudo code is present here:
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm. So, if we
want to build the path matrix, we need to code Warshall from scratch, using
maybe boost data structures.

If we have vertex ids of whole graph, the path matrix is sufficient to
extract all paths (extracting one path will take O(n) time), and I think
there is no need for additional queries to database.

Please correct me if I am missing something.

Anyway, these are some things to start a discussion and provoke some
> thoughts. I do not want to grow the scope of this project to the point that
> it is problematic, so we should focus on what can be done and plan for
> future additions if they are needed.
>
> I look forward to working with you. Thank you for your interest in
> pgRouting.
>
> Best regards,
>  -Steve W
> _______________________________________________
> 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/4d9893b9/attachment.html