python - 如何根据依赖排序？

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