前端如何绘制DAG图？

这次分享一个半年前在公司内某团队的一段经历，摘取全部功能中较为通用的、与业务无关的一小部分来聊一聊。

一、DAG 图是什么？

DAG 全称是 Directed Acyclic Graph，中文名是有向无环图，是逻辑图像的一种。

如果一幅图由一个个独立的节点，以及具有方向的连线组成，并且任何一个节点都不可能通过遍历连线回到自身，那么这幅图即可称之为 DAG 图。

简单来说就是整个图表渲染有一个统一的方向，并且不会形成任何回路。

更专业的介绍请移步至wikipedia。

二、业务里有没有附加约束？

宽泛的来聊 DAG 的图像绘制比较无聊，因为 DAG 图像可以被绘制成任何样子。并且标准的 DAG 图像允许有多个起点、终点。

在我们的业务里，对 DAG 图的应用做了更细致的规范设计，与渲染相关的如下：

1、业务所使用的 DAG 需要有一个起始节点，并且只允许有一个结束节点。有点类似于平时所见的流程图，区别于流程图就是这个业务的流程是单向的。

2、节点分为两种，一种是承载业务的功能节点，另一种是用发来发散、收拢分支的虚拟节点。它们总是成对出现，类似于 for 循环中的 { 和 }。

图一、DAG 示例截图

三、DAG 数据模型设计

知道了 DAG 图是什么，业务里的规范，以及效果图，接下来需要动手去实现了。

为了实现工作流 DAG 图表的渲染，我们需要构建出一个干净、严谨的数据模型做支持，并且需要相关算法辅助渲染和编辑。

根据 DAG 图表有向、无环这个两个特点，我们在数据模型上做了两层抽象。

第一层为图表自身，包含布局信息、节点列表、关联列表及配备丰富的方法支持，是定义整个 DAG 的上层模型。

第二层为节点 node、关联 relation。

node 承载独立节点的详细配置，及屏幕坐标数据。

relation 模型则相对简单，仅描述起始、目标节点 id，并附带屏幕坐标数据。

借助于这两层数据模型设计，即可描述一个 DAG 图表的流转信息及各个节点的数据存储。

图二、DAG 图表数据模型

四、DAG 渲染算法

在提到渲染算法前，我们先聊聊图表渲染的逻辑。常规图表有两种渲染逻辑，一种是自由拖拽，另一种是自适应渲染。

自由拖拽随意性较高，用户可以随意将节点拖放到任意位置，问题在于节点的增删可能会导致图表过于凌乱。

而自适应渲染则需要根据图表数据对节点位置做调整，无论节点增删都会展示整齐的布局。弊端也很明显，用户无法自由的调整节点位置。

根据我们业务的一些特性我们最终采用了后面的方案，即自适应渲染。

相信你已经注意到了，在上面数据模型部分有提到，节点、关联线部分均有屏幕坐标数据，这里的坐标是如何计算出来的呢？

4.1、示例代码

我们以一个例子展开，画布上有八个节点，关联关系如下面数据所示：

<code>let nodeList = ['a', 'b', 'c', 'd', 'e'， 'f', 'g', 'h']
let relationList = [
  ['a', 'b'],
  ['a', 'c'],
  ['b', 'd'],
  ['d', 'h'],
  ['c', 'e'],
  ['c', 'f'],
  ['e', 'g'],
  ['f', 'g'],
  ['g', 'h']
]
复制代码/<code>

希望你能看明白这个两个数组的作用，这很重要，因为它对应了数据模型里的节点列表和关联线列表。你可以拿出一张纸，试着画一下这幅图的大致样貌。

下面按照渲染顺序简单聊聊我们用到的算法。

4.2、寻找图形的起点

这是我们需要的第一个算法，单纯看数据可能没有头绪，但是把逻辑简单理一理就能很快写出查找起点的方法。

在一个正常的 DAG 图表中，除了起点和终点，任何一个节点都会有上下游关系，而起点只会有下游节点，终点只会存在上游节点。

因此我们可以把起点描述成：

根据这个逻辑，可以把 relationList 做以下转换：

<code>// 原始关联列表
let relationList = [
  ['a', 'b'],
  ['a', 'c'],
  ['b', 'd'],
  ['d', 'h'],
  ['c', 'e'],
  ['c', 'f'],
  ['e', 'g'],
  ['f', 'g'],
  ['g', 'h']
]

// 枚举出全部上游、下游数据
let fromList = ['a', 'a', 'b', 'd', 'c', 'c', 'e', 'f', 'g']
let toList = ['b', 'c', 'd', 'h', 'e', 'f', 'g', 'g', 'h']

// 做去重处理
fromList = ['a', 'b', 'd', 'c', 'e', 'f', 'g']
toList = ['b', 'c', 'd', 'h', 'e', 'f', 'g']

// 去除同时存在于上游、下游列表中的节点
fromList = ['a']
toList = ['h']

// 得到起点、终点
let root = fromList[0] // 'a'
let end = toList[0] // 'h'

复制代码/<code>

通过这样一番转换，我们就得到了起点、终点，是不是很简单？

当然，这里有两种异常情况要处理！

一是 fromList 或 toList 可能为空，只要其中一个为空，图表必然存在环状结构，不符合 DAG 的定义，即数据不合法。

另一种是 fromList 或 toList 的返回长度大于一，即有多个起点或终点。这虽然符合 DAG 的定义，但是不符合我们业务对 DAG 的约束，此类异常也可以归类于数据不合法。

4.3、查找从起点到终点的全部路径

这一步是构建可视化的关键，后面的渲染都会基于此次计算的结果。

查找从起点到终点的全部路径是什么意思？简单来说就是列出从起点到终点所有的走法，类似于百度地图导航时的行程规划。

相对于导航，DAG 图表的路径遍历还算简单，因为在起点明确后，我们只需要通过递归查找节点的下游即可枚举出全部路径。过程如下：

<code>// 原始关联列表
let relationList = [
  ['a', 'b'],
  ['a', 'c'],
  ['b', 'd'],
  ['d', 'h'],
  ['c', 'e'],
  ['c', 'f'], 

  ['e', 'g'],
  ['f', 'g'],
  ['g', 'h']
]
// 上一步查找到的起点
let root = 'a'

// 定义方法：查找下游节点
const findLowerNodes = nodeName => {
\tlet lowerNodes = []
\tlet hasUpperNodeRelations = relationList.forEach(item => {
    if (item[0] === nodeName) {
\t\t\tlowerNodes.push(item[1])
\t\t}
  })
  return lowerNodes
}
// 定义方法：递归查找下有节点
const recursionGetPath = (nodeName, basePath, pathList) => {
\tbasePath = basePath || []
  pathList = pathList || []
\tbasePath.push(nodeName)
\tlet lowerNodes = findLowerNodes(nodeName)
\tlowerNodes.forEach(lowerNodeName => {
\t\t// 制作 path 副本
\t\tlet newBasePath = basePath.slice(0)
\t\trecursionGetPath(lowerNodeName, newBasePath, pathList)
\t})
\tif (lowerNodes.length === 0) {
\t\tpathList.push(basePath)
\t}
  return pathList
}
// 从起点 'a' 开始，递归查找下游节点
let pathList = recursionGetPath(root)

// 得到 path list
pathList = [
\t["a", "b", "d", "h"],
\t["a", "c", "e", "g", "h"],
\t["a", "c", "f", "g", "h"]
]

复制代码/<code>

通过这个过程，我们可以获得以下信息，这张图表从起点有三条路径可以走到终点，最大的一条路径需要经历五个节点，最短的仅需要四个节点。

可能你还看不出这个 pathList 有什么作用，咱们继续往下走。

4.4、 构建流程图雏形

流程图的绘制需要一个二维的结构，上一步的全部路径可以作为二维结构的基础，我们再来做一次转换。

<code>// 上一步的结果
pathList = [
\t["a", "b", "d", "h"],
\t["a", "c", "e", "g", "h"],
\t["a", "c", "f", "g", "h"]
]

// 二维数组旋转90度
let map = [
  ['a', 'a', 'a'],
  ['c', 'c', 'b'],
  ['f', 'e', 'd'],
  ['g', 'g', 'h'],
  ['h', 'h']
]

// 行内去重
let map = [
  ['a'],
  ['c', 'b'],
  ['f', 'e', 'd'],
  ['g', 'h'],
  ['h']
]
// 全局去重，优先保留下方的节点 

let map = [
  ['a'],
  ['c', 'b'],
  ['f', 'e', 'd'],
  ['g'],
  ['h']
]
复制代码/<code>

看到 map 的数据结构，是不是感觉有点意思了，咱们继续往下走。

4.5、绘制流程图

上一步的 map 是 DAG 图绘制的准备工作，接下来我们结合 relationList 对数据做进一步的解释。

<code>// 上一步的结果
let map = [
  ['a'],
  ['c', 'b'],
  ['f', 'e', 'd'],
  ['g'],
  ['h']
]
// 原始关联列表
let relationList = [
  ['a', 'b'],
  ['a', 'c'],
  ['b', 'd'],
  ['d', 'h'],
  ['c', 'e'],
  ['c', 'f'],
  ['e', 'g'],
  ['f', 'g'],
  ['g', 'h']
]

/**
 * DAG 图形结构
 *   a
 *   ↓  ↘
 *   c     b
 *   ↓  ↘   ↘ 

 *   f    e    d
 *   ↓  ↙   ↙
 *   g    ↙
 *   ↓ ↙
 *   h
**/
复制代码/<code>

到这一步，整个 DAG 图的雏形就已经出来了。

整个例子中的 'a' 'b' 'c' 只是说明的示例，【图二、DAG 图表数据模型】中提到过，每个节点都是一个独立结构的对象，包含屏幕显示的位置信息。这一步就是计算节点在屏幕坐标的时机。

4.5.1、计算每个节点坐标

数据模型部分，map -> layout 部分会在特定时候记录画布尺寸，并且预先配置了节点水平间距范围、垂直间距范围。

根据上一步计算出的 map 行数及最大宽度，与 map -> layout 的配置项相计算，即可得出每个节点所在坐标。

这里就不展开代码实现了，需要注意的是，要根据上下游节点关系适当调节各个节点水平位置，保证视觉稳定性。

4.5.2、计算关联线坐标

关联线的坐标计算放在最后一步，因为这是最简单的一步，我们只需要将起、止节点的坐标拷贝过来即可。

4.5.3、页面绘制

因为各个节点、连线的坐标已经计算完毕，接下来就是依葫芦画瓢了。

我们可以用 svg、canvas、CSS，或者 D3 之类的任何一种方法做绘制。

图三、DAG 示例效果草图

结尾

可能看完你会骂小剧：“说好的教我绘制 DAG，一行绘制代码都没写！”

其实这是我们在做复杂业务的常态，如果你能把逻辑思考清楚，一、二、三步列出来，你最终要的东西自然就浮现在眼前了。

就像本文分享的 DAG 图绘制，在没有现成工具可用的前提下，如果你能在一开始就把数据结构设计清楚，数据转换过程明确下来，最终的绘制相对变得就不那么重要了。

作者：剧中人
链接：https://juejin.im/post/5e66cb9451882549507b1a27
来源：掘金

閱讀更多 啟迪雲Tuscloud 的文章

關鍵字: 设计 全称 维基百科