Tri topologique

En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t.

En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs.

Exemple de tri topologique

Représentation graphique du graphe G.

Soit $G=(S,A)$ un graphe orienté avec $S=\{1,2,3,4,5,6,7,8,9\}$ et $A=\{(1,2),(1,8),(2,8),(2,3),(3,6),(4,3),(4,5),(5,6),(9,8)\}$.

Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6. En effet, chaque sommet apparaît bien avant ses successeurs. Il n'y a pas unicité de l'ordre.

Algorithme

Pour un graphe représenté en mémoire sous une forme facile à parcourir, par exemple par listes d'adjacence, le calcul d'un tri topologique est simple. Il suffit d'effectuer un parcours en profondeur du graphe, au cours duquel on empile chaque sommet une fois ses successeurs visités. En désempilant, on obtient un tri topologique.

Sans dédier une procédure pour ce traitement (gros graphes), on peut se re-servir d'un parcours en profondeur déjà effectué pour déterminer directement un ordre topologique. En effet, la lecture des sommets dans l'ordre inverse de la numérotation postfixe du parcours en profondeur est un ordre topologique.

Une autre façon de procéder consiste à rechercher une racine (sommet sans prédécesseur), l'enlever, et répéter l'opération autant de fois que nécessaire. C'est facile si l'on peut facilement calculer le nombre de prédécesseurs d'un sommet ; en effet, les racines à une itération sont parmi les successeurs des racines à l'itération précédente, et un compteur des prédécesseurs permet de les reconnaître.

L'algorithme de tri topologique d'un graphe fonctionne sur le même principe que l'algorithme de parcours en profondeur en rajoutant une notion de date de début et de date de fin. L'ordre topologique sera à la fin les sommets dans l'ordre du tableau de date de fin. On commence par un sommet donné puis tant qu'il est possible on « descend » de niveau en suivant les arcs orientés en incrémentant à chaque étape la date de début, jusqu'à arriver à un sommet d'où aucun arc ne part. On inscrit alors notre première date de fin. Puis on « remonte » en passant par le parent d'où on est venu, et on visite les autres arcs qui n'ont pas encore été traités. Et on répète l'opération.

Afin de savoir si un sommet a été vu ou non, on utilise un système de couleurs : Blanc pour : « Non traité », Gris pour : « En traitement » et Noir pour « Traité ».

• « Non traité » correspond aux sommets qui n'ont ni date de début, ni date de fin.
• « En traitement » correspond aux sommets qui ne possèdent qu'une date de début et pas encore de date de fin.
• « Traité » correspond aux sommets qui possèdent les deux.

Par exemple avec le graphe ci-dessus (on écrit le couple dateDébut/dateFin ainsi : (dateDébut , dateFin) ) :

• On commence par le sommet 1, on a alors pour ce point la date de début : (1, ) , la date de fin n'étant pas encore connue. On a alors le choix de continuer soit vers 2 ou vers 8. Supposons que l'on aille vers 2. On aura alors pour 2 (2, ), puis en 3 avec (3, ) et enfin en 6 avec (4, ).
• Ici, 6 est un sommet dont ne part aucun arc. Il est donc impossible de descendre encore de niveau. On marque donc notre première date de fin pour 6 : (4 , 5). Puis on « remonte » en passant par le parent d'où l'on vient, c'est-à-dire 3.
• Comme il n'y a pas d'autre arc partant du sommet 3, on marque notre deuxième date de fin pour 3 : (3 , 6) puis on « remonte » encore par le parent d'où l'on est venu, c'est-à-dire 2.
• Du sommet 2, on continue en suivant l'arc qui n'a pas encore été visité (vers 8), d'où il est impossible de descendre davantage. On a donc pour 8 : (7 , 8) puis on remonte au sommet 2.
• Cette fois, tous les arcs partant du sommet 2 ont été traités, donc on marque la date de fin pour 2 : (2 , 9) et on remonte vers le sommet 1, qui est dans la même situation, donc 1 : (1, 10).
• On répète ensuite ces opérations en commençant par un sommet qui n'a pas encore été visité, par exemple 4 : (11, ) d'où on peut descendre en 5 : (12, ), mais pas plus loin car 6 a déjà été visité. On a donc pour 5 : (12 , 13), puis après être remonté en 4 : (11, 14) car tous ses voisins ont été visités.
• On recommence avec 7 : (15 , 16) et 9 : (17 , 18), qui n'ont aucun voisin non-traité.
• Finalement, on trie les sommets par date de fin décroissante pour obtenir l'ordre suivant: 9, 7, 4, 5, 1, 2, 8, 3, 6.

Il existe plusieurs parcours topologiques pour un graphe, de même pour un parcours en profondeur, qui varieront en fonction de la direction prise. Dans l'algorithme qui suit, on traite les sommets dans l'ordre de la liste des fils d'un sommet, soit en commençant toujours par l’élément de gauche, mais ce n'est pas obligatoire.

Pseudo-code

Il se décompose en 2 fonctions :

Algorithme tri_topo (Graphe g)
  Entrée : Un graphe G =(V,E) orienté non cyclique.
  Sortie : La liste des sommets dans l'ordre topologique.
  Variables : listeSommets = []
              t = 0   //C'est la variable qui établira les dates d'entrées et sorties.
              couleur = [] //Le tableau qui indiquera la couleur et donc le traitement d'un sommet.

  Exécution : Pour i allant de 1 à nbSommets :
                   ajouter(couleur, Blanc) //On initialise tous les sommets à blancs, soit non traité.
              Fin Pour;
              
              Pour chaque x appartenant à V Faire :
                   Si couleur(x) = Blanc alors :
                          Parcours_Profondeur_Topo(G, listeSommets, x, t)
              Fin Pour;
              Retourner(listeSommets)
  Fin Exécution;  

L'algorithme Parcours_Profondeur_Topo(G, listeSommets, x, t) :

Algorithme Parcours_Profondeur_Topo(G, listeSommets, x, t)
  Entrée : Un graphe G =(V,E) orienté non cyclique.
           La liste des sommets.
           Le sommet en traitement.
           La date.
  Sortie : Les sommets empilés dans l'ordre topologique dans listeSommets.
 
  Exécution : couleur(x) = Gris
              t = t + 1
              dateDébut(x) = t
              Pour chaque y appartenant à Γ+ (x) Faire : //Γ+ (x) est l'ensemble des voisins de x.
                      Si couleur(y) == Blanc alors : 
                           Parcours_Profondeur_Topo(G, listeSommets, y, t)
                      Fin Si;
              Fin Pour;
              couleur(x) = Noir
              t = t + 1
              dateFin(x) = t             //Les dates ne sont pas nécessaires à l'algorithme mais pourraient être utilisées à d'autre fins.
              empiler(x, listeSommets) 
  Fin Exécution;

Exemple du code en Python

Dans le code ci-contre n'ont pas été implémentées les dates de début et de fin (correspondants à t ci-dessus) :

BLANC = 0
GRIS = 1
NOIR = 2

def tri_topologique(G):
    listeSommets = []

    for i in G.vertices():
        tabCouleur.append(BLANC)

    for x in G.vertices():
        if tabCouleur[x] == BLANC:
            parcours_profondeur_topo(G, listeSommets, x)

    print(listeSommets)

def parcours_profondeur_topo(G, listeSommets, x):
    tabCouleur[x] = GRIS
    for i in G.neighbors(x):
        if tabCouleur[i] == BLANC:
            parcours_profondeur_topo(G, listeSommets, i)

    tabCouleur[x] = NOIR
    listeSommets.append(x)

Ici : G.vertices() renvoie la liste des sommets du Graphe G et G.neighbors(x) renvoie la liste des sommets adjacents à x.

Exemple d'utilisation

• Le logiciel Make.
• Le tri topologique est un prétraitement qui permet ensuite de calculer les distances de plus court chemins dans un graphe pondéré acyclique en temps linéaire en la taille du graphe.

Lien externe

« Ordonnancement séquentiel: tri topologique » (version du 3 mars 2016 sur Internet Archive)