[pgrouting-dev] APSP Implementation
Stephen Woodbridge
woodbri at swoodbridge.com
Sun Dec 19 16:42:06 EST 2010
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
More information about the pgrouting-dev
mailing list