Le blog de Jean David TECHER, un Réunionnais à Saint-Priest/Lyon

This is my favorite function in PgRouting . Here we will see an example. For more info, please see http://pgrouting.postlbs.org/wiki/ShootingStar

Let's suppose that we have the following network with two roundabouts as shown in the following picture. The SQL file used here is available at http://www.davidgis.fr/download/pgrouting_wr.sql

The network The associated table is named wr. The wr's content is

routing=# SELECT gid as id, source, target, cost, reverse_cost,x1, y1,x2, y2, rule, to_cost FROM wr order by id;
 id | source | target |       cost       |   reverse_cost   |        x1        |        y1         |        x2        |        y2         | rule | to_cost 
----+--------+--------+------------------+------------------+------------------+-------------------+------------------+-------------------+------+---------
  1 |      1 |      2 | 14.2572101668807 |             1000 | 76.7176891326003 |   33.775246780918 | 87.3962905382969 |  43.2217018705726 |      |        
  2 |      2 |      3 | 11.0893168443772 |             1000 | 87.3962905382969 |  43.2217018705726 | 87.3962905382969 |  54.3110187149498 |      |        
  3 |      3 |      4 | 13.9884637834871 |             1000 | 87.3962905382969 |  54.3110187149498 | 76.7176891326003 |  63.3467583659239 |      |        
  4 |      4 |      5 | 14.2572101668807 |             1000 | 76.7176891326003 |  63.3467583659239 | 67.2712340429456 |  52.6681569602273 |      |        
  5 |      5 |      6 | 10.6864968606796 |             1000 | 67.2712340429456 |  52.6681569602273 |  66.860518604265 |  41.9895555545307 |      |        
  6 |      6 |      1 | 12.8311604873812 |             1000 |  66.860518604265 |  41.9895555545307 | 76.7176891326003 |   33.775246780918 |      |        
  7 |      7 |      1 | 53.8753258085636 | 53.8753258085636 |               80 |               -20 | 76.7176891326003 |   33.775246780918 |      |        
  8 |      8 |      4 | 62.5380849791951 | 62.5380849791951 | 73.0212501844746 |  125.775505045381 | 76.7176891326003 |  63.3467583659239 |      |        
  9 |      7 |      9 |               40 |               40 |               80 |               -20 |              120 |               -20 |      |        
 10 |      9 |     10 | 33.4201752293529 | 33.4201752293529 |              120 |               -20 | 141.610728444141 | -45.4928328844451 |      |        
 11 |      9 |     11 |               60 |               60 |              120 |               -20 |              180 |               -20 |      |        
 12 |     11 |     12 | 25.9044654619518 | 25.9044654619518 |              180 |               -20 | 180.217979680121 | -45.9035483231257 |      |        
 13 |     12 |     10 | 38.6094358307609 | 38.6094358307609 | 180.217979680121 | -45.9035483231257 | 141.610728444141 | -45.4928328844451 |      |        
 14 |     13 |     12 | 29.5829181472758 | 29.5829181472758 | 181.039410557482 | -75.4750599081316 | 180.217979680121 | -45.9035483231257 |      |        
 15 |     13 |     14 | 39.4286821133412 | 39.4286821133412 | 181.039410557482 | -75.4750599081316 | 141.610728444141 | -75.4750599081316 |      |        
 16 |     14 |     10 | 29.9822270236865 | 29.9822270236865 | 141.610728444141 | -75.4750599081316 | 141.610728444141 | -45.4928328844451 |      |        
 17 |     15 |     13 | 39.2224758594282 | 39.2224758594282 |              220 |               -80 | 181.039410557482 | -75.4750599081316 |      |        
 18 |     15 |     16 | 38.0005743220152 |             1000 |              220 |               -80 | 251.682466010552 | -79.1714988562574 |      |        
 19 |     16 |     15 | 38.0539027874633 |             1000 | 251.682466010552 | -79.1714988562574 |              220 |               -80 |      |        
 20 |     17 |     16 | 48.3246366252935 | 48.3246366252935 |              300 |               -80 | 251.682466010552 | -79.1714988562574 |      |        
 21 |     11 |     18 |  115.27849852631 |  115.27849852631 |              180 |               -20 | 295.218302510699 | -23.7249146343713 |      |        
 22 |     18 |     17 | 56.4778705670458 | 56.4778705670458 | 295.218302510699 | -23.7249146343713 |              300 |               -80 |      |        
(22 rows)

I. Roundabouts

We have two roundabouts. First done with (1,2,3,4,5,6) and secund done with (18,19). So that is the reason why reverse_cost is enough expensive: reverse_cost=1000

In a first time, we want the path from edge=20 to edge=8. Using shooting_star, we have

routing=# SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,x1, y1,x2, y2, rule, to_cost FROM wr order by id',20,8,true,true);
 vertex_id | edge_id |       cost       
-----------+---------+------------------
        31 |      20 | 48.3246366252935
        29 |      19 | 38.0539027874633
        27 |      17 | 39.2224758594282
        23 |      14 | 29.5829181472758
        21 |      13 | 38.6094358307609
        17 |      10 | 33.4201752293529
        15 |       9 |               40
        12 |       7 | 53.8753258085636
         1 |       1 | 14.2572101668807
         2 |       2 | 11.0893168443772
         4 |       3 | 13.9884637834871
         6 |       8 | 62.5380849791951
(12 rows)

We have
Shortest path using shooting star from edge=20 to 8

II. Turn restrictions

Let's suppose now that we have following restrictions:

1. from edge from 17 to 14 ;
2. from edge from 16 to 10;

You can' tgo from 17 to 14 and from 16 to 10. The restricted edges are shown on the following picture

Restricted edges: You can't go from 17 to 14 and from 16 to 10

So we have to do

routing=# update wr set to_cost=100,rule='17' where gid=14;
UPDATE 1
routing=# update wr set to_cost=100,rule='16' where gid=10;

So we have

routing=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,x1, y1,x2, y2, rule, to_cost FROM wr order by id',20,8,true,true);
 edge_id 
---------
      20
      19
      17
      15
      16
      13
      12
      11
       9
       7
       1
       2
       3
       8
(14 rows)

Beautifull...The final result is
Shortest path from edge=20 to 8

We have the following roads. See the following image

The table test has the following content

routing_db=# SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test order by gid;
 id | source | target |       cost       |   reverse_cost   | x1 |  y1  | x2  |  y2  | rule | to_cost 
----+--------+--------+------------------+------------------+----+------+-----+------+------+---------
  1 |      1 |      2 |             27.5 |             27.5 | 60 | 87.5 |  60 |  115 |      |        
  2 |      2 |      3 | 25.4950975679639 | 25.4950975679639 | 60 |  115 |  85 |  120 |      |        
  3 |      1 |      4 |             62.5 |             1000 | 60 | 87.5 |  60 |   25 |      |        
  4 |      5 |      6 | 29.0688837074973 | 29.0688837074973 |  1 |    1 |  20 |   23 |      |        
  5 |      6 |      4 | 40.0499687890016 | 40.0499687890016 | 20 |   23 |  60 |   25 |      |        
  6 |      4 |      7 | 27.3130005674953 | 27.3130005674953 | 60 |   25 |  85 |   36 |      |        
  7 |      8 |      1 |               59 |               59 |  1 | 87.5 |  60 | 87.5 |      |        
  8 |      1 |      9 |               25 |               25 | 60 | 87.5 |  85 | 87.5 |      |        
  9 |      9 |     10 |               65 |               65 | 85 | 87.5 | 150 | 87.5 |      |        
 10 |     11 |      3 |               15 |               15 | 85 |  135 |  85 |  120 |      |        
 11 |      3 |      9 |             32.5 |             32.5 | 85 |  120 |  85 | 87.5 |      |        
 12 |      9 |      7 |             51.5 |             51.5 | 85 | 87.5 |  85 |   36 |      |        
 13 |      7 |     12 |               35 |               35 | 85 |   36 |  85 |    1 |      |        
(13 lignes)

Suppose now that we have build a bridge from edge=8 to edge=9 and a one-way street. We have the following image

Question: How to use shooting start in order to taking account the bridge?

First we have to update the fields rule and to_cost for edge in (8,9,11,12) and add required tuples. Then we have the following content.

Notice: Edge 3 is a one-way street. so reverse_cost=1 000 000

routing_db=# select gid,astext(the_geom),source,target,x1,y1,x2,y2,cost,reverse_cost,rule,to_cost from test order by 1;
 gid |               astext                | source | target | x1 |  y1  | x2  |  y2  |       cost       |   reverse_cost   | rule | to_cost 
-----+-------------------------------------+--------+--------+----+------+-----+------+------------------+------------------+------+---------
   1 | MULTILINESTRING((60 87.5,60 115))   |      1 |      2 | 60 | 87.5 |  60 |  115 |             27.5 |             27.5 |      |        
   2 | MULTILINESTRING((60 115,85 120))    |      2 |      3 | 60 |  115 |  85 |  120 | 25.4950975679639 | 25.4950975679639 |      |        
   3 | MULTILINESTRING((60 87.5,60 25))    |      1 |      4 | 60 | 87.5 |  60 |   25 |             62.5 |          1000000 |      |        
   4 | MULTILINESTRING((1 1,20 23))        |      5 |      6 |  1 |    1 |  20 |   23 | 29.0688837074973 | 29.0688837074973 |      |        
   5 | MULTILINESTRING((20 23,60 25))      |      6 |      4 | 20 |   23 |  60 |   25 | 40.0499687890016 | 40.0499687890016 |      |        
   6 | MULTILINESTRING((60 25,85 36))      |      4 |      7 | 60 |   25 |  85 |   36 | 27.3130005674953 | 27.3130005674953 |      |        
   7 | MULTILINESTRING((1 87.5,60 87.5))   |      8 |      1 |  1 | 87.5 |  60 | 87.5 |               59 |               59 |      |        
   8 | MULTILINESTRING((60 87.5,85 87.5))  |      1 |      9 | 60 | 87.5 |  85 | 87.5 |               25 |               25 | 11   |    2000
   8 | MULTILINESTRING((60 87.5,85 87.5))  |      1 |      9 | 60 | 87.5 |  85 | 87.5 |               25 |               25 | 12   |    2000
   9 | MULTILINESTRING((85 87.5,150 87.5)) |      9 |     10 | 85 | 87.5 | 150 | 87.5 |               65 |               65 | 10   |    2000
   9 | MULTILINESTRING((85 87.5,150 87.5)) |      9 |     10 | 85 | 87.5 | 150 | 87.5 |               65 |               65 | 11   |    2000
   9 | MULTILINESTRING((85 87.5,150 87.5)) |      9 |     10 | 85 | 87.5 | 150 | 87.5 |               65 |               65 | 12   |    2000
  10 | MULTILINESTRING((85 135,85 120))    |     11 |      3 | 85 |  135 |  85 |  120 |               15 |               15 |      |        
  11 | MULTILINESTRING((85 120,85 87.5))   |      3 |      9 | 85 |  120 |  85 | 87.5 |             32.5 |             32.5 | 8    |    1000
  11 | MULTILINESTRING((85 120,85 87.5))   |      3 |      9 | 85 |  120 |  85 | 87.5 |             32.5 |             32.5 | 9    |    1000
  12 | MULTILINESTRING((85 87.5,85 36))    |      9 |      7 | 85 | 87.5 |  85 |   36 |             51.5 |             51.5 | 8    |    1000
  12 | MULTILINESTRING((85 87.5,85 36))    |      9 |      7 | 85 | 87.5 |  85 |   36 |             51.5 |             51.5 | 9    |    1000
  13 | MULTILINESTRING((85 36,85 1))       |      7 |     12 | 85 |   36 |  85 |    1 |               35 |               35 |      |        
(18 lignes)

Notice: for more informations, please see http://pgrouting.postlbs.org/

Let's now do a few tests

Example 1

Find the path from edge=7 to edge=13

routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',7,13, true,true);
 edge_id 
---------
       7
       3
       6
      13

For the reversed path (from 13 to 7), we have

routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',13,7, true,true);
 edge_id 
---------
      13
      13
      12
      11
       2
       1
       7

Example 2

Find the path from edge=9 to edge=13

routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',9,13, true,true);
 edge_id 
---------
       9
       9
       8
       3
       6
      13

If start is 13 and stop is 9 then we have

routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',13,9, true,true);
 edge_id 
---------
      13
      13
      12
      11
       2
       1
       8
       9

Example 3

Find the path from edge=12 to edge=9

routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',12,9, true,true);
 edge_id 
---------
      12
      12
      11
       2
       1
       8
       9

From 9 to 12, we have

routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',9,12, true,true);
 edge_id 
---------
       9
       9
       8
       1
       2
      11
      12

Example 4

From 9 to 10 and vice-versa

routing_db=# SELECT *  FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',9,10, true,true);
 vertex_id | edge_id |       cost       
-----------+---------+------------------
         8 |       9 |               65
        12 |       9 |               65
         8 |       8 |               25
         6 |       1 |             27.5
        18 |       2 | 25.4950975679639
        16 |      10 |               15
(6 lignes)

routing_db=# SELECT *  FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',10,9, true,true);
 vertex_id | edge_id |       cost       
-----------+---------+------------------
        15 |      10 |               15
        16 |       2 | 25.4950975679639
        18 |       1 |             27.5
         6 |       8 |               25
         8 |       9 |               65
(5 lignes)

Let's suppose that we are at Montpellier in France. (the one of the most beautifull towns in South France !). We want to go from "Avenue du Fès" to "Rue de Casseyrols", i.e.

• start point := "Avenue du Fès";
• end point := "Rue de Casseyrols".

Everything is shown in the following picture

start point and and point

In order to manage the street, we had the following column to hour table. If the status field is yes, then the street is available.

ALTER TABLE routing add column status text default 'yes';

We use

SELECT the_geom FROM routing r JOIN 
           (SELECT edge_id FROM shortest_path_shooting_star(
         'SELECT gid as id,source,target,cost,reverse_cost,x1,y1,x2,y2,rule,to_cost from routing WHERE status='::text||'''yes'''::text,
           426515,
          404982, true, true)) AS  x(e)
     ON x.e = r.gid;

Then we have We go through the street "Avenue du Père Soulas". Suppose now that the street is not available. We do

 UPDATE routing SET status='no' WHERE name='Avenue du Père Soulas';

We have

Depuis que je suis sur la côte, que ce soit lors de mes sorties nocturnes ou au taf, j'ai rencontré beaucoup de personnes qui ont cotoyé cette ville. De l'expérience et du vécu de chacun, il en ressort toujours la même impression: belle et charmante ville.

On me dit que c'est une ville qui bouge, qui est vivante. J'aimerais bien y faire un tour à l'occasion. Non pas que pour des vacances mais au moins pour un séjour assez long. Pourquoi pas professionnellement?...LOL! Mais bon on verra ça dans les temps à venir. Laisson l'été passé et profitons-en. Du temps où je taffais à 01MAP, de part les formations en informatique que je donnais, j'ai souvent eu l'occasion pendant mes courts séjours de faire un peu de tourisme!

Toulouse est l'une des villes que je n'ai pas encore inscrit dans mon parcours. Mais à entendre les gens que je cotois en parler, cette ville et sa région, il fait bon y vivre!...On verra, on verra si l'occasion de s'y échapper/rentre se présente, j'y ferais bien un tour sur place!

S'il faut amener le chat, j'amène le chat!