浅谈图的层次布局

1094次阅读  |  发布于3年以前

简介

图是一种常见的数据结构和表示形式，可视化场景也经常会用到图来展现有关联关系的数据。进行图的可视化时，往往需要将其自动布局，而针对不同的问题和场景，需要不同的布局方法。本文主要介绍图的层次布局的思路。

一些常用的图的布局方法。图片截自G6[1]

图的层次布局

在数据有一定层级结构或先后顺序时，经常会用到层次布局来展现，一般对应的数据结构是DAG（Directed Acyclic Graph，即有向无环图）。常用的场景包括：流程图、组织架构图、状态转移图等。

层次布局[2]的方法是 Kozo Sugiyama 首先于1981年详细阐明的，因此也常被称为 Sugiyama 布局。这里我们讲一下Sugiyama布局的思路。

目的

根据图的数据，自动画出一个易于理解的有层次(hierarchy)的图。

画图的基本规则

这样，给节点分层后，把每层的节点放到合理的水平位置，就可以把图画出来。

布局思路

根据以上原则，Sugiyama把图的布局问题分成了多个步骤，每个步骤解决不同的子问题。Sugiyama算法总共分为以下4步。

步骤1：节点分层

步骤2：减少交叉

步骤3：计算节点坐标

步骤4：画图

每一步的具体算法

看起来是很简单的4步，但每一步的实现都并不简单，也有很多种不同的算法。

节点分层

怎么把节点分到不同的层呢？这里介绍几种算法。

首先最容易想到的可能就是最长路径算法。即一个节点的层级等于要到达它需要走过的最长路径。最长路径算法的优点是速度很快，遍历图即可完成分层。然而它有比较明显的问题：节点被分到尽可能低的层级，给图的下方留出很多空白，并且可能会出现很多长边。不过，由于它速度快，经常被用于分层的预处理，粗分层后再交给其他算法来进行优化。

一个最长路径算法得到的结果，截自d3-dag[3]

紧致树算法就是一种优化方法，目的是减少长边的数量。从名称可以看出，「紧致」，即调整节点的分层，使更多边变成“紧致边”。

主要思路：

一个Network Simplex算法得到的结果，截自d3-dag[4]

减少交叉

怎样画一个图才是美观、可理解的是比较主观的，但尽可能减少边的交叉这个标准得到了广泛的认可。

由于节点已经分层，纵坐标已确定，且对于每个长边也已经通过增加伪节点的方式被分成了相邻层之间的短边，减少边的交叉问题就变成了如何对层内节点排序的问题。

然而已经有研究证明，即使是最简单的情况，即只处理两层之间的交叉，这个问题仍是一个NP困难[5]问题。因此，很多启发式算法被提出来解决这个问题，比较经典的是重心算法和中心算法。

计算坐标

根据此前所述原则，计算每层节点的坐标主要的目的是：边尽量垂直、节点布局平衡、长边尽量直。

Sugiyama提出了一种二次规划算法(Quadratic Programming)和一种基于优先级的启发式算法（我都没看懂）。之后也有很多研究者提出了多种不同的算法。

这里介绍一下 dagre 中使用的 Brandes & Kopf 提出的一种简单快速的启发式算法，在线性时间内即可完成坐标计算。（不过这个算法似乎会导致一些异常情况，见issue[6]）

其它考虑

实际布局的过程中，可能还会有更多需要考虑的点。这里列举一些供大家参考，就不详细展开了。

一个有嵌套的图，截自ELK[7]

实现自己的布局

Sugiyama布局提供了图的层次布局的基本框架，而实际业务场景中的需求可能各有侧重，已有的布局方法可能无法满足要求，就需要实现自己的布局方式。

因为Sugiyama布局已经把布局分成了不同的步骤和子问题，所以比较灵活。可以对其进行调整，在不同的步骤使用不同的算法达到目的。举个例子，下图这种流程图，边的关系不复杂，没有长边，即使边有交叉也影响不大，展示的重点可能是整个图的居中的效果，那么在分层、去交叉之后，第三步计算坐标时，可以直接用简单的居中对齐的方式排布节点。

简单看一个js实现 - dagre

dagre[8]是一个实现了层次布局的 js 库，G6 就是直接引用的 dagre 来实现的层次布局。

布局流程很清晰地写在了这个runLayout方法里，虽然看起来有27步之多，整体思路还是我们上面说的：分层、减少交叉、计算坐标。而dagre也增加了一些比如去自环、去环等一些预处理，以及支持了我们上面提到一些其它能力比如：边的label、嵌套布局等。

function runLayout(g, time) { // 给边label留出空间
time("makeSpaceForEdgeLabels", function() { makeSpaceForEdgeLabels(g); }); // 去除自环 
time("removeSelfEdges",        function() { removeSelfEdges(g); }); // 如果有环，去环，方法是反转一些成环的边
time("acyclic",                function() { acyclic.run(g); }); // 嵌套图的布局
time("nestingGraph.run",       function() { nestingGraph.run(g); }); // Step 1. 分层
time("rank",                   function() { rank(util.asNonCompoundGraph(g)); }); // 在边的中间位置生成虚拟节点，代表label的位置
time("injectEdgeLabelProxies", function() { injectEdgeLabelProxies(g); }); // 移除空层 
time("removeEmptyRanks",       function() { removeEmptyRanks(g); }); // 移除虚拟根节点和虚拟边 
time("nestingGraph.cleanup",   function() { nestingGraph.cleanup(g); }); // 标准化rank的值 
time("normalizeRanks",         function() { normalizeRanks(g); }); // 找到节点组的最大和最小层级 
time("assignRankMinMax",       function() { assignRankMinMax(g); }); // 移除边的label虚拟节点 
time("removeEdgeLabelProxies", function() { removeEdgeLabelProxies(g); }); // 把长边拆分为长度1的边，并插入虚拟节点
time("normalize.run",          function() { normalize.run(g); });
time("parentDummyChains",      function() { parentDummyChains(g); });
time("addBorderSegments",      function() { addBorderSegments(g); }); // Step 2. 节点排序
time("order",                  function() { order(g); }); // 回填自环
time("insertSelfEdges",        function() { insertSelfEdges(g); }); // 调整坐标系 上下/左右布局 
time("adjustCoordinateSystem", function() { coordinateSystem.adjust(g); }); // Step 3. 节点定位 
time("position",               function() { position(g); });
time("positionSelfEdges",      function() { positionSelfEdges(g); });
time("removeBorderNodes",      function() { removeBorderNodes(g); }); // 移除长边插入的虚拟节点 
time("normalize.undo",         function() { normalize.undo(g); });
time("fixupEdgeLabelCoords",   function() { fixupEdgeLabelCoords(g); });
time("undoCoordinateSystem",   function() { coordinateSystem.undo(g); });
time("translateGraph",         function() { translateGraph(g); }); // 计算边和节点的交点
time("assignNodeIntersects",   function() { assignNodeIntersects(g); }); // 反转在去环阶段被反转的边
time("reversePoints",          function() { reversePointsForReversedEdges(g); });
time("acyclic.undo",           function() { acyclic.undo(g); }); }

总结

参考资料

[1]G6: https://g6.antv.vision/

[2]层次布局: https://en.wikipedia.org/wiki/Layered_graph_drawing

[3]d3-dag: https://observablehq.com/@erikbrinkman/d3-dag-sugiyama

[4]d3-dag: https://observablehq.com/@erikbrinkman/d3-dag-sugiyama

[5]NP困难: https://en.wikipedia.org/wiki/NP-hardness

[6]issue: https://github.com/dagrejs/dagre/issues/239

[7]ELK: https://www.eclipse.org/elk/documentation/tooldevelopers/graphdatastructure.html

[8]dagre: https://github.com/dagrejs/dagre

[9]Github - dagre/dagre: https://github.com/dagrejs/dagre

[10]Github - d3-dag: https://github.com/erikbrinkman/d3-dag

[11]G6: https://g6.antv.vision/

[12]Eclipse Layout Kernel: https://www.eclipse.org/elk/

[13]Wiki - Layered Graph Drawing: https://en.wikipedia.org/wiki/Layered_graph_drawing

[14]图可视化之图布局: https://zhuanlan.zhihu.com/p/346059370

[15]深入解读Dagre布局算法: https://www.yuque.com/antv/g6-blog/xxp5nl

[16]Methods for Visual Understanding of Hierarchical System Structures: https://ieeexplore.ieee.org/document/4308636/

[17]A Technique for Drawing Directed Graphs: https://www.researchgate.net/profile/Emden-Gansner/publication/3187542_A_Technique_for_Drawing_Directed_Graphs/links/5c0abd024585157ac1b04523/A-Technique-for-Drawing-Directed-Graphs.pdf

[18]Fast and Simple Horizontal Coordinate Assignment: https://link.springer.com/content/pdf/10.1007%2F3-540-45848-4_3.pdf

[19]Layout of Compound Directed Graphs: https://publikationen.sulb.uni-saarland.de/bitstream/20.500.11880/25862/1/tr-A03-96.pdf

[20]An Efficient Implementation of Sugiyama’s Algorithm for Layered Graph Drawing: https://link.springer.com/content/pdf/10.1007%2F978-3-540-31843-9_17.pdf

[21]Port Constraints in Hierarchical Layout of Data Flow Diagrams: https://link.springer.com/content/pdf/10.1007%2F978-3-642-11805-0_14.pdf

[22]Improved Vertical Segment Routing for Sugiyama Layouts: https://rtsys.informatik.uni-kiel.de/~biblio/downloads/theses/thw-bt.pdf

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8