Les logiciels de routage requièrent toujours un noeud source et destination pour chaque arc afin de créer une recherche du plus court chemin. La création de ces données sur des réseaux de lignes implique la création de la topologie de ce réseau. Bien que pgDijkstra donne la possibilité de créer les noeuds sources et destinations dans PostgreSQL, les performances ne sont pas bonne, parfois cette opération peut prendre un jour ou plus pour un grand nombre de données (le paramétrage de la base de donnée peux réduire le temps necéssaire).

Il y a d'autre logiciel qui peuvent être utilisés pour créer une topologie plus rapidement.

Certains d'entre eux sont :

PostGIS

Lors de la rédaction de cette documentation, la dernière version de PostGIS (1.1.2), a commencé à ajouter des fonctionnalités topologiques. Mais cela reste dans un état de développement très primaire et il y a encore très peu de documentation sur la création de topologies. Cette page sera mise à jour lorsque les fonctionnalités topologiques de PostGIS seront dans un état suffisament stable pour être utilisées.

ArcInfo

Pour ceux qui possède un licence ArcInfo, la création de topologie est faite simplement en utilisant la commend build: build line {Coverage Name} et en exportant ensuite la couverture dans un fichier vecteur, qui peut être ensuite importé dans PostGIS. La commande build va créer les colonnes fnode_,tnode_,length qui peuvent être renommées dans PotgreSQL comme source,target, et la colonne length peut être utilisé comme le coût intial.

GRASS

GRASS peut aussi être utilisé pour créer une topologie, mais l'extraction de l'information topologique et l'insertion dans PostgreSQL n'est pas aussi simple que dans ArcInfo puisque l'information topologique n'est pas inclue dans l'ensemble des donnée lors de l'export dans un fichier vecteur.

La commande de création de topologie, v.build, a un option dump qui permet d'afficher l'information dans un flux qui peut être redirigé dans un fichier. Par exemple :

La sortie devrait ressembler à cela :

Un programme perl comme celui-ci (table_topo.pl) peut être utilisé pour convertir la sortie de GRASS dans un fichier SQL qui créera les table de noeuds et d'arcs contenant l'imformation topologique. Ces tables peuvent ensuite être liés dans la table réseau de PostGIS pour créer les information source-destination.

La fonction shortest_path est définie de la manière suivante :

CREATE OR REPLACE FUNCTION shortest_path(sql text, source_id integer, 
       target_id integer, directed boolean, has_reverse_cost boolean) 
    RETURNS SETOF path_result

sql

une requête SQL qui doit renvoyer les champs suivants :

SELECT id, source, target, cost FROM edge_table;

• id: l'identifiant entier (int4) de l'arc
• source: un identifiant entier (int4) du noeud de départ
• target: un identifiant entier (int4) du noeud d'arrivée
• cost: le coût de la traversée d'un arc (float8, un coût négatif permet de s'assurer qu'on ne passera jamais par cette arc)
• reverse_cost : (optionel) le coût de la traversée de l'arc en sens invers. Cela n'estutilisé que lorsque la fonction est appelé avec l'argument has_reverse_cost à vrai.

source_id

identifiant du noeud de départ.

target_id

identifiant du noeud d'arrivée.

directed

vrai si le graphe est orienté.

has_reverse_cost

vrai si la colonne reverse_cost doit être considérée lors de la recherche du plus court chemin, dans le cas où lma traversée de l'arc se fait en sens invers.

• vertext_id : l'identifiant du noeud source de chaque arc. Il y a une ligne supplémentaire contenant l'identifiant du noeud d'arrivée,
• edge_id : l'identifiant de l'arc traversé,
• cost : le coût de la traversée de l'arc. Cette valeur vaut 0 pour la dernière ligne renvoyée. Donc le coût total du parcour peut être calculé en faisant la somme des valeurs de cette colonne.

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
          target::int4, length::double precision AS cost,
    FROM dourol',3, 7, false, false);

 vertex_id | edge_id | cost 
-----------+---------+------------------------
         3 |       2 |    0.000763954363701041
         4 |      21 |    0.00150254971056274
         6 |       5 |    0.000417442425988342
         7 |      -1 |    0
(4 rows)

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
         target::int4, length::double precision AS cost,length::double precision 
    AS reverse_cost FROM dourol', 3, 7, true, true);

La fonction shortest_path_astar est définie de la façon suivante :

Les arguments sont :

sql
une requête SQL, qui doit renvoyer un ensemble de lignes ayant les colonnes suivantes :

• id: une entier (int4), l'identifiant de l'arc
• source: un entier (int4), l'identifiant du noeud source
• target: un entier (int4), l'identifiant du noeud destination
• cost: une valeur flotante (float8) représentant le coût de la traversé de l'arc. (un coût négatif permettra d'empécher l'insertion de l'arc dans le graphe).
• x1: coordonée x du noeud source de l'arc
• y1: coordonée y du noeud source de l'arc
• x2: coordonée x du noeud destination de l'arc
• y2: coordonée x du noeud destination de l'arc
• reverse_cost (optional): le coût de la traversée dans le sens inverse de l'arc. Cela est uniquement utilisé lorsque le graphe est orienté et que les paramètres has_reverse_cost sont à vrai (voir la remarque ci-dessous concernant les coûts inverses).

source_id
int4 identifiant du point de départ
target_id
int4 identifiant du point d'arrivé
directed
vrai si le graphe est orienté
has_reverse_cost
si sa valeur est vrai, la colonne reverse_cost du résultat SQL généré sera utilisé pour le coût de la traversé d'un arc dans la direction oposée.

La fonction renvoie un ensemble de lignes. Il y a une ligne pour chaque arc traversé et une en plus contenant le noeud terminal. Les colonnes de chaque lignes sont :

• vertex_id: l'identifiant du noeud origine de chaque arc. Il y a une ligne supplémentaire après le dernier arc qui contient le noeud de la destination du chemin.
• edge_id: l'identifiant de l'arc croisé
• cost: le coût associé à l'arc courant. Il vaut 0 pour les lignes après le dernier arc. Donc, le coût total du chemin peut être calculé en utilisant la somme de la colonne coût de toutes le lignes.

Exemple:

SELECT * from shortest_path_astar('SELECT gid as id, source::int4,
target::int4, length::double precision as cost, x1, y1, x2, y2
FROM dourol',3, 7, false, false);
vertex_id | edge_id | cost
----------+---------+------------------------
        3 |       2 | 0.000763954363701041
        4 |      21 | 0.00150254971056274
        6 |       5 | 0.000417442425988342
        7 |      -1 | 0
(4 rows)
SELECT * from shortest_path_astar('SELECT gid as id, source::int4,
target::int4, length::double precision as cost,length::double precision
as reverse_cost, x1, y1, x2, y2 FROM dourol', 3, 7, true, true);
haut de la page | table des matières

La fonction shortest_path_shooting_star est définie de la façon suivante :

Les arguments sont :

sql

une requête SQL, qui doit renvoyer un ensemble de lignes ayant les mêmes colonnes que celles nécessaires à A* plus :

• rule: une chaîne de caractère contenant une liste d'identifiants d'arcs, séparés par une virgule, qui décrit le sens giratoir (si je suis sur tel tronçon je peux aller sur tel tronçon avec le coût décrit dans la colonne to_cost)
• to_cost : le coût d'un passage restrain (peut être très élevé dans le cas où le fait de tourner vers tel arc entraine le passage par un feu)
  

source_id

int4 identifiant de l'arc de départ

target_id

int4 identifiant de l'arc d'arrivé

directed

vrai si le graphe est orienté

has_reverse_cost

si sa valeur est vrai, la colonne reverse_cost du résultat SQL généré sera utilisé pour le coût de la traversé d'un arc dans la direction oposée.

La fonction renvoie un ensemble de lignes équivalent à celui renvoyé par A* mis à part que le dernier coût retourné n'est pas -1.

Exemple:

La fonction driving_distance est définie comme suit :

Les arguments sont :

sql

une requête SQL, qui devrait renvoyer un ensemble de lignes ayant les colonnes suivantes :

• id: un identifiant (int4) de l'arc
• source: un identifiant (int4) du noeud origine
• target: un identifiant (int4) du noeud destination
• cost: une valeur float8 représentant le coût de traversé d'un arc. (un coût négatif entrainera la non insertion de l'arc dans le graphe).

source_id

un identifiant (int4) du point de départ id of the start point

distance

une valeur float8 de la distance en degrés

La focntion renvoie un ensemble de lignes. Il y a une ligne pour chaque arc tranversés et un ligne supplémentaire contenant le noeud terminal. Les colonnes de chaque lignes sont :

• vertex_id: l'identifiant du noeud source de chaque arc. Il y a une ligne supplémentaire contenant l'identifiant du noeud final du chemin.
• edge_id: l'identifiant de l'arc traversé
• cost: le coût associé à l'arc. Il vaut 0 pour la ligne après le dernier arc. Donc, le cou^t total du chemin peut être calculé comme la somme de la colonne cost de toutes les lignes.

  Exemple:
  

  SELECT * from driving_distance('select gid as id,source,target,
  length::double precision as cost from dourol',10549,0.01);
  vertex_id | edge_id |            cost
  -------------+------------+--------------------------
          6190 |   120220 | 0.00967666852
          6205 |    118671 | 0.00961557335
          6225 |   119384 | 0.00965668162
          6320 |   119378 | 0.00959826176
           ...
           ...
           ...
          15144 |   122612 | 0.00973386526
          15285 |   120471 | 0.00912965866
          15349 |  122085 | 0.00944814966
           15417 |   120471 | 0.00942316736
          15483 |   121629 | 0.00972957546
  (293 rows)
  haut de la page | table des matières

La fonction tsp est définie comme suit :

Les arguments sont :

sql

un requête SQL qui devrait retourner un ensemble de lignes ayant les colonnes suivantes :

• source_id: un int4 identifiant du noeud
• x: la coordonée x du noeud
• y: la coordonée y du noeud

ids

une chaîne de charactères contenant les idetifiants (int4) des noeuds séparés par une virgule.

source_id

identifiant (int4) du point de départ

La fonction renvoie un ensemble de lignes. Il y a une ligne pour chaque arc travsersé et une en plus contenant le noeud final. Les colonnes de chaques lignes sont les suivantes :

• vertex_id: l'identidiant du noeud source de chaque arc. Il y a une ligne supplémentaire après le dernier arc qui contient l'identifiant du noeud final du chemin.
• edge_id: innutilisé, vaut toujours 0
• cost: innutilisé, vaut toujours 0

Exemple:

Ensuite la colonne vertex_id peut être utilisée pour le calcul du plus court chemin.

Il y a de nombreuses fonctions dans le fichier routing_postgis.sql qui renvoient le résultat sous la forme d'une geometrie (objet de type geometry). Vous pouvez trouver leur noms facilement - elles contiennent "as_geometry".