1. 什么是Dagre布局算法？
Dagre布局算法，是指对“DAG图”进行“层次布局”的一个成熟算法实现，它在Github上开放的源代码仓库地址是github.com/dagrejs/dag…，很多可视化库的DAG层次布局也都借鉴了该方案，蚂蚁金服的G6、X6的@antv/layout布局，就是直接使用了它的实现。
什么是DAG图？
DAG 图全称 Directed acyclic graph，指的是有向无环图，常用的场景包括：流程图、组织架构图、状态转移图等。凡是不满足有向和无环两个条件的，都不算 DAG 图。有向树为有向图的真子集。
图 有向树、DAG 图和有向图
在数据有一定层级结构或先后顺序时，经常会用到层次(hierarchy)布局，比如我们常见的流程图，就是一个从左往右很有层次的DAG图。
我们在流程图编辑场景中有一个自动布局的需求，而Dagre布局最能贴近业务需求，所以我们对Dagre布局算法做了一些研究，在这里分享给有同样场景的各位同学。
2. 基本概念
在 dagre 中，为了方便分步计算图的布局信息，算法中定义了几个基本概念：
（1）rankDir：图的延展方向，分为由上到下（tb）、由下到上（bt）、由左到右（lr）、由右到左（rl）四种。
图 图的延展方向rankdir
（2）rank：沿着图的延展方向划分的层级，每个顶点都存在于某个层级上，一个层级上可能有多个顶点。
图 图的层次划分rank
（3）level：在每个 rank 中针对每一个节点划分的级。不同 rank 中的 level 互不影响。
图 布局中的层级划分
3. 计算流程
整个计算的流程分为 4 步：去环、节点分层、同层节点排序、绘制。
（1）第1步 去环
去环是为了对用户输入的数据进行初步的处理，将图中存在的环路进行变换，确保得到一个完整的有向无环图。
DFS 算法：使用 DFS 进行遍历，若在一条通路中，同一个节点被访问了多次，则该通路上存在环路，去掉成环的通路上最后一条边即可。
贪心算法：优先反转同时存在于多个环的边，尽量减少需要反转的边。
（2）第2步 节点分层
节点分层有 3 种布局方式：
① 最长路径（longest-path）：节点的层级等于要到达它需要走过的路径，并将末端对齐。
特点：速度最快，遍历完即完成分层。
② 紧凑树（tight-tree）：在最长路径树的基础上，遍历并移动各个节点，使得每个边都达到它需要的最短长度。
特点：排列紧凑，复杂度中等。
图 紧凑树示例
③ 网格单纯形（network-simplex）：在紧凑树的基础上，遍历并调整各个节点，使得所有边长度总和最小。
特点：得到一颗最优生成树，复杂度最高。
图 网格单纯形示例
（3）第3步 同层节点排序
经过第二步的处理，图中的节点已经按照 rank 分好层级，但每一个层级中的节点先后顺序仍然需要调整，以达到减少边的交叉的目的。
计算每个节点的重心值，并按照重心值调整每一层中节点的先后顺序。
图 按照重心值从小到大调整
（4）第4步 绘制
最后，为了达到节点之间有基本的层级对齐关系的目的，还需要比较不同 rank 和 level，来计算出一个节点的最终坐标。
① 深度坐标：节点的深度坐标比较简单，可以直接通过 rank 来计算（比如 tb 的延展方向里，节点 y 坐标为上一层的 y 坐标加上本层的最大高度）。
② 横向坐标：节点的横向对齐坐标计算比较复杂。为了满足：1. 有基本的对齐布局 2. 减少边的长度和交叉，dagre 针对不同的节点冲突情况，做了不同的处理。
4. 使用方法
这里直接使用蚂蚁金服提供的@antv/layout包中的Dagre算法实现：
（1）配置Dagre算法相关参数：
const dagreLayout: DagreLayout = new DagreLayout({
type: 'dagre',
ranker: 'tight-tree', // 节点分层算法，可选：'tight-tree' 'longest-path' 'network-simplex'
rankdir: 'LR', // 图的延展方向，可选： 'TB' | 'BT' | 'LR' | 'RL'
ranksep: 20, // 图的各个层次之间的间距
nodesep: 20, // 同层各个节点之间的间距
align: 'UL', // 节点对齐方式，可选：'UL' | 'UR' | 'DL' | 'DR' | undefined
nodeSize: 30,
controlPoints,
});
（2）调用Dagre布局算法：
let { nodes: newNodes = [] } = dagreLayout.layout({ nodes, edges });
（3）使用Dagre布局之后的新位置：
nodes.forEach((current) => {
const newNode = newNodes.find((node) => node.id === current.id);
current.position(newNode.x, newNode.y);
});
5. 其他需要考虑的地方
（1）增量布局
在图新增节点和边时，尽量保持原有的布局不变。
在@antv/layout中的Dagre算法实现中，有nodeOrder、preset等相关参数，可使用上一次布局的结果数据作为输入，可以进行增量布局、保证重新布局的连续性。
dagreLayout.updateCfg({
nodeOrder,
preset: { nodes },
});
（2）图的分组和嵌套
有时，图的节点有嵌套关系。这时候，可以考虑进行多次布局：每一个分组进行独立的Dagre布局，然后再整体做一次Dagre布局，Antv G6也有一个“流水线子图布局”的概念，支持在 Graph.layout 中同时配置多个子图布局。
（3）边的label
边上可能会有一些描述性的文字，计算位置时需要把label也考虑进来。
（4）节点的端口
上述算法中，节点是被看成点，边是直接和节点相连的，而实际应用中，经常会给节点定义一些端口(ports)，即指定边必须从某个端口连入或连出。
6. 相关资料推荐
《浅谈图的层次布局》：mp.weixin.qq.com/s/68I6SXlrd…
《深入解读Dagre布局算法》：www.yuque.com/antv/g6-blo…
《Dagre层次布局》:g6.antv.vision/zh/docs/api…
《Dagre 布局参数动态变化》：
