Les graphes orientés acycliques (DAGs) et le tri topologique

Derrière la plupart des systèmes qui automatisent l’exécution de tâches (bases de données, pipelines CI/CD, moteurs de traitement de données, compilateurs, runtimes) se cache une même structure de données : le graphe orienté acyclique, ou DAG (Directed Acyclic Graph). C’est cette structure, et la garantie qu’elle apporte, qui rend possibles des optimisations aussi essentielles que la parallélisation ou la résolution fiable d’un ordre de dépendances. Encore faut-il comprendre pourquoi l’acyclicité n’est pas un détail théorique, et comment on en tire un ordre d’exécution concret.

Qu’est-ce qu’un DAG ?

Un DAG est, tout simplement, un graphe orienté qui ne contient aucun cycle, aucune « boucle ». Chaque arête a une direction, et il est impossible, en suivant ces directions, de revenir à un nœud déjà visité.

Cette absence de cycle est précisément ce qui distingue un DAG d’un graphe orienté quelconque. Un cycle peut se former de deux façons :

• De manière directe, entre deux nœuds : A dépend de B et B dépend de A. La dépendance circulaire est immédiate et facile à repérer.
• De manière indirecte, à travers une chaîne de nœuds : A → B → C → … → A. Plus la profondeur de la chaîne augmente, plus la détection devient coûteuse et complexe, sans parler des impacts sur les performances quand le graphe grandit.

Quel est le problème avec les cycles ?

Les cycles ne sont pas qu’une curiosité de théorie des graphes : ils introduisent des problématiques bien concrètes lors de la résolution et de l’interprétation d’un graphe de dépendances.

La conséquence directe est qu’un graphe contenant un cycle devient, au mieux, partiellement interprétable, et au pire totalement impossible à résoudre. Comment décider que A doit s’exécuter avant B si B doit lui-même s’exécuter avant A ? La question n’a pas de réponse. Il existe bien des stratégies pour détecter et casser ces cycles, mais elles ont toutes un coût non négligeable, en temps de calcul comme en complexité de l’implémentation.

C’est pourquoi garantir l’acyclicité en amont est si précieux : cela transforme un problème potentiellement insoluble en un problème qui admet toujours une solution.

Pourquoi les DAGs sont au cœur de l’orchestration de tâches

L’un des domaines qui s’appuie le plus directement sur les DAGs, et pas le moindre, est l’orchestration de tâches. Cela englobe une grande variété de systèmes :

• les bases de données ;
• les pipelines CI/CD et de traitement de données ;
• les workflows distribués ;
• les exécuteurs de tâches et orchestrateurs de ressources ;
• les compilateurs et les runtimes.

Tout système qui automatise l’exécution de tâches s’appuie, directement ou indirectement, sur les propriétés offertes par un DAG. Sans elles, il serait privé d’un grand nombre d’optimisations, la parallélisation au premier chef, qui sont souvent la raison même pour laquelle ces systèmes sont intéressants.

Un modèle d’exécution fondé sur un DAG offre en effet deux garanties fondamentales : il s’assure que toutes les dépendances requises par un nœud sont satisfaites avant de l’exécuter, et que l’ordre des dépendances est rigoureusement respecté. Ces deux propriétés sont le socle sur lequel reposent la correction et l’efficacité de l’orchestration.

Comment déterminer l’ordre d’exécution des tâches ?

Une fois que l’on dispose d’un DAG, reste à en extraire un ordre d’exécution exploitable. Plusieurs algorithmes propres aux DAGs permettent de le faire ; l’un des plus populaires est le tri topologique (topological sort).

Le tri topologique produit une séquence valide d’opérations au sein d’un DAG, en respectant l’ordre des dépendances : pour toute dépendance « un nœud doit en précéder un autre », la séquence place bien le premier avant le second.

Prenons un graphe composé de trois nœuds A, B et C, où la notation A → B signifie « A dépend de B ». Avec les dépendances A → B et B → C, le tri topologique nous indique que C doit être exécuté en premier, puis B, puis enfin A.

En analysant ainsi les nœuds d’un graphe et leurs dépendances, on détermine non seulement l’ordre d’exécution, mais aussi la nature de l’opération applicable : séquentielle ou parallèle. Dans l’exemple ci-dessus, aucune parallélisation n’est possible : A dépend de B, qui dépend lui-même de C. Tout doit se dérouler de manière strictement séquentielle. En revanche, si A dépendait à la fois de B et de C, mais que B et C étaient indépendants l’un de l’autre, le tri topologique révélerait que B et C peuvent être exécutés en parallèle avant de passer à A, exactement le genre d’optimisation que la structure rend possible.

Le tri topologique en pratique

Une façon classique de calculer un tri topologique est l’algorithme de Kahn, qui repose sur le degré entrant (in-degree) de chaque nœud, c’est-à-dire le nombre de dépendances non encore résolues. On commence par les nœuds sans dépendance, puis on « épluche » le graphe :

type Graph = Map<string, string[]>;

/**
 * Renvoie un ordre d'exécution valide (algorithme de Kahn).
 * Lève une erreur si le graphe contient un cycle : c'est précisément
 * la propriété d'acyclicité qui garantit qu'un ordre existe.
 */
function topologicalSort(graph: Graph): string[] {
  const inDegree = new Map<string, number>();
  for (const node of graph.keys()) inDegree.set(node, 0);
  for (const deps of graph.values()) {
    for (const dep of deps) {
      inDegree.set(dep, (inDegree.get(dep) ?? 0) + 1);
    }
  }

  // Les nœuds sans dépendance entrante sont prêts à être traités.
  const ready = [...inDegree].filter(([, d]) => d === 0).map(([n]) => n);
  const ordered: string[] = [];

  while (ready.length > 0) {
    const node = ready.shift()!;
    ordered.push(node);

    for (const dep of graph.get(node) ?? []) {
      const next = inDegree.get(dep)! - 1;
      inDegree.set(dep, next);
      if (next === 0) ready.push(dep);
    }
  }

  if (ordered.length !== graph.size) {
    throw new Error("Cycle détecté : aucun ordre topologique n'existe.");
  }

  return ordered;
}

Le détail à retenir n’est pas tant l’algorithme lui-même que ce qu’il révèle : si, à la fin du parcours, tous les nœuds n’ont pas été ordonnés, c’est qu’il restait des nœuds dont le degré entrant n’a jamais atteint zéro, autrement dit, un cycle. La détection de cycle n’est donc pas une étape séparée : elle tombe naturellement de l’algorithme. C’est l’illustration concrète du lien entre acyclicité et résolubilité.

Conclusion

Le DAG n’est pas une abstraction réservée aux cours d’algorithmique : c’est la fondation silencieuse de tout ce qui orchestre des tâches. Sa propriété centrale, l’absence de cycle, est ce qui transforme un graphe de dépendances en un problème toujours résoluble. Le tri topologique en est le corollaire pratique : il traduit cette structure en un ordre d’exécution concret, tout en révélant les opportunités de parallélisation et en signalant, le cas échéant, les dépendances circulaires.

Comprendre cette mécanique, c’est mieux saisir ce qui se passe sous le capot des compilateurs, des pipelines CI/CD et des orchestrateurs que l’on utilise au quotidien, et, le jour où l’on conçoit son propre moteur d’exécution, savoir sur quelles garanties s’appuyer.