淺談圖的層次佈局

簡介

圖是一種常見的數據結構和表示形式，可視化場景也經常會用到圖來展現有關聯關係的數據。進行圖的可視化時，往往需要將其自動佈局，而針對不同的問題和場景，需要不同的佈局方法。本文主要介紹圖的層次佈局的思路。

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

圖的層次佈局

在數據有一定層級結構或先後順序時，經常會用到層次佈局來展現，一般對應的數據結構是 DAG（Directed Acyclic Graph，即有向無環圖）。常用的場景包括：流程圖、組織架構圖、狀態轉移圖等。

層次佈局 [2] 的方法是 Kozo Sugiyama 首先於 1981 年詳細闡明的，因此也常被稱爲 Sugiyama 佈局。這裏我們講一下 Sugiyama 佈局的思路。

目的

根據圖的數據，自動畫出一個易於理解的有層次 (hierarchy) 的圖。

節點的佈局是有層次的 - Hierarchical
邊的交叉儘可能的少 - Less Crossing
邊的路徑儘量可以是一條直線 - Straight
邊的路徑儘可能的短 - Close
佈局儘可能平衡 - Balanced

畫圖的基本規則

如何放置節點 - 每一層的節點都放在同一水平線上，且不重疊
如何畫邊 - 每條邊都通過直線畫出

這樣，給節點分層後，把每層的節點放到合理的水平位置，就可以把圖畫出來。

佈局思路

根據以上原則，Sugiyama 把圖的佈局問題分成了多個步驟，每個步驟解決不同的子問題。Sugiyama 算法總共分爲以下 4 步。

步驟 1：節點分層

根據邊的方向，把節點劃分到不同層
如果有邊跨越了多層，在穿過的每一層增加一個僞節點與其相連，保證每條邊只連接相鄰的兩層
如圖 (a)

步驟 2：減少交叉

改變每層的節點的順序來減少邊的交叉
如圖 (a) -> (b)

步驟 3：計算節點座標

在保證上一步的節點順序的基礎上，調整節點的水平位置來滿足上述 Straight、Close、Balanced 原則
如圖 (b) -> (c)

步驟 4：畫圖

根據之前步驟生成的節點位置把圖畫出來，並移除僞節點和邊。
如圖 (c)

每一步的具體算法

看起來是很簡單的 4 步，但每一步的實現都並不簡單，也有很多種不同的算法。

節點分層

怎麼把節點分到不同的層呢？這裏介紹幾種算法。

最長路徑算法 (Longest Path)

首先最容易想到的可能就是最長路徑算法。即一個節點的層級等於要到達它需要走過的最長路徑。最長路徑算法的優點是速度很快，遍歷圖即可完成分層。然而它有比較明顯的問題：節點被分到儘可能低的層級，給圖的下方留出很多空白，並且可能會出現很多長邊。不過，由於它速度快，經常被用於分層的預處理，粗分層後再交給其他算法來進行優化。

一個最長路徑算法得到的結果，截自 d3-dag[3]

緊緻樹 (Tight Tree)

緊緻樹算法就是一種優化方法，目的是減少長邊的數量。從名稱可以看出，「緊緻」，即調整節點的分層，使更多邊變成 “緊緻邊”。

主要思路：

前提
每條邊需要給定一個最小長度，比如 1。
計算鬆弛度 delta：邊的長度 - 最小長度。如果松弛度爲 0，則爲緊緻邊。
把所有緊緻邊和節點加入緊緻生成樹
每次取鬆弛度最小的邊
如果 source 節點已在緊緻樹中，把 target 節點向上移 delta 層級
如果 source 節點不在緊緻樹中，把 source 節點向下移 delta 層級
循環，直到緊緻樹中已經包含了所有的節點
Network Simplex
目的：減少邊的總長度（也就會減少僞節點的數量）
思路：
用緊緻生成樹來表示圖並得到節點的層級。目的是找到一個最優的生成樹。
邊的切割值 (cut value)：在生成樹中，如果移除某條邊，圖會被分成 2 部分，邊的切割值爲所有 source 部分指向 target 部分的邊數減去 target 部分指向 source 部分的邊數。
一般情況下，儘可能延長切割值爲負的邊可以減少邊的總長度
在緊緻生成樹的基礎上，計算每條邊的切割值，移除切割值爲負的邊，另找一條邊來構建更優的生成樹，直到所有的邊的切割值都非負。如圖 (a)，實線爲當前的生成樹，邊上的數字爲切割值，g->h 的切割值爲負，從生成樹中移除後重新得到了圖(b) 的更優的生成樹。

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

減少交叉

怎樣畫一個圖纔是美觀、可理解的是比較主觀的，但儘可能減少邊的交叉這個標準得到了廣泛的認可。

由於節點已經分層，縱座標已確定，且對於每個長邊也已經通過增加僞節點的方式被分成了相鄰層之間的短邊，減少邊的交叉問題就變成了如何對層內節點排序的問題。

然而已經有研究證明，即使是最簡單的情況，即只處理兩層之間的交叉，這個問題仍是一個 NP 困難 [5] 問題。因此，很多啓發式算法被提出來解決這個問題，比較經典的是重心算法和中心算法。

重心法 (Barycenter)
基本原理是認爲層次圖中，垂直的邊越多，邊的交叉越少
一層一層從上往下 & 從下往上掃，每次假定層 i-1 中順序固定，對層 i 排序來減少交叉
層 i 中每一個節點的位置由所有在層 i-1 上和其鄰接的節點位置的平均值決定，這個值即爲節點的重心值。每一層中按重心從小到大排序。
中心法 (Median)
和重心定位類似，區別是它用中位的那個鄰接節點的位置來計算排序值。

計算座標

根據此前所述原則，計算每層節點的座標主要的目的是：邊儘量垂直、節點佈局平衡、長邊儘量直。

Sugiyama 提出了一種二次規劃算法 (Quadratic Programming) 和一種基於優先級的啓發式算法（我都沒看懂）。之後也有很多研究者提出了多種不同的算法。

這裏介紹一下 dagre 中使用的 Brandes & Kopf 提出的一種簡單快速的啓發式算法，在線性時間內即可完成座標計算。（不過這個算法似乎會導致一些異常情況，見 issue[6]）

思路：儘可能把節點和其中位的鄰接節點對齊，來減少邊的長度並平衡佈局。

步驟
垂直對齊。
嘗試將每個節點與其上層或下層的中位鄰接節點對齊。
對齊的過程中可能會有衝突 - 即邊交叉或連接到同一個節點時。採用左側優先或右側優先對齊，忽略後續衝突節點。如圖 (a) -> (b)，是一個向上對齊、左側優先的例子。
水平壓縮。
將對齊的節點放在相同的水平座標，如圖 (b) -> (c)
在水平方向進行壓縮，使節點儘可能接近，如圖 (c) -> (d)
前兩步在對齊時可以向上或向下對齊，解決衝突時可以左側或右側優先。因此在四個方向（左上、左下、右上、右下）上各執行一次前兩步，最終結果由這四個結果平衡後得出。

其它考慮

實際佈局的過程中，可能還會有更多需要考慮的點。這裏列舉一些供大家參考，就不詳細展開了。

增量佈局
在圖新增節點和邊時，儘量保持原有的佈局不變。
圖的嵌套
有時，圖的節點有嵌套關係

一個有嵌套的圖，截自 ELK[7]

邊的 label
邊上可能會有一些描述性的文字，計算位置時需要把 label 也考慮進來
邊的畫法
在上述的 Sugiyama 算法中，邊是畫成直線的（長邊是折線）。而實際場景中，邊可以展示成曲線、或水平 / 垂直走向的折線 (Orthogonal) 等等，不同的邊的形式需要不同的算法來處理。
節點的端口
上述算法中，節點是被看成點，邊是直接和節點相連的，而實際應用中，經常會給節點定義一些端口 (ports)，即指定邊必須從某個端口連入或連出。

實現自己的佈局

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); }); }

總結

本文主要介紹了圖的層次佈局的基本思路、步驟和相關算法
層次佈局主要分爲 4 步：節點分層、減少交叉、計算座標、畫圖。或者是 5 步 (即包括首先通過去環算法把有環圖轉換成無環圖)
每一步都是一個複雜的子問題，有很多啓發式算法被提出來解決相關問題，在具體業務場景的基礎上，也可以使用自己的算法解決問題。

References

Github - dagre/dagre[9]
Github - d3-dag[10]
G6[11]
Eclipse Layout Kernel[12]
Wiki - Layered Graph Drawing[13]
圖可視化之圖佈局 [14]
深入解讀 Dagre 佈局算法 [15]
Methods for Visual Understanding of Hierarchical System Structures[16]
A Technique for Drawing Directed Graphs[17]
Fast and Simple Horizontal Coordinate Assignment[18]
Layout of Compound Directed Graphs[19]
An Efficient Implementation of Sugiyama’s Algorithm for Layered Graph Drawing[20]
Port Constraints in Hierarchical Layout of Data Flow Diagrams[21]
Improved Vertical Segment Routing for Sugiyama Layouts[22]

參考資料

[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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/68I6SXlrdMS84AqLm8daKQ

簡介