Le tri topologique

Chaque fois que vous installez un logiciel, compilez un programme ou planifiez un projet, quelque chose doit déterminer ce qu'il faut faire en premier. Si la tâche B a besoin de la tâche A, A doit venir avant. Un tri topologique transforme un réseau de telles règles en une seule ligne droite.

Un graphe de nœuds reliés par des flèches à sens unique, les nœuds placés en vert, et l'ordre obtenu jusqu'ici dessiné sur une ligne en dessous
Un graphe de nœuds reliés par des flèches à sens unique, les nœuds placés en vert, et l'ordre obtenu jusqu'ici dessiné sur une ligne en dessous

L'idée

Dessinez chaque tâche comme un nœud et chaque règle « A avant B » comme une flèche de A vers B. Un ordre topologique est une ligne de tous les nœuds dans laquelle chaque flèche pointe vers la droite. On parle de tri parce qu'il met les choses en ordre, mais contrairement au tri de nombres, il doit seulement respecter les flèches : des nœuds qu'aucune chaîne de flèches ne relie peuvent venir dans n'importe quel ordre.

Quand c'est impossible

Si les flèches forment un cycle, disons A avant B, B avant C et C avant A, alors A devrait venir avant lui-même. Un ordre topologique existe donc exactement quand le graphe n'a pas de cycle orienté. Un tel graphe s'appelle un graphe orienté acyclique, ou DAG. Les deux méthodes ci-dessous trouvent un cycle s'il y en a un, ce qui en fait aussi un test de cycle pratique.

Un exemple

Prenez les flèches A → C, B → C, B → D, C → E et D → E. L'algorithme de Kahn compte les flèches entrantes : A et B n'en ont aucune, donc A passe en premier, puis B. Retirer les flèches de B libère C et D, qui suivent, puis E : l'ordre A, B, C, D, E. La méthode DFS visite A, puis C, puis E ; E est terminé en premier, puis C, puis A, chacun passant en tête. Elle visite ensuite B et D, qui se terminent et passent devant eux : l'ordre B, D, A, C, E. Les deux ordres sont corrects.

Kahn ou DFS ?

L'algorithme de Kahn, publié par Arthur Kahn en 1962, travaille vers l'avant : il sait toujours quelles tâches peuvent commencer maintenant, ce qui convient à l'ordonnancement, et il peut choisir parmi les tâches libres selon n'importe quelle règle, comme l'ordre alphabétique. La méthode DFS, popularisée par Robert Tarjan en 1976, travaille à rebours depuis les fins et n'a besoin que d'un parcours en profondeur. Les deux prennent un temps qui croît avec le nombre de nœuds plus d'arêtes.

Robert Tarjan, qui avec John Hopcroft montra en 1972–73 que la recherche en profondeur résout de nombreux problèmes de graphes en temps linéaire ; ils reçurent le prix Turing 1986 en partie pour ce travail.
Robert Tarjan, qui avec John Hopcroft montra en 1972–73 que la recherche en profondeur résout de nombreux problèmes de graphes en temps linéaire ; ils reçurent le prix Turing 1986 en partie pour ce travail.

Usages

Les outils de compilation comme make compilent les fichiers après ceux dont ils dépendent. Les gestionnaires de paquets installent les bibliothèques dans l'ordre des dépendances. Les tableurs recalculent une cellule après les cellules qu'utilise sa formule. Les universités vérifient que les prérequis des cours peuvent être remplis, les compilateurs ordonnent les instructions, et les pipelines de données lancent chaque étape quand ses entrées sont prêtes. La commande Unix tsort fait à elle seule un tri topologique.

À vous d'essayer

Ouvrez l'application et appuyez sur Étape. Les flèches disent quel nœud doit venir avant lequel. Avec l'algorithme de Kahn, le nombre sur chaque nœud compte ses flèches entrantes restantes, et les nœuds libres sont bleus. Avec la méthode DFS, les nœuds bleus sont en cours de visite et les verts sont placés. L'ordre grandit sur la ligne sous le graphe. Cochez Ajouter un cycle et regardez les deux méthodes découvrir qu'aucun ordre n'existe.

Questions fréquemment posées

Que veut dire topologique ici ?

Le nom vient de la topologie, l'étude de la façon dont les choses sont reliées plutôt que de leur forme exacte. L'ordre dépend seulement des nœuds reliés par des flèches, pas de l'endroit où ils sont dessinés.

Comment trouver le cycle quand il n'y a pas d'ordre ?

La méthode DFS le montre directement : l'arête vers un nœud encore en cours de visite, avec le chemin des nœuds en cours de visite, forme le cycle. L'algorithme de Kahn dit seulement quels nœuds sont bloqués ; une recherche parmi eux trouve le cycle.

Puis-je choisir un ordre précis parmi les ordres valides ?

Oui. Dans l'algorithme de Kahn, quand plusieurs nœuds sont libres, prenez celui que vous préférez, par exemple la plus petite lettre ou la tâche la plus urgente. Une file de priorité donne l'ordre qui vient en premier alphabétiquement.

Comment le tri topologique sert-il pour les plus courts chemins ?

Sur un graphe orienté acyclique, relâcher les arêtes de chaque nœud dans l'ordre topologique trouve tous les plus courts chemins depuis un départ en un seul passage, même avec des arêtes négatives, plus vite que Dijkstra ou Bellman–Ford.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer le tri topologique