[pgrouting-dev] APSP Implementation

[Jay Mahadeokar]

Hi,

*A quick update:*

I have coded apsp.h, apsp.c and apsp_boost_wrapper.cpp
The apsp_boost function has following prototype:

int
boost_apsp(edge_t *edges, unsigned int edge_count, const int node_count,
           bool directed, bool has_reverse_cost,
           apsp_element_t **pair, int *pair_count, char **err_msg);

apsp_element is on similar lines to path_element in dijkestra:
typedef struct apsp_element
{
    int src_vertex_id;
    int dest_vertex_id;
    float8 cost;

} apsp_element_t;

It has a corresponding apsp_result in routing_core.sql

Above function seems to be working for small static input data and returns
the apsp_element pairs in the desired format.

*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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20101217/8745c066/attachment.html