[pgrouting-dev] APSP Implementation
Stephen Woodbridge
woodbri at swoodbridge.com
Sun Dec 19 19:47:21 EST 2010
Hi Jay,
I have not done this myself, so you might have to wait for Anton. But
you might check out:
http://www.google.com/#q=postgresql+server+debug
I believe that you need to runt postgresql in single user mode to start
with. Beyond that I think a quick look at the postgresql docs should
indicate how to run this in gdb so you can catch the error.
-Steve
On 12/19/2010 5:07 PM, Jay Mahadeokar wrote:
> 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 <mailto: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>
> <mailto: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>
> <mailto: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>
> <mailto: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>
> <mailto: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>
> <mailto: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>
> <mailto: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>
> <mailto: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
>
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
More information about the pgrouting-dev
mailing list