[pgrouting-dev] APSP Implementation
Stephen Woodbridge
woodbri at swoodbridge.com
Wed Dec 1 10:36:10 EST 2010
On 12/1/2010 9:08 AM, Jay Mahadeokar wrote:
> Hi,
>
> I am Jay Mahadeokar, Computer Science MTech Student at Indian Institute
> of Technology, Kanpur.
>
> I am interested in contributing to pgRouting and was looking at APSP
> implementation. I have discussed this with Mr. Daniel Kastl and we
> thought it would be better to float the ideas on the dev mailing list.
Greeting Jay,
I think this would be an excellent addition to pgRouting. I have been
interested in seeing an algorithm like this added, as it is a good
precursor to feed data to TSP problem using a simulated annealing algorithm.
> For the APSP implementation, I read the boost documentation, and it has
> implemented APSP using Johnsons algorithm as well as Warshall's
> Algorithm. Which one should we look at? To implement it for pgRouting,
> we will need to code a boost_wrapper function (which will call the
> actual boost apsp function) and one outer APSP function which will use
> the executor/SPI to query database and call the wrapper (similar to the
> dijkestra's implementation). Please correct me if I am wrong.
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.
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
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
> It would also be helpful to come up with a concrete prototype for the
> function. The initial RFC is drafted here:
> http://www.pgrouting.org/rfc/rfc-03.html
>
> Since I am new to this community, I would like to know the development
> tools and conventions used.
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list