[pgrouting-dev] APSP Implementation

[Daniel Kastl]

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

As Anton mentioned, this can get confusing sometimes. Too many sources and
targets, can be the ones of an edge or of a route.
Any good idea how define names in an easy to understand and clear way is
welcome. This is probably going to become more of an issue as more pgRouting
grows.

@Anton: maybe we should somewhere define a dictionary of terms we use and
what we use them for.
Other thing, I didn't really get your answer how to prevent mixing
source/target ... was there a "not" missing? It wasn't clear to me



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

If I find some time I want to study the CMake manual, too, and see if we can
make some improvements here and there. I think it was also new for Anton at
the time of writing the files, so if you find some possible improvements,
let me know.

There are no "coding standards" defined yet, which would be probably a good
idea when more algorithm will be implemented in the future.
Same as above, if you have some idea, then you can share with us. We're open
for criticism! Otherwise I believe it's sometimes better to have a couple of
algorithms first and then see what could be "standardized" and define them
based on our experience.

Btw., if you want to make use of GitHub, then you can create an account and
fork the pgRouting repository: https://github.com/pgRouting/pgrouting
It will be then easy to apply your changes.

Anton, where will APSP go? To "core" or to "extras"?
Seeing the number of extensions grow, does this structure still work for us?
How do we define what is "core" and what is "extra"?
I think the initial main idea was to provide pgRouting without Gaul and CGAL
dependencies.



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

I think that pgRouting should have unit tests ... but we don't have so far,
which is not so good ;-)
Here is a ticket already:
https://github.com/pgRouting/pgrouting/issues#issue/20
As usual it's a lack of time to work on this.

It's probably better to have some generic testing data than just take OSM
data from the workshop, Anton.
OSM data won't allow us to test all possible functionality some functions
provide.

Daniel



-- 
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/20101208/a41e8eaf/attachment.html