[pgrouting-dev] APSP Implementation

[Daniel Kastl]

Hi Jay,

Thank you for giving us some updates!
Anton traveled to freezing cold Siberia yesterday and it could take some
days for him to defrost ;-)
So maybe it will a while until he can answer.

I will try to take a look the next days and see if I can give some advice,
but probably it's better to hear Anton.

Daniel




> *Some Questions:*
>
> Now, I need to code apsp.c which will retrieve the edges / nodes from
> postgres database and call the above function. The result will be returned
> as apsp_result.
>
> For dijkestra, we have the following query format:
> SELECT gid, source, target, cost FROM edge_table
>
> For, apsp will the query format remain same?
>
> Or do we take the vertices(in form of points) as input separately, in some
> other format? One application of this might be when a user will select a set
> of points on map and call apsp on those points.


>
>
> On Wed, Dec 8, 2010 at 2:12 PM, Daniel Kastl <daniel at georepublic.de>wrote:
>
>>
>>>> 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
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> 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
>
>


-- 
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/20101217/4d8b31ff/attachment-0001.html