PgRouting 1.02 on Win32


1. Requirements
2. Installation
3. Create a routing database and load data
4. Shortest Path Dijkstra: shortest_path and dijkstra_sp_directed()
4.1. Change to do for reverse_cost
4.2. Shortest_path()
4.3. Dijkstra_sp_directed
4.4. Example for 11 and 29
5. Shortest Path A*: shortest_path_astar() and astar_sp_directed()
6. Shortest Path Shooting Star : shortest_path_shooting_star()
6.1. Edges from roads
6.2. shortest_path_shooting_star()
6.3. View Data in QGIS without shootingstar_sp
6.4. View Data in QGIS with shootingstar_sp
7. Traveling Sales Person (TSP): tsp_astar_directed()
Revision History
2008-07-12 add example for shortest_path and dijkstra_sp_directed and shooting_sp 

Important

This is a tutorial about pgrouting on windows. This tutorial has been written by a French guy (not very very good in english...) Please refer to the documentation for PgRouting at http://pgrouting.postlbs.org for more information.


A Flash demo for A* using Ming

1. Requirements

You should have the following items

  • PostgreSQL 8.3.3. You can download it from http://www.postgresql.org;

  • PostGIS 1.3.3. Once PostgreSQL is installed on your computer, use the Stack Buildder from PostgreSQL.

2. Installation

Download pgrouting 1.02 from http://www.davidgis.fr/download/pgRouting-1.02_pg-8.3.3.zip. Then

  • Unzip the file

  • Copy lib and share dir to C:\Program Files\PostgreSQL\8.3

  • Add C:\Program Files\PostgreSQL\8.3\bin;C:\Program Files\PostgreSQL\8.3\lib at the beginning of your environment variable PATH

3. Create a routing database and load data

Open a DOS shell then

SET PGUSER=postgres
cd C:\Program Files\PostgreSQL\8.3\share\contrib
createdb -T template_postgis testgis
psql -d testgis -f routing_core.sql
psql -d testgis -f routing_core_wrappers.sql
psql -d testgis -f routing_tsp.sql
psql -d testgis -f routing_tsp_wrappers.sql
psql -d testgis -f routing_dd.sql
psql -d testgis -f routing_dd_wrappers.sql

In the zip file, you will find the file roads.sql. Load it by doing

psql -d testgis -f roads.sql

The table has the following structure

testgis=# \d roads
                             Table « public.roads »
   Colonne    |       Type       |                   Modificateurs
--------------+------------------+----------------------------------------------------
 id           | integer          | not null default nextval('roads_id_seq'::regclass)
 source       | integer          |
 target       | integer          |
 cost         | double precision |
 reverse_cost | double precision |
 oneway       | text             |
 x1           | double precision |
 y1           | double precision |
 x2           | double precision |
 y2           | double precision |
 gid          | integer          | not null
 the_geom     | geometry         |
 length       | double precision |
 rule         | text             |
 to_cost      | double precision |
Index :
    « roads_pkey » PRIMARY KEY, btree (gid)
    « roads_source_key » UNIQUE, btree (source, target)
    « roads_source_target_idx » btree (source, target)
Contraintes de vérification :
    « enforce_dims_the_geom » CHECK (ndims(the_geom) = 2)
    « enforce_geotype_the_geom » CHECK (geometrytype(the_geom) = 'MULTILINESTRING'::text OR the_geom IS NULL)
    « enforce_srid_the_geom » CHECK (srid(the_geom) = (-1))

Figure 1. Sources and targets from table roads

Sources and targets from table roads

Here is the roads' content. I've decided to add the requested fields for the differents kind of functions.

testgis=# SELECT id,source,target,x1,y1,x2,y2,cost,reverse_cost,oneway,length,rule,to_cost from roads order by id;
 id | source | target |        x1         |         y1         |        x2         |         y2         |       cost       |   reverse_cost   | oneway |      length      | rule | to_cost
----+--------+--------+-------------------+--------------------+-------------------+--------------------+------------------+------------------+--------+------------------+------+--------
  1 |      1 |      2 |                 1 |                  0 |                 5 |                  0 |                4 |                4 | N      |                4 |      |
  2 |      2 |      3 |                 5 |                  0 |                 5 |                  6 |                6 |                6 | N      |                6 |      |
  3 |      4 |      5 |                 0 |                7.5 |                 3 |                7.5 |                3 |                3 | N      |                3 |      |
  4 |      5 |      3 |                 3 |                7.5 |                 5 |                  6 | 2.91421356237309 |               -1 | Y      | 2.91421356237309 |      |
  5 |      3 |      6 |                 5 |                  6 |                 7 |                7.5 | 2.91421356237309 |               -1 | Y      | 2.91421356237309 |      |
  6 |      6 |      7 |                 7 |                7.5 |                 5 |                  9 | 2.91421356237309 |               -1 | Y      | 2.91421356237309 |      |
  7 |      7 |      5 |                 5 |                  9 |                 3 |                7.5 | 2.91421356237309 |               -1 | Y      | 2.91421356237309 |      |
  8 |      6 |      8 |                 7 |                7.5 |                11 |                7.5 |                4 |                4 | N      |                4 |      |
  9 |      8 |      9 |                11 |                7.5 |                11 |                 11 |              3.5 |              3.5 | N      |              3.5 |      |
 10 |      8 |     10 |                11 |                7.5 |                14 |                7.5 |                3 |                3 | N      |                3 |      |
 11 |     10 |     11 |                14 |                7.5 |                21 |                7.5 |                7 |                7 | N      |                7 |      |
 12 |     10 |     12 |                14 |                7.5 |                14 |                 11 |              3.5 |              3.5 | N      |              3.5 |      |
 13 |     12 |     13 |                14 |                 11 |                18 |                 11 |                4 |                4 | N      |                4 |      |
 14 |     13 |     14 |                18 |                 11 |                18 |                 13 |                2 |                2 | N      |                2 |      |
 15 |     13 |     15 |                18 |                 11 |                20 |                 11 |                2 |                2 | N      |                2 |      |
 16 |     15 |     16 |                20 |                 11 |                20 |                  9 |                2 |                2 | N      |                2 |      |
 17 |     12 |     17 |                14 |                 11 |                14 |                 13 |                2 |                2 | N      |                2 |      |
 18 |      7 |     18 |                 5 |                  9 |                 8 |               14.5 |              8.5 |              8.5 | N      |              8.5 |      |
 19 |     18 |     19 |                 8 |               14.5 |                 8 |                 18 |              3.5 |              3.5 | N      |              3.5 |      |
 20 |     18 |     20 |                 8 |               14.5 |                12 |               14.5 |                4 |                4 | N      |                4 |      |
 21 |     20 |     17 |                12 |               14.5 |                14 |                 13 | 2.91421356237309 |               -1 | Y      | 2.91421356237309 |      |
 22 |     17 |     21 |                14 |                 13 |                16 |               14.5 | 2.98079618907396 |               -1 | Y      | 2.98079618907396 |      |
 23 |     21 |     22 |                16 |               14.5 |              15.5 |               15.5 | 1.20710678118655 |               -1 | Y      | 1.20710678118655 |      |
 24 |     22 |     23 |              15.5 |               15.5 |                14 |                 16 | 1.70710678118655 |               -1 | Y      | 1.70710678118655 |      |
 25 |     23 |     20 |                14 |                 16 |                12 |               14.5 | 2.91421356237309 |               -1 | Y      | 2.91421356237309 |      |
 26 |     23 |     24 |                14 |                 16 |                14 |                 20 |                4 |                4 | N      |                4 |      |
 27 |     21 |     25 |                16 |               14.5 |              23.5 |                 19 |               12 |               12 | N      |               12 |      |
 28 |     22 |     25 |              15.5 |               15.5 |              23.5 |                 19 | 9.44974746830583 | 9.44974746830583 | N      | 9.44974746830583 |      |
 29 |     25 |     26 |              23.5 |                 19 |                30 |                 19 |              6.5 |              6.5 | N      |              6.5 |      |
 30 |      1 |     27 |                 1 |                  0 | -1.24301510067114 |   -2.5522432885906 | 3.61523066112342 | 3.61523066112342 | N      | 3.61523066112342 |      |
 31 |     28 |     29 | -1.48505369127517 |  -3.85925167785235 |                 4 |                 -7 |   6.728520725894 |   6.728520725894 | N      |   6.728520725894 |      |
 32 |     30 |      4 |                -4 |                  4 |                 0 |                7.5 | 5.86670129625104 | 5.86670129625104 | N      | 5.86670129625104 |      |
 33 |     31 |     28 | -2.11435402684564 |   -3.4719899328859 | -1.48505369127517 |  -3.85925167785235 | 0.84274652312971 |               -1 | Y      | 0.84274652312971 |      |
 34 |     28 |     27 | -1.48505369127517 |  -3.85925167785235 | -1.24301510067114 |   -2.5522432885906 |   1.643652980008 |               -1 | Y      |   1.643652980008 |      |
 35 |     27 |     31 | -1.24301510067114 |   -2.5522432885906 | -2.11435402684564 |   -3.4719899328859 | 1.51352166586552 |               -1 | Y      | 1.51352166586552 |      |
 36 |     32 |     33 | -5.07865086257376 |   2.26953745529481 |  -3.5712446684834 |   2.22091144903383 | 1.73350805494058 |               -1 | Y      | 1.73350805494058 |      |
 37 |     33 |     30 |  -3.5712446684834 |   2.22091144903383 |                -4 |                  4 | 1.99498090204589 |               -1 | Y      | 1.99498090204589 |      |
 38 |     30 |     32 |                -4 |                  4 | -5.07865086257376 |   2.26953745529481 | 2.42470775726398 |               -1 | Y      | 2.42470775726398 |      |
 39 |     34 |     35 |  16.9050866893397 |   5.03750410181188 |  17.8313340915255 |   4.01375697308019 | 1.73750308554073 |               -1 | Y      | 1.73750308554073 |      |
 40 |     35 |     34 |  17.8313340915255 |   4.01375697308019 |  16.9050866893397 |   5.03750410181188 | 2.20661903277814 |               -1 | Y      | 2.20661903277814 |      |
 41 |     36 |     31 |  -9.0366577181208 |  -4.14969798657718 | -2.11435402684564 |   -3.4719899328859 | 7.08611544792685 | 7.08611544792685 | N      | 7.08611544792685 |      |
 42 |      1 |     33 |                 1 |                  0 |  -3.5712446684834 |   2.22091144903383 | 5.16592533550955 | 5.16592533550955 | N      | 5.16592533550955 |      |
 43 |     37 |     32 |  -11.497283689023 | -0.064510845232198 | -5.07865086257376 |   2.26953745529481 | 7.08935847100446 | 7.08935847100446 | N      | 7.08935847100446 |      |
 44 |     38 |     39 |  -7.3154471505788 | -0.210388864015136 | -8.67697532588622 |  -1.62054304558353 | 2.81901636360908 | 2.81901636360908 | N      | 2.81901636360908 |      |
 45 |     40 |     39 | -6.92643910049097 |  -2.10680310819333 | -8.67697532588622 |  -1.62054304558353 | 2.71375967514431 | 2.71375967514431 | N      | 2.71375967514431 |      |
 46 |     41 |     39 | -10.3788855450205 |  -2.05817710193235 | -8.67697532588622 |  -1.62054304558353 | 1.76395914112196 | 1.76395914112196 | N      | 1.76395914112196 |      |
 47 |     37 |     41 |  -11.497283689023 | -0.064510845232198 | -10.3788855450205 |  -2.05817710193235 | 2.28593953367386 | 2.28593953367386 | N      | 2.28593953367386 |      |
 48 |     41 |     36 | -10.3788855450205 |  -2.05817710193235 |  -9.0366577181208 |  -4.14969798657718 | 2.48516300274436 | 2.48516300274436 | N      | 2.48516300274436 |      |
 49 |     42 |     43 |  19.1963302631677 |  -6.07746472441785 |  19.1963302631677 |  -1.00747894403236 | 5.06998578038549 | 5.06998578038549 | N      | 5.06998578038549 |      |
 50 |     44 |     45 |  10.8113537802225 |   2.64876080143794 |  10.8113537802225 | -0.568730174575924 | 3.21749097601387 | 3.21749097601387 | N      | 3.21749097601387 |      |
 51 |     46 |     47 |  7.39886335111687 |   2.84376025452969 |  7.44761321438981 |  0.211267637791074 | 2.63392519805962 | 2.63392519805962 | N      | 2.63392519805962 |      |
 52 |     47 |     45 |  7.44761321438981 |  0.211267637791074 |  10.8113537802225 | -0.568730174575924 | 3.45299104857306 | 3.45299104857306 | N      | 3.45299104857306 |      |
 53 |     48 |     49 |  5.10761977728881 |   -3.9324707404086 |  14.8575924318763 |  -1.34872798694292 | 13.0297765905234 | 13.0297765905234 | N      | 13.0297765905234 |      |
 54 |     45 |     49 |  10.8113537802225 | -0.568730174575924 |  14.8575924318763 |  -1.34872798694292 | 4.12073340722674 | 4.12073340722674 | N      | 4.12073340722674 |      |
 55 |     50 |     51 |  26.8988086602918 |   7.71874658182343 |    28.36130455848 |   3.81875751998844 | 4.63167714107961 | 4.63167714107961 | N      | 4.63167714107961 |      |
 56 |     52 |     53 |  31.0912969017644 |   9.66874111274093 |   31.432545944675 |   4.40375587926369 | 5.29390700081218 | 5.29390700081218 | N      | 5.29390700081218 |      |
 57 |     43 |     54 |  19.1963302631677 |  -1.00747894403236 |    28.36130455848 |    3.7700076567155 | 10.3354309080009 | 10.3354309080009 | N      | 10.3354309080009 |      |
 58 |     54 |     53 |    28.36130455848 |    3.7700076567155 |   31.432545944675 |   4.40375587926369 | 3.13594650175355 | 3.13594650175355 | N      | 3.13594650175355 |      |
 59 |     49 |     43 |  14.8575924318763 |  -1.34872798694292 |  19.1963302631677 |  -1.00747894403236 | 4.35213704724091 | 4.35213704724091 | N      | 4.35213704724091 |      |
 60 |     43 |     35 |  19.1963302631677 |  -1.00747894403236 |  17.8313340915255 |   4.01375697308019 | 5.23594066797949 | 5.23594066797949 | N      | 5.23594066797949 |      |
 61 |     10 |     34 |                14 |                7.5 |  16.9050866893397 |   5.03750410181188 |  3.8083349013935 |  3.8083349013935 | N      |  3.8083349013935 |      |
(61 lignes)

4. Shortest Path Dijkstra: shortest_path and dijkstra_sp_directed()

Suppose that we want to know what is the best path from source = 26 and target = 39 and vice versa

4.1. Change to do for reverse_cost

Here before using our functions, we must take care of the value of field reverse_cost. Indeed reverse_cost must take positive value else PostgreSQL server crash! :(. We can take a expensive value. reverse_cost=1000 should be enough in order to supporting one-way streets.

UPDATE roads SET reverse_cost=1000 WHERE oneway='Y';

4.2. Shortest_path()

We have

  1. source=26 and target = 39

    testgis=# SELECT * FROM shortest_path('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',26,39,true,true);
     vertex_id | edge_id |       cost
    -----------+---------+------------------
            26 |      29 |              6.5
            25 |      28 | 9.44974746830583
            22 |      24 | 1.70710678118655
            23 |      25 | 2.91421356237309
            20 |      20 |                4
            18 |      18 |              8.5
             7 |       7 | 2.91421356237309
             5 |       3 |                3
             4 |      32 | 5.86670129625104
            30 |      38 | 2.42470775726398
            32 |      43 | 7.08935847100446
            37 |      47 | 2.28593953367386
            41 |      46 | 1.76395914112196
            39 |      -1 |                0
    (14 lignes)
  2. source=39 and target=26

    testgis=# SELECT * FROM shortest_path('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',39,26,true,true);
     vertex_id | edge_id |       cost
    -----------+---------+------------------
            39 |      46 | 1.76395914112196
            41 |      47 | 2.28593953367386
            37 |      43 | 7.08935847100446
            32 |      36 | 1.73350805494058
            33 |      37 | 1.99498090204589
            30 |      32 | 5.86670129625104
             4 |       3 |                3
             5 |       4 | 2.91421356237309
             3 |       5 | 2.91421356237309
             6 |       8 |                4
             8 |      10 |                3
            10 |      12 |              3.5
            12 |      17 |                2
            17 |      22 | 2.98079618907396
            21 |      23 | 1.20710678118655
            22 |      28 | 9.44974746830583
            25 |      29 |              6.5
            26 |      -1 |                0
    (18 lignes)

Let's now see our paths in QGIS

4.3. Dijkstra_sp_directed

We will create two tables associated to the paths!

BEGIN TRANSACTION;
DROP TABLE IF EXISTS shortest_path_table_1,shortest_path_table_2;
CREATE TABLE shortest_path_table_1(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_table_1(the_geom) 
 SELECT the_geom FROM dijkstra_sp_directed('roads',26,39,true,true);


CREATE TABLE shortest_path_table_2(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_table_2(the_geom) 
 SELECT the_geom FROM dijkstra_sp_directed('roads',39,26,true,true);
END TRANSACTION;

Here is the result in QGIS

Figure 2. Shortest path for (26,39) and(39,26)

Shortest path for (26,39) and(39,26)

4.4. Example for 11 and 29

If you have understood what we have do before, here is an example for couple (11,29) and (29,11)

Figure 3. Shortest path for (11,29) and(29,11)

Shortest path for (11,29) and(29,11)

I let you to find the requested SQL queries :)

5. Shortest Path A*: shortest_path_astar() and astar_sp_directed()

Let's have a few tests. Here we will use shortest_path_astar().

If (source,target)=(37,43) then

testgis=# SELECT * FROM shortest_path_astar('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',37,43,true,true);
 vertex_id | edge_id |       cost
-----------+---------+------------------
        37 |      43 | 7.08935847100446
        32 |      36 | 1.73350805494058
        33 |      37 | 1.99498090204589
        30 |      32 | 5.86670129625104
         4 |       3 |                3
         5 |       4 | 2.91421356237309
         3 |       5 | 2.91421356237309
         6 |       8 |                4
         8 |      10 |                3
        10 |      61 |  3.8083349013935
        34 |      39 | 1.73750308554073
        35 |      60 | 5.23594066797949
        43 |      -1 |                0
(13 rows)

By reversing (source,target)=(43,37) we have

testgis=# SELECT * FROM shortest_path_astar('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',43,37,true,true);
 vertex_id | edge_id |       cost
-----------+---------+------------------
        43 |      60 | 5.23594066797949
        35 |      40 | 2.20661903277814
        34 |      61 |  3.8083349013935
        10 |      10 |                3
         8 |       8 |                4
         6 |       6 | 2.91421356237309
         7 |       7 | 2.91421356237309
         5 |       3 |                3
         4 |      32 | 5.86670129625104
        30 |      38 | 2.42470775726398
        32 |      43 | 7.08935847100446
        37 |      -1 |                0
(12 rows)

We can use astar_sp_directed() to see the geometric paths

testgis=# SELECT id,gid,astext(the_geom) FROM astar_sp_directed('roads',43,37,true,true);
 id | gid |                                                                                                                                                                              astext
----+-----+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  1 |  43 | MULTILINESTRING((19.1963302631677 -1.00747894403236,17.8800839547984 2.94125998107557,17.8313340915255 4.01375697308019))
  2 |  61 | MULTILINESTRING((17.8313340915255 4.01375697308019,18.0047396454493 4.20401231196082,18.1257963529056 4.51270691597435,18.0410566576862 4.785084507751,17.9199999502299 4.94245822744417,17.6415695230805 5.10588478251016,17.4841958033873 5.21483581922082,17.266293729966 5.208782983848,17.1210256810184 5.16036030086549,16.9050866893397 5.03750410181188))
  3 |  44 | MULTILINESTRING((14 7.5,16.9050866893397 5.03750410181188))
  4 |   6 | MULTILINESTRING((11 7.5,14 7.5))
  5 |   4 | MULTILINESTRING((7 7.5,11 7.5))
  6 |  47 | MULTILINESTRING((7 7.5,7 8,6 9,5 9))
  7 |  48 | MULTILINESTRING((5 9,4 9,3 8,3 7.5))
  8 |   3 | MULTILINESTRING((0 7.5,3 7.5))
  9 |  23 | MULTILINESTRING((-4 4,-2.8 6.7,0 7.5))
 10 |  59 | MULTILINESTRING((-4 4,-4.46274864568763 3.93807848556878,-4.75377039792406 3.78754999303269,-4.90429889046015 3.59688056915365,-4.9946159859818 3.4563873094533,-5.10500354717493 3.15533032438113,-5.14514447851788 2.8643085721447,-5.15517971135362 2.53314588856532,-5.07865086257376 2.26953745529481))
 11 |  26 | MULTILINESTRING((-11.497283689023 -0.064510845232198,-10.4761375575425 0.227245192333677,-8.9687313634521 0.470375223638574,-7.36407315683978 0.762131261204449,-6.1484230003153 1.05388729877032,-5.07865086257376 2.26953745529481))

Let's create the two associated tables in order to seeing them in QGIS

-- (source,target)=(37,43)
CREATE TABLE shortest_path_astar_table_1(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_astar_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_astar_table_1(the_geom) 
 SELECT the_geom FROM astar_sp_directed('roads',37,43,true,true);

-- (source,target)=(43,37) 
CREATE TABLE shortest_path_astar_table_2(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_astar_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_astar_table_2(the_geom) 
 SELECT the_geom FROM astar_sp_directed('roads',43,37,true,true);

Here is the result

Figure 4. Shortest path for (source=37,target=37)

Shortest path for (source=37,target=37)

and for (source=43,target=37)

Figure 5. Shortest path (source43,target=43)

Shortest path (source43,target=43)

6. Shortest Path Shooting Star : shortest_path_shooting_star()

Here we must begin to see the edge from roads (see the field id from roads)

6.1. Edges from roads

The id field give us the edges from roads table

Figure 6. Edges from table roads

Edges from table roads


Suppose that we want the path from 29 to 46 and from 46 to 49.

6.2. shortest_path_shooting_star()

on't forget to use the field rule and tocost for this function.

  • from 29 to 46

    testgis=# SELECT * FROM shortest_path_shooting_star('SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads',29,46,true,true);
     vertex_id | edge_id |       cost
    -----------+---------+------------------
            40 |      29 |              6.5
            43 |      29 |              6.5
            40 |      28 | 9.44974746830583
            41 |      24 | 1.70710678118655
            37 |      25 | 2.91421356237309
            36 |      20 |                4
            32 |      18 |              8.5
            31 |       7 | 2.91421356237309
            10 |       3 |                3
             9 |      32 | 5.86670129625104
            48 |      38 | 2.42470775726398
            54 |      43 | 7.08935847100446
            53 |      47 | 2.28593953367386
            58 |      46 | 1.76395914112196
    (14 rows)
  • from 46 to 29

    testgis=# SELECT * FROM shortest_path_shooting_star('SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads',46,29,true,true)
     vertex_id | edge_id |       cost
    -----------+---------+------------------
            58 |      46 | 1.76395914112196
            56 |      46 | 1.76395914112196
            58 |      47 | 2.28593953367386
            53 |      43 | 7.08935847100446
            54 |      36 | 1.73350805494058
            52 |      37 | 1.99498090204589
            48 |      32 | 5.86670129625104
             9 |       3 |                3
            10 |       4 | 2.91421356237309
             8 |       5 | 2.91421356237309
            11 |       8 |                4
            12 |      10 |                3
            16 |      12 |              3.5
            20 |      17 |                2
            30 |      22 | 2.98079618907396
            39 |      23 | 1.20710678118655
            41 |      28 | 9.44974746830583
            40 |      29 |              6.5
    (18 rows)

6.3. View Data in QGIS without shootingstar_sp

Here we will use two table

  • from 29 to 46

    BEGIN;
    CREATE TABLE shooting_star_table_1(gid int4) with oids;
    SELECT AddGeometryColumn( 'shooting_star_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 );
    INSERT INTO shooting_star_table_1(the_geom) SELECT the_geom FROM roads WHERE id IN
    (
    	SELECT edge_id FROM shortest_path_shooting_star
    	  (
         'SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads',
         29,46,true,true
         )
    );
    END;

    Figure 7. From edge=29 to edge=46

    From edge=29 to edge=46

  • from 46 to 29

    BEGIN;
    CREATE TABLE shooting_star_table_2(gid int4) with oids;
    SELECT AddGeometryColumn( 'shooting_star_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 );
    INSERT INTO shooting_star_table_2(the_geom) SELECT the_geom FROM roads WHERE id IN
    (
    	SELECT edge_id FROM shortest_path_shooting_star
    	  (
         'SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads',
         46,29,true,true
         )
    );
    END;

    Figure 8. From edge=46 to edge=29

    From edge=46 to edge=29

6.4. View Data in QGIS with shootingstar_sp

Here we will use shootingstar_sp(). We are trying to find the path from edge=31 to edge=56 and vice versa. The requested query is

SELECT the_geom FROM  shootingstar_sp('roads',31,56,1,'cost',true,true);

In order to see our path in QGIS, we can create the requested tables

BEGIN TRANSACTION;
DROP TABLE IF EXISTS shooting_table_1,shooting_table_2;
CREATE TABLE shooting_table_1(gid int4) with oids;
SELECT AddGeometryColumn( 'shooting_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shooting_table_1(the_geom) 
 SELECT the_geom FROM  shootingstar_sp('roads',31,56,1,'cost',true,true);

CREATE TABLE shooting_table_2(gid int4) with oids;
SELECT AddGeometryColumn( 'shooting_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shooting_table_2(the_geom) 
 SELECT the_geom FROM  shootingstar_sp('roads',56,31,1,'cost',true,true);
END TRANSACTION;

Here is the result

Figure 9. shootingstar_sp for edges 31 and 56

shootingstar_sp for edges 31 and 56

7. Traveling Sales Person (TSP): tsp_astar_directed()

It's times to try TSP. Let's suppose that we want to know what is the best path from source=7 to (46,43,25?18)???. Here we can use tsp_astar_directed.

Caution

tsp_astar_directed() is based on astar_sp_delta_directed(). [For my personal use of this function, I use astar_sp_directed() instead]. (Just see the function in routing_tsp_wrappers.sql...)

testgis=# SELECT * FROM tsp(
          'SELECT distinct source AS source_id,x1 as x,y1 as y,cost,reverse_cost FROM roads WHERE source IN (28,37,43,18,23)',
          '28,37,43,18,23',37);;

will give us

 vertex_id |  edge_id   |         cost
-----------+------------+-----------------------
        37 |   25784720 |                     0
        37 |         -1 | 9.12458190115067e-313
        18 |         16 | 4.24399190603761e-314
        18 |   25784800 | 1.69874584211253e-313
        23 |   25784800 | 1.69874584211253e-313
        23 |   25784776 | 3.39634247488474e-313
        28 | 1818326113 | 3.30605350921819e-028
        28 |          8 | 1.27393917699377e-316
        43 |          8 | 2.96839805221217e-301
        43 |          8 | 1.97484348732601e+166
(10 lignes)

We can create a table in order to seeing data in QGIS.

BEGIN TRANSACTION;
DROP TABLE IF EXISTS tsp_table;
CREATE TABLE tsp_table(gid integer,the_geom geometry)WITH oids;
INSERT INTO tsp_table 
         SELECT  foo.gid,foo.the_geom FROM (SELECT * FROM tsp_astar_directed('roads','28,37,43,18,23',37,3,true,true)) AS foo JOIN roads r ON foo.gid=r.gid;
END TRANSACTION;

Figure 10. TSP from 37 throw 28,43,18 and 23

TSP from 37 throw 28,43,18 and 23