[pgrouting-dev] APSP Implementation

dkastl · December 2, 2010, 8:29am

Hey… The dijextras algo should be able to provide solution for single source shortest paths to all other points (1 to n points). The boost doc here: http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html states that: "If you provide a distance property map through the distance_map() parameter then the shortest distance from the source vertex to every other vertex in the graph will be recorded in the distance map. Also you can record the shortest paths tree in a predecessor map: for each vertex u in V, p[u] will be the predecessor of u in the shortest paths tree "

So, I think there is no need for doing APSP / Warshall O(n^3) time for this purpose, Dijextra will do that in O(m+nlog n). I am not fully aware of the pgRouting dijextra implementation, does it provide above functionality?

Well, for the case 1:n you’re right. This would be Dijkstra.
I thought about cases like 2:n or more … just I thought what if n and m are not the same.
But I can’t say this is possible with Warshall or any other algorithm. It’s just some brainstorming

One more thing: Can we have a wiki page or something like that where we can put up our ideas, and we can keep on modifying the draft as the ideas are refined? I guess there are too many ideas in this thread and I am finding some difficulty to keep track of all of them all… Just a suggestion

True. This thread is turning to be too long already.

I enabled the Wiki addon for the pgRouting repository on GitHub: https://github.com/pgRouting/pgrouting/wiki
Let me know if you can access. Maybe you need some user account for GitHub and maybe I have to give you permissions … I haven’t tried it yet.

Daniel

Jay_Mahadeokar · December 2, 2010, 9:05am

Hi,

I created a wiki page for APSP here: https://github.com/pgRouting/pgrouting/wiki/APSP

I have tried to put down some ideas already discussed on this thread. Please go on and modify the page if I have missed something. Again, I dont have experience with standard docs, so page would need a lot of restructuring I guess…

We can put up any new idea there and discuss it here so that the overall draft keeps getting refined.

On Thu, Dec 2, 2010 at 1:59 PM, Daniel Kastl <daniel@georepublic.de> wrote:

Hey… The dijextras algo should be able to provide solution for single source shortest paths to all other points (1 to n points). The boost doc here: http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html states that: "If you provide a distance property map through the distance_map() parameter then the shortest distance from the source vertex to every other vertex in the graph will be recorded in the distance map. Also you can record the shortest paths tree in a predecessor map: for each vertex u in V, p[u] will be the predecessor of u in the shortest paths tree "

So, I think there is no need for doing APSP / Warshall O(n^3) time for this purpose, Dijextra will do that in O(m+nlog n). I am not fully aware of the pgRouting dijextra implementation, does it provide above functionality?

Well, for the case 1:n you’re right. This would be Dijkstra.
I thought about cases like 2:n or more … just I thought what if n and m are not the same.
But I can’t say this is possible with Warshall or any other algorithm. It’s just some brainstorming

One more thing: Can we have a wiki page or something like that where we can put up our ideas, and we can keep on modifying the draft as the ideas are refined? I guess there are too many ideas in this thread and I am finding some difficulty to keep track of all of them all… Just a suggestion

True. This thread is turning to be too long already.

I enabled the Wiki addon for the pgRouting repository on GitHub: https://github.com/pgRouting/pgrouting/wiki
Let me know if you can access. Maybe you need some user account for GitHub and maybe I have to give you permissions … I haven’t tried it yet.

Daniel

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

dkastl · December 3, 2010, 2:44am

Hi Jay,

Thank you for adding the Wiki page.
So there was no restriction? No permission problem to add or edit a page? That’s fine then.

I formatted the page a little bit for readability (no content changes).
Anyone else who wants to make some additions or changes, please go ahead!

Daniel

2010/12/2 Jay Mahadeokar <jai.mahadeokar@gmail.com>

Hi,

I created a wiki page for APSP here: https://github.com/pgRouting/pgrouting/wiki/APSP

I have tried to put down some ideas already discussed on this thread. Please go on and modify the page if I have missed something. Again, I dont have experience with standard docs, so page would need a lot of restructuring I guess…

We can put up any new idea there and discuss it here so that the overall draft keeps getting refined.

On Thu, Dec 2, 2010 at 1:59 PM, Daniel Kastl <daniel@georepublic.de> wrote:

Hey… The dijextras algo should be able to provide solution for single source shortest paths to all other points (1 to n points). The boost doc here: http://www.cs.brown.edu/~jwicks/boost/libs/graph/doc/dijkstra_shortest_paths.html states that: "If you provide a distance property map through the distance_map() parameter then the shortest distance from the source vertex to every other vertex in the graph will be recorded in the distance map. Also you can record the shortest paths tree in a predecessor map: for each vertex u in V, p[u] will be the predecessor of u in the shortest paths tree "

So, I think there is no need for doing APSP / Warshall O(n^3) time for this purpose, Dijextra will do that in O(m+nlog n). I am not fully aware of the pgRouting dijextra implementation, does it provide above functionality?

Well, for the case 1:n you’re right. This would be Dijkstra.
I thought about cases like 2:n or more … just I thought what if n and m are not the same.
But I can’t say this is possible with Warshall or any other algorithm. It’s just some brainstorming

One more thing: Can we have a wiki page or something like that where we can put up our ideas, and we can keep on modifying the draft as the ideas are refined? I guess there are too many ideas in this thread and I am finding some difficulty to keep track of all of them all… Just a suggestion

True. This thread is turning to be too long already.

I enabled the Wiki addon for the pgRouting repository on GitHub: https://github.com/pgRouting/pgrouting/wiki
Let me know if you can access. Maybe you need some user account for GitHub and maybe I have to give you permissions … I haven’t tried it yet.

Daniel

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Anton_Patrushev · December 6, 2010, 1:25am

Hi Jay,

Thanks for the wiki page!
I think we should start with Floyd-Warshall algorithm from Boost.
Having difficult part done we can concentrate on function interface,
input-output format etc.
Once it is settled down, we can start thinking about algorithm
improvements and different use cases.

Anton.

Jay_Mahadeokar · December 8, 2010, 1:42am

Hi,

On Mon, Dec 6, 2010 at 6:55 AM, Anton Patrushev <anton.patrushev@georepublic.de> wrote:

Hi Jay,

Thanks for the wiki page!
I think we should start with Floyd-Warshall algorithm from Boost.

I have run the Boost Floyd_Warshall Algorithm on a small sample graph, and it is giving back the distance matrix correctly. I modified the johnsons example given in the BGL manual. (Example file attached)

In Dijkstra, we used the predecessor_map passed as the third argument to the boost Dijkstra function extract the path from source to target. I am not sure how we can extract paths from the boost warshall algo. (I am not able to get the significance of the third parameter that we can pass to the function).

Having difficult part done we can concentrate on function interface,
input-output format etc.

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…)

Some queries:

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)
Are there any sample test cases/scripts, which were used to test dijkstras algo (which can be useful here too)?

Once it is settled down, we can start thinking about algorithm
improvements and different use cases.

Anton.

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

warshall.cpp (1.04 KB)

Anton_Patrushev · December 8, 2010, 2:48am

Hi Jay,

I have run the Boost Floyd_Warshall Algorithm on a small sample graph, and
it is giving back the distance matrix correctly. I modified the johnsons
example given in the BGL manual. (Example file attached)
In Dijkstra, we used the predecessor_map passed as the third argument to the
boost Dijkstra function extract the path from source to target. I am not
sure how we can extract paths from the boost warshall algo. (I am not able
to get the significance of the third parameter that we can pass to the
function).

For now the distance matrix is great. I didn't look inside Boost's
Floyd Warshall, so can't suggest anything right now.

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..)

Yes, sure. I would call columns source, target, distance to prevent
mixing source and target of edges with source and target of APSP.

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)

It is clear, but unfortunately we have no clear instructions, so you
can try to take Dijkstra part as an example. Cmake files are quite
self-explaining, again, you can try to copy entries for Dijkstra.

2. Are there any sample test cases/scripts, which were used to test
dijkstras algo (which can be useful here too)?

You mean sample data? Unfortunately, no. But you can take simple data
sets from our tutorials and workshops here -
http://www.pgrouting.org/docs/tutorials.html

Anton.

dkastl · December 8, 2010, 8:42am

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:

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.

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@georepublic.de
Web: http://georepublic.de

Jay_Mahadeokar · December 17, 2010, 3:30am

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@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:

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.

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@georepublic.de
Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

dkastl · December 17, 2010, 11:18am

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@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:

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.

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@georepublic.de
Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Jay_Mahadeokar · December 19, 2010, 8:54pm

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@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@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:

For testing the new function, am I following correct approach?
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@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@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:

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.

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@georepublic.de
Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · December 19, 2010, 9:42pm

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@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@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@georepublic.de
<mailto:daniel@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@georepublic.de <mailto:daniel@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@georepublic.de
            <mailto:daniel.kastl@georepublic.de>
            Web: http://georepublic.de/>

            _______________________________________________
            pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

        --
        Regards,
        -Jay Mahadeokar

        _______________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

    --
    Georepublic UG & Georepublic Japan
    eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
    Web: http://georepublic.de/>

    _______________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Regards,
-Jay Mahadeokar

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Jay_Mahadeokar · December 19, 2010, 10:07pm

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@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@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@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:
*
*

For testing the new function, am I following correct approach?

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@georepublic.de

mailto:[daniel@georepublic.de](mailto:daniel@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@georepublic.de mailto:[daniel@georepublic.de](mailto:daniel@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:

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.

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@georepublic.de

mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de <http://georepublic.de/>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org

mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list

pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan

eMail: daniel.kastl@georepublic.de mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de <http://georepublic.de/>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · December 20, 2010, 12:47am

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@swoodbridge.com <mailto:woodbri@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@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@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@georepublic.de <mailto:daniel@georepublic.de>
        <mailto:daniel@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@georepublic.de <mailto:daniel@georepublic.de>
        <mailto:daniel@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@georepublic.de
        <mailto:daniel.kastl@georepublic.de>
        <mailto:daniel.kastl@georepublic.de
        <mailto:daniel.kastl@georepublic.de>>
                    Web: http://georepublic.de/>

                    _______________________________________________
                    pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>

        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

                --
                Regards,
                -Jay Mahadeokar

                _______________________________________________
                pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>

        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

            --
            Georepublic UG & Georepublic Japan
            eMail: daniel.kastl@georepublic.de
        <mailto:daniel.kastl@georepublic.de>
        <mailto:daniel.kastl@georepublic.de
        <mailto:daniel.kastl@georepublic.de>>
            Web: http://georepublic.de/>

            _______________________________________________
            pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>

        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

        --
        Regards,
        -Jay Mahadeokar

        _______________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Regards,
-Jay Mahadeokar

Anton_Patrushev · January 12, 2011, 6:15am

Hi Jay,

Sorry for such late reply - some parts of our world still live offline

It is quite difficult to debug PostgreSQL stored procedures. I use
debug messages (NOTICE command) in pl/pgsql and same approach for C
(good old print). It is possible to debug it with gdb and Valgrind
(try to google for some tutorials - there must be few of them).

Anton.

Jay_Mahadeokar · January 24, 2011, 4:54pm

Hi Anton,

Again sorry for late reply. My college restarted, I got busy with some academic work. Anyways, I looked back again into the code and the NOTICE commands helped a lot. The problem was that boost warshall algorithm expects the vertex ids in sequence starting from 0 (according to the example in their docs) and the node ids in database were random.I worked around it and I am now able to see output.

Another problem is that the warshall algorithm expects distances between nodes to be integers (again according to tutorial). So, I have converted the float8 cost values to integers by multiplying by 10000000 as a temporary fix, since all cost values in ways table seem to be much less than 1.

Can you suggest any better way of handling this? (May be a deeper look in boost documentation can help!)

Also, there are negative costs to edges. How should we handle that scenario?

I will try and commit the code in the the gitHub repo i have forked here https://github.com/jay-mahadeokar/pgrouting in next few days. (Still not learned git commands! )

Regards,

On Wed, Jan 12, 2011 at 11:45 AM, Anton Patrushev <anton.patrushev@georepublic.de> wrote:

Hi Jay,

Sorry for such late reply - some parts of our world still live offline

It is quite difficult to debug PostgreSQL stored procedures. I use
debug messages (NOTICE command) in pl/pgsql and same approach for C
(good old print). It is possible to debug it with gdb and Valgrind
(try to google for some tutorials - there must be few of them).

Anton.

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Anton_Patrushev · January 26, 2011, 3:30am

Hi Jay,

Sounds great already!

As far as I remember, distance type in DistanceMatrix depends on the
way you initialize DistanceMatrix type template - you need to set
proper value type of your weight map.

Anton.

Jay_Mahadeokar · January 28, 2011, 12:04pm

Hi,

I have committed to https://github.com/jay-mahadeokar/pgrouting. Its just a initial draft, will look into in again for optimising and making changes as suggested by Anton. The current code should serve as the basic template for apsp I guess.

I have modified the /core/src/CMakeLists.txt file such that it only compiles dijekstra and apsp. Please look into it and change as it suits you before compiling.

After installing, you may try and run queries like this: SELECT * from all_pairs_shortest_path(‘SELECT gid as id,source::integer,target::integer,length::double precision as cost from ways where source in (169,170,171,168)’::TEXT,false,false);

Note - I have set Debug ON. Put it to off for faster outputs.

TODO List -

How to deal with negative edge weights? I am finding negative values in some output. I have still not yet looked into it thoroughly.
Changing the Distance Matrix type so that float8 is supported.
Commenting the code.

On Wed, Jan 26, 2011 at 9:00 AM, Anton Patrushev <anton.patrushev@georepublic.de> wrote:

Hi Jay,

Sounds great already!

As far as I remember, distance type in DistanceMatrix depends on the
way you initialize DistanceMatrix type template - you need to set
proper value type of your weight map.

Anton.

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Anton_Patrushev · January 29, 2011, 7:01am

Hi Jay,

Splendid! Great work!

What about negative costs - I think there shouldn't be any negative
costs in distance matrix. According to our convention, edges with
negative costs are not included in a graph for shortest path
calculation in Dijkstra, A* and Shooting*.

Anton.

Jay_Mahadeokar · August 10, 2011, 5:17pm

Hi,

Waking up a sleeping thread after a long time!

Well, I have corrected the problem with float values in distance matrix and negative costs. So, the APSP algorithm seems to be working fine now.

Updated the gsoc-tdsp branch with the code[1].

I also wrote a tutorial to get started and try out the APSP algorithm using pgRouting[2].

Any inputs are welcome!

[1] https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
[2] https://github.com/pgRouting/pgrouting/wiki/APSP

On Sat, Jan 29, 2011 at 12:31 PM, Anton Patrushev <anton.patrushev@georepublic.de> wrote:

Hi Jay,

Splendid! Great work!

What about negative costs - I think there shouldn’t be any negative
costs in distance matrix. According to our convention, edges with
negative costs are not included in a graph for shortest path
calculation in Dijkstra, A* and Shooting*.

Anton.

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar