[pgrouting-dev] APSP Implementation
Daniel Kastl
daniel at georepublic.de
Wed Dec 1 20:40:00 EST 2010
Hi Jay,
First of all I want to say welcome to the community and that it's great you
want to join development of pgRouting!
To others on the list I want to say, that Jay contacted me already a few
weeks ago asking for the possibility and conditions to participate in GSoC
2011 and do some contribution to pgRouting. I really appreciate that Jay
contacted us so much in advance and I'm glad that he wants to bring in his
skills and contribute to the project.
Well, Anton knows a lot better about the internals how pgRouting works. My
comments won't be very technical.
I mostly follow the discussion with interest and just wanted to add a few
remarks:
Distance matrix:
I think the current problem is, that for calculating a distance matrix you
would make a huge amount of single pgRouting shortest path queries. Each of
these queries would involve to select a bounding box, load the data and find
the shortest path. That is not very efficient and takes too much time for
many points. Maybe it doesn't need to be a second per query but still too
slow.
With APSP you would just make one bounding box select and load the data to
memory once, where you do then the calculation of all paths you need. This
should be a lot faster, right? And it would also ensure that all paths are
calculated based on the same road network status at a the time of the select
by the way.
TSP
TSP currently doesn't calculate a matrix with real distances, but APSP would
make this possible then.
The new DARP solver takes as a third parameter a distance matrix, so it
would be another function that would have a huge benefit from a APSP
function. I think TSP could be rewritten in a similar way as DARP to be able
to chose the way you want to calculate the distance matrix.
I think in general we also need to talk about
- which parameters we want to pass to the APSP function
- how the result of the function should look like
pgRouting's speciality is that you can make SQL statements be a parameter
and also can later post-process your result in a SQL query.
Anton, this is probably the part someone new to PostgreSQL/PostGIS/pgRouting
needs some advice.
Hope this makes sense.
Daniel
2010/12/2 Stephen Woodbridge <woodbri at swoodbridge.com>
> Jay,
>
> Sounds like you have a good handle on all the pieces to this problem.
> What do you need to get started :)
>
> -Steve
>
>
> On 12/1/2010 6:21 PM, Jay Mahadeokar wrote:
>
>> 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>
>> <mailto: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 <mailto:
>> pgrouting-dev at lists.osgeo.org>
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
>> _______________________________________________
>> 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
>
--
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/1861f13d/attachment-0001.html
More information about the pgrouting-dev
mailing list