[pgrouting-dev] APSP Implementation

Wed Dec 1 16:34:08 EST 2010

On 12/1/2010 3:16 PM, Jay Mahadeokar wrote:
> 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.

Yes, I also thought of this point, but did not put complexity equations 
to the problem. I am glad you did.

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

OK, I will try to explain. Typically the process of running a pgRouting 
query follows something along this pseudo code:

1. select a subset of all node that we think will be enough to solve our 
problem. This is done via a bounding box of the start and end nodes inw 
question and expanded somewhat in case the route wanders out of the 
bounding box.

2. these nodes and the edges connected to them are built into a boost graph

3. the boost graph is solved

4. the results are return to the SQL caller as a set of database records.

5. the boost graph is destroyed

So basically one input, one process, one output. Nothing is saved. If on 
the other hand we had a process like:

1. build graph
2. solve graph
3. return matrix of distances
4. hold onto graph because these might be addition requests the need the 
matrix
5. request path A-B from graph
6. request path D-H from graph
7. request ...
8. we are done with the graph so destroy it

Which is my assumption that we would need to do to extract paths, then 
we do not have a paradigm for this in SQL.

Now we may not need to do that, but I was assuming that there was 
information in the graph that was easy to extract about the paths that 
gave the distance returned in the distance matrix.

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

I guess this is up to the use cases for this and maybe we should ask 
others to chime in based on their needs.

I think this really depends on the number of nodes that a user needs to 
work with. If you assume asymmetric directed graph, the you need to 
compute n^2 distances. for small say n<20 that is 400 routes and if at 1 
sec per route it takes 6.67 minutes; n=100 it takes about 2.78 hours.

My use case would be to feed the results into TSP solver to order the 
nodes, then to extract the routes between the ordered nodes. I have used 
simulated annealing to solve TSP very fast.

http://imaptools.com/cgi-bin/tsp.cgi

Copy and paste the cities into the text area and compute the TSP. This 
demo application geocodes all the cities and comput the straight line 
distance between them and then solves the TSP problem. It would really 
be grate to compute the network paths before solving the TSP.

I know pgRouting has a TSP solver, but it requires the CGAL package I 
think which is hard to find and build on many systems.

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

I saw the path extraction code in the wiki page , but I need to go back 
over it in more detail.

Best regards,
   -Steve W

> 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 <mailto:pgrouting-dev at lists.osgeo.org>
>     http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev