Tables de routage

En bref

Résumé de l’article

Dans cet article, vous apprendrez à stocker le résultat d’un parcours dans une structure de données appelée table de routage. Ensuite, vous apprendrez à utiliser cette structure pour retrouver le chemin trouvé par le parcours jusqu’à un sommet donné. Après la vidéo, nous établirons un lien entre les tables de routage et certaines structures de données que vous avez déjà vues.

Points clés à retenir

• Les tables de routage permettent de stocker le résultat d’un parcours de graphe en mémoire.

• Elles peuvent ensuite être utilisées pour analyser le parcours effectué, par exemple pour trouver un chemin.

• Elles peuvent être implémentées à l’aide d’une liste ou d’un dictionnaire.

Contenu de l’article

Vidéo

Veuillez consulter la vidéo ci-dessous (en anglais, affichez les sous-titres si besoin). Nous fournissons également une traduction du contenu de la vidéo juste après, si vous préférez.

Implémentation des tables de routage

Pour implémenter des tables de routage dans un langage de programmation, vous avez besoin d’une structure de données qui peut vous aider à associer les sommets à leurs parents le long du parcours. Dans l’article sur comment représenter les graphes en mémoire, vous avez étudié quelques-unes de ces structures. Avec un peu d’imagination, toutes ces structures peuvent être utilisées pour implémenter des tables de routage. Voici quelques pistes :

• Tableaux ou listes – Numérotez arbitrairement les sommets du graphe de 1 à $n$. Utilisez un tableau de taille $n$, ou une liste initialisée avec $n$ entrées égales à 0 (ou toute valeur en dehors de l’intervalle $[1, n]$). Ensuite, pour indiquer que le sommet à l’index $i$ est un prédécesseur du sommet à l’index $j$, il suffit de placer $i$ dans l’entrée $j$ de la structure. Plus tard, pour récupérer le chemin, il sera nécessaire de convertir les indices en sommets réels pour obtenir le chemin.

• Dictionnaires – L’utilisation de dictionnaires est un peu plus directe, car ce sont des structures qui peuvent directement associer des variables à d’autres. Ainsi, il n’est pas nécessaire de numéroter les sommets. Par conséquent, pour indiquer que $v_1$ est un prédécesseur de $v_2$, il suffit d’associer la valeur $v_1$ à la clé $v_2$ dans la structure.

Pour aller plus loin

Pourquoi stocker les parents plutôt que les enfants ?

Dans un arbre enraciné, chaque sommet autre que la racine a exactement un parent, mais il peut avoir plusieurs enfants, ou aucun. Stocker le parent de chaque sommet donne donc une structure très simple, avec une seule valeur par sommet.

Stocker les enfants demanderait au contraire une liste par sommet. Surtout, pour aller de la racine à une destination, il faudrait choisir à chaque sommet dans quelle branche descendre, sans savoir laquelle mène à la destination. En partant de la destination et en remontant vers la racine, il n’y a qu’un seul choix possible à chaque étape : le parent. C’est pour cette raison que le routage se lit à l’envers, comme expliqué dans la vidéo.

Une seule table pour tous les chemins

Une table de routage obtenue par un BFS contient un plus court chemin depuis le sommet de départ vers chaque sommet atteignable, et elle n’utilise pour cela qu’une entrée par sommet.

À titre de comparaison, imaginons que l’on stocke explicitement chacun de ces chemins, sous forme de liste de sommets. Dans un labyrinthe en forme de long couloir de $n$ cases, parcouru depuis l’une de ses extrémités, les chemins contiennent respectivement $1, 2, \dots, n$ sommets. Il faudrait donc stocker $\frac{n(n+1)}{2}$ sommets au total, soit une mémoire en $O(n^2)$, contre $O(n)$ pour la table de routage.

Cette économie est possible car les chemins partagent leurs débuts. Si $(u, \dots, w, v)$ est un plus court chemin de $u$ à $v$, alors $(u, \dots, w)$ est un plus court chemin de $u$ à $w$. En effet, s’il existait un chemin plus court de $u$ à $w$, il suffirait de lui ajouter l’arête $\{w,v\}$ pour obtenir un chemin plus court de $u$ à $v$. Il suffit donc de retenir, pour chaque sommet, par où l’on y arrive : c’est exactement ce que fait la table de routage.

Deux remarques pratiques en découlent :

• Retrouver un chemin de $k$ arêtes demande $k$ lectures dans la table. Avec un dictionnaire, chaque lecture se fait en temps constant, donc le coût est proportionnel à la longueur du chemin, et non à la taille du graphe.
• Un sommet apparaît comme clé dans la table si et seulement si il est atteignable depuis le sommet de départ, puisque le parcours explore exactement les sommets atteignables (voir l’article sur les parcours). La table permet donc aussi de savoir immédiatement si une destination peut être atteinte.

Partir de la destination

Dans un graphe non orienté, un chemin de $t$ à $v$ lu à l’envers est un chemin de $v$ à $t$. On peut donc effectuer le parcours depuis la destination $t$ plutôt que depuis le point de départ. Dans la table obtenue, le parent d’un sommet $v$ est alors le prochain sommet où aller pour se rapprocher de $t$. Avec un BFS, suivre ces parents depuis n’importe quel sommet donne un plus court chemin jusqu’à $t$.

Ce point de vue est intéressant lorsque la destination est fixe, mais que le point de départ ne l’est pas. Par exemple, dans PyRat, on peut effectuer un parcours depuis le morceau de fromage au début de la partie. À chaque tour, il suffit ensuite de lire dans la table le parent de la case où se trouve le rat, sans avoir besoin de reconstruire un chemin complet :

def preprocessing ( self,
                    maze:       Maze,
                    game_state: GameState,
                  ) ->          None:

    # Perform the traversal from the piece of cheese rather than from the player
    distances, self.routing_table = self.traversal(maze, game_state.cheese[0])



def turn ( self,
           maze:       Maze,
           game_state: GameState,
         ) ->          Action:

    # The next location to go to is the parent of the current location
    my_location = game_state.player_locations[self.get_name()]
    next_location = self.routing_table[my_location]
    return maze.locations_to_action(my_location, next_location)

C’est aussi ainsi que fonctionnent les routeurs d’Internet. Chaque routeur possède une table qui associe, à chaque destination possible, le routeur voisin auquel transmettre les données pour s’en rapprocher. Autrement dit, l’entrée correspondant à une destination $t$ dans le routeur $v$ est le parent de $v$ dans un arbre de plus courts chemins enraciné en $t$. Ces tables ne sont pas calculées par un parcours centralisé, mais par des protocoles où les routeurs échangent progressivement des informations avec leurs voisins.

Pour aller encore plus loin

• Table de routage

  Les tables de routage utilisées par les routeurs des réseaux informatiques, qui indiquent où transmettre les données pour atteindre chaque destination.
• Routing Information Protocol

  Un protocole historique d’Internet, dans lequel les routeurs construisent leurs tables de routage en échangeant des distances avec leurs voisins.
• Union-find

  Une autre structure de données où chaque élément stocke simplement son parent dans un arbre, utilisée par exemple pour savoir rapidement si deux sommets sont dans la même composante connexe.