如何基于依赖关系进行排序？

Question

我有一个类，这个类里面有一个“依赖”列表，指向其他同类型的类。

class Foo(Base):
    dependencies = []

class Bar(Base):
    dependencies = [Foo]

class Baz(Base):
    dependencies = [Bar]

我想根据这些类的依赖关系来排序它们生成的实例。在我的例子中，我希望Foo的实例排在最前面，然后是Bar，最后是Baz。

有什么好的方法来进行排序吗？

Answer 1

我上周也遇到过类似的问题——真希望那时候就知道有Stack Overflow！我找了找，后来意识到我有一个叫做DAG（有向无环图）的东西，因为我的依赖关系不能是递归的或循环的。然后我找到了一些关于如何排序这些图的算法的资料。我用了一种叫做深度优先遍历的方法，先找到叶子节点，然后把它们添加到排序列表中。

这里有一个我觉得很有用的页面：

有向无环图

Answer 2

这叫做拓扑排序。

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