Calculateur de Tri Topologique

Calculateur de Tri Topologique

Le Calculateur de tri topologique calcule un ordonnancement linéaire des sommets d'un graphe orienté acyclique (DAG) tel que pour chaque arête orientée de u vers v, u soit placé avant v. Entrez votre graphe sous forme de liste d'arêtes ou de liste d'adjacence et l'outil renvoie l'ordre topologique en utilisant l'algorithme de Kahn ou le post-ordre DFS, détecte les cycles (avec le chemin exact du cycle), regroupe les tâches en couches d'exécution parallèle, compte le nombre d'ordres valides et anime chaque étape sur un graphe interactif.

Qu'est-ce qu'un tri topologique ?

Étant donné un graphe orienté G = (V, E), un tri topologique (ou ordonnancement topologique) est une disposition linéaire v₁, v₂, …, vₙ de ses sommets telle que pour chaque arête orientée (u → v), u apparaisse avant v dans la disposition. Un ordonnancement topologique existe si et seulement si le graphe n'a pas de cycles orientés — c'est-à-dire que le graphe est un DAG. L'ordre est rarement unique : un graphe peut avoir de nombreux tris topologiques valides lorsque plusieurs sommets ont un degré entrant nul simultanément.

Algorithmes utilisés par ce calculateur

Algorithme de Kahn (basé sur BFS, 1962)

L'algorithme de Kahn est le tri topologique le plus intuitif. À chaque étape, il choisit un sommet avec un degré entrant nul (aucune arête entrante), l'ajoute à la sortie et le "supprime" du graphe en décrémentant le degré entrant de chacun de ses successeurs. Lorsque plusieurs sommets ont un degré entrant nul, la résolution des égalités peut utiliser un min-heap (donnant l'ordonnancement lexicographique le plus petit) ou une file FIFO (donnant l'ordre d'insertion). L'algorithme de Kahn s'exécute en temps O(|V| + |E|) et sert également de détecteur de cycle : si un sommet a encore un degré entrant > 0 après que la file s'est vidée, le graphe possède un cycle.

Post-ordre DFS (Tarjan, 1976)

L'algorithme DFS exécute une recherche en profondeur, et chaque fois qu'un sommet est terminé (c'est-à-dire que tous ses successeurs ont été entièrement explorés), il est poussé sur une pile. Inverser la pile à la fin produit un ordre topologique valide. La détection de cycle est naturelle : rencontrer un sommet qui est encore en cours (marqué GRIS) signifie qu'une arête arrière a été trouvée, donc le graphe n'est pas un DAG. Le post-ordre DFS s'exécute également en temps O(|V| + |E|).

Couches d'exécution parallèle

Une vue par couches d'un DAG partitionne ses sommets en niveaux de sorte que chaque arête passe d'un niveau inférieur à un niveau supérieur. Les sommets d'une même couche sont indépendants les uns des autres, ils peuvent donc être exécutés en parallèle. Le nombre de couches est égal à la longueur du chemin le plus long plus un — c'est le chemin critique du DAG, le nombre minimum de tours séquentiels nécessaires pour terminer toutes les tâches, même avec un parallélisme illimité. Ce calculateur produit automatiquement la vue par couches chaque fois que l'entrée est un DAG.

Détection de cycle

Si le graphe contient un cycle orienté, aucun tri topologique n'est possible. Notre calculateur rapporte le chemin exact du cycle (ex: A → B → C → A) et met en évidence les arêtes du cycle en rouge sur la visualisation. La suppression d'une seule arête sur le cycle suffit à restaurer l'acyclicité.

Formats d'entrée

Liste d'arêtes

Écrivez chaque arête orientée sous la forme source -> cible, séparée par des virgules ou des retours à la ligne. Variantes de flèches acceptées : ->, →, =>, -->, :. Vous pouvez également enchaîner les arêtes : A -> B -> C est un raccourci pour A->B et B->C. Les étiquettes de sommets peuvent être des lettres, des chiffres, des underscores, des tirets et des points.

Liste d'adjacence

Écrivez chaque sommet, deux-points, et ses successeurs directs (sommets vers lesquels il pointe). Un sommet sans successeur a toujours besoin de sa ligne, telle que D:.

Comment utiliser ce calculateur

1. Choisir un format : Basculez entre liste d'arêtes et liste d'adjacence avec les boutons radio.
2. Entrer le graphe : Collez vos données ou cliquez sur l'un des exemples rapides (ordre d'habillage, prérequis de cours, cibles de construction, un graphe avec un cycle, etc.).
3. Choisir un algorithme : Kahn lexicographique pour un ordre unique et reproductible ; ordre d'insertion pour préserver l'ordonnancement d'entrée ; post-ordre DFS pour la méthode classique en profondeur ; ou Tout afficher pour voir chaque ordre côte à côte.
4. Cliquez sur "Trier topologiquement" : L'ordre, la détection de cycle, la vue par couches, la longueur du chemin critique, le nombre total d'ordres valides et un graphe interactif apparaissent ci-dessous.
5. Explorer : Appuyez sur Lecture pour voir chaque sommet être émis une étape à la fois. Les badges de degré entrant se mettent à jour en direct. Faites glisser n'importe quel nœud pour réorganiser la disposition.

Applications dans le monde réel

Systèmes de construction et compilateurs

Des outils comme make, Bazel, Gradle et npm trient topologiquement leurs cibles de construction afin que chaque cible soit compilée seulement après toutes ses dépendances. Un cycle dans le graphe de dépendance est généralement signalé comme une erreur fatale — le système de construction ne peut pas décider par où commencer.

Planification de tâches

Les gestionnaires de projet utilisent des DAG pour capturer les dépendances des tâches. Le tri topologique donne un ordre d'exécution valide, et la vue par couches donne le nombre minimum de tours sous un parallélisme illimité. La chaîne la plus longue est le chemin critique qui détermine la durée du projet.

Planification des prérequis de cours

Un catalogue de cours universitaires est un DAG : les arêtes sont des relations de prérequis. Un ordre topologique est un plan d'étude valide, et les couches indiquent aux étudiants quels ensembles de cours ils peuvent suivre en parallèle au cours de chaque semestre.

Recalcul de feuilles de calcul

Lorsqu'une cellule change, un tableur doit recalculer chaque cellule en aval dans l'ordre des dépendances — un tri topologique du DAG de dépendance des cellules. Les références circulaires (cycles) sont rejetées par l'application.

Gestionnaires de paquets et chargeurs de plugins

Apt, pip, Homebrew, Maven et d'innombrables frameworks de plugins résolvent l'ordre d'installation ou de chargement en triant topologiquement leurs DAG de dépendance.

Résolution de symboles et ordonnancement d'instructions

Les compilateurs utilisent le tri topologique pour ordonner les déclarations, et les CPU utilisent des DAG de dépendance de données pour planifier les instructions dans le tampon de réordonnancement sans violer les hasards de données.

Compter les ordonnancements topologiques

Pour un DAG avec n sommets, le nombre de tris topologiques valides distincts peut varier de 1 (pour une chaîne totalement ordonnée) à n! (pour un graphe sans arêtes). Calculer le compte exact est un problème #P-complet en général, mais pour les graphes allant jusqu'à 16 sommets, ce calculateur les énumère en utilisant une formulation de programmation dynamique par masque binaire : f(S) = Σ f(S ∪ {v}) pour tous les v ∉ S dont les prédécesseurs sont tous dans S.

Complexité et performance

• Temps : L'algorithme de Kahn et le post-ordre DFS s'exécutent en O(|V| + |E|) — linéaire par rapport à la taille du graphe.
• Espace : O(|V|) pour le suivi du degré entrant et l'ordre de sortie, plus O(|V| + |E|) pour la structure d'adjacence.
• Détection de cycle : Intégrée aux deux algorithmes. Kahn détecte les cycles quand |sortie| < |V| ; DFS les détecte lorsqu'une arête arrière (voisin GRIS) est trouvée.
• Limites de cet outil : jusqu'à 80 sommets et 800 arêtes pour la visualisation interactive. Le comptage des ordres est limité à 16 sommets.

Foire aux questions

Qu'est-ce qu'un tri topologique ?

Un tri topologique d'un graphe orienté acyclique est un ordonnancement linéaire de ses sommets tel que chaque arête orientée de u vers v place u avant v. Il représente un ordre valide pour traiter des tâches respectant leurs dépendances.

Quel algorithme ce calculateur utilise-t-il ?

Le calculateur exécute l'algorithme de Kahn et le post-ordre DFS. L'algorithme de Kahn supprime de manière répétée un sommet de degré entrant nul et décrémente les degrés entrants de ses successeurs. Le post-ordre DFS exécute une recherche en profondeur et inverse l'ordre de fin. Les deux s'exécutent en temps O(|V| + |E|).

Et si mon graphe a un cycle ?

Un graphe avec un cycle orienté n'a pas de tri topologique. Le calculateur détecte le cycle, le met en évidence en rouge sur la visualisation et rapporte le chemin exact du cycle afin que vous puissiez voir quelles arêtes supprimer pour transformer le graphe en DAG.

Qu'est-ce que l'ordre topologique lexicographique le plus petit ?

Lorsque de nombreux ordres topologiques sont valides, le plus petit lexicographiquement est obtenu en choisissant toujours le sommet le plus petit par ordre alphabétique parmi ceux dont le degré entrant est nul à chaque étape. Le mode Kahn par défaut de ce calculateur renvoie cet ordre unique, stable et facile à reproduire.

Qu'est-ce que la vue par couches ou par niveaux ?

La vue par couches regroupe les sommets par la longueur du chemin le plus long depuis n'importe quelle source. Les sommets d'une même couche n'ont pas de dépendance entre eux, ils peuvent donc fonctionner en parallèle. Le nombre de couches est égal à la chaîne de dépendance la plus longue plus un et donne le nombre minimum de tours parallèles nécessaires pour terminer toutes les tâches.

Un graphe peut-il avoir de nombreux ordres topologiques valides ?

Oui. Si à n'importe quelle étape l'algorithme de Kahn possède plusieurs sommets de degré entrant nul, n'importe lequel d'entre eux peut être choisi ensuite. Ce calculateur compte le nombre exact d'ordres topologiques distincts pour les graphes allant jusqu'à 16 sommets.

Quelle est la différence entre l'algorithme de Kahn et le post-ordre DFS ?

Kahn travaille de haut en bas : il choisit de manière répétée les sources (degré entrant 0) et les émet en premier. Le post-ordre DFS travaille de bas en haut : il termine d'abord les puits et les ajoute au début de l'ordre. Les deux sont en O(|V| + |E|) et produisent des tris topologiques valides, mais généralement différents. Kahn est plus facile à paralléliser et à adapter pour l'ordre lexicographique ; DFS est plus facile à combiner avec d'autres analyses basées sur DFS comme les composantes fortement connexes.

Quelle est la taille maximale de graphe supportée par cet outil ?

Le calculateur prend en charge jusqu'à 80 sommets et 800 arêtes. Le comptage du nombre total d'ordres topologiques valides est limité à 16 sommets car le problème est #P-complet et l'espace d'état croît en 2ⁿ. La visualisation interactive et l'animation de l'algorithme fonctionnent de manière fluide jusqu'à la taille maximale.

Lectures complémentaires

• Tri topologique — Wikipédia
• Graphe orienté acyclique — Wikipédia
• Recherche en profondeur — Wikipédia
• Méthode du chemin critique — Wikipédia
• Composante fortement connexe — Wikipédia

Opérations mathématiques avancées:

• Calculatrice d'Antilogarithme
• Calculatrice de la fonction bêta
• Calculateur de Coefficient Binomial En vedette
• Calculatrice de distribution binomiale
• Calculatrice de Bit
• Calculateur du Théorème Central Limite
• Calculatrice de Combinaison En vedette
• Calculatrice de Fonction d'Erreur Complémentaire
• Calculatrice de Nombres Complexes
• Calculatrice d'Entropie
• Calculatrice de fonction d'erreur
• Calculatrice de désintégration exponentielle
• Calculatrice de croissance exponentielle
• Calculatrice d'intégrale exponentielle
• calculatrice-des-exposants-haute-précision En vedette
• Calculatrice Factorielle
• Calculatrice de Fonction Gamma En vedette
• Calculateur de Nombre d'Or
• Calculatrice de demi-vie
• Calculatrice du Taux de Croissance en Pourcentage
• Calculatrice de permutation
• Calculatrice de Distribution de Poisson
• Calculatrice des racines de polynômes avec étapes détaillées
• Calculatrice de probabilité
• Calculatrice de Distribution de Probabilité
• Calculatrice de Proportion
• Calculatrice de Formule Quadratique
• Calculatrice Scientifique
• Calculatrice de notation scientifique
• Calculateur de Chiffres Significatifs Nouveau
• Calculatrice de Somme de Cubes
• Calculatrice de la somme des entiers positifs
• Calculatrice de la somme des carrés
• Générateur de table de vérité
• Calculateur de Théorie des Ensembles
• Générateur de Diagramme de Venn (3 Ensembles)
• Calculatrice du Théorème des Restes Chinois
• Calculatrice de la fonction indicatrice d'Euler
• Calculatrice de l'Algorithme Euclidien Étendu
• Calculatrice de l'Inverse Multiplicatif Modulaire
• Calculatrice de fractions continues
• Calculateur de plus court chemin de Dijkstra
• Calculateur d'arbre couvrant minimum
• Validateur de séquence de degrés de graphe
• Calculateur de Dérangement (Sous-factorielle)
• Calculateur de Nombres de Stirling
• Calculateur du principe des tiroirs
• Calculateur d'état stationnaire de chaîne de Markov
• Calculateur d'Arrondi Nouveau
• Calculateur de Distribution Binomiale Négative Nouveau
• Calculateur de Permutations avec Répétition Nouveau
• Calculateur d'Exponentiation Modulaire Nouveau
• Calculateur de Racine Primitive
• Simplificateur d'Algèbre de Boole Nouveau
• Solveur de Tableau de Karnaugh (K-Map) Nouveau
• Calculateur de Coloration de Graphes Nouveau
• Calculateur de Tri Topologique Nouveau
• Calculateur de Matrice d'Adjacence Nouveau
• Calculateur d'Inclusion-Exclusion Nouveau
• Solveur de Programmation Linéaire Nouveau
• Solveur du Voyageur de Commerce (TSP) Nouveau
• Vérificateur de Chemin Hamiltonien Nouveau
• Vérificateur de Graphe Planaire Nouveau
• Calculateur de Flot Maximal dans un Réseau Nouveau
• Solveur du Problème des Mariages Stables Nouveau
• Calculateur d'Ordre en Théorie des Groupes Nouveau
• Calculateur d’Anneaux et de Corps Nouveau