DAG 图的可视化

前言

在做一个 Multi-Agent Research System。对于大量有复杂依赖的子任务，根据依赖关系逐步执行，先执行无依赖任务，然后下一步执行依赖被满足的任务，如此按序执行。想做一个可视化图来展示这个过程，自顶至下。

复杂依赖处理

按步骤进行：

• 依赖继承：父节点依赖转移到所有子节点
• 依赖下沉：所有非叶子节点的依赖替换为对应的叶子节点的依赖
• 传递归约：假如 A -> B -> C, A -> C，那么这两条依赖链可以归约为 A -> B -> C，因为在执行层面是一致的，要进行任务 C 必须完成任务 B，而任务 B 依赖 A 任务，A -> C 没有传递新信息。

Sugiyama

一般采用 Sugiyama 来画 DAG 图，其内置了 layer 计算、最少边交叉的迭代实现、最长路径分层算法等等。

由于依赖线是曲线，于是出现了这种 “拉面图”：

这显然不好看，但是还不知道较好的可视化方法 …

自实现

抛弃 Sugiyama ，先不进行层内重排，将等价节点（上游、下游任务集合一致）合并为一个节点，把跨 layer 的连线变为虚线：

有一点乱，重新设计一个层内排序的规则：

一、基本定义

1.1 跨层连线

• 跨层连线：连接非相邻层级的边（如 stage 1 → stage 3）
• 跨层任务：该任务存在跨层连出线（有边连到下游非相邻层）
• 不算跨层：若任务只有上游跨层连线到它（仅连入线），则不视为跨层任务

1.2 连接类型（仅考虑相邻层连线）

类型	含义	合并节点
一对多	1 个上游 → 多个下游	合并节点算作「一」
一对一	1 个上游 → 1 个下游	—
多对一	多个上游 → 1 个下游	合并节点算作「一」

1.3 跨层数

• 某条边的跨层数 = stage_dst - stage_src（目标层 − 源层）
• 任务的最大跨层数 = 该任务所有连出线中跨层数的最大值（仅连出线，不含连入线）

---

二、Layer 0（根层）排序

1. 非跨层任务：按 一对多 > 一对一 > 多对一 排序
2. 跨层任务：排在最后，按最大跨层数升序（跨层越多越靠后）
3. 同类型内部：按 id 排序（如两个一对多任务按 id 排）

---

三、下游层排序与对齐

对每一层，从上游到下游递归处理。

3.1 第一步：摘出跨层任务

• 找出本层中有跨层连出线的任务
• 这些任务放在本层最后，不参与后续对齐计算
• 跨层任务之间按最大跨层数升序，同值按 id

3.2 第二步：非跨层任务排序与对齐

仅对无跨层连出线的任务进行排序和对齐：

连接类型	排序优先级	垂直对齐规则
一对多	1（最高）	本层「多」的中心与上游「一」垂直对齐
一对一	2	本层节点与上游节点垂直对齐
多对一	3	本层「一」与上游「多」的中心垂直对齐

同类型内部按 id 排序。

3.3 第三步：跨层任务放置

• 跨层任务紧接在非跨层任务之后
• 按顺序排列，不参与对齐

---

四、流程概览

每层处理：
  1. 摘出有跨层连出线的任务 → 放最后，按最大跨层数升序、id
  2. 非跨层任务：按 一对多 > 一对一 > 多对一 排序
  3. 非跨层任务：按对齐规则计算 x 坐标
  4. 跨层任务：在非跨层之后顺序排列

---

五、示例

• 一对多：A → B、C、D，则 B、C、D 的中心与 A 垂直对齐
• 一对一：A → B，则 B 与 A 垂直对齐
• 多对一：A、B、C → D，则 D 与 A、B、C 的中心垂直对齐
• 跨层：A 有边到 B（相邻）和 C（跨层），则 A 视为跨层任务，排在最后，不参与对齐

---

六、连线样式

• 相邻层连线：上游下侧中点 → 下游顶部中心，实线
• 跨层连线：上游下侧中点 → 下游顶部中心，虚线样式

样式微调

再把虚线调透明一点，最终效果：