[pgrouting-dev] APSP Implementation

Jay Mahadeokar jai.mahadeokar at gmail.com
Wed Dec 1 18:21:01 EST 2010


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

Hey.. Again, during  step 3 above, if we build the path matrix along with
the distance matrix for Warshall Algo, we can use that to extract all paths,
we will not need any more queries to database. We also need not hold on to
the graph! And the overall time is still O(n^3)  :)



>
>
>  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.
>
>
I guess assuming 1 sec per route is too slow for modern processors! If you
are including the database query latency, then again Path Matrix will make
sure we need to query database only once, so the rest of the work should be
fast.



> 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.
>
>
Nice Application! I am not sure what is complexity of your algorithm. But if
you want to compute actual paths before feeding the algo, I guess the number
of nodes in the path will increase by a big factor which will slow down APSP
significantly. (You may just consider Highways to get around this, could
discuss this on a separate topic!)

>
>  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
>>
>
> _______________________________________________
> 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/5ad5a032/attachment-0001.html


More information about the pgrouting-dev mailing list