Сортировка Python с использованием cmp_to_key не меняет местами некоторые элементы

Question

Моя программа получила список для сортировки с использованием «прямых зависимостей», переданных как dict. Один должен появляться после других элементов, от которых он зависит.

Я использую functools.cmp_to_key, чтобы вернуть 1 или -1, когда сравниваемые элементы зависят друг от друга, или 0, если они не:

Вот мой MCVE:

Определение зависимостей:

def dependencies():
    return { "B" : ["A"], "C" : ["B","A"], "D" : ["C","B"] }

Функция сравнения:

def dependency_cmp(module_left, module_right):
    if module_right in dependencies() and module_left in dependencies()[module_right]:
        print( module_right + " needs " + module_left )
        return -1
    elif module_left in dependencies() and module_right in dependencies()[module_left]:
        print( module_left + " needs " + module_right )
        return 1
    else:
        print( module_left + " and " + module_right + " are independent" )
        return 0

Функция сортировки:

def doSort( the_list ):
    original = the_list[:]
    the_list.sort(key=cmp_to_key(lambda left, right: dependency_cmp(left,right)))
    print( "Dependencies [" + ",".join(original) + "] sorted to [" + ",".join(the_list) + "]" )

Затем, когда я звоню:

doSort( ["C","D","B","A"] )
doSort( ["B","E","A"] )

Он выводит:

D needs C
D needs B
D needs B
C needs B
C needs A
B needs A
Dependencies [C,D,B,A] sorted to [A,B,C,D]

, что правильно, но:

E and B are independent
A and E are independent
Dependencies [B,E,A] sorted to [B,E,A]

, что не правильно, ябудет ожидать, что на выходе будет [A,B,E] или [E,A,B] или [A,E,B], поскольку B нужно A, а E не нужно ...

Но как B, E и E, A порядок правильный, функция сортировки не проверяет B против A. Это имеет смысл, но это определенно не то, что я хочу. Вероятно, проблема связана с этим return 0. Я знаком с C ++, где sort функции возвращают логическое, а не целое число ...

Какова была бы лучшая стратегия для правильного упорядочивания этих списков?

Answer 1

Спасибо за комментарий Aran-Fey и использование кода toposort из Python: сортировка списка зависимостей :

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, set(names of dependancies))`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source]        
    emitted = []
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(set((name,)), emitted) # <-- pop self from dep, req Py2.6
            if deps:
                next_pending.append(entry)
            else:
                yield name
                emitted.append(name) # <-- not required, but preserves original order
                next_emitted.append(name)
        if not next_emitted:
            raise ValueError("cyclic dependancy detected: %s %r" % (name, (next_pending,)))
        pending = next_pending
        emitted = next_emitted

Затем:

def doSort( the_list ):
    original = the_list[:]

    source = []
    for item in the_list:
        source.append( [ item, set( dependencies()[item] ) if item in dependencies() else set() ] )

    the_list = [x for x in topological_sort( source )]

    print( "Dependencies [" + ",".join(original) + "] sorted to [" + ",".join(the_list) + "]" )

И, наконец, мыполучить ожидаемый результат:

Dependencies [C,D,B,A] sorted to [A,B,C,D]
Dependencies [B,E,A] sorted to [E,A,B]