Ordonnez un graphe sans circuit

Vous devez exécuter une chaîne de traitements de données : extraire, nettoyer, joindre, calculer des variables, entraîner un modèle, publier un tableau de bord. Certaines étapes dépendent d’autres, certaines peuvent tourner en parallèle, et si quelqu’un introduit par erreur une dépendance circulaire, rien ne peut démarrer. Dans quel ordre lancer les tâches ?

C’est la question du tri topologique, qui ne se pose que sur un graphe sans circuit. Ce chapitre vous montre comment reconnaître ces graphes, les ranger par niveaux et détecter un circuit caché.

Le fil rouge : un pipeline de données

Voici un pipeline de dix tâches. Un arc $x \to y$ signifie « $y$ a besoin du résultat de $x$ ».

Tâche	Dépend de
`ventes` (extraction des ventes)	rien
`clients` (extraction des clients)	rien
`calendrier` (jours fériés, vacances)	rien
`nett_ventes` (nettoyage)	`ventes`
`nett_clients` (nettoyage)	`clients`
`jointure`	`nett_ventes`, `nett_clients`
`features` (calcul des variables)	`jointure`, `calendrier`
`entrainement`	`features`
`evaluation`	`entrainement`
`tableau_de_bord`	`jointure`, `evaluation`

Un graphe orienté sans circuit (on dit aussi acyclique, et en anglais DAG, pour directed acyclic graph) est exactement ce qu’il faut pour décrire des dépendances : s’il y avait un circuit, par exemple features qui dépend de evaluation qui dépend de features, aucune des tâches du circuit ne pourrait commencer la première.

Mettre un graphe en niveaux

L’idée : éplucher le graphe

Dans un graphe sans circuit, il existe toujours au moins un sommet sans prédécesseur ( $d^-(x) = 0$ ), que l’on appelle une entrée ou une source. Pourquoi ? Partez de n’importe quel sommet et remontez les arcs à l’envers : comme il n’y a pas de circuit, vous ne repassez jamais deux fois au même endroit, et comme le graphe est fini, vous finissez par tomber sur un sommet sans prédécesseur.

D’où l’algorithme de mise en niveaux (on dit aussi le calcul du rang) :

Le niveau 0 regroupe les sommets sans prédécesseur.
On les retire du graphe (avec leurs arcs sortants). Les nouveaux sommets sans prédécesseur forment le niveau 1.
On recommence jusqu’à épuisement.

Sur le pipeline :

Niveau	Tâches
0	`ventes`, `clients`, `calendrier`
1	`nett_ventes`, `nett_clients`
2	`jointure`
3	`features`
4	`entrainement`
5	`evaluation`
6	`tableau_de_bord`

Tous les sommets ont reçu un niveau : le graphe est sans circuit. Le niveau d’un sommet est la longueur (en nombre d’arcs) du plus long chemin qui y arrive.

Les niveaux ont une lecture très concrète : toutes les tâches d’un même niveau sont indépendantes et peuvent tourner en parallèle. Avec assez de machines, le pipeline demande 7 « vagues » d’exécution, pas 10. C’est exactement ce que font les ordonnanceurs de workflows comme Airflow ou Dagster.

Tous les arcs descendent d'un niveau vers un niveau plus bas ; les tâches d'une même bande peuvent tourner en même temps.

Un tri topologique

Un tri topologique (ou ordre topologique) est une numérotation des sommets telle que chaque arc va d’un sommet vers un sommet de numéro plus grand. Autrement dit, un ordre d’exécution qui respecte toutes les dépendances. Lire les sommets niveau par niveau en donne un :

ventes, clients, calendrier, nett_ventes, nett_clients, jointure, features, entrainement, evaluation, tableau_de_bord.

Détecter un circuit

L’algorithme de Marimont

Que se passe-t-il si le graphe contient un circuit ? La mise en niveaux se bloque : à un moment, il reste des sommets, mais tous ont encore un prédécesseur. Les sommets d’un circuit ne perdent jamais tous leurs prédécesseurs, puisque chacun a son prédécesseur dans le circuit.

L’algorithme de Marimont, vu en cours, exploite cette idée des deux côtés : il retire itérativement les entrées ( $d^- = 0$ ) et les sorties ( $d^+ = 0$ ). Si le graphe se vide, il est sans circuit ; s’il reste des sommets, le graphe contient un circuit, et les sommets restants contiennent tous les circuits (ainsi que les chemins qui les relient).

Marimont retire les entrées et les sorties (passes 1 et 2), puis se bloque : les cinq tâches restantes forment le circuit créé par le nouvel arc.

L’algorithme de Kahn : la même idée, en temps linéaire

Retirer « physiquement » des sommets à chaque niveau coûte cher si l’on recalcule tout. L’algorithme de Kahn (complément standard) fait la même chose efficacement : il tient à jour le demi-degré intérieur de chaque sommet et une file des sommets devenus libres.

from collections import deque

def tri_topologique(succ):
    """Algorithme de Kahn. succ : dictionnaire sommet -> liste de successeurs."""
    d_moins = {x: 0 for x in succ}
    for x in succ:
        for y in succ[x]:
            d_moins[y] += 1
    file = deque(x for x in succ if d_moins[x] == 0)    # les entrées
    ordre = []
    while file:
        x = file.popleft()
        ordre.append(x)
        for y in succ[x]:                  # on « retire » x : ses successeurs perdent un prédécesseur
            d_moins[y] -= 1
            if d_moins[y] == 0:
                file.append(y)
    if len(ordre) < len(succ):
        raise ValueError("circuit détecté : pas de tri topologique")
    return ordre

pipeline = {
    "ventes": ["nett_ventes"], "clients": ["nett_clients"], "calendrier": ["features"],
    "nett_ventes": ["jointure"], "nett_clients": ["jointure"],
    "jointure": ["features", "tableau_de_bord"], "features": ["entrainement"],
    "entrainement": ["evaluation"], "evaluation": ["tableau_de_bord"], "tableau_de_bord": [],
}
print(tri_topologique(pipeline))

Chaque sommet entre une fois dans la file, et chaque arc fait baisser un compteur une fois : la complexité est en $O(n + m)$ . Si la file se vide alors que tous les sommets n’ont pas été traités, les restants ne perdront jamais leurs prédécesseurs : il y a un circuit.

Avec un parcours en profondeur

Le DFS du chapitre 2 fournit une autre méthode, tout aussi linéaire. Dans un graphe sans circuit, quand l’exploration d’un sommet $x$ se termine, tous ses descendants sont déjà terminés. Donc :

Sur le pipeline, avec les tâches parcourues dans l’ordre du tableau, le DFS termine d’abord tableau_de_bord, puis evaluation, entrainement, features, jointure, nett_ventes, ventes, etc. En lisant les dates de fin à l’envers, on obtient : calendrier, clients, nett_clients, ventes, nett_ventes, jointure, features, entrainement, evaluation, tableau_de_bord. C’est un ordre différent de celui de Kahn, mais tout aussi valide.

Deux tris topologiques différents du même pipeline : dans chacun, chaque arc va vers la droite, donc chaque tâche passe après ses dépendances.

Pourquoi c’est si utile

Les graphes sans circuit ont une propriété précieuse : on peut y résoudre en un seul passage, dans l’ordre topologique, des problèmes qui sont difficiles ailleurs. Quand on traite un sommet, tous ses prédécesseurs ont déjà été traités, donc leur résultat est définitif.

Plus courts et plus longs chemins : en relâchant les arcs dans l’ordre topologique, on obtient les plus courts chemins en $O(n + m)$ , même avec des arcs négatifs, et les plus longs chemins avec le même algorithme (en remplaçant min par max). Sur un graphe quelconque, le plus long chemin élémentaire est un problème NP-difficile ! Nous nous en servirons au chapitre 7 et surtout au chapitre 8, pour l’ordonnancement de projets.
Programmation dynamique : tout calcul par récurrence (suite de Fibonacci, distance d’édition) se ramène à un graphe sans circuit de sous-problèmes, traité dans l’ordre topologique.
Compilation, tableurs, gestionnaires de paquets : un tableur recalcule les cellules dans l’ordre topologique de leurs formules, et signale une « référence circulaire » quand il détecte un circuit. Un gestionnaire de paquets comme pip ou npm installe les dépendances dans l’ordre topologique.

import networkx as nx

G = nx.DiGraph([(x, y) for x, succ in pipeline.items() for y in succ])
print(nx.is_directed_acyclic_graph(G))           # True
print(list(nx.topological_sort(G)))              # un tri topologique
print(list(nx.topological_generations(G)))       # les niveaux, vague par vague

G.add_edge("evaluation", "nett_ventes")          # la dépendance fautive
print(nx.find_cycle(G))                          # les arcs d'un circuit

En résumé

Un graphe sans circuit (DAG) modélise des dépendances ; il a toujours au moins une entrée ( $d^- = 0$ ) et une sortie ( $d^+ = 0$ ).
La mise en niveaux retire les entrées vague par vague ; les sommets d’un même niveau sont indépendants et peuvent être traités en parallèle.
Un tri topologique existe si et seulement si le graphe est sans circuit ; il n’est pas unique.
Marimont retire entrées et sorties : s’il reste des sommets, il y a un circuit. Kahn fait le tri en $O(n + m)$ avec des compteurs de degrés.
Avec un DFS, l’ordre des dates de fin décroissantes est topologique, et un arc arrière révèle un circuit.
Sur un DAG, plus courts et plus longs chemins se calculent en un seul passage dans l’ordre topologique.

Exercices

Exercice · Mettre en niveaux

facile

Un cursus comporte six cours avec des prérequis : Algo (aucun), Maths (aucun), Graphes (Algo, Maths), Proba (Maths), Stats (Proba), Apprentissage (Graphes, Stats). Mettez le graphe en niveaux et donnez deux tris topologiques différents. Combien de semestres faut-il au minimum, si l’on peut suivre autant de cours que l’on veut par semestre ?

Voir la solution

Niveau 0 : Algo, Maths.
Niveau 1 : Graphes (ses deux prérequis sont au niveau 0), Proba.
Niveau 2 : Stats.
Niveau 3 : Apprentissage (il attend Stats).

Deux tris topologiques : (Algo, Maths, Graphes, Proba, Stats, Apprentissage) et (Maths, Proba, Stats, Algo, Graphes, Apprentissage). Il faut au minimum 4 semestres : c’est le nombre de niveaux, déterminé par la plus longue chaîne de prérequis Maths → Proba → Stats → Apprentissage.

En code

Python
R

prerequis = {"Algo": [], "Maths": [], "Graphes": ["Algo", "Maths"], "Proba": ["Maths"],
             "Stats": ["Proba"], "Apprentissage": ["Graphes", "Stats"]}

restants, niveaux = dict(prerequis), []
while restants:
    # les cours dont aucun prérequis ne reste à suivre forment le niveau suivant
    niveau = [c for c, pre in restants.items() if not any(p in restants for p in pre)]
    if not niveau:
        raise ValueError("circuit dans les prérequis")
    niveaux.append(niveau)
    for c in niveau:
        del restants[c]

for k, niveau in enumerate(niveaux):
    print(k, niveau)
# 0 ['Algo', 'Maths']
# 1 ['Graphes', 'Proba']
# 2 ['Stats']
# 3 ['Apprentissage']
print(len(niveaux), "semestres")   # 4 semestres

prerequis <- list(Algo = c(), Maths = c(), Graphes = c("Algo", "Maths"), Proba = "Maths",
                  Stats = "Proba", Apprentissage = c("Graphes", "Stats"))

restants <- names(prerequis); niveaux <- list()
while (length(restants) > 0) {
  # les cours dont aucun prérequis ne reste à suivre forment le niveau suivant
  libres <- restants[sapply(restants, function(c) !any(prerequis[[c]] %in% restants))]
  if (length(libres) == 0) stop("circuit dans les prérequis")
  niveaux[[length(niveaux) + 1]] <- libres
  restants <- setdiff(restants, libres)
}
str(niveaux)       # Algo Maths ; Graphes Proba ; Stats ; Apprentissage
length(niveaux)    # 4 semestres

Exercice · Dérouler Kahn sur un graphe à circuit

moyen

Déroulez l’algorithme de Kahn sur le graphe de sommets a, b, c, d, e et d’arcs a → b, b → c, c → d, d → b, a → e. Que renvoie-t-il ? Que donne l’algorithme de Marimont ?

Voir la solution

Demi-degrés intérieurs : a : 0, b : 2 (a et d), c : 1, d : 1, e : 1. La file contient a.

On sert a : b passe à 1, e passe à 0 et entre dans la file.
On sert e : il n’a pas de successeur.

La file est vide, mais seuls a et e ont été traités : b, c et d restent bloqués (b attend toujours d, qui attend c, qui attend b). Kahn signale un circuit.

Marimont : on retire l’entrée a et la sortie e. Il reste b, c, d, qui ont chacun un prédécesseur et un successeur : on s’arrête, et ces trois sommets forment bien le circuit b → c → d → b.

En code

Python
R

from collections import deque

succ = {"a": ["b", "e"], "b": ["c"], "c": ["d"], "d": ["b"], "e": []}

# Kahn : on sert les sommets dont le demi-degré intérieur tombe à 0
d_moins = {x: 0 for x in succ}
for x in succ:
    for y in succ[x]:
        d_moins[y] += 1
file, ordre = deque(x for x in succ if d_moins[x] == 0), []
while file:
    x = file.popleft()
    ordre.append(x)
    for y in succ[x]:
        d_moins[y] -= 1
        if d_moins[y] == 0:
            file.append(y)
print(ordre, [x for x in succ if x not in ordre])   # ['a', 'e'] ['b', 'c', 'd'] : circuit

# Marimont : on retire entrées et sorties tant qu'il y en a
restants = set(succ)
while True:
    retirables = {x for x in restants
                  if not any(x in succ[p] for p in restants)          # entrée
                  or not any(y in restants for y in succ[x])}         # sortie
    if not retirables:
        break
    restants -= retirables
print(sorted(restants))   # ['b', 'c', 'd'] : le circuit b -> c -> d -> b

succ <- list(a = c("b", "e"), b = "c", c = "d", d = "b", e = c())

# Kahn : on sert les sommets dont le demi-degré intérieur tombe à 0
d_moins <- table(factor(unlist(succ), levels = names(succ)))
file <- names(succ)[d_moins == 0]; ordre <- c()
while (length(file) > 0) {
  x <- file[1]; file <- file[-1]; ordre <- c(ordre, x)
  for (y in succ[[x]]) {
    d_moins[y] <- d_moins[y] - 1
    if (d_moins[y] == 0) file <- c(file, y)
  }
}
ordre                              # "a" "e"
setdiff(names(succ), ordre)        # "b" "c" "d" : circuit

# Marimont : on retire entrées et sorties tant qu'il y en a
restants <- names(succ)
repeat {
  entree <- sapply(restants, function(x) !any(sapply(restants, function(p) x %in% succ[[p]])))
  sortie <- sapply(restants, function(x) !any(succ[[x]] %in% restants))
  if (!any(entree | sortie)) break
  restants <- restants[!(entree | sortie)]
}
restants                           # "b" "c" "d" : le circuit b -> c -> d -> b

Exercice · Plus long chemin dans un DAG

difficile

Dans le pipeline du fil rouge, on connaît la durée de chaque tâche en minutes : ventes 10, clients 5, calendrier 1, nett_ventes 8, nett_clients 4, jointure 6, features 12, entrainement 30, evaluation 5, tableau_de_bord 3. Avec des machines en nombre illimité, quelle est la durée minimale du pipeline ? Expliquez comment la calculer en un seul passage.

Voir la solution

On note $f(x)$ la date de fin au plus tôt de la tâche $x$ : $f(x) = \text{durée}(x) + \max f(p)$ sur ses prédécesseurs $p$ (0 s’il n’y en a pas). En traitant les tâches dans l’ordre topologique, les prédécesseurs sont toujours déjà calculés :

ventes 10, clients 5, calendrier 1 ;
nett_ventes $10 + 8 = 18$ , nett_clients $5 + 4 = 9$ ;
jointure $\max(18, 9) + 6 = 24$ ;
features $\max(24, 1) + 12 = 36$ ;
entrainement $36 + 30 = 66$ ; evaluation $66 + 5 = 71$ ;
tableau_de_bord $\max(24, 71) + 3 = 74$ .

La durée minimale est de 74 minutes. C’est la longueur (pondérée par les durées) du plus long chemin ventes → nett_ventes → jointure → features → entrainement → evaluation → tableau_de_bord, le chemin critique : accélérer clients ne sert à rien, accélérer l’entraînement si. Nous formaliserons cette méthode au chapitre 8.

En code

Python
R

duree = {"ventes": 10, "clients": 5, "calendrier": 1, "nett_ventes": 8, "nett_clients": 4,
         "jointure": 6, "features": 12, "entrainement": 30, "evaluation": 5, "tableau_de_bord": 3}
pred = {"ventes": [], "clients": [], "calendrier": [], "nett_ventes": ["ventes"],
        "nett_clients": ["clients"], "jointure": ["nett_ventes", "nett_clients"],
        "features": ["jointure", "calendrier"], "entrainement": ["features"],
        "evaluation": ["entrainement"], "tableau_de_bord": ["jointure", "evaluation"]}

fin, avant = {}, {}
for x in pred:                          # les tâches sont déjà rangées dans un ordre topologique
    p = max(pred[x], key=lambda q: fin[q], default=None)   # prédécesseur qui finit le plus tard
    fin[x] = duree[x] + (fin[p] if p else 0)
    avant[x] = p
print(fin["tableau_de_bord"])           # 74

chemin, x = [], "tableau_de_bord"
while x:                                # on remonte le chemin critique
    chemin.append(x)
    x = avant[x]
print(" -> ".join(reversed(chemin)))
# ventes -> nett_ventes -> jointure -> features -> entrainement -> evaluation -> tableau_de_bord

duree <- c(ventes = 10, clients = 5, calendrier = 1, nett_ventes = 8, nett_clients = 4,
           jointure = 6, features = 12, entrainement = 30, evaluation = 5, tableau_de_bord = 3)
pred <- list(ventes = c(), clients = c(), calendrier = c(), nett_ventes = "ventes",
             nett_clients = "clients", jointure = c("nett_ventes", "nett_clients"),
             features = c("jointure", "calendrier"), entrainement = "features",
             evaluation = "entrainement", tableau_de_bord = c("jointure", "evaluation"))

fin <- c(); avant <- c()
for (x in names(pred)) {               # les tâches sont déjà dans un ordre topologique
  p <- pred[[x]]
  if (length(p) == 0) { fin[x] <- duree[x]; avant[x] <- NA }
  else {
    q <- p[which.max(fin[p])]          # prédécesseur qui finit le plus tard
    fin[x] <- duree[x] + fin[q]; avant[x] <- q
  }
}
fin["tableau_de_bord"]                 # 74

chemin <- c(); x <- "tableau_de_bord"
while (!is.na(x)) { chemin <- c(x, chemin); x <- avant[[x]] }
paste(chemin, collapse = " -> ")
# ventes -> nett_ventes -> jointure -> features -> entrainement -> evaluation -> tableau_de_bord