The routing plugins deals with the pgRouting Postgresql extension allowing to perform, among several algorithms, computation of the shortest path between two nodes of a graph. This plugin provides a graphical user interface to query a Postgresql/PostGiS database with pgRouting functions installed on it.
Extended documentation on pgRouting functions can be found at the pgRouting website.
The demo_plugins demonstration shows an example of the routing plugin.
This documentation details how to install pgRouting on a PostGIS-enabled database and how to load demo data to be used in the demo_plugins project.
Before installing the pgRouting extension, a sample PostGIS database have to be created, as explained in the installation manual: Chapter 1, Installation.
-
Install the PgRouting PostgreSQL module.
Note
To do so,
- Download pgRouting from http://pgrouting.postlbs.org/ and follow install instruction. Mac users can find a version here: http://www.kyngchaos.com/software/unixport/postgres or find some basic compilation instructions (in French), here: http://www.davidgis.fr/documentation/win32/html/apa.html
-
Execute the routing.sql file to install the functions in your database by typing:
$ psql -d demo_plugins -f routing.sql
-
If you have PostGIS installed, you should launch routing_postgis.sql :
$ psql -d demo_plugins -f routing_postgis.sql
-
Import Europe road geodata in PostGIS, create its graph structure and configure plugin routing database. To do so, simply execute the demo_routing.sql file, located in the
<CARTOWEB_HOME>/projects/demoPlugins/server_conf/sql
directory.Note
These steps are detailed in the next section.
-
Edit the
cartoweb3/projects/demoPlugins/demo.properties
file. and uncomment the line beginning with ;ROUTING_PLUGINS -
Execute
cw3setup.php
. file, with the --config-from-file option as described in the previous chapter.
The routing module is a set of functions that compute a shortest path from a set of edges and vertices. Some functions are provided for importing data from geometric tables, and for generating results as geometries.
Note
For more information on these functions, you can have a look at the pgRouting documentation: http://pgrouting.postlbs.org/wiki/pgRoutingDocs.
This section explains the main steps to integrate the routing fonctionnalities in a custom application. We describe the steps followed to install the routing demo. To make short, we used an Europe roads shapefile, imported it in PostGIS, generated the graph tables and configured files to suggest a search of the shortest path between two European towns.
Note
The following chapters describe steps necessary to build a graph structure from shapefiles. It is not
necessary to execute these commands if the demo_routing.sql file
(<CARTOWEB_HOME>/projects/demoPlugins/server_conf/sql
)
was loaded into the demo_plugins database. This file already installs all the routing structure.
$ shp2pgsql -I roadl.shp roads_europe > /tmp/roadl.sql $ psql -d demo_plugins -f /tmp/roadl.sql # Only lauch the following commmands if you did not import the town table already $ shp2pgsql -I mispopp.shp town > /tmp/town.sql $ psql -d demo_plugins -f /tmp/town.sql
The first step is to add needed columns to the table roads_europe. To do so, you can type:
$ ALTER TABLE roads_europe ADD COLUMN source_id int; $ ALTER TABLE roads_europe ADD COLUMN target_id int; $ ALTER TABLE roads_europe ADD COLUMN edge_id int; -- next line is to work around a pgRouting bug in update_cost_from_distance (fixed in latest CVS) $ ALTER TABLE roads_europe RENAME id TO id_old;
You can then fill the columns source_id and target_id with the "assign_vertex_id" function.
$ SELECT assign_vertex_id('roads_europe', 1);
Here is the content of the roads_europe table:
$ SELECT gid, source_id, target_id, edge_id, AStext(the_geom) FROM roads_europe limit 3; gid | source_id | target_id | edge_id | AStext -------+-----------+-----------+---------+---------------------------------------------- 13115 | 11051 | 11099 | 14 | MULTILINESTRING((1062096.06 4861316.234,...)) 12869 | 10918 | 10916 | 267 | MULTILINESTRING((250681.597 4779596.532,...)) 12868 | 10918 | 10913 | 268 | MULTILINESTRING((250681.597 4779596.532,...)) (3 lignes)
But if the data quality is poor, you need to delete the duplicates edges (they have the same source-target pairs of vertices). For example, to check that you have duplicated edges, you can type:
$ SELECT * FROM (SELECT source_id, target_id, count(*) AS c FROM roads_europe group by source_id, target_id order by c) AS foo where foo.c = 2;
If there is duplicated edges, to delete one of two rows, you can type:
$ CREATE TABLE doublons AS SELECT * FROM roads_europe WHERE gid in (SELECT gid FROM (SELECT DISTINCT on (source_id, target_id) source_id, gid FROM roads_europe) AS doublon); $ DELETE FROM roads_europe; $ INSERT INTO roads_europe (SELECT * FROM doublons); $ DROP TABLE doublons;
The following step is to create and fill the edges and vertices tables of the resulting graph. To do so, you can use "create_graph_tables" function.
$ SELECT create_graph_tables('roads_europe', 'int4');
SELECT * FROM roads_europe_edges LIMIT 3; id | source | target | cost | reverse_cost ----+--------+--------+------+-------------- 1 | 1 | 2 | | 2 | 3 | 3 | | 4 | 2 | 2 | | (3 rows)
We can see that it contains NULL values for the cost column. The function update_cost_from_distance can update the cost column with the distance of the lines contained in the geometry table, attached to each edge:
$ SELECT update_cost_from_distance('roads_europe');
The costs are now:
id | source | target | cost | reverse_cost ----+--------+--------+------------------+-------------- 1 | 1 | 2 | 6857.46585793103 | 2 | 3 | 4 | 37349.9592156392 | 3 | 5 | 6 | 14040.5673116933 | (3 lignes)
Then you need to add the column which will contain the town labels, which will be shown in the drop-down list for selecting the two points of a path.
The label information is contained in the roads
table which was originally imported using the
shp2pgsql utility. The following
commands will create a temporary table, fill it with the town
information, and then update the vertices table. The towns contained
in the shapefile may not be on the exact same point that the intersections
of the roads. Thus, all intersections which are in a distance
less that 2000 meters are associated to the town label. This distance
may be adjusted according to the dataset you are using.
$ CREATE TABLE roads_source_town AS SELECT DISTINCT t.txt, source_id, distance(PointN(r.the_geom, 1), t.the_geom) AS d FROM roads_europe r, town t, roads_europe_vertices WHERE t.txt != 'UNK' AND distance(PointN(r.the_geom, 1), t.the_geom) < 2000 AND geom_id = source_id ORDER BY t.txt, d; $ CREATE TABLE roads_source_town_uniq AS SELECT * FROM roads_source_town a WHERE a.txt IN (SELECT b.txt FROM roads_source_town b where a.txt = b.txt LIMIT 1) AND a.d IN (SELECT b.d FROM roads_source_town b WHERE a.txt = b.txt LIMIT 1); $ ALTER TABLE roads_europe_vertices ADD COLUMN txt character varying(50); $ SELECT AddGeometryColumn('','roads_europe_vertices','the_geom','-1','POINT',2); $ UPDATE roads_europe_vertices SET txt = (SELECT DISTINCT txt FROM roads_source_town_uniq WHERE roads_europe_vertices.geom_id = roads_source_town_uniq.source_id); -- clean the temporary tables $ DROP TABLE roads_source_town; $ DROP TABLE roads_source_town_uniq;
The last step is to fill the geometry column of the vertices table:
$ CREATE TABLE roads_europe_vertices_geom AS SELECT v.id, v.geom_id, v.txt,startPoint(geometryn(r.the_geom, 1)) AS the_geom FROM roads_europe r LEFT JOIN roads_europe_vertices v ON v.geom_id = r.source_id; $ INSERT INTO roads_europe_vertices_geom SELECT v.id, v.geom_id, v.txt, endPoint(geometryn(r.the_geom, 1)) AS the_geom FROM roads_europe r LEFT JOIN roads_europe_vertices v ON v.geom_id = r.target_id; $ DELETE FROM roads_europe_vertices; $ INSERT INTO roads_europe_vertices SELECT DISTINCT ON (id) * FROM roads_europe_vertices_geom; $ DROP TABLE roads_europe_vertices_geom;
Now, all is set up correctly for using the shortest path function on these data. But to include the routing fonctionnalities in a custom project, we also must respect some rules dictated by the routing plugin.
The two things to do are to:
-
create the routing results table. In this example the table is routing_results.
$ CREATE TABLE routing_results ( results_id integer, "timestamp" bigint, gid integer ); $ SELECT AddGeometryColumn('','routing_results','the_geom','-1', 'MULTILINESTRING',2);
-
create the 'routing_results_seq' sequence.
$ CREATE SEQUENCE routing_results_seq INCREMENT 1 MINVALUE 1 MAXVALUE 9223372036854775807 START 1 CACHE 1;
In the mapfile, you must include the routing layer, its connection to the database, a symbology for the route and a first route using a unique identifier. The data parameter will be overwritten by the routing plugin to draw the route chosen by the end-user. Example:
LAYER NAME "graph" TYPE LINE TRANSPARENCY 80 CONNECTIONTYPE postgis CONNECTION "user=@DB_USER@ password=@DB_PASSWD@ host=@DB_HOST@ dbname=@DB_NAME@" DATA "the_geom from (SELECT the_geom from routing_results) as foo using unique gid using srid=-1" TEMPLATE "t" CLASS NAME "0" STYLE SYMBOL "circle" SIZE 10 COLOR 90 27 191 END END END
For the demo, we suggest that you select your route by starting from a town until an other town. This is possible because for each object of a european-towns layer, we have identified the nearest object of the roads_europe_vertices table. That is why in the demoRouting configuration there is a client-side configuration. Normally, in the plugin routing, client-side only allows you to type an id of object, from which to start and an other to finish the route. No configuration is needed. So, if you use demoRouting extension, you must specify client-side, the:
- postgresRoutingVerticesTable: vertices table
- stepName: vertices table col containing informations you want to propose a choice on
- dsn: the connexion string to the database
Anyway, server-side, you must specify :
- the routing table (postgresRoutingTable option),
- the routing layer in the mapfile (postgresRoutingResultsLayer option),
- the results routing table (postgresRoutingResultsTable),
- the connexion string to the database (dsn option).