Cohérence des noeuds

La première vérification à faire est la cohérence de la numérotation des noeuds entre tronçon d'un même itinéraire ou axe : un tronçon T(AB) entre le noeud A et le noeud B se doit d'avoir comme attribut l'identifiant du noeud A en noeud de début de tronçon et l'identifiant du noeud B comme noeud de fin de tronçon et le tronçon T(BC) est connecté avec T(AB) si et seulement si le noeud de fin de T(AB) est le même que le noeud de départ de T(BC), en l'occurrence le noeud B.

Voici la table utilisée pour modéliser les itinéraires du graphe :

Un itinéraire peut représenter un itinéraire de bus, un axe d'autoroute, un résultat de plus court chemin etc.

Comment trouver les extrémités de l'itinéraire ?

Une manière assez simple de procéder est d'utiliser la requête suivante :

(Q1) SELECT start_node FROM GRAPHE_ITI WHERE iti_name='ITI_1' AND start_node NOT IN (SELECT end_node FROM GRAPHE_ITI WHERE iti_name='ITI_1'

Cette première requête devrait vous donner le noeud initial. Dans le cas d'itinéraire non fermé et sans boucles, la requête doit théoriquement vous renvoyer un seul enregistrement correspondant au premier tronçon de l'itinéraire. Si il y a plus d'une réponse, il y a soit des ruptures dans le graphe, soit un bouclage.

Obtenir le noeud final est un jeu d'enfant : il suffit d'inverser les rôles pour noeud de départ et de fin de tronçon :

(Q2) SELECT end_node FROM GRAPHE_ITI WHERE iti_name='ITI_1' AND end_node NOT IN (SELECT start_node FROM GRAPHE_ITI WHERE iti_name='ITI_1'

Comment obtenir la liste ordonnée des tronçons de l'itinéraire ?

Une première solution pourrait consister à faire un self-join sur la table et rapprocher les segments 2 à 2 par les noeuds. Mais cette solution ne convient lorsque l'on veut véritablement la liste des troncons et non une extraction partielle. L'idéal est d'utiliser les fonctions SQL de parcours du graphe par les noeuds. La fonction CONNECT BY (non standard SQL) implémenté sur Oracle  permet une navigation dans un arbre :  c'est une requête récursive. Voici sa syntaxe :

SELECT LEVEL, id_tr, iti_name, start_node, end_node
  FROM (SELECT * FROM GRAPHE_ITI WHERE iti_name ='ITI_1')
  WHERE iti_name = 'ITI_1'
   START WITH start_node = (Q1)
   CONNECT BY PRIOR end_node = start_node

Le résultat doit comprendre le nombre de tronçons de l'itinéraire. Quelques explications sur la structure de la requête :

• LEVEL (mot-clé réservé) indique ici la profondeur de l'arbre. Si l'itinéraire est valide au niveau des connexions par les noeuds, LEVEL doit être égal au ROWNUM c'est à dire le numéro d'ordre du tronçon dans l'itinéraire.
• START WITH est assez explicite : il indique par quel valeur de noeud commencer; ici on utilise le résultat de la requête (Q1)
• CONNECT BY PRIOR indique comment choisir le suivant; ici la condition est de choisir le suivant pour que son noeud de départ soit égal au noeud de fin du tronçon courant

Ayant beaucoup pratiqué ces requêtes sous Oracle, je me suis posé la question pour utiliser cette syntaxe également sous PostgreSQL. Apparemment rien d'implémenté dans la version officielle pour le moment mis à part quelques contributions sous forme de fonctions PL/PgSQL. Mais il existe apparemment une version patchée de la version PostgreSQL 8.3 RC2 avec la fonction CONNECT BY.
Le blog de Hans-Jürgen SCHÖNIG explique la démarche.