Python graphlib:给构建步骤排依赖顺序,并发现循环
打包要等编译和测试,而这两步都要先准备环境。把依赖关系交给 graphlib.TopologicalSorter,就不用手工维护一份固定的执行清单。以下用 Python 3.9 及以上版本即可运行,例子只排序,不执行真实的构建。
字典写的是每一步的前置任务
from graphlib import CycleError, TopologicalSorter
dependencies = {
"package": ("compile", "test"),
"compile": ("prepare",),
"test": ("prepare",),
"prepare": (),
}
order = tuple(TopologicalSorter(dependencies).static_order())
assert len(order) == len(dependencies)
assert set(order) == set(dependencies)
position = {step: i for i, step in enumerate(order)}
for step, prerequisites in dependencies.items():
for prerequisite in prerequisites:
assert position[prerequisite] < position[step]
print(" → ".join(order))
键是任务,值是它必须等待的任务。一种合法输出是 prepare → compile → test → package。但编译和测试之间没有依赖,交换顺序也正确。测试时检查每条依赖的先后,不要把某个合法输出误当成唯一答案。
发现环就先修依赖,不要硬排
cycle_graph = {"compile": ("test",), "test": ("compile",)}
try:
tuple(TopologicalSorter(cycle_graph).static_order())
except CycleError as exc:
cycle = exc.args[1]
assert cycle[0] == cycle[-1]
assert set(cycle[:-1]) == {"compile", "test"}
print("检测到环:", " → ".join(cycle))
else:
raise AssertionError("应该检测到依赖环")
两步都在等对方,谁也不能先执行。异常会提供检测到的一条循环,首尾是同一个节点;不要依赖它从哪个节点开始,也不要把它当成所有循环的清单。这里先完整生成顺序再执行工作,避免配置含环时已经开始执行。
只做诊断时,区分环上的步骤和被它挡住的步骤
假如文档和主程序一起打包,主程序依赖有环,文档本身却仍然能生成。下面只列出不受阻的分支,不运行任何构建命令。这个例子只有一个环;实际大图不该把“未列出”当成“必然在环上”。
broken_build = {
"package": ("compile", "docs"),
"docs": ("readme",),
"readme": (),
"compile": ("test",),
"test": ("compile",),
}
sorter = TopologicalSorter(broken_build)
try:
sorter.prepare()
except CycleError as exc:
cycle_members = set(exc.args[1])
else:
raise AssertionError("应该检测到依赖环")
reachable = set()
while sorter.is_active():
batch = sorter.get_ready()
reachable.update(batch)
sorter.done(*batch) # 诊断中只模拟批次完成,不执行构建
blocked = set(broken_build) - reachable
assert reachable == {"readme", "docs"}
assert cycle_members == {"compile", "test"}
assert blocked - cycle_members == {"package"}
print("不受阻:", sorted(reachable))
print("未能排出:", sorted(blocked))
虽然 prepare() 报告了环,get_ready() 仍能返回没有被环挡住的节点。这个例子里的 package 不在环上,修复时应先看 compile 和 test 的双向依赖。真正执行构建时,只有任务完成后才调用 done();如果整批必须成功,就继续采用上面先验图再执行的做法。
参考:Python 标准库文档 graphlib,重点见 TopologicalSorter 的 static_order、prepare、get_ready、done 与 CycleError。
- 点赞
- 收藏
- 关注作者
评论(0)