Problème — Ordonnancement de tâches et détection d'interblocage

Les graphes · niveau 3 (difficile)

Énoncé

Problème — Ordonnancement de tâches et détection d'interblocage.

Un projet comporte des tâches, certaines ne pouvant commencer qu'après d'autres. On modélise les dépendances par un graphe orienté : un arc $(A, B)$ signifie « la tâche $A$ doit être réalisée avant la tâche $B$ ». Un ordonnancement valide n'existe que si le graphe est acyclique.

Écrire ordonnancable(taches) indiquant si un ordre de réalisation existe (absence de cycle).
Si oui, écrire ordre_taches(taches) renvoyant un ordre valide (tri topologique).

Corrigé

La première question est une détection de cycle dans un graphe orienté (coloriage en trois états). La seconde réalise un tri topologique fondé sur les degrés entrants (algorithme de Kahn) : on retire répétitivement un sommet sans dépendance restante.


from collections import deque

def ordonnancable(taches):
    BLANC, GRIS, NOIR = 0, 1, 2
    couleur = {u: BLANC for u in taches}

    def explorer(u):
        couleur[u] = GRIS
        for v in taches[u]:
            if couleur[v] == GRIS:
                return False        # cycle : non ordonnancable
            if couleur[v] == BLANC and not explorer(v):
                return False
        couleur[u] = NOIR
        return True

    return all(explorer(u) for u in taches if couleur[u] == BLANC)

def ordre_taches(taches):
    # calcul des degres entrants
    entrant = {u: 0 for u in taches}
    for u in taches:
        for v in taches[u]:
            entrant[v] += 1
    # file des taches sans dependance
    file = deque(u for u in taches if entrant[u] == 0)
    ordre = []
    while file:
        u = file.popleft()
        ordre.append(u)
        for v in taches[u]:
            entrant[v] -= 1
            if entrant[v] == 0:
                file.append(v)
    if len(ordre) != len(taches):
        return None                 # presence d'un cycle
    return ordre

taches = {
    "fondations": ["murs"],
    "murs":       ["toit", "fenetres"],
    "toit":       [],
    "fenetres":   ["peinture"],
    "peinture":   [],
}
print(ordonnancable(taches))   # True
print(ordre_taches(taches))
# ['fondations', 'murs', 'toit', 'fenetres', 'peinture']

Les deux algorithmes reposent sur un parcours en $O (n + m)$ . Le tri topologique de Kahn renvoie None si un cycle empêche d'ordonnancer toutes les tâches, détectant ainsi un éventuel interblocage.