Graph 怎样变成可执行依赖：Representation、Validation 与 Cycle Detection

前置：一次 Run 如何被推进：Lifecycle、State Machine 与 Node Transition

Node B 的 input 可引用 A.output.artifact id ，依赖边同时说明为什么 B 不能在 A 前启动。计划引用不存在的 node-17 时应 compile fail，而不是运行到一半才 KeyError。

Mental Model

Runtime 的主线是状态推进：接收 decision，校验并执行，提交 observation/state，再根据 terminal/deadline/budget 决定下一步。

Graph Representation

Graph Representation 是 Runtime 对可执行计划的结构化表示：至少包含 Node、dependency edge、reverse dependent/indegree 等调度所需关系，并为状态、重试和 trace 提供稳定 node identity。

不能仅保留 planner 的文本。Graph 是 scheduler 的确定性输入。

Dependency Validation

Dependency Validation 在 Graph 进入 Scheduler 前检查引用的 Node 是否存在、依赖关系是否满足 schema/业务约束，以及必需输入是否能由上游产出；它的产物是“依赖合法”这一编译期事实。

验证每个 dependency 是否存在、自依赖/重复依赖是否非法、输入引用是否可满足。它应在运行前尽量发现结构错误。

Cycle Detection

Cycle Detection 专门判断依赖图是否存在无法拓扑推进的环。它通常用 Kahn/DFS 等确定性算法完成，是 Graph Validation 的一个子问题，而不是 Graph 本身的表示。

DAG 调度要求无环；可用 Kahn/DFS 在 compile 阶段检测。发现 cycle 说明计划依赖定义矛盾，需要 replan 或人工修正。

把一个错误计划在执行前拦下来

考虑下面的编译结果：

text

A search_code
B read_file      depends_on=[A]
C patch_file     depends_on=[B, X]
D run_tests      depends_on=[C]

X 根本不存在。正确行为不是让 Scheduler 先跑完 A、B，再在 C 上抛 KeyError，而是在 Graph 进入执行态之前直接 COMPILE_FAILED。

一个最小验证过程可以是：

python

nodes = {n.id: n for n in graph.nodes}
for node in graph.nodes:
    for dep in node.depends_on:
        if dep not in nodes:
            raise UnknownDependency(node.id, dep)
        if dep == node.id:
            raise SelfDependency(node.id)

assert_no_cycle(graph)

Cycle Detection 可以用 Kahn 算法：先把 indegree=0 的节点入队，不断移除并降低下游 indegree；如果最终处理节点数小于总节点数，剩下部分就在环里。

这一步的价值在于把 Planner 的概率性输出 转成一个明确编译结果：

text

VALID GRAPH   → Scheduler 可以接管
INVALID GRAPH → replan / reject，不产生任何执行副作用

自测

Graph 中节点 C 依赖一个不存在的 B。为什么这个问题必须在执行前发现，而不是等 C 入队时再报错？
除了缺失 dependency，Graph validation 还应怎样处理 cycle、重复 node id 和非法 edge？

Graph 怎样变成可执行依赖：Representation、Validation 与 Cycle Detection ​

Mental Model ​

Graph Representation ​

Dependency Validation ​

Cycle Detection ​

把一个错误计划在执行前拦下来 ​

自测 ​

Sources ​