Python：对依赖项列表进行排序

Python：对依赖项列表进行排序

您想要的就是所谓的拓扑排序。尽管可以使用内建函数实现

sort()

，但是这很尴尬，最好直接在python中实现拓扑排序。

为什么会很尴尬？如果您在Wiki页面上研究这两种算法，它们都依赖于运行中的一组“标记节点”，很难

sort()

使用这种概念来扭曲形式，因为

key=xxx

（甚至

cmp=xxx

）最适合与无状态比较函数一起使用，尤其是因为timsort不保证该元素将被检查的顺序。我（美丽的）肯定，任何解决方案
确实 使用

sort()

将要结束了冗余计算每个呼叫键/ CMP功能的一些信息，以避开无国籍问题。

以下是我一直在使用的算法（对一些Javascript库依赖关系进行排序）：

编辑：基于Winston Ewert的解决方案对此做了很大的修改

def topological_sort(source):    """perform topo sort on elements.    :arg source: list of ``(name, [list of dependancies])`` pairs    :returns: list of names, with dependancies listed first    """    pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-placeemitted = [] while pending:        next_pending = []        next_emitted = []        for entry in pending: name, deps = entry deps.difference_update(emitted) # remove deps we emitted last pass if deps: # still has deps? recheck during next pass     next_pending.append(entry)  else: # no more deps? time to emit     yield name      emitted.append(name) # <-- not required, but helps preserve original ordering     next_emitted.append(name) # remember what we emitted for difference_update() in next pass        if not next_emitted: # all entries have unmet deps, one of two things is wrong... raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,))        pending = next_pending        emitted = next_emitted

---

旁注：它 是
可能的鞋拔一个

cmp()

函数成

key=xxx

，如在本蟒错误跟踪概述消息。