2011-06-09 92 views
7

我需要创建一个插件系统,它具有依赖关系支持,我不确定解释依赖关系的最佳方式。插件将全部从基类中分类,每个基类都有自己的​​方法。在每个插件类中,我计划创建一个dependencies属性作为它依赖的所有其他插件的列表。计算插件依赖关系

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

我一直在模糊的地方是排序的逻辑。我可以开始将它们按字母顺序排列,直到遇到有依赖关系的一个 - 如果它的依赖关系不在列表中,则将其放入tmp列表中。在第一轮导入结束时,从temp列表(仅含有依赖项的插件的列表)开始,然后再次检查'run list'。如果我在“运行列表”中找到它的依赖关系,请确保它具有比其最高依赖性更高的索引号。如果它的依赖关系不在列表中,请暂时搁置它并移动到临时列表中的下一个插件。一旦我到达tmp列表的末尾,请重新开始回到顶部,然后重试。一旦所有的插件被排序,或者tmp列表在循环之后不会改变大小 - 开始执行插件。

临时列表中剩下的是插件,它们没有找到它们的依赖关系,或者具有循环依赖关系。 (在tmp列表中的两个插件相互依赖)

如果你还在阅读并且你能够遵循我的逻辑;这是一个完美的计划吗?有一种更简单的方法吗?如果我想为执行顺序实现序列号,有没有一种'简单'的方法来同时存在序列和依赖关系? (如果存在冲突,依赖性会跳过排序)或者插件是否使用序列OR依赖关系? (运行带有序列号的第一个插件,比依赖的人?)

TL; DR

你会怎么写的插件系统计算的依赖逻辑?


编辑:

Alright-我觉得我实现从维基百科页面的拓扑排序;遵循其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] 

回答

5

您描述的算法听起来像它会工作,但会很难检测循环依赖。

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

如果您在每个顶点上使用有序列表来存储图中的连接,则可以使用它们的序列号添加依赖关系。使用DFS的一个优点是,当它不与依赖性顺序冲突时,得到的排序列表应该尊重顺序排序。 (我相信;我需要测试这个。)

+0

@takeek - 我编辑了这个问题,试图逻辑... – tMC 2011-06-09 06:04:55