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

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.