Как сортировать по зависимости?

Question

У меня есть класс со списком «зависимостей», указывающих на другие классы того же базового типа.

class Foo(Base):
    dependencies = []

class Bar(Base):
    dependencies = [Foo]

class Baz(Base):
    dependencies = [Bar]

Я хотел бы отсортировать экземпляры этих классов на основе их зависимостей. В моем примере я ожидал, что сначала появятся экземпляры Foo, затем Bar, затем Baz.

Как лучше всего отсортировать это?

Answer 1

Это называется топологической сортировкой.

def sort_deps(objs):
    queue = [objs with no dependencies]
    while queue:
        obj = queue.pop()
        yield obj
        for obj in objs:
            if dependencies are now satisfied:
                queue.append(obj)
    if not all dependencies are satisfied:
        error
    return result

Answer 2

У меня был похожий вопрос только на прошлой неделе - хотел бы я знать о переполнении стека! Я немного поохотился, пока не понял, что у меня есть DAG (направленный ациклический график, поскольку мои зависимости не могут быть рекурсивными или круговыми). Затем я нашел несколько ссылок на алгоритмы для их сортировки. Я использовал обход в глубину, чтобы добраться до конечных узлов и сначала добавить их в отсортированный список.

Вот страница, которая мне показалась полезной:

Направленные ациклические графы