Tri topologique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques image illustrant l’informatique
Cet article est une ébauche concernant les mathématiques et l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 une extension linéaire de l'ordre partiel sur les sommets déterminé par les arêtes, c'est-à-dire un ordre total compatible avec ce dernier. En d'autres termes, il s'agit d'un ordre de visite des sommets tel qu'un sommet soit toujours visité avant ses successeurs.

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épilant, 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.

Exemple de tri topologique[modifier | modifier le code]

Représentation graphique du graphe G.

Soit un graphe orienté avec et

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 apparait bien avant ses successeurs. Il n'y a pas unicité de l'ordre.

Exemple d'utilisation[modifier | modifier le code]

  • 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.

Algorithme et Application en Python[modifier | modifier le code]

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 soit par un arc dont le parent n'a pas été traité (si possible) soit par le parent d'où on est venu. 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 donc impossible de descendre encore de niveau.On marque donc notre première date de fin 6 à donc (5 , 6). On regarde alors les parents de 6 soit 3 et 5. Sachant que trois est actuellement gris on regarde 5.
  • 5 n'étant le parent que de 6 il est également de nouveau impossible de descendre de niveau. On a donc pour 5 : (7 , 8). On remonte alors en 4, puis en 3 puis en 2, 8, 9 et 1 en inscrivant les dates de début et de fin correspondantes.

ATTENTION : Il existe plusieurs parcours topologique 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.

Algorithme[modifier | modifier le 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.
              tabCouleur = [] //Le tableau qui indiquera la couleur et donc le traitement d'un sommet.

  Exécution : Pour i allant de 1 à nbSommets :
                   ajouter(tabCouleur, 0) //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;
              Afficher(listeSommets) et/ou 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[modifier | modifier le code]

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

Tri topologique pour un graphe orienté acyclique en python.

Le code écrit ici est en python mais utilise des fonctions de Sage (logiciel de calcul formel) qui permettent de modéliser des graphes et des méthodes sur ces-derniers.

Ici : G.vertices() renvoie la liste des sommets du Graphe G.

et G.neighbors(x) renvoie la liste des sommets adjacents à x.

Sage contient également d'autres méthodes pouvant être utiles selon si le graphe est orienté ou non, comme is_eulerian qui détermine si un graphe est eulérien ou non.

Ou encore is_connected qui renvoie si un graphe est connexe ou non.

Notes et références[modifier | modifier le code]

http://zanotti.univ-tln.fr/enseignement/I51/TP7.html