有向无环图（DAG）布局

有向无环图及其布局算法

有向无环图（directed acyclic graph，以下简称 DAG）是一种常见的图形，其具体定义为一种由有限个顶点和有限条带有方向的边组成的图，并且其中任意一个顶点都不能沿着边再次指向自己。

DAG 可以用于模型化许多不同种类的信息，因此将一个 DAG 数据结构可视化的需求也变得非常普遍。并且由于大部分图的数据都非常复杂甚至动态变化，所以自动、可配置的 DAG 可视化布局算法显然比人为排版更为高效且可靠。

为满足笔者所在项目一个可视化功能（其逻辑可视为一个 DAG）的开发，我们需要一个可在浏览器端进行布局计算的 js 库，并且基于计算结果进行渲染。经过调研，社区的一个项目 dagre 基本可以满足我们的需求，但需要彻底掌握其计算逻辑我们还需要理解一些基本概念和对应配置项之间的关系。

基本概念

dagre 主要基于《A Technique for Drawing Directed Graphs》 的理论进行实现，因此也有以下几类单位：

• graph，即图整体，我们可以对图配置一些全局参数。
• node，即顶点，dagre 在计算时并不关心 node 实际的形状、样式，只要求提供维度信息。
• edge，即边，edge 需要声明其两端的 node 以及本身方向。例如A -> B表示一条由 A 指向 B 的 edge。
• rank，即层级，rank 是 DAG 布局中的核心逻辑单位，edge 两端的 node 一定属于不同的 rank，而同一 rank 中的 node 则会拥有同样的深度坐标（例如在纵向布局的 graph 中 y 坐标相同）。下文中我们会用示例 graph 进一步解释 rank 的作用。
• label，即标签，label 不是 DAG 中的必要元素，但 dagre 为了适用更多的场景增加了对 edge label 的布局计算。

深入 rank

接下来的示例中我们会用一种易懂的描述语言表达一个 DAG 的 node 与 edge：A -> B代表 A 和 B 两个 node 以及一条由 A 指向 B 的 edge。

示例 1

A->B;
B->C;

    +---+       +---+        +---+  
    | A |------>| B |------->| C |  
    +---+       +---+        +---+

在这个示例中，node A, B, C 分别属于 3 个 rank。

示例 2

A->B;
A->C;

                +---+
            --> | B |
    +---+--/    +---+
    | A |
    +---+--\    +---+
            --> | C |
                +---+

在这个示例中，A 在 rank1 中，而 B 和 C 都比 A 低一个层级，属于 rank2，因此 B 和 C 拥有同样的 x 坐标（示例图为横行延伸，因此深度方向为 x 方向）。

示例 3

A->B;
B->C;
A->C;

                +---+
             -->| B |---\
    +---+---/   +---+    --->+---+  
    | A |                    | C |  
    +---+------------------->+---+

在这个示例中，我们发现 edge 两端的 node 可以相差超过一个 rank。由于 edge 两端的 node 不可属于同样的 rank，所以我们不能让 B 和 C 属于同一个 rank，进而最优的绘制结果为 A 和 C 之间相隔两个 rank。

在这三个例子中，我们已经对 rank 的含义和规则有了更好的理解，接下来可以看看 dagre 允许我们对各类布局元素做怎样的配置。