Ordre des dépendances par parcours de graphe : BFS, DFS et tri topologique

Objectif

Étant donné des éléments qui dépendent les uns des autres (cibles de build, migrations de base de données, étapes de déploiement, modules), calculer un ordre dans lequel chaque élément vient après toutes ses dépendances, signaler explicitement les cycles, et trouver l'ensemble des éléments affectés par un changement.

Prérequis

Une liste de nœuds et d'arêtes orientées avec une lecture fixée, par exemple « A doit s'exécuter avant B ». Les deux sens fonctionnent tant que l'ensemble du programme n'en utilise qu'un seul. Les identités des nœuds doivent être uniques et comparables afin que les égalités puissent être départagées de façon déterministe.

Étapes

1. Construire deux listes d'adjacence (dépendances de chaque nœud, dépendants de chaque nœud) et un compte de degré entrant par nœud ; inclure les nœuds qui n'ont aucune arête du tout.
2. Ensemble affecté par parcours : en partant d'un nœud modifié, suivre les arêtes de dépendance inverse et rassembler les nœuds visités. Le parcours en largeur avec une file visite par distance, ce qui sépare les dépendants directs des dépendants transitifs ; le parcours en profondeur avec une pile explicite est équivalent pour l'ensemble obtenu. Marquer les nœuds comme visités avant de les mettre en file pour que les sous-graphes partagés et les cycles ne bouclent pas.
3. Ordre par l'algorithme de Kahn : mettre en file tout nœud de degré entrant nul ; en retirer un, l'émettre, décrémenter le degré entrant de chaque dépendant et mettre en file ceux qui atteignent zéro. Les nœuds jamais émis se trouvent sur un cycle ou derrière un cycle ; les signaler par leur nom.
4. Ordre alternatif par ordre post-fixe du DFS : visiter un nœud, récurser dans ses dépendances, puis l'ajouter en fin de liste. Un nœud rencontré alors qu'il est encore « en cours » referme un cycle ; conserver le chemin pour le message d'erreur. L'ordre d'ajout constitue un ordre de dépendance valide.
5. Ordonnancement parallèle : les nœuds prêts en même temps dans l'algorithme de Kahn peuvent s'exécuter simultanément. Le graphlib.TopologicalSorter de Python expose cela via prepare(), get_ready() et done(), et prepare() lève CycleError lorsqu'un cycle existe. Le tsort GNU lit des paires et écrit un ordre total cohérent avec l'ordre partiel qu'on lui donne.
6. Rendre les égalités déterministes en triant l'ensemble des nœuds prêts par nom ; sinon chaque exécution peut produire un ordre valide différent et les builds deviennent irreproductibles.
7. Tester avec un losange (A avant B et C, les deux avant D), un cycle, un nœud isolé et une longue chaîne pour vérifier la gestion de la profondeur.

Résultat attendu

Un ordre reproductible, un signalement de cycle qui nomme les nœuds impliqués, et un ensemble affecté utilisable pour des builds incrémentaux ou des exécutions de tests ciblées.

Limites et base de vérification

Seuls les graphes acycliques ont un ordre topologique ; un cycle est une erreur de modélisation à corriger, pas à contourner. Des dépendances non déclarées produisent un ordre qui paraît valide et qui est faux ; l'algorithme ne peut pas détecter des arêtes manquantes. Le DFS récursif est limité en profondeur sur de longues chaînes ; préférer la forme itérative. Le comportement des bibliothèques est tel que décrit dans la documentation citée.