内涵各种论文和算法，阅读起来较为费力。
适读人群：对Dagre内部实现原理有兴趣的同学。
阅读时长：1小时。
一、前言
常见的图可视化布局算法有：Dagre布局、Sankey布局、力导布局、随机布局等。
由于近期业务中需要，几种布局算法中，Dagre布局最能贴近业务需求，但同时也需要有一些定制能力。所以花时间研究了下Dagre布局的源码部分，以及其中涉及到的论文部分。
有部分算法的理解可能不是很透彻，欢迎大家交流。
二、核心步骤
源码地址：https://github.com/dagrejs/dagre
算法核心：布局算法的核心函数如下。
建议：在直接看源码之前，建议大家可以先大概看一下《A Technique for Drawing Directed Graphs》这篇论文，论文中讲述的是有向图的一种布局算法。Dagre的大体思路和步骤和论文中讲述的差不多，只是在每一步的具体实现上会有些差异点。
function runLayout(g, time) {
// 优化边上label的位置
time(" makeSpaceForEdgeLabels", function() { makeSpaceForEdgeLabels(g); });
// 去除自环
time(" removeSelfEdges", function() { removeSelfEdges(g); });
// 去环
time(" acyclic", function() { acyclic.run(g); });
// 复合图布局，复合图生成虚拟节点，并排序成nesting graph
time(" nestingGraph.run", function() { nestingGraph.run(g); });
// 层级分配
time(" rank", function() { rank(util.asNonCompoundGraph(g)); });
// 边lable的处理。在边的中间位置生成虚拟节点，代表lable的位置
time(" injectEdgeLabelProxies", function() { injectEdgeLabelProxies(g); });
// 移除空的层级，并将rank都调整为正数
time(" removeEmptyRanks", function() { removeEmptyRanks(g); });
// 移除虚拟边和虚拟根节点
time(" nestingGraph.cleanup", function() { nestingGraph.cleanup(g); });
// 调整rank为>=0的数
time(" normalizeRanks", function() { normalizeRanks(g); });
// 找到节点组的最大和最小层级
time(" assignRankMinMax", function() { assignRankMinMax(g); });
// 移除边的label虚节点，将虚节点的层级记录到label对象中
time(" removeEdgeLabelProxies", function() { removeEdgeLabelProxies(g); });
// 将长度大于1的边，分割成长度为1的n条边，并在边中插入虚拟节点
time(" normalize.run", function() { normalize.run(g); });
time(" parentDummyChains", function() { parentDummyChains(g); });
// 给组添加边框，增加左侧虚节点和右侧虚节点
time(" addBorderSegments", function() { addBorderSegments(g); });
// 节点排序
time(" order", function() { order(g); });
// 回填自环路
time(" insertSelfEdges", function() { insertSelfEdges(g); });
// 调整坐标系，默认是按照上下布局来算的，如果是左右布局，就对调节点和图的width和height
time(" adjustCoordinateSystem", function() { coordinateSystem.adjust(g); });
// 布局，计算位置
time(" position", function() { position(g); });
time(" positionSelfEdges", function() { positionSelfEdges(g); });
// 根据group的虚节点，计算group的位置，然后移除虚节点
time(" removeBorderNodes", function() { removeBorderNodes(g); });
// 移除前面长边切割中插入的虚拟节点
time(" normalize.undo", function() { normalize.undo(g); });
// 边的label
time(" fixupEdgeLabelCoords", function() { fixupEdgeLabelCoords(g); });
// 根据布局方向，调整节点和边的宽度、高度，以及xy坐标
time(" undoCoordinateSystem", function() { coordinateSystem.undo(g); });
// 算出x，y坐标
time(" translateGraph", function() { translateGraph(g); });
// 计算边的point坐标轴
time(" assignNodeIntersects", function() { assignNodeIntersects(g); });
// 反转反转边
time(" reversePoints", function() { reversePointsForReversedEdges(g); });
time(" acyclic.undo", function() { acyclic.undo(g); });
}总共是23步，其中有很多数据转换和处理的部分。
布局最核心的是四个阶段：
第一阶段：去环。
第二阶段：层级划分。
第三阶段：同层级内节点排序。
第四阶段：绘图
下面分别描述四个阶段的具体算法和细节。
三、去环算法
由于环路的存在，会影响层级分配的稳定性，所以在层级分配之前，需要先去环。
Dagre中提供了两种去环算法：DFS去环算法、贪心算法
1. DFS去环算法
算法核心
每个节点从自己的每条出边开始深度优先遍历，如果出边e1的遍历路径中不存在当前节点，说明当前链路不存在环路。如果出边e1的遍历路径中存在当前节点，则说明存在环。通过去掉最后环路的最后一条边，达到去环的效果。
时间复杂度
2. 贪心算法
参考论文
Dagre中贪心算法的实现参考了论文《A FAST & EFFECTIVE HEURISTIC FOR THE FEEDBACK ARC SET PROBLEM》。
算法核心
优先反转那些同时存在于多个环路中的边，尽可能的少反转边。
对于给定的一张图，按照一定顺序从左到右排列节点，使得边的方向尽量是从左到右的，那么从右到左的边则成为可能形成环路的边，即为需要反转的边。从而将求最少反转环的问题，转换成求一个节点序列。
以下为求节点序列的算法伪代码。
时间复杂度
, m为边的个数
示例
图中存在两个环，分别为b->d->c, d->c->e。按照上述算法思路，对节点进行排序
- 初始状态：s1=[], s2=[], s=[], G=a,b,c,d,e,f
- 叶子节点f，放入s2，并从图中移除。 s2=[f]
- 根节点a，放入s1，并从图中移除，s1=[a],并从图中移除，如图2
- 选取一个节点（出度-入度）最大的，即节点c。
- 将节点c加入到s1的末尾，并从图中移除，此时s1=[a,c]，如图3
- 将叶子节点d放入s2，s2=[d,f]，图中移除d。
- 将根节点b,e放入s1，s1=[a,c,b,e]。
- 图为空，结束。
- s=[a,c,b,e,d,f].
根据得到的序列，重新从左到右绘制图。如下图：
Dagre的做法：逆转第一个出度-入度 max节点的入边。即在上述步骤3的时候，就移除了d->c.
四、层级分配
输入条件：图必须是一个连通图、边均含有minlen和weight两个属性。（其中minlen表示边的长度，weight表示边的权重。）
返回结果：图中的节点都会有一个rank属性表示其所在层级。
Dagre中实现了三种层级分配算法：最长路径、紧致树、network-simplex三种。
1. 最长路径算法
算法核心
前提条件：图必须是一个有向无环图
返回结果：每一个节点都有rank属性。
尽可能多的把节点置于最底层。
时间复杂度
，n为图中节点个数。
最长路径算法是最快最简单的，但其效果不好，会导致很多长边的存在。但是因为这种算法速度快，所以也通常会用来当做其他算法的预处理步骤，计算一个初始的层级。
示例
2. 紧致树算法
算法核心
先用最长路径算出初始层级，然后调整松弛边的长度，松弛度的定义是相对于边的minlen。
松弛边定义：边的长度大于其实际所需长度。即松弛度 > minlen。
用最长路径算法舒适分层后，紧接着进行去松弛边，伪代码：
- 定义边的松弛度为（边长-边的minlen）。
- 把目前已经紧致的节点添加到tightTree中，然后从松弛度最小的边开始逐步处理。
- 如果松弛边的源节点在tightTree，将边的目标节点层级向上移动delta；
- 如果松弛边的源节点不在tightTree，将边的源节点层级向下移动delta；
- 直至所有的节点都被加到tightTree中。
时间复杂度
，n为图中节点个数。
示例
3. networks simplex算法
参考论文
《A Technique for Drawing Directed Graphs》
核心思想
迭代修改节点的层级，缩小松弛边。
- 先将图中紧致的边及其相关的节点加入到树中，构建一颗紧致生成树。（生成紧致树的算法使用上面的紧致树算法）
- 分配给起始节点一个层级，然后从起始节点出发，找到邻近的节点，然后根据其与起始节点的上下游关系，计算连通边的最小长度。
- 直到所有的节点都有一个默认层级。
- 计算每条边的切割值。切割值的计算：移除该边，将生成树分为两个区域，根据边的方向，分为头部区域v和尾部区域w，那么该边的切割值就等于，尾部区域w到 头部区域v的所有连接边的weight之和（注如果边的方向是从头部到尾部的，那么该边的weight即为负值）。
如针对下图，其最小紧致生成树为去掉虚线边的部分。
则边e的其切割值为：从v到w的边为1条，从w到v的边为2条。因此其切割值为-1
- 切割值为负的边，即为需要调整的边。调整方式：加长该边的长度。
- 替换生成树的边，构成新的生成树。
- 根据新的生成树，重新调整层级。
procedure rank（）
feasible_tree();
while (e=leave_edge(e)) != nil do
f = enter_edge(e);
exchange(e,f);
end;
normalize();
balance();
end示例
算法优化
上述算法步骤中其中生成紧致生成树和初始的切割值耗时较大，复杂度
。论文中针对这两个步骤又分别提出了优化的解法。
1）生成初始切割值优化
思路：选取生成树的叶子节点，计算该节点的边的切割值。对于非叶子节点的切割值，可以根据已有边的切割值算出。
验证：下图中，u,v,w,x四个节点之间有三条边，三条边的切割值
满足下面的计算公式
从数学公式中，可以看到边的切割值可以通过其相关联边的切割值计算出来。
对应到场景中，即叶子节点边的切割值直接算出、非叶子节点相关的边的切割值计算公式如下:
切割值 = 边的weight + 节点其他边切割值之和 + 节点的出边weight - 节点的入边weight。
整个算法复杂度从原先的降到了
。
2）将树划分为头部和尾部的优化。
默认需要遍历所有节点，复杂度。
定义
和
，对树做后序遍历，节点在序列中的位置作为。计算叶子节点的low = lim，非叶子节点的low等于其子节点low的最小值。
则在划分区域时，在尾部区域的节点满足以下条件： 源节点的low <= 节点的lim <= 源节点的lim。
五、同层内节点排序
核心思想
返回结果：图中每一个节点都有一个order属性，表示其在同层内的次序
算法步骤：
- 针对每一个层级，分别生成两个图，downlayer和uplayer。（见单层级图构建）
- 给图中所有节点一个初始的order。
- 返回一个层级矩阵，每一个层级对应一个数组，每一层按照节点的顺序进行排序。
- 按照节点在所在层级数组中的位置，赋予其初始order。
- 遍历downlayer和uplayer，计算每一层级中节点的barycenter和weight（见barycenter的计算）
- 根据barycenter的值，调整节点顺序。（见Resolve Conflict）
- 根据调整后的结果，重新计算出层级矩阵。
- 根据层级矩阵，算出交叉边的个数。
- 与上一次计算出的交叉边数作比较，交叉少的排序方案。
- 5-8迭代执行4次。（为什么是4次？）
- 根据最终得到的order结果，修改图中节点的order属性。
单层级图构建
核心思想：构建一个图，图中包含某层级内所有的节点，以及指向这些节点的边（或从这些节点的边指出）。层级内没有父节点的节点会被当做返回图的根节点，这样更便于移动节点的层次位置。
前置条件：
- DAG
- 实体节点都有rank属性
- 子图节点有minrank和maxrank属性
- 边有weight属性
返回结果：
- 输出的图中所有的节点都有可移动的层级
- 可移动层的根节点，是根据graph的root节点指向的子节点决定的。
- 指向可移动节点的不可移动节点（与relationship有关），也包含在图中（无层次结构）
- 指向可移动节点的边（与relationship有关），也包含在图中
- 如果有相同的边，合并权重成一条边。
算法步骤
- 找到图的根节点，作为返回图的根节点。
- 筛选中指定层级内的子图和节点，放到图中。如果不存在parent，就设置根节点为该节点的parent。
- 获取节点的入边（与relationship有关），放入到图中。
- 如果是子图，将子图的左右边框的同层虚节点也加入到图中。
示例
结果：
downLayerGraph
| rank | 节点 | 边 |
|---|---|---|
| 0 | a | |
| 1 | b,c,d | a->b, a->c, a->d |
| 2 | e,f | c->f, d->e |
| 3 | g,h | e->h, e->g, f->h |
upLayerGraph
| rank | 节点 | 边 |
|---|---|---|
| 0 | a | a->b, a->c, a->d |
| 1 | b,c,d | c->f, d->e |
| 2 | e,f | c->f, d->e |
| 3 | g,h |
BaryCenter计算过程
核心思想
计算每个节点的重心值。
简单情况：不考虑边的权重，rank层的节点v1，v2，v1的上游节点u1和v2的上游节点u2位于rank-1层。如果u1的order大于u2的order，那么必须满足v1的order大于v2的order。否则将出现交叉，如下图:
复杂情况：考虑边的权重，以及节点可能存在多个上游节点。节点上增加属性weight和barycenter。
其中表示v节点的order。
表示边e的weight。
则针对上面例子downLayerGraph[2]，得出如下结果：
| 节点 | weight | sum | barycenter |
|---|---|---|---|
| e | 1 | 2 | 2 |
| f | 1 | 1 | 1 |
Resolve Conflict
参考论文
A Fast and Simple Hueristic for Constrained Two-Level Crossing Reduction
核心思想
根据上一步计算出来的节点中心值，解决图和节点重心不一致的地方。如果节点的重心值违反了图的约束条件，就合并冲突的节点，使其符合约束条件。
前置条件：输入的数组中，每一个元素都包含{v， barycenter，weight} 或者{v}
返回结果：新的数组，元素 {vs, i, barycenter, weight} 。vs是一个节点列表，里面可能只有一个节点，也有可能是多个节点，这多个节点是需要合并的节点顺序。属性“ i”是“ vs”中任何元素的最低原始索引。
统一层级中两个节点，如果存在
，则必须存在
。否则将肯定存在交叉，这种情况下对换v1和v2即可。
六、布局
节点Y轴
y轴坐标就根据层级来分配，每一层级都是基于上一层级的Y 加上 本层级maxHeight的一半。x,y的坐标是中心点。rankSep是配置项，由使用者配置层级之间的间隔。
function positionY(g) {
var layering = util.buildLayerMatrix(g);
var rankSep = g.graph().ranksep;
var prevY = 0;
_.forEach(layering, function(layer) {
var maxHeight = _.max(_.map(layer, function(v) { return g.node(v).height; }));
_.forEach(layer, function(v) {
g.node(v).y = prevY + maxHeight / 2;
});
prevY += maxHeight + rankSep;
});
}节点X轴
参考论文
《Fast and Simple Horizontal Coordinate Assignment》
术语：
-
表示层级，
表示节点
所在的层级。如果有一条边从
，则
- 如果边
存在
,那么就称这条边为短边，否则，称其为长边。 - 定义
,即节点的上游节点；定义
,即节点的下游节点； - 定义
,即节点的入度；定义
,即节点的出度。 - 定义图的表达式
。表示图中的节点由实体节点
和虚拟节点
组成，
表示所有的边，表示层级。 - 定义图的大小
- 同层级内节点的顺序关系用<表示，例如
, 存在关系
. - 节点在同层内的位置定义为
- 定义交叉边。
- 内部线段：两个虚节点之间的连线
问题定义：
水平坐标分配问题：对于一个给定的分层图，，找到
, 
，满足
。其中
表示最小分割约束。
一个可读性较高的图应该满足：
- 边尽量的短
- 上下层的节点位置要平衡，长边尽量不要出现拐点。
核心思想
该算法包括三个基本步骤。 前两个步骤执行了四次。
- 垂直对齐。尝试将每个顶点与其中上邻或中下邻对齐，然后以最左或最右的方式解决对齐冲突（类型0）。 因此，对于具有最左和最右冲突解决方案的向上和向下对齐的每种组合，我们都获得一个垂直对齐。
- 水平压缩。将对齐的顶点约束为获得相同的水平坐标，并且将所有顶点放置在对齐的首选水平方向上，使其尽可能靠近下一个顶点。
- 将由此获得的四个分配，即左上、右上、左下、右下四个组合起来以平衡其坐标偏差。
下面以左上这个方面的对齐为示例，说明算法。 其他三种情况是类似的。
1）垂直对齐
在垂直对齐的部分，需要尽可能的将每个层级的顶点与上一个层级相连的顶点对齐。
如果两个对齐方式的对应边线段相交或共享一个顶点，则称这两种对齐方式是冲突的。 我们根据包含的内部线段的数量来对冲突进行分类。
类型2：两个内部线段发生交叉，并且两端线段中都不垂直。
类型1：非内部线段和内部线段有交叉。
类型0：两个非内部线段交叉，或者共用一个节点的非内部线段
三种类型的解决方法
类型0：因此，在确定对齐方式时，可以将涉及的一个或两个段标记为非垂直段并忽略。 由于垂直内部线段具有很高的可读性，所以需要在交叉减少的阶段就避免了类型2冲突。或者，可以在水平坐标分配之前的预处理步骤中消除类型2冲突，例如：通过交换涉及的两个较低的顶点，直到两个内部线段不再交叉为止。需要注意的是，这个过程会更改节点的顺序，可能会影响到交叉点的数量。所以如果节点顺序比垂直线段更重要的话，可以在最终布局中恢复原始排序
类型1：非内部线段和内部线段有交叉。 其次，因为垂直的内部线段是可取的，所以它们被解析为有利于内部线段。我们在Alg1给定的预处理步骤中标记类型1冲突。该算法从左到右遍历各层级（索引l），同时记录两个最接近的内部线段的上邻
和
。 算法复杂度为。同时算法中还标记了类型1冲突的非内部线段，便于在确定对齐方式时忽略它们。
可以很容易地修改这个预处理算法，用来标记类型2冲突，或通过交换交叉内部线段的较低顶点来即时消除它们。
类型0：两个非内部线段交叉，或者共用一个节点的非内部线段。我们定义如果节点v在v'的左边，u在u'的左边，那么线段（u，v）一定在线段（u',v'）的左边。类型0冲突以最左端的方式贪婪地解决，即在每一层，从左到右遍历顶点，考虑其中上邻节点（如果有两个，就按照左右顺序）。 如果没有冲突的对齐，则该对将对齐。 所产生的偏差是由以下事实引起的：将对称偏差应用于其他三个分配之一。
通过下面的算法，我们就得到了一个左侧向上对齐方式。垂直对齐最多的节点，我们称之为block，定义最顶部的节点为这个block的root节点。请注意，block用循环链接列表表示，其中每个顶点都引用了其下对齐的邻居，而最低的顶点又引用了最上层的邻居。 此外，每个顶点还具有对其root节点的附加引用。 这些数据结构足以满足下一节中描述的实际放置。
【水平压缩】
分配水平坐标。一个block共享root节点的水平坐标。如左图对应的block划分为右图所示。
观察图，每个block的root节点就是这个无环图的sink，通过在层间的左上角，同时同一层级最多有一个这样的节点
我们将框图划分为多个类。块所属的类由其最高根节点决定。在每个类中，我们应用最长路径分层算法，即，block相对于sink的相对坐标，递归的计算为相同类别中的上一个block的最大坐标加上最小间隔。
然后，对于每个类，从上到下，我们通过将类与先前放置的类之间的距离最小化，来计算其成员的绝对坐标。
整个压缩算法如alg3所示。
第一次迭代使用了最长路径分层算法的递归版本，计算出相对于类接收器的所有根的相对坐标。 然后，计算每个接收器类中的一个顶点，与具有更高接收器的类中其相邻顶点之间的最小距离。 第二次迭代将这些信息从根部分发到所有顶点以获得绝对坐标。
以上即为迭代四次后，分别得到的左上、左下、右上、右下的四个图。下面根据四个图做平衡
【平衡】
最简单的平衡，横坐标根据左右两个图中节点的横坐标取平均值。
边的路径计算
计算出边的point坐标，是的边不传过box，同时边指向box的中心。
即如何算出a和b的坐标。
七、嵌套子图的处理
参考论文
Layout of Compound Directed Graphs
核心思想
基于分层布局，把一个子图当做虚拟节点，然后全局划分所有节点到不同的层级，再调整统一层级内节点的顺序，避免产生交叉线。论文中定义，所有的嵌套图都可以用一个连通关系图
和一个嵌套关系图
表示。如下图
层级划分
层级分配规则：
a. 所有的节点都需要划分到不同的层级，同一层级的节点，y轴坐标一致。
b. 节点之间，节点与线之间不能有重叠交叉
c. 线之间可能有拐点和交叉，要尽量避免
d. 边应该尽可能保持方向一致，比如从上到下。
e. 矩形边框内应该包含所有在子图内的节点。
f. 两个子图之间的矩形边框，不能有重叠
g. 线可能会与子图的边框有交叉，应该尽量避免。
h. 减少跨级的边，如果有，就通过产生虚拟节点的方式来消除跨级边**
划分定义：
a. 对于每一个子图，都有两个虚拟节点，虚拟节点
表示图顶部，虚拟节点
表示图底部。
b. 同时虚拟节点和真实节点不能处于同一层级。
c. 两个不同层级的节点之间，至少有2k个层级，其中k是嵌套关系树的深度。如下图
可以看出最终得到嵌套图中upper和lower是对称的。所以问题可以转换为求所有实体节点v和虚节点u-的层级。
公式一： 节点来说，其层级就是它的所有父节点中层级最大值+1，即
我们可以根据上面的计算，得出所有节点的层级如右图。
但是看得出这个图的问题，就是子图内的布局很空旷，因为子图的虚拟节点 离内部的实体节点很远。所以需要进一步的优化
公式二：虚拟节点的顶部应该离内部的实例节点越近越好，即
优化后的层级图如下图
生成虚拟节点
找到子图中合适的点，作为连通线的端点。对于子图
和
来说，（
）,（
）,（
）都是一样的，代表同一条线。
在这个过程中，同样要避免产生环，如果过程中产生了反向的边（如从下到上的边），就把边做标记并反转过来，布局结束后再把边恢复。
把跨多个层级的长边，通过生成中间虚拟节点的方式，将其分割为多条边。从而使得图中所有的边的长度均为1。
在一个嵌套图中，所有的节点必须都是在一个图中，所以生成一个虚拟根节点。
虚拟节点生成过程有以下两个策略：
- 将边
尽可能的布局在子图边框外。如果节点
不在同一个子图内，就穿过各自的子图，将它们的边全部都布局到子图外部。在嵌套树中，我们找到这两个节点的第一个父节点，然后把生成的虚节点放到树的边缘。如下图
- 将边尽可能的布局在子图边框内。如果节点不在同一个子图内，通过调整它们所在子图的区域，将边尽量的放到子图内。对于嵌套树来说，需要找到对应的子图，然后把图内的虚拟节点添加到子图中。如下图所示：
