关于前端:图可视化之图布局

可视化是一种利用计算机图形学和图像处理技术，将数据转换成图形或图像在屏幕上显示进去，再进行交互解决的实践、办法和技术。数据在通过图可视化的形式展现后可能辅助用户去剖析简单的关系数据，从而发现数据中蕴含的价值。而图布局则是图可视化中十分重要的基石，对可视化图进行正当的布局能够帮忙咱们疾速剖析，精确定位问题。如果没有对图进行正当的布局，那么用户就很难从图中提炼出想要的信息，甚至有时候还会误导用户作出谬误的判断。例如在下图中，左侧是没有进行过特定布局横七竖八的图，右侧则是通过有向分层布局后的图，咱们从右图中能够十分疾速地分辨出图中的根节点、二级节点、三级节点以及节点之间的关系等重要信息，然而咱们却很难从左侧图中辨认出这些信息。因而在咱们日常的业务场景应用正当的图布局至关重要。

在可视化畛域中常见的布局有树形布局、Dagre 布局、力导布局、同心圆布局、网格布局等。

布局计划	实用场景
力导布局	实用于形容事物间关系，比方社交网络关系、计算机网络关系、资金交易关系等各类关系网络场景
网格布局	节点按肯定排序网状排开，适应于分层网络，便于看清整体档次
同心圆布局	将节点依照度数排序，节点度数大的一群点会排列在最核心，度数小的节点会散布在最外层，使其以同心圆的形式排布，适应于疾速查找出度数较多的节点
圆形布局	实用于查找关联关系较多的要害节点场景，例如在圆形布局的图中能够显著分辨出哪些节点关联关系较多
树形布局 / Dagre 布局	适应于层次分明，或者须要紧密拓扑性质的场景，比方分层网络图、流程图等

在很多业务场景中，咱们通常会比拟关注节点之间的层级关系，并且还须要判断图中是否存在环路等状况状况，这种状况下树形布局就十分适合，对于树形布局大家惯例的意识必定是下图左侧这种传统的布局模式，从根节点登程，依照层级关系向同一方向自上而下或自左而右累加。这种展现形式最为直观，也合乎咱们对树的惯例感知，但它也存在一些问题，比方对屏幕空间的利用率不高。越凑近根节点的层级节点越稠密，导致大量留白，从而节约屏幕空间。

因而对于一些布局空间无限的场景，咱们能够采纳上图（右）的布局形式，该布局是依据节点深度将整棵树以辐射状展现，根节点在最核心，叶子节点在外围。这种布局形式相比于传统的树图布局可能以更好地利用空间，美中不足之处就是可能不如传统树图布局合乎人对树结构的感知，并且随着节点数量的减少，树的门路就越不清晰，不过咱们也能够通过肯定的交互方式来补救有余，比方点击某个子节点默认展现该节点的回溯门路。
树形布局的算法难度不大，我在 GitHub 上找了一篇对于紧凑树布局的文章，大家能够点击中转，这文章对于实现的原理也有具体的论述，本文就不再讲述了。

Dagre（有向无环图）布局其实有点相似于树形布局，不过也有些差别；对于任何有向树图必然是有向无环图，然而有向无环图未必是有向树图，因为有向无环图有其紧密的拓扑性质，使其具备很强的流程表达能力。基于这一特点，在很多须要对零散化工作进行组织和管制的场景中，利用十分宽泛，比方下图是阿里云的机器学习平台 PAI 中的截图，它就是一张典型的有向无环图。

对于 DAG 布局 GitHub 上有一套成熟的算法传送门，很多可视化库的 DAG 布局也都借鉴了该计划，从上面的 runLayout 函数咱们能够大抵看出 dagre 布局的过程。

function runLayout(g, time) {time("makeSpaceForEdgeLabels", function() {makeSpaceForEdgeLabels(g); });
  time("removeSelfEdges",        function() {removeSelfEdges(g); });
  time("acyclic",                function() {acyclic.run(g); });
  time("nestingGraph.run",       function() {nestingGraph.run(g); });
  time("rank",                   function() {rank(util.asNonCompoundGraph(g)); });
  time("injectEdgeLabelProxies", function() {injectEdgeLabelProxies(g); });
  time("removeEmptyRanks",       function() {removeEmptyRanks(g); });
  time("nestingGraph.cleanup",   function() {nestingGraph.cleanup(g); });
  time("normalizeRanks",         function() {normalizeRanks(g); });
  time("assignRankMinMax",       function() {assignRankMinMax(g); });
  time("removeEdgeLabelProxies", function() {removeEdgeLabelProxies(g); });
  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); });
  time("adjustCoordinateSystem", function() {coordinateSystem.adjust(g); });
  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); });
}

如果咱们按每个 time 相当于每步的计算过程来算，emm… 这样算下来应该是有 26 个步骤，这也太简单了吧？不过深刻去看了下调用的各个函数，就会发现实际上大部分函数其实都是在解决数据。DAG 布局的外围步骤应该能够大抵分为 4 步：

去除环，包含自环和非自环即 removeSelfEdges 和 makeSpaceForEdgeLabels（最初如果有自环路还是会回填回去的）
划分层级即 nestingGraph.run
同层级内节点排序即 addBorderSegments
计算地位布局

理解关系图谱相干业务的同学必定对力导布局不生疏，力导布局最早是被 Eades 提出的，之后被很多钻研人员从新定义和改良，下图是 D3 上的三种力导布局。

力导布局的劣势在于因为互斥力的存在，能够缩小节点之间的重叠，但实际上当节点过多时，依然会呈现节点重叠的状况，在无限的空间里想要防止所有节点不重叠，这已被证实是一个 NP 难题（世界难题，目前无解），并且在一些大数据的场景下还会呈现毛团景象，如下图。

圆形布局是将所有节点先进行肯定的排序（这里的排序能够自定义），而后再按序排列在一个圆环上，这种布局的益处是通过自定义排序后的圆形布局，咱们能够疾速剖析出想要的后果，例如下图是依照关联度数排序后的圆形布局，咱们能够很清晰地看出红框的中的节点相较于其余节点的关联度数更多，这是其余布局形式所难以达到的成果，比方应用上文的力导布局，就很难分辨出哪些节点的关联度数更多。然而它的毛病也比拟显著，因为随着节点数量的减少，圆环的半径也会越来越大，很容易就超出咱们惯例屏幕的可视区域。

对于圆形布局的具体形式，实际上外围步骤理论就只有两步：

自定义排序
环形布局

对于第二步的环形布局，这个算法就比拟固定了，次要是依据节点的数量计算出每个节点在环形中的地位即可，上面是 antvis/layout 中对于环形布局的代码：

public execute() {
    const self = this
    const nodes = self.nodes
    const edges = self.edges
    const n = nodes.length
    if (n === 0) {if (self.onLayoutEnd) self.onLayoutEnd()
      return
    }

    if (!self.width && typeof window !== 'undefined') {self.width = window.innerWidth}
    if (!self.height && typeof window !== 'undefined') {self.height = window.innerHeight}
    if (!self.center) {self.center = [self.width / 2, self.height / 2]
    }
    const center = self.center

    if (n === 1) {nodes[0].x = center[0]
      nodes[0].y = center[1]
      if (self.onLayoutEnd) self.onLayoutEnd()
      return
    }

    let radius = self.radius
    let startRadius = self.startRadius
    let endRadius = self.endRadius
    const divisions = self.divisions
    const startAngle = self.startAngle
    const endAngle = self.endAngle
    const angleStep = (endAngle - startAngle) / n
    // layout
    const nodeMap: IndexMap = {}
    nodes.forEach((node, i) => {nodeMap[node.id] = i
    })
    self.nodeMap = nodeMap
    const degrees = getDegree(nodes.length, nodeMap, edges)
    self.degrees = degrees
    if (!radius && !startRadius && !endRadius) {radius = self.height > self.width ? self.width / 2 : self.height / 2} else if (!startRadius && endRadius) {startRadius = endRadius} else if (startRadius && !endRadius) {endRadius = startRadius}
    const angleRatio = self.angleRatio
    const astep = angleStep * angleRatio

    const ordering = self.ordering
    let layoutNodes = []
    if (ordering === 'topology') {
      // layout according to the topology
      layoutNodes = self.topologyOrdering()} else if (ordering === 'topology-directed') {
      // layout according to the topology
      layoutNodes = self.topologyOrdering(true)
    } else if (ordering === 'degree') {
      // layout according to the descent order of degrees
      layoutNodes = self.degreeOrdering()} else {
      // layout according to the original order in the data.nodes
      layoutNodes = nodes
    }

    const clockwise = self.clockwise
    const divN = Math.ceil(n / divisions) // node number in each division
    for (let i = 0; i < n; ++i) {
      let r = radius
      if (!r && startRadius !== null && endRadius !== null) {r = startRadius + (i * (endRadius - startRadius)) / (n - 1)
      }
      if (!r) {r = 10 + (i * 100) / (n - 1)
      }
      let angle =
        startAngle +
        (i % divN) * astep +
        ((2 * Math.PI) / divisions) * Math.floor(i / divN)
      if (!clockwise) {
        angle =
          endAngle -
          (i % divN) * astep -
          ((2 * Math.PI) / divisions) * Math.floor(i / divN)
      }
      layoutNodes[i].x = center[0] + Math.cos(angle) * r
      layoutNodes[i].y = center[1] + Math.sin(angle) * r
      layoutNodes[i].weight = degrees[i]
    }

    if (self.onLayoutEnd) self.onLayoutEnd()

    return {
      nodes: layoutNodes,
      edges: this.edges,
    }
  }

然而对于第一步的自定义排序，因为排序算法的不确定，因而会让咱们的环形布局呈现很多很有意思的布局状况。也有相干钻研人员专门钻研过此类布局，论文详情大家能够点击中转

同心圆布局在图剖析的场景中通常是将节点先依照度数排序，度数最大的节点会排列在最核心的地位，越往外度数越小，整体成同心圆模式排列，如下图所示。在上文中的圆形布局中，其实咱们还是很难精确定位出度数最多的节点，然而同心圆布局能够做到，因为最近靠近圆心地位的节点就是度数最多的节点，并且在雷同面积下同心圆布局能够比圆形布局包容更多的节点。因而在查找度数最多节点的场景中，同心圆布局要比圆形布局更占优势。

增量布局是为了解决在数据产生增量变动时，使原有布局可能放弃绝对稳固的问题。在图剖析中的关系扩散、关系发现等场景下，剖析的数据往往都在继续变动，难以一次性剖析结束。这时就须要增量布局算法，在数据发生变化时可能放弃整体布局的绝对稳固如下图所示。

增量布局个别分为两种状况，一种是稳固布局的增量，一种是力导布局的增量。
• 稳定性布局的增量布局：例如 circle，grid 布局，新增的节点通过原有的布局函数，节点地位可预测，通过节点的补间动画即可实现
• 力导布局的增量布局：如果以后画布是力导布局，新增节点通过 tweak 算法，为新增节点找到适合的初始地位，再通过力导的能量优化，实现整体布局，具体的细节图如下。

子图的概念源于图论，它是指节点集和边集别离是某一图的节点集的子集和边集的子集的图。若这个节点子集或边子集是真子集，则称这个子图为真子图；若图 G 的每一个节点也是它的子图 H 的节点，则称 H 是 G 的撑持子图。设 S 是 V(G)的子集，以 S 为节点集，以 G 的所有那些两端点都在 S 内的边组成边集，所失去的 G 的子图称为 S 在 G 中的导出子图。设 B 是 E(G)的子集，由 G 的所有与 B 内至多有一条边关联的节点组成节点集，以 B 为边集，所失去的 G 的子图称为 B 在 G 中的边导出子图；对于某种性质 P，若一个图的具备 P 的子图不是任何具备 P 的子图的真子图，则称它为具备 P 的极大子图，在所有极大子图中，边数最多的那个称为最大子图。
上文讲了一大段，预计大家对于子图还是没有任何体感。不过咱们来看下图，可能就会很快了解子图布局了。因为在实在的业务场景中，咱们的数据关系常常会是盘根错节的，因而咱们很难只用一种布局形式就能清晰地表白，上文咱们也讲到了各类布局形式的劣势和劣势，那么咱们是否能够将各类布局计划的劣势交融在一起，呈现出更正当的布局成果，子图布局就是为了解决此类问题。

上图的布局形式即把子图布局的数据独自进去，别离施加布局算法，失去一个精确的地位，而后对立渲染到画布上。不过，这外面存在两个技术难点：

A，B 两组数据点，初始地位如何确定？
A，B 两组数据如果存在关联点，它们将会对两个子网络产生何种影响？

这个其实能够提供一些策略，比方两组数据的初始地位，能够通过 A，B 组数据的均匀中心点来确定。而 A，B 组见相关联的共同点能够通过一些数学计算，得出一个适合的组内边缘地位

针对子图布局存在的技术难点，有些钻研方向也尝试通过机器学习建模的形式，应用大量的标注数据（标记布局分类）进行模型训练，在实在的业务场景中通过模型对实在的图数据的布局形式进行预测，从而举荐出该数据最适宜的布局，具体过程如下图。

下图是北大可视化钻研人员对于智能布局的钻研，他们提出了一个基于拉普拉斯变换的图布局放弃算法。该工作能主动生成初始图布局，容许用户在图中任意选取子图并进行个性化编辑。收集多用户编辑的子图，对这些子图进行正当的缩放，保留子图中任意两点间的间隔，联合图的初始布局使用拉普拉斯子图放弃算法失去联合了多用户输出的更满足用户需要、易于了解的图布局。如下图所示，用户定义了许多形态各异的子图，该算法能够无效的解决子图编辑抵触，以及将编辑过的子图布局融入到初始布局中，连接处晦涩天然，而且子图布局放弃成果十分好。图中数字示意通过算法交融后的子图布局与用户输出的子图布局的类似度，齐全一样为 100%；有趣味的同学能够点击中转

上文说了那么多的布局计划，上面咱们就来看看实在图剖析中的案例吧。下图就是咱们在业务中常常可能会看到的场景，这是惯例的力导布局，节点之间都没有任何重叠，所以整体看起来整张图的关系网络还是比拟清晰的，并且咱们还能够通过点击某个节点高亮其所有一度关系的交互来查看每个节点的关系。咱们这次剖析的目标是要找出 关联度数最多 的节点，因为在很多弱社交关系的场景，某类节点关系简单，往往就意味着危险。

下面的力导布局显然很难帮忙咱们找出度数最多的节点，除非咱们一个节接一个节点地点击用肉眼去统计，然而这显然不太事实。
力导布局 pass，那我来尝试一下树形布局，首先切换到惯例的树形布局（又称有向分层布局）就变成下图左侧的样子了，这布局形式也太长了，我是缩到了很小能力勉强看清整张图的全貌，咱们再切换到相似辐射型的树形布局形式如右侧所示，这时候不必放大咱们就能看清整张图的全貌了，而且节点的档次也十分清晰明了，尽管如此，咱们找的度数最大的节点还是很难分辨进去

树形布局 pass，那咱们再切换成圆形布局试试，上文说到圆形布局个别都是先自定义排序后再布局的，这次咱们的指标是要找出度数最多的节点，那我果决就抉择了按度数排序的形式，最终的后果是下图左侧这样子。emm… 如同有点不太对，我还是没法一眼看出关联度数最多的节点，我尝试点击下布局中右侧的几个节点，因为圆形布局中的节点是依照度数排序后的，从图中能够看出右上局部的节点度数较稠密，有呈逆时针增减减少的趋势，所以只有在图中的右侧找出某个节点的度数比相邻的节点大，那么这个节点就是度数最大的节点，如下图右侧就是我找出的度数最大的节点，然而实际上度数最大的节点也有可能存在多个，因而通过圆形的布局去查找度数最大的节点也不是十分完满。

那咱们在尝试一下同心圆布局，因为同心圆布局能够将度数最大的节点搁置最靠近圆心的地位，实践上来说对于找出度数最大的节点，堪称完满。下图就是同心圆布局的最终成果，不出所料，这种布局对于定位节点度数真的是十分完满，从中咱们疾速定位到度数最大的节点，并且每个节点的度数也都清晰明了。

不同的业务场景，应该抉择什么样的布局才是正当的？本文次要探讨了各种不同场景的布局解决方案，心愿能给大家在图布局方面提供肯定的思路和参考。

文章可随便转载，但请保留此 [原文链接]()。
十分欢送有激情的你退出 ES2049 Studio，简历请发送至 caijun.hcj@alibaba-inc.com。

关于前端:图可视化之图布局

前言

常见的布局计划

各类布局图

各类布局计划以及对应的场景

树形布局

Dagre 布局

力导布局

圆形布局

同心圆布局

增量布局

子图布局

智能布局

图剖析中的布局

总结