05 — Le tri topologique : ordonner des dépendances

Ce que tu vas apprendre

• Ce que produit un tri topologique et à quoi il sert
• L'algorithme de Kahn, par degrés entrants
• L'alternative par DFS
• Comment le tri topologique détecte aussi les cycles

Prérequis

• 04 — Détection de cycle et DAG
• La file et la pile (série Structures de données)

Le tri topologique répond à une question d'ordonnancement omniprésente : dans quel ordre exécuter des tâches qui dépendent les unes des autres ? Compiler des modules qui s'importent, installer des paquets aux dépendances imbriquées, planifier des étapes de build : tous ces problèmes reviennent à ordonner les sommets d'un DAG de façon que chaque sommet vienne après ceux dont il dépend. C'est exactement ce que fait le tri topologique.

Ce qu'il produit

Un tri topologique est un ordre linéaire des sommets tel que, pour chaque arête A→B, A apparaît avant B. Si A→B signifie « A doit être fait avant B », alors le tri topologique donne un ordre d'exécution valide.

DAG de dépendances :

  vaisselle → essuyage
  courses → cuisine
  cuisine → vaisselle

Un tri topologique valide :
  courses, cuisine, vaisselle, essuyage

Il peut exister plusieurs ordres valides (ici, « courses » et « cuisine » pourraient précéder ou suivre des tâches indépendantes). Le tri topologique en produit un parmi les valides. Il n'existe que pour un DAG : un cycle rend tout ordre impossible.

L'algorithme de Kahn (par degrés entrants)

La méthode la plus intuitive repose sur le degré entrant de chaque sommet, soit le nombre d'arêtes qui pointent vers lui (le nombre de dépendances non encore satisfaites). L'idée : un sommet sans dépendance peut être traité tout de suite. Une fois traité, on retire ses arêtes, ce qui peut libérer d'autres sommets.

pythonfrom collections import deque

def tri_topologique_kahn(graphe):
    # calculer le degré entrant de chaque sommet
    degre_entrant = {s: 0 for s in graphe}
    for s in graphe:
        for voisin in graphe[s]:
            degre_entrant[voisin] += 1

    # commencer par les sommets sans dépendance
    file = deque([s for s in graphe if degre_entrant[s] == 0])
    ordre = []
    while file:
        sommet = file.popleft()
        ordre.append(sommet)
        for voisin in graphe[sommet]:
            degre_entrant[voisin] -= 1     # une dépendance satisfaite
            if degre_entrant[voisin] == 0:  # plus de dépendance : prêt
                file.append(voisin)

    if len(ordre) != len(graphe):
        raise ValueError("Le graphe contient un cycle")
    return ordre

On enfile les sommets dès que leur dernière dépendance est levée. La complexité est O(V + E) : on visite chaque sommet et chaque arête une fois.

La détection de cycle gratuite

L'algorithme de Kahn détecte les cycles sans effort supplémentaire. Si à la fin l'ordre ne contient pas tous les sommets, c'est qu'il en restait avec un degré entrant non nul : ils font partie d'un cycle (chacun attend un autre, indéfiniment). C'est le lien direct avec l'article précédent : trier topologiquement, c'est aussi vérifier que le graphe est bien un DAG.

L'alternative par DFS

On peut aussi obtenir un tri topologique avec un DFS. L'astuce : quand le DFS finit de traiter un sommet (tous ses descendants sont explorés), on l'empile. L'ordre topologique est la pile inversée.

pythondef tri_topologique_dfs(graphe):
    visites = set()
    pile = []

    def visiter(sommet):
        visites.add(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visiter(voisin)
        pile.append(sommet)   # empilé une fois tous les descendants traités

    for s in graphe:
        if s not in visites:
            visiter(s)
    return pile[::-1]          # l'ordre est la pile inversée

L'intuition : un sommet n'est empilé qu'après tous ceux qui dépendent de lui (ses descendants dans le DFS). En inversant, il se retrouve avant eux. Cette version est en O(V + E) également. Elle est concise, mais pour détecter un cycle, elle demande d'ajouter la coloration gris/noir de l'article précédent ; la méthode de Kahn détecte le cycle naturellement, ce qui la rend souvent préférable en pratique.

Les usages

• Systèmes de build : Make, et la plupart des outils de build modernes, ordonnent les tâches par tri topologique sur le graphe de dépendances.
• Gestionnaires de paquets : déterminer l'ordre d'installation de paquets aux dépendances imbriquées.
• Résolution de modules : l'ordre de chargement de modules qui s'importent mutuellement (et la détection des imports circulaires interdits).
• Planification de tâches et pipelines : ordonnancer des étapes avec des contraintes d'antériorité.
• Tableurs : recalculer les cellules dans l'ordre où leurs formules dépendent les unes des autres.

Le tri topologique conclut la partie « structure » des graphes. Les articles suivants passent à l'optimisation de chemins sur des graphes pondérés, en commençant par le plus connu : Dijkstra.

Sources

• Kahn, A. B. (1962). Topological sorting of large networks. Communications of the ACM, 5(11). (Algorithme de Kahn)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 22.4 "Topological Sort". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 4.2. Addison-Wesley.