< WMS Browser Light

Bounding box history plugin >

## 26. Routing Plugin

## 26.1. Introduction

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.

## 26.2. Installation

Before installing the pgRouting extension, a sample PostGIS database have to be created, as explained in the installation manual: Chapter 1, Installation.

### 26.2.1. Quick Install

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

### 26.2.2. Detailled installation steps

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.

#### 26.2.2.1. Europe Roads Geodata Importation in PostGIS

    $ 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

#### 26.2.2.2. Graph Importation

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.

#### 26.2.2.3. Routing Plugin Database Configuration

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;

#### 26.2.2.4. Mapfile Configuration

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

#### 26.2.2.5. General Configuration

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