<p>这看起来像拓扑排序,所以从某处获取一个实现(例如<a href="http://rosettacode.org/wiki/Topological_sort#Python" rel="nofollow">here</a>),并修改您的数据格式以使用它。例如:</p>
<pre><code>def toposort2(data):
# modified from http://rosettacode.org/wiki/Topological_sort#Python
for k, v in data.items():
v.discard(k) # Ignore self dependencies
extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
data.update({item:set() for item in extra_items_in_deps})
while True:
ordered = set(item for item,dep in data.items() if not dep)
if not ordered:
break
for x in sorted(ordered):
yield x
data = {item: (dep - ordered) for item,dep in data.items()
if item not in ordered}
if data:
raise ValueError("a cyclic dependency exists")
def toposort_wrap(data):
dep_dict = {}
for d in data:
for bef in d.get("before", ()):
dep_dict.setdefault(bef, set()).add(d["value"])
dep_dict.setdefault(d["value"], set()).update(d.get("after", ()))
print dep_dict
result = list(toposort2(dep_dict))
return result
</code></pre>
<p>之后我们有</p>
<pre><code>>>> data = [dict(value=3, before=(5,), after=(2,)),
... dict(value=8, before=(5,)),
... dict(value=2, before=(3,)),
... dict(value=5)]
>>> toposort_wrap(data)
{8: set([]), 2: set([]), 3: set([2]), 5: set([8, 3])}
[2, 8, 3, 5]
</code></pre>
<p>(未经测试,因此比其他任何东西都更能证明概念,但我会这样做。)</p>