Joyeux Noël | Python Fiddle

'''2'''

def topSort(deps):
    """ Retourne la liste des tâches triées dans un ordre 
        compatible avec les contraintes de dépendances.
        
        Pour chaque tâche u, deps[u] est la liste des tâches
        qui dépendent de u.
    """
    #étape 1
    n = len (deps)
    counts = [0 for k in range (n)]
    for i in range (n) :
        for j in range (len(deps[i])) :
            counts[ deps[i][j] ] += 1
    #étape 2
    nodeps = []
    for k in range (n) :
        if counts[k] == 0 :
            nodeps.append(k)
    #étape 3
    sortedTasks = []
    #étape 4
    while len(nodeps) > 0 :
        u = nodeps.pop()
        #étape 5
        sortedTasks.append(u)
        #étape 6
        for i in range (len(deps[u])) :
            counts[ deps[u][i] ] -= 1
            if counts[ deps[u][i] ] == 0 :
                nodeps.append(deps[u][i])
    #étape 7 (la boucle while permet de revenir à l'étape 4 si nodeps n'est pas vide)
    return (sortedTasks)
    
'''4'''

def getTasks(depsfile):
    tasks=[]
    fichier = open(depsfile,"r")
    for line in fichier :
        ligne = line.split()
        for i in ligne:
            if i not in tasks :
                tasks.append(i)
    return tasks

'''6'''

def getDeps(depsfile, tasks):
    """ Retourne un tableau deps de même longueur que tasks
        tel que deps[u] contienne la liste des numéros de tâches
        qui dépendent de la tâche numéro u.      
    """
    deps = [ [] for k in range (len(tasks)) ]
    fichier = open(depsfile,"r")
    for line in fichier:
        ligne = line.split()
        if tasks.index(ligne[1]) not in deps[ tasks.index(ligne[0]) ] :
            deps[ tasks.index(ligne[0]) ].append(tasks.index(ligne[1]))
    fichier.close()
    return deps

'''8'''

def reverseDeps(deps):
    """ Retourne une représentation des dépendances sous la forme
        d'un tableau rdeps tel que rdeps[v] contienne la liste
        de tous les numéros de tâche dont dépend la tâche numéro
        v.
    """
    rdeps = [ [] for k in range (len(deps))]
    for i in range (len(deps)) :
        for j in range (len(deps[i])) :
            rdeps[ deps[i][j] ].append(i)
    return rdeps

'''9'''

def testSortedTasks(depsfile):
    """ Construit le tableau `deps` à partir du fichier `depsfile`,
        génère la liste des tâches triées par topSort
        puis vérifie que l'ordre des tâches est bien compatible
        avec les contraintes de dépendances.
        
        La fonction retourne True si la liste est correctement
        triée. Elle retourne False sinon.
    """
    tasks = getTasks(depsfile)
    deps = getDeps(depsfile,tasks)
    rdeps = reverseDeps(deps)
    triees = topSort(deps)
    n= len(triees)
    res = True
    k = 0
    while k < n and res :
        i = k+1
        while i < n and res :
            if triees[i] in rdeps[triees[k]] :
                res = False
            i += 1
        k += 1
    return res

'''10'''

def genSortedTasks(depsfile, tasksfile):
    """ Crée le fichier tasksfile qui donne la liste les
        mnémoniques des tâches dans un ordre compatible avec les
        contraintes de dépendances définies dans le fichier 
        depsfile.
    
        Le fichier contient une ligne par tâche.
    """
    fichier = open(tasksfile,"w")
    tasks = getTasks(depsfile)
    deps = getDeps(depsfile,tasks)
    rdeps = reverseDeps(deps)
    triees = topSort(deps)
    for i in range (len(triees)) :
        fichier.write(tasks[triees[i]])
        fichier.write("\n")
    fichier.close()
    return tasksfile

Python Fiddle

Python Cloud IDE