[pgrouting-dev] APSP Implementation

[Stephen Woodbridge]

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