tMC*_*tMC 7 python algorithm logic
我需要创建一个具有依赖支持的插件系统,我不确定解决依赖关系的最佳方法.插件将全部从基类中进行子类化,每个基类都有自己的execute()方法.在每个插件类中,我计划创建一个dependencies属性作为它依赖的所有其他插件的列表.
当加载插件,我会导入所有的人,并把它们放在一个列表,并根据依赖关系进行排序.一旦它们都处于正确的顺序(因此任何具有依赖关系的东西都在其所述依赖关系之后的列表中)我将遍历执行每个方法execute()方法的列表.
我不断变得模糊的是排序背后的逻辑.我可以开始按字母顺序排列它们直到我遇到一个具有依赖关系的 - 如果它的依赖关系不在列表中,则将其放入tmp列表中.在第一轮导入结束时,从临时列表的末尾开始(除了具有依赖项的插件之外的任何列表)并再次检查"运行列表".如果我在"运行列表"中找到它的依赖项,请确保它的索引号高于其最高依赖项.如果它的依赖项不在列表中,请按住它并移动到临时列表中的下一个插件.一旦我到达tmp列表的末尾,请从顶部开始再试一次.一旦所有插件都被排序,或者tmp列表在循环之后没有改变大小 - 开始执行插件.
临时列表中剩下的是插件,它们没有找到它们的依赖关系,或者具有循环依赖关系.(tmp列表中的2个插件彼此依赖)
如果你还在阅读并且你能够遵循我的逻辑; 这是一个合理的计划吗？有更简单的方法吗？如果我想为执行顺序实现序列号,那么有一种"简单"的方法来同时拥有序列和依赖关系吗？(如果存在冲突,依赖性会击败排序)或者插件是否应该使用序列或依赖性？(首先运行带有序列号的插件,而不是带有依赖性的插件？)
TL; DR
您如何编写用于计算插件系统中的依赖项的逻辑？
编辑:
好吧 - 我想我从维基百科页面实现了拓扑排序; 遵循其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]