python - 计算插件依赖

Question

我需要创建一个具有依赖性支持的插件系统，但我不确定解决依赖性的最佳方式。这些插件都将继承自一个基类，每个都有自己的 execute() 方法。在每个插件类中，我计划创建一个 dependencies 属性作为它所依赖的所有其他插件的列表。

加载插件时，我会导入所有插件并将它们放在一个列表中，并根据依赖项对它们进行排序。一旦它们都以正确的顺序排列(因此任何具有依赖性的东西都在其所述依赖性之后的列表中)我将遍历列表执行每个方法 execute() 方法。

我一直不清楚的是排序背后的逻辑。我可以开始按字母顺序排列它们，直到我遇到一个具有依赖项的依赖项 - 如果它的依赖项不在列表中，请将其放入 tmp 列表中。在第一轮导入结束时，从临时列表的末尾开始(除了具有依赖性的插件之外什么都没有的列表)并再次检查“运行列表”。如果我在“运行列表”中找到它的依赖项，请确保它的索引号高于其最高依赖项。如果它的依赖项不在列表中，请暂停它并移至临时列表中的下一个插件。一旦我到达 tmp 列表的末尾，从顶部开始并重试。一旦所有插件都排序完毕，或者 tmp 列表在遍历后没有改变大小 - 开始执行插件。

留在临时列表中的是没有找到依赖项或具有循环依赖项的插件。 (tmp 列表中的 2 个插件相互依赖)

如果您仍在阅读并且您能够遵循我的逻辑；这是一个合理的计划吗？有更简单的方法吗？如果我想为执行顺序实现序列号，是否有一种“简单”的方法来同时拥有序列和依赖项？ (如果存在冲突，则依赖性优先于排序)或者插件应该使用序列还是依赖性？ (先运行带序列号的插件，而不是带依赖的插件？)

长话短说

您将如何编写插件系统中计算依赖关系的逻辑？

---

编辑:

好吧——我想我从维基百科页面实现了拓扑排序；遵循其 DFS 的逻辑示例。它似乎有效，但我以前从未做过这样的事情。

http://en.wikipedia.org/wiki/Topological_sorting#Examples

data = {
    '10' :  ['11', '3'],
    '3'  :  [],
    '5'  :  [],
    '7'  :  [],
    '11' :  ['7', '5'],
    '9'  :  ['8', '11'],
    '2'  :  ['11'],
    '8'  :  ['7', '3']
}

L = []
visited = []

def nodeps(data):
    S = []
    for each in data.keys():
        if not len(data[each]):
            S.append(each)
    return S

def dependson(node):
    r = []
    for each in data.keys():
        for n in data[each]:
            if n == node:
                r.append(each)
    return r

def visit(node):
    if not node in visited:
        visited.append(node)
        for m in dependson(node):
            visit(m)
        L.append(node)

for node in nodeps(data):
    visit(node)

print L[::-1]

Answer 1

您描述的算法听起来可行，但很难检测到循环依赖。

您正在寻找的是 Topological sort你的依赖。如果您创建一个依赖关系图，其中从 A 到 B 的边表示 A 依赖于 B，那么您可以执行 Depth-first search以确定正确的顺序。你会想要做一个 variation of a regular DFS可以检测周期，因此您可以在这种情况下打印错误。

如果您在每个顶点上使用有序列表来存储图中的连接，则可以使用它们的序号添加依赖关系。使用 DFS 的一个优点是生成的排序列表在不与依赖顺序冲突时应遵守您的序列顺序。 (我相信；我需要对此进行测试。)