TD d’algorithmique avancée

Ce TD d’algorithmique avancée porte sur le tri topologique, une méthode d’ordonnancement des sommets d’un graphe orienté acyclique (DAG). Il permet de comprendre et d’implémenter deux algorithmes fondamentaux de tri topologique, ainsi que d’analyser leur complexité. Pour réaliser ce TP, il est nécessaire de connaître les notions de graphes orientés, de parcours en profondeur (DFS) et d’algorithmes de tri.

Objectifs

• Comprendre la définition et les propriétés du tri topologique d’un graphe orienté acyclique.
• Implémenter un parcours en profondeur modifié pour calculer les dates de fin de traitement des nœuds.
• Utiliser les dates de fin pour obtenir un tri topologique.
• Améliorer l’algorithme pour obtenir une complexité linéaire.
• Implémenter un second algorithme basé sur les degrés entrants nuls des sommets.
• Analyser la complexité des algorithmes proposés.

Prérequis et installation

• Connaissance des graphes orientés acycliques (DAG).
• Maîtrise des parcours en profondeur (DFS) sur graphes.
• Notions de complexité algorithmique.
• Environnement de programmation permettant d’implémenter des algorithmes sur graphes (par exemple Python, C++, Java).
• Structure de données pile et file.

Définition et premier exercice : tri topologique d’un graphe

Un tri topologique d’un graphe orienté acyclique G = (S, A) est un ordre linéaire des sommets tel que pour tout arc (u, v), u apparaisse avant v dans l’ordre. Ce tri peut être vu comme un alignement des sommets sur une ligne horizontale où tous les arcs vont de gauche à droite.

Attention, le tri topologique n’est pas forcément unique. Par exemple, le graphe de la figure 1 propose plusieurs tris topologiques possibles.

À faire : Proposez un tri topologique pour le graphe donné (figure 1). Vérifiez que pour chaque arc (u, v), u précède bien v dans votre ordre.

Calcul des dates de fin de traitement par parcours en profondeur

Pour chaque nœud u, on souhaite calculer la date de fin de traitement fin[u], c’est-à-dire le moment où u et tous ses descendants ont été entièrement visités.

Voici l’algorithme modifié de parcours en profondeur (PP) :

PP(G)
pour chaque sommet u de G faire
  couleur[u] ← Blanc
pour chaque sommet u de G faire
  si couleur[u] = Blanc alors
    Visiter-PP(G, u, couleur)

Visiter-PP(G, s, couleur)
  couleur[s] ← Gris
  pour chaque voisin v de s faire
    si couleur[v] = Blanc alors
      Visiter-PP(G, v, couleur)
  couleur[s] ← Noir
  temps ← temps + 1
  fin[s] ← temps

Explication : La variable temps est un compteur global incrémenté à chaque fin de visite d’un sommet. La date fin[s] correspond à ce compteur.

À faire : Implémentez cet algorithme et appliquez-le au graphe de la figure 1. Vérifiez que les dates de fin sont cohérentes.

Relation entre dates de fin et tri topologique

On observe que si le graphe contient un arc (u, v), alors fin[u] > fin[v]. En effet, le traitement de u se termine après celui de v.

Par conséquent, trier les sommets par ordre décroissant de leurs dates de fin fournit un tri topologique du graphe.

La figure 2 illustre ce principe en annotant les nœuds du graphe avec leurs dates de fin issues du parcours en profondeur.

À faire : Vérifiez que le tri obtenu en ordonnant les sommets par dates de fin décroissantes correspond bien à un tri topologique.

Algorithme de tri topologique basé sur le parcours en profondeur et tri des dates de fin

L’algorithme consiste à :

1. Effectuer un parcours en profondeur modifié pour calculer les dates de fin.
2. Trier les sommets par ordre décroissant de ces dates.

La complexité est la somme de celle du parcours O(|S| + |A|) et celle du tri O(|S| log(|S|)), soit :

O(|S| log(|S|) + |A|)

À faire : Implémentez cet algorithme et mesurez son temps d’exécution sur des graphes de taille variable.

Amélioration vers un algorithme linéaire

Pour éviter le tri des dates de fin, on utilise une pile P dans laquelle on empile les sommets à la fin de leur traitement. Le tri topologique est obtenu en dépilant les sommets dans l’ordre inverse de leur empilement.

Voici l’algorithme amélioré :

PP(G)
Soit P une pile initialement vide
pour chaque sommet u de G faire
  couleur[u] ← Blanc
pour chaque sommet u de G faire
  si couleur[u] = Blanc alors
    Visiter-PP(G, u, couleur, P)

tant que non Pile-Vide(P) faire
  u ← Dépiler(P)
  Afficher(u)

Visiter-PP(G, s, couleur, P)
  couleur[s] ← Gris
  pour chaque voisin v de s faire
    si couleur[v] = Blanc alors
      Visiter-PP(G, v, couleur, P)
  couleur[s] ← Noir
  Empiler(P, s)

Explication : La pile stocke les sommets dans l’ordre inverse de leur fin de traitement. L’affichage en dépilant donne directement un tri topologique sans tri supplémentaire.

La complexité devient linéaire :

O(|S| + |A|)

À faire : Implémentez cet algorithme et vérifiez qu’il produit un tri topologique correct plus rapidement que la version avec tri.

Algorithme de tri topologique basé sur les degrés entrants

Une autre méthode repose sur le fait qu’un sommet avec un degré entrant nul peut être placé en tête d’un tri topologique.

Voici l’algorithme :

Tri-Topologique(G = (S, A))
Soit F une file initialement vide
pour chaque sommet u de G faire
  degré(u) ← degré entrant de u
  si degré(u) = 0 alors
    Insertion(F, u)

tant que non File-Vide(F) faire
  u ← Suppression(F)
  Afficher(u)
  pour chaque voisin v de u faire
    degré(v) ← degré(v) − 1
    si degré(v) = 0 alors
      Insertion(F, v)

Explication : On commence par insérer dans la file tous les sommets sans prédécesseurs. On retire ensuite un sommet de la file, on l’affiche, et on diminue le degré entrant de ses voisins. Si un voisin atteint un degré entrant nul, il est inséré dans la file. Ce processus garantit que les sommets sont ordonnés sans violer les arcs.

La complexité est également linéaire :

O(|S| + |A|)

À faire : Implémentez cet algorithme et comparez ses résultats et performances avec ceux des algorithmes précédents.

Résultats attendus

• Un ou plusieurs tris topologiques valides pour le graphe donné, respectant l’ordre des arcs.
• Dates de fin de traitement cohérentes avec la relation fin[u] > fin[v] pour chaque arc (u, v).
• Tri topologique obtenu par tri décroissant des dates de fin.
• Tri topologique obtenu par dépilage de la pile dans l’algorithme amélioré.
• Tri topologique obtenu par l’algorithme basé sur les degrés entrants nuls.
• Complexité linéaire observée pour les deux derniers algorithmes.

Pièges courants

• Ne pas vérifier que le graphe est acyclique avant d’appliquer le tri topologique. Un cycle empêche l’existence d’un tri topologique.
• Confondre la couleur des sommets dans le parcours en profondeur (Blanc, Gris, Noir) et ne pas gérer correctement les états, ce qui peut entraîner des boucles infinies.
• Oublier d’incrémenter correctement le compteur temps dans le calcul des dates de fin.
• Ne pas empiler les sommets à la fin de leur traitement dans l’algorithme amélioré, ce qui empêche d’obtenir un ordre correct.
• Dans l’algorithme basé sur les degrés entrants, ne pas mettre à jour correctement les degrés lors de la suppression d’un sommet.
• Ne pas gérer correctement les sommets isolés ou sans arcs entrants ni sortants.