如何根据依赖进行排序？

问题描述

我有一个类，它具有指向相同基类型的其他类的依赖关系列表。

I have an class that has a list of "dependencies" pointing to other classes of the same base type.

class Foo(Base):
    dependencies = []

class Bar(Base):
    dependencies = [Foo]

class Baz(Base):
    dependencies = [Bar]

我想对这些类生成的实例进行排序对他们的依赖。在我的例子中，我希望Foo的实例先到，然后是Bar，然后是Baz。

I'd like to sort the instances these classes generate based on their dependencies. In my example I'd expect instances of Foo to come first, then Bar, then Baz.

最好的排序方式是什么？

What's the best way to sort this?

推荐答案

这被称为拓扑排序。

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

这篇关于如何根据依赖进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！