[pgrouting-dev] APSP Implementation

Sun Dec 19 15:54:27 EST 2010

Hi,

*I am currently trying to implement apsp as follows: *
CREATE OR REPLACE FUNCTION all_pairs_shortest_path(sql text, directed
boolean, has_reverse_cost boolean)
        RETURNS SETOF apsp_result
        AS '$libdir/librouting'
        LANGUAGE 'C' IMMUTABLE STRICT;

Now, I think my boost_apsp() function is working for small input data, and I
want to test if the overall query is working. I have coded apsp.c
accordingly.

I have modified /core/cMakeLists.txt so as to just build apsp and dijkstra
for now:
"ADD_LIBRARY(routing SHARED dijkstra.c apsp.c boost_wrapper.cpp
apsp_boost_wrapper.cpp)"

Here is the output after I run "cmake -DWITH_DD=ON", and then "make":

jay at jay-HP-Compaq-6720s:~/Desktop/pgRouting/pgRouting-pgrouting-7b07040$
make
[ 50%] Built target routing_dd
Scanning dependencies of target routing
[ 62%] Building C object core/src/CMakeFiles/routing.dir/apsp.o
Linking CXX shared library ../../lib/librouting.so
[100%] Built target routing
jay at jay-HP-Compaq-6720s:~/Desktop/pgRouting/pgRouting-pgrouting-7b07040$
sudo make install
[sudo] password for jay:
[ 50%] Built target routing_dd
[100%] Built target routing
Install the project...
-- Install configuration: ""
-- Installing: /usr/lib/postgresql/8.4/lib/librouting.so
-- Installing: /usr/share/postlbs/routing_core.sql
-- Up-to-date: /usr/share/postlbs/routing_core_wrappers.sql
-- Up-to-date: /usr/share/postlbs/routing_topology.sql
-- Up-to-date: /usr/share/postlbs/matching.sql
-- Installing: /usr/lib/postgresql/8.4/lib/librouting_dd.so
-- Installing: /usr/share/postlbs/routing_dd.sql
-- Installing: /usr/share/postlbs/routing_dd_wrappers.sql

I think there were no compilation errors while compiling apsp files. Now,
when i log into postgres and query for shortest_path() on pgrouting-workshop
database, I get the correct results.

*But, query on all_pairs_shortest_path() gives this: *SELECT * from
all_pairs_shortest_path('SELECT gid as
id,source::integer,target::integer,length::double precision as cost from
ways',false,false);
ERROR:  function all_pairs_shortest_path(unknown, boolean, boolean) does not
exist
LINE 1: SELECT * from all_pairs_shortest_path('SELECT gid as id,sour...
HINT:  No function matches the given name and argument types. You might need
to add explicit type casts.

I tried restarting the postgres server too.

*Questions:*
*
*
1. For testing the new function, am I following correct approach?

2. I will try to learn some git commands and upload my source code in the
repository that I have forked here:
https://github.com/jay-mahadeokar/pgrouting, I guess it would be easier for
you guys to provide help and see what is actually going on that way, right?

On Fri, Dec 17, 2010 at 4:48 PM, Daniel Kastl <daniel at georepublic.de> wrote:

> 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
>
> _______________________________________________
> 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/20101220/466323ed/attachment.html