[pgrouting-dev] APSP Implementation

Jay Mahadeokar jai.mahadeokar at gmail.com
Sun Dec 19 17:07:59 EST 2010


Hi Stephen,

Thanks for the quick reply.

I did as you said, and now I can see the function when I do \df.

Now, Im getting following msg:
server closed the connection unexpectedly
 This probably means the server terminated abnormally
before or while processing the request.
The connection to the server was lost. Attempting reset: Failed.

How can I print the errors/ stack traces that are going on in background?
 (I am sorry if this is too naive, but I am doing this kind of debugging for
the first time) Any online documentation/manuals in this regard would really
help.

On Mon, Dec 20, 2010 at 3:12 AM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:

> Hi Jay,
>
> It sounds like you have the correct approach as outlined. I think the only
> step that you missed is that you have to load you wrapper function into the
> database.
>
> psql mydatabase
>
>  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 run your query
>
> The wrappers get loaded because they are in the sql files like:
>
>
> > -- Up-to-date: /usr/share/postlbs/routing_core_wrappers.sql
>
> You could create a new file like:
> routing_extra_wrappers.sql  or
> routing_apsp_wrappers.sql
>
> And have cmake install them, or manually install them like above.
>
> If you areadly did that and you can see you function in the list of
> functions in psql like:
>
> \df+ all_pairs_shortest_path
>
> Then try adding a cast TEXT as shown below:
>
>
> SELECT * from  all_pairs_shortest_path(
>  'SELECT gid as id,source::integer,target::integer,
>     length::double precision as cost from ways'::TEXT,
>     false,false);
>
> -Steve
>
>
> On 12/19/2010 3:54 PM, Jay Mahadeokar wrote:
>
>> 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
>> <mailto: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 <mailto: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
>>            <mailto:daniel.kastl at georepublic.de>
>>            Web: http://georepublic.de <http://georepublic.de/>
>>
>>
>>            _______________________________________________
>>            pgrouting-dev mailing list
>>            pgrouting-dev at lists.osgeo.org
>>            <mailto: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 <mailto:
>> pgrouting-dev at lists.osgeo.org>
>>
>>        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
>>
>>
>>    --
>>    Georepublic UG & Georepublic Japan
>>    eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de
>> >
>>    Web: http://georepublic.de <http://georepublic.de/>
>>
>>    _______________________________________________
>>    pgrouting-dev mailing list
>>    pgrouting-dev at lists.osgeo.org <mailto: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
>>
>
>


-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20101220/3ef1db27/attachment-0001.html


More information about the pgrouting-dev mailing list