[pgrouting-dev] APSP Implementation

[Anton Patrushev]

Hi Jay,

> I have run the Boost Floyd_Warshall Algorithm on a small sample graph, and
> it is giving back the distance matrix correctly. I modified the johnsons
> example given in the BGL manual. (Example file attached)
> In Dijkstra, we used the predecessor_map passed as the third argument to the
> boost Dijkstra function extract the path from source to target. I am not
> sure how we can extract paths from the boost warshall algo. (I am not able
> to get the significance of the third parameter that we can pass to the
> function).

For now the distance matrix is great. I didn't look inside Boost's
Floyd Warshall, so can't suggest anything right now.

> For now, can we go ahead and implement the above algo in pgRouting? I am
> thinking of a warshall_wrapper class that would call the above function, and
> the actuall warshall apsp would return distances in form of rows, each row
> having three columns:
> source, target, distance. (We will have nC2 such rows for now..)

Yes, sure. I would call columns source, target, distance to prevent
mixing source and target of edges with source and target of APSP.

> Some queries:
> 1. I have not yet tried modifying the pgRouting source code, and compiling
> other files together with the existing ones. I am completely new to cmake
> and will try and learn how to work with that. From what I have understood,
> every new algorithm that we add to existing set will have a similar flow and
> similar files etc. Is there any doc which can guide as to what configuration
> changes would be needed for adding a new algo (For example we would usually
> add following files: algo.h, algo.cpp, algo.sql, algo_boost_wrapper.cpp
> etc).  (I hope my query is clear)

It is clear, but unfortunately we have no clear instructions, so you
can try to take Dijkstra part as an example. Cmake files are quite
self-explaining, again, you can try to copy entries for Dijkstra.

> 2. Are there any sample test cases/scripts, which were used to test
> dijkstras algo (which can be useful here too)?

You mean sample data? Unfortunately, no. But you can take simple data
sets from our tutorials and workshops here -
http://www.pgrouting.org/docs/tutorials.html


Anton.