Python graphlib:给构建步骤排依赖顺序,并发现循环

举报
yd_254857454 发表于 2026/11/19 10:56:36 2026/11/19
【摘要】 打包要等编译和测试,而这两步都要先准备环境。把依赖关系交给 graphlib.TopologicalSorter,就不用手工维护一份固定的执行清单。以下用 Python 3.9 及以上版本即可运行,例子只排序,不执行真实的构建。 字典写的是每一步的前置任务from graphlib import CycleError, TopologicalSorterdependencies = { ...

打包要等编译和测试,而这两步都要先准备环境。把依赖关系交给 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。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。