前端如何繪製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 的文章

關鍵字: 設計 全稱 維基百科