Graph 數(shù)據(jù)可視化：JS 自動布局有向無環(huán)圖

zhouzhou 發(fā)布于2019-08-26 11:52 / 3302人閱讀

摘要：可以用于模型化許多不同種類的信息，因此將一個數(shù)據(jù)結構可視化的需求也變得非常普遍。并且由于大部分圖的數(shù)據(jù)都非常復雜甚至動態(tài)變化，所以自動可配置的可視化布局算法顯然比人為排版更為高效且可靠。

有向無環(huán)圖（DAG）布局 有向無環(huán)圖及其布局算法

有向無環(huán)圖（directed acyclic graph，以下簡稱 DAG）是一種常見的圖形，其具體定義為一種由有限個頂點和有限條帶有方向的邊組成的圖，并且其中任意一個頂點都不能沿著邊再次指向自己。

DAG 可以用于模型化許多不同種類的信息，因此將一個 DAG 數(shù)據(jù)結構可視化的需求也變得非常普遍。并且由于大部分圖的數(shù)據(jù)都非常復雜甚至動態(tài)變化，所以自動、可配置的 DAG 可視化布局算法顯然比人為排版更為高效且可靠。

為滿足筆者所在項目一個可視化功能（其邏輯可視為一個 DAG）的開發(fā)，我們需要一個可在瀏覽器端進行布局計算的 js 庫，并且基于計算結果進行渲染。經(jīng)過調研，社區(qū)的一個項目 dagre 基本可以滿足我們的需求，但需要徹底掌握其計算邏輯我們還需要理解一些基本概念和對應配置項之間的關系。

基本概念

dagre 主要基于《A Technique for Drawing Directed Graphs》的理論進行實現(xiàn)，因此也有以下幾類單位：

graph，即圖整體，我們可以對圖配置一些全局參數(shù)。

node，即頂點，dagre 在計算時并不關心 node 實際的形狀、樣式，只要求提供維度信息。

edge，即邊，edge 需要聲明其兩端的 node 以及本身方向。例如A -> B表示一條由 A 指向 B 的 edge。

rank，即層級，rank 是 DAG 布局中的核心邏輯單位，edge 兩端的 node 一定屬于不同的 rank，而同一 rank 中的 node 則會擁有同樣的深度坐標（例如在縱向布局的 graph 中 y 坐標相同）。下文中我們會用示例 graph 進一步解釋 rank 的作用。

label，即標簽，label 不是 DAG 中的必要元素，但 dagre 為了適用更多的場景增加了對 edge label 的布局計算。

深入 rank

接下來的示例中我們會用一種易懂的描述語言表達一個 DAG 的 node 與 edge：A -> B代表 A 和 B 兩個 node 以及一條由 A 指向 B 的 edge。

示例 1

A->B;
B->C;

    +---+       +---+        +---+  
    | A |------>| B |------->| C |  
    +---+       +---+        +---+

在這個示例中，node A, B, C 分別屬于 3 個 rank。

示例 2

A->B;
A->C;

                +---+
            --> | B |
    +---+--/    +---+
    | A |
    +---+--    +---+
            --> | C |
                +---+

在這個示例中，A 在 rank1 中，而 B 和 C 都比 A 低一個層級，屬于 rank2，因此 B 和 C 擁有同樣的 x 坐標（示例圖為橫行延伸，因此深度方向為 x 方向）。

示例 3

A->B;
B->C;
A->C;

                +---+
             -->| B |---
    +---+---/   +---+    --->+---+  
    | A |                    | C |  
    +---+------------------->+---+

在這個示例中，我們發(fā)現(xiàn) edge 兩端的 node 可以相差超過一個 rank。由于 edge 兩端的 node 不可屬于同樣的 rank，所以我們不能讓 B 和 C 屬于同一個 rank，進而最優(yōu)的繪制結果為 A 和 C 之間相隔兩個 rank。

在這三個例子中，我們已經(jīng)對 rank 的含義和規(guī)則有了更好的理解，接下來可以看看 dagre 允許我們對各類布局元素做怎樣的配置。

GPU云服務器云服務器無環(huán)圖 js繪制有向圖自動布局可視化布局

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/107710.html

有向無環(huán)圖自動布局

摘要：判斷是否成環(huán)執(zhí)行拓撲排序，如果序列中的頂點數(shù)不等于有向圖的頂點個數(shù)，則說明圖中存在環(huán)。如果訪問過，且不是其父節(jié)點，那么就構成環(huán)圖有向無環(huán)圖的最小路徑覆蓋圖存儲鄰接矩陣圖的鄰接矩陣存儲方式是用兩個數(shù)組來表示圖。何為有向無環(huán)圖？ 1、首先它是一個圖，然后它是一個有向圖，其次這個有向圖的任意一個頂點出發(fā)都沒有回到這個頂點的路徑，是為有向無環(huán)圖2、DAG（Directed Acyclic G...

shenhualong 2019-08-26 10:21 評論0 收藏0
IaC 自動化配置與編排神器 - Terraform 深度解析

摘要：而對于依賴關系的抽象，業(yè)界最通行的做法即使用有向無環(huán)圖，來描述事務間的依賴關系。圖表并行遍歷，執(zhí)行資源動作從根節(jié)點開始，并行地去編排整個資源拓撲，遍歷整個有向無環(huán)圖，直到所有資源都被成功編排，并執(zhí)行清理操作。前言Terraform 是 Hashicorp 公司開源的一種多云資源編排工具。使用者通過一種特定的配置語言（HCL Hashicorp Configuration Language）來...

Tecode 2022-06-28 18:59 評論0 收藏0
Spark Streaming遇到問題分析

摘要：遇到問題分析之后搞了個還沒仔細了解可參考的與的有區(qū)別及并發(fā)控制先看看的，與的這幾個概念。一個可以認為就是會最終輸出一個結果的一條由組織而成的計算。在中，我們通過使用新極大地增強對狀態(tài)流處理的支持。 Spark Streaming遇到問題分析 1、Spark2.0之后搞了個Structured Streaming 還沒仔細了解,可參考：https://github.com/lw-lin/...

stormzhang 2019-08-15 10:52 評論0 收藏0
算法（第4版） Chapter 4.2 有向圖

摘要：只好特地拎出來記錄證明一下算法步驟第一步在逆圖上運行，將頂點按照逆后序方式壓入棧中顯然，這個過程作用在有向無環(huán)圖上得到的就是一個拓撲排序作用在非上得到的是一個偽拓撲排序第二步在原圖上按第一步的編號順序進行。等價于已知在逆圖中存在有向路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...

曹金海 2019-08-14 17:13 評論0 收藏0
【超越白皮書3】DAG技術解析與實測

摘要：有向無環(huán)圖，以下簡稱是其中的代表之一。的去中心化和可擴展性可認為是一體兩面的，因為基于數(shù)據(jù)結構帶來的異步記賬特性，同時實現(xiàn)了高度的參與網(wǎng)絡節(jié)點的去中心化和交易的可擴展性。因此，目前對于雙花問題，需要綜合考慮實際情況進行設計。本報告由火幣區(qū)塊鏈研究院出品，作者：袁煜明、胡智威。原文地址相關報告：【超越白皮書2】EOS主網(wǎng)上線前夕的實測分析與技術建議【超越白皮書1】EOSIO程序實...

caikeal 2019-06-27 18:33 評論0 收藏0