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

shenhualong 發(fā)布于2019-08-26 10:21 / 1046人閱讀

摘要：判斷是否成環(huán)執(zhí)行拓?fù)渑判?，如果序列中的頂點數(shù)不等于有向圖的頂點個數(shù)，則說明圖中存在環(huán)。如果訪問過，且不是其父節(jié)點，那么就構(gòu)成環(huán)圖有向無環(huán)圖的最小路徑覆蓋圖存儲鄰接矩陣圖的鄰接矩陣存儲方式是用兩個數(shù)組來表示圖。

何為有向無環(huán)圖？

1、首先它是一個圖，然后它是一個有向圖，其次這個有向圖的任意一個頂點出發(fā)都沒有回到這個頂點的路徑，是為有向無環(huán)圖
2、DAG（Directed Acyclic Graph）不一定能轉(zhuǎn)化為樹，但是樹一定是一個DAG

DAG相關(guān)問題

拓?fù)湫蛄?/p>

圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。拓?fù)渑判蛑饕脕斫鉀Q有向圖中的依賴問題
求一個DAG的一條拓?fù)湫蛄校?br>1.找到當(dāng)前所有的無直接前驅(qū)的節(jié)點(入度為0)，若沒有這樣的頂點，跳到3。若有，從中選一個v，標(biāo)記為已訪問，加入到當(dāng)前序列的尾部，繼續(xù)2。
2.將從v出發(fā)的有向邊全部刪除(這樣會得到一個新的有向圖G’)。
3.如果序列中的頂點數(shù)不等于有向圖G的頂點個數(shù)，則說明圖G中存在環(huán)；如果相等，則該序列即是所求的拓?fù)湫蛄小?br>

{ 1, 2, 4, 3, 5 }

判斷是否成環(huán)

1、執(zhí)行拓?fù)渑判颍绻蛄兄械捻旤c數(shù)不等于有向圖G的頂點個數(shù)，則說明圖G中存在環(huán)。
2、深度優(yōu)先遍歷該圖，如果在遍歷的過程中，發(fā)現(xiàn)某個節(jié)點有一條邊指向已經(jīng)訪問過的節(jié)點，并且這個已訪問過的節(jié)點不是當(dāng)前節(jié)點的父節(jié)點（這里的父節(jié)點表示dfs遍歷順序中的父節(jié)點），則表示存在環(huán)。
換種說法：1條深度遍歷路線中如果有結(jié)點被第二次訪問到，那么有環(huán)。

bool dfs(int i,int pre){
    visit[i]=true;
    for(int j=1;j<=v;j++)
        if(g[i][j])
        {
            if(!visit[j])
                return dfs(j,i);
            else if(j!=pre)  //如果訪問過，且不是其父節(jié)點，那么就構(gòu)成環(huán)
                return true;
        }
}

DAG圖（有向無環(huán)圖）的最小路徑覆蓋

圖存儲

鄰接矩陣

圖的鄰接矩陣（Adjacency Matrix)存儲方式是用兩個數(shù)組來表示圖。一個一維的數(shù)組存儲圖中頂點信息，一個二維數(shù)組（稱為鄰接矩陣）存儲圖中的邊或弧的信息。
設(shè)圖G有n個頂點，則鄰接矩陣是一個n*n的方陣
無向圖：

有向圖：

鄰接表

鄰接表的核心思想就是針對每個頂點設(shè)置一個鄰居表。

以上面的圖為例，這是一個有向圖，分別有頂點a, b, c, d, e, f, g, h共8個頂點。使用鄰接表就是針對這8個頂點分別構(gòu)建鄰居表，從而構(gòu)成一個8個鄰居表組成的結(jié)構(gòu)，這個結(jié)構(gòu)就是我們這個圖的表示結(jié)構(gòu)或者叫存儲結(jié)構(gòu)。

const node = [a, b, c, d, e, f, g, h];
const edges = [{b, c, d, e, f},  // a 的鄰居表
{c, e},  // b 的鄰居表
qoyqs8suu2u,  // c 的鄰居表
{e},  // d 的鄰居表
{f},  // e 的鄰居表
{c, g, h},  // f 的鄰居表
{f, h},  // g 的鄰居表
{f, g}]  // h 的鄰居表

圖布局

graphlib
graphlib提供表示圖的數(shù)據(jù)結(jié)構(gòu)。它不做布局或渲染
darge
dagre執(zhí)行節(jié)點，布局節(jié)點位置，其中所有節(jié)點通過一個graphlib圖表示的布局（x和y定位）。它不會渲染。
dagre-d3
dagre-d3使用dagre進(jìn)行布局，并使用d3進(jìn)行渲染。請注意，dagre-d3默認(rèn)包含dagre和graphlib，如dagreD3.dagre和dagreD3.graphlib。
元素：

graph，即圖整體，我們可以對圖配置一些全局參數(shù)。
node，即頂點，dagre 在計算時并不關(guān)心 node 實際的形狀、樣式，只要求提供維度信息。
edge，即邊，edge 需要聲明其兩端的 node 以及本身方向。例如A -> B表示一條由 A 指向 B 的 edge。
rank，即層級，rank 是 DAG 布局中的核心邏輯單位，edge 兩端的 node 一定屬于不同的 rank，而同一 rank 中的 node 則會擁有同樣的深度坐標(biāo)（例如在縱向布局的 graph 中 y 坐標(biāo)相同）。
label，即標(biāo)簽，label 不是 DAG 中的必要元素，但 dagre 為了適用更多的場景增加了對 edge label 的布局計算。

深入理解rank：

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

A B C分別處于3個rank

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

A 處于rank1，B C都處于A的下一層級rank2

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

在這個示例中，我們發(fā)現(xiàn) edge 兩端的 node 可以相差超過一個 rank。由于 edge 兩端的 node 不可屬于同樣的 rank，所以我們不能讓 B 和 C 屬于同一個 rank，進(jìn)而最優(yōu)的繪制結(jié)果為 A 和 C 之間相隔兩個 rank。
布局算法
DAG 可以用于模型化許多不同種類的信息，因此將一個 DAG 數(shù)據(jù)結(jié)構(gòu)可視化的需求也變得非常普遍。并且由于大部分圖的數(shù)據(jù)都非常復(fù)雜甚至動態(tài)變化，所以自動、可配置的 DAG 可視化布局算法顯然比人為排版更為高效且可靠。
約束條件：

結(jié)點之間不能有重疊

連線之間盡量減少交差

結(jié)點之間是有基本的層次關(guān)系對齊的

主要分4個步驟：
1、消除圖中的環(huán)。
2、尋找最優(yōu)的等級（分層）分配。
3、在同一個等級內(nèi)，設(shè)置頂點的順序，使交叉數(shù)最小。
4、計算頂點的坐標(biāo)。
dagre布局步驟：

removeSelfEdges // 刪除自環(huán)邊
acyclic.run // 反向設(shè)置成環(huán)的邊
rank // 計算最優(yōu)的等級分配
order // 同層排序
insertSelfEdges // 插入自環(huán)邊
position // 計算頂點的坐標(biāo)
acyclic.undo // 恢復(fù)反向邊設(shè)置

尋找成環(huán)的邊：

遍歷所有的節(jié)點，遞歸遍歷每個節(jié)點的出邊，把一條路徑上的所有節(jié)點按路徑順序入棧，當(dāng)遍歷到某個出邊的目標(biāo)點已經(jīng)在這個路徑上遍歷過了，那么這條邊就是成環(huán)的邊，存下來，然后對所有成環(huán)邊反向。

function dfsFAS(g) {
  var fas = [];
  var stack = {};
  var visited = {};

  function dfs(v) {
    if (_.has(visited, v)) {
      return;
    }
    visited[v] = true;
    stack[v] = true;
    _.forEach(g.outEdges(v), function(e) {
      if (_.has(stack, e.w)) {
        fas.push(e);
      } else {
        dfs(e.w);
      }
    });
    delete stack[v];
  }

  _.forEach(g.nodes(), dfs);
  return fas;
}

算法：network-simplex（網(wǎng)絡(luò)單純型） longest-path（最長路徑）

ranker=network-simplex

A->B->C->E;
A->D->F;
A->G->H->I->J;

                +---+        +---+        +---+
               >| B |------->| C |------->| E |
             -/ +---+        +---+        +---+
           -/
    +---+-/     +---+        +---+
    | A |------>| D |------->| F |
    +---+-     +---+        +---+
           -
             - +---+        +---+        +---+        +---+
               >| G |------->| H |------->| I |------->| J |
                +---+        +---+        +---+        +---+

ranker=longest-path
A->B->C->E;
A->D->F;
A->G->H->I->J;
                             +---+        +---+        +---+
                         --->| B |------->| C |------->| E |
                   -----/    +---+        +---+        +---+
             -----/
    +---+---/                             +---+        +---+
    | A |-------------------------------->| D |------->| F |
    +---+-                               +---+        +---+
           -
             - +---+        +---+        +---+        +---+
               >| G |------->| H |------->| I |------->| J |
                +---+        +---+        +---+        +---+

longestPath算法就是快速初始化一個層級關(guān)系，求出來的是一條路徑的盡頭都對齊，定為0，然后逆向路徑計算，都為負(fù)值。
深度優(yōu)先遍歷

function longestPath(g) {
  var visited = {};
  // 深度優(yōu)先
  function dfs(v) {
    var label = g.node(v);
    if (_.has(visited, v)) {
      return label.rank;
    }
    visited[v] = true;
    // g.outEdges(v) v點的出度，v的rank就是他出度的點的層級減去出度的minlen，如果v是指向多個點的，那么就取最小的那個層級
    var rank = _.min(_.map(g.outEdges(v), function(e) {
      return dfs(e.w) - g.edge(e).minlen;
    }));

    if (rank === Number.POSITIVE_INFINITY || // return value of _.map([]) for Lodash 3
        rank === undefined || // return value of _.map([]) for Lodash 4
        rank === null) { // return value of _.map([null])
      rank = 0;
    }
    return (label.rank = rank);
  }
  _.forEach(g.sources(), dfs);
}

緊湊樹型：
1、任意節(jié)點的層級必須滿足邊的長度大于等于邊的minlen最小長度。
2、某條邊的松弛度被定義為其長度和最小長度之間的差值，邊的松弛度為0，則為緊湊的。

從圖中任意找一個節(jié)點，作為起點，從這個點開始遞歸找到一棵最大的緊湊樹，并返回這顆樹的節(jié)點個數(shù)。
遞歸遍歷松弛度為0的節(jié)點加到新的樹上，新樹的節(jié)點個數(shù)少于舊樹的節(jié)點個數(shù)，說明還有節(jié)點因為松弛度大于0而沒被加到新樹上。在所有的邊里找只有起點或者終點只有一個在新樹上的邊，然后判斷邊的兩個端點里不在新樹上的節(jié)點是起點還是終點，如果是起點，則把新樹上所有的點對應(yīng)的舊樹上的點的rank加這個點的松弛度，如果是終點則是減去松弛度。

function tightTree(t, g) {
  function dfs(v) {
    // 遍歷v節(jié)點的所有邊，然后檢查邊的對點是否存在樹上，不存在且該邊是緊湊的即緊湊度是0，則該點可以加到這棵樹上
    _.forEach(g.nodeEdges(v), function(e) {
      var edgeV = e.v,
          w = (v === edgeV) ? e.w : edgeV;
      if (!t.hasNode(w) && !slack(g, e)) {
        t.setNode(w, {});
        t.setEdge(v, w, {});
        dfs(w);
      }
    });
  }

  _.forEach(t.nodes(), dfs);
  return t.nodeCount();
}

                             +---+        +---+        +---+
                         --->| B |------->| C |------->| E |
                   -----/    +---+        +---+        +---+
             -----/            -2           -1           0
    +---+---/                             +---+        +---+
    | A |-------------------------------->| D |------->| F |
    +---+-                               +---+        +---+
     -4    -                               -1           0
             - +---+        +---+        +---+        +---+
               >| G |------->| H |------->| I |------->| J |
                +---+        +---+        +---+        +---+
                  -3           -2           -1           0

                +---+        +---+        +---+
               >| B |------->| C |------->| E |
             -/ +---+        +---+        +---+
           -/     -2           -1           0
    +---+-/                               +---+        +---+
    | A |-------------------------------->| D |------->| F |
    +---+-                               +---+        +---+
     -3    -                               -1           0
             - +---+        +---+        +---+        +---+
               >| G |------->| H |------->| I |------->| J |
                +---+        +---+        +---+        +---+
                  -2           -1           0           1

                +---+        +---+        +---+
               >| B |------->| C |------->| E |
             -/ +---+        +---+        +---+
           -/     -1           0            1
    +---+-/     +---+        +---+
    | A |------>| D |------->| F |
    +---+-     +---+        +---+
     -2    -     -1           0
             - +---+        +---+        +---+        +---+
               >| G |------->| H |------->| I |------->| J |
                +---+        +---+        +---+        +---+
                  -1           0            1            2

排序：
每層中的頂點順序決定了布局的邊交叉情況，因此一個好的層級內(nèi)頂點順序應(yīng)該要盡量少產(chǎn)生交叉邊。
前提條件：分配完層級之后，跨越多個層級的邊會被替換成由多條連接臨時節(jié)點或者“虛擬節(jié)點”的單位長度的邊。虛擬節(jié)點被安插到中間層級上，使得整張圖中所有邊都只連接相鄰層級的節(jié)點。
理論：
把多層的DAG圖，分成一個個的雙層圖，兩層兩層的進(jìn)行排序。當(dāng)訪問某一層時，這一層每個頂點都會根據(jù)其關(guān)聯(lián)的上一層頂點的位置分配一個權(quán)重。然后這一層的頂點會根據(jù)這個權(quán)重進(jìn)行排序。
權(quán)重計算：定義一個兩層圖，下層節(jié)點根據(jù)上層節(jié)點排序，下層每個頂點v的權(quán)重等于：
每條與v關(guān)聯(lián)的邊的weight*order/sumWeight。weight是邊的權(quán)重，默認(rèn)為1，order是邊的上層節(jié)點在上層的排序，sumWeight是關(guān)聯(lián)邊的權(quán)重總和。
然后我們就可以執(zhí)行一系列迭代嘗試改進(jìn)這個順序，直到找到一個滿意的解時停止迭代。
啟發(fā)式迭代：
biasRight：重心相等時索引小的左偏還是右偏
downLayerGraphs：從上到下分層，n行根據(jù)n-1行排序
upLayerGraphs：從下到上分層，n行根據(jù)n+1行排序
重心相等時索引小的左偏的情況下，先從下到上分層掃描，排序；再進(jìn)行從上到下分層掃描，排序；
重心相等時索引小的右偏的情況下，先從下到上分層掃描，排序；再進(jìn)行從上到下分層掃描，排序；
每次排序后都會計算交叉點個數(shù)，如果交叉?zhèn)€數(shù)更好了，則替換節(jié)點矩陣，然后再進(jìn)行上述的4邊掃描，直到上述4遍掃描后都沒有再取得更優(yōu)解，迭代結(jié)束。

A->B;
A->C;
A->F
B->E;
C->D;
C->G;
F->D;

原始圖:

第一次迭代：從下到上分層掃描，左偏

crossCount = 1
第二次迭代：再進(jìn)行從上到下分層掃描，左偏

crossCount = 1
第三次迭代：從下到上分層掃描，右偏

crossCount = 0
獲得了更優(yōu)解，這個迭代周期結(jié)束，重新開始一個迭代周期，在這個迭代周期都沒有再找到更優(yōu)解，迭代結(jié)束
輸出矩陣:

[
  [A],
  [25, 27, 26],
  [B, F, C],
  [28, 31, 29, 30],
  [E, D, G]
]

下面是上述過程的代碼：

function order(g) {
  var maxRank = util.maxRank(g),
      downLayerGraphs = buildLayerGraphs(g, _.range(1, maxRank + 1), "inEdges"), // 從上到下分層，n行根據(jù)n-1行排序
      upLayerGraphs = buildLayerGraphs(g, _.range(maxRank - 1, -1, -1), "outEdges"); // 從下到上分層，n行根據(jù)n+1行排序
  var layering = initOrder(g);
  assignOrder(g, layering);
  var bestCC = Number.POSITIVE_INFINITY,
      best;
  for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) {
    sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2); // 掃描按權(quán)重排序
    layering = util.buildLayerMatrix(g); // 節(jié)點id的矩陣
    var cc = crossCount(g, layering); // 返回當(dāng)前矩陣下交叉點個數(shù)
    if (cc < bestCC) {
      lastBest = 0;
      best = _.cloneDeep(layering);
      bestCC = cc;
    }
  }
  assignOrder(g, best);
}

計算頂點坐標(biāo)：
節(jié)點的層號和層內(nèi)序號確定后,布局結(jié)果的基本框架就已經(jīng)確定了.一般有向圖可以采用在垂直方向或者水平方向按序號遞增的方式分別分配縱坐標(biāo)和橫坐標(biāo)。

實際應(yīng)用場景

1、依賴關(guān)系：
可視化項目依賴，組件依賴關(guān)系：比如打包編譯依賴的時候，把各種包的依賴關(guān)系按照拓?fù)湫蛄信判颍纫肱旁谇懊娴陌?，后引入排在后面的包?br>2、調(diào)度流程：
自動化布局UML圖，workflow等。
事項流程：

spark任務(wù)執(zhí)行：大規(guī)模數(shù)據(jù)處理計算引擎

UML類圖

兒茶酚胺合成代謝路徑

3、決策樹：鄙視鏈案例-婚姻市場中的房市

4、復(fù)雜人物關(guān)系鏈分析：紅樓夢

參考資料：
http://jgaa.info/accepted/200...
http://www.jos.org.cn/jos/ch/...
http://leungwensen.github.io/...

GPU云服務(wù)器云服務(wù)器無環(huán)圖自動布局 python有向圖環(huán) js繪制有向圖

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/106039.html

發(fā)表評論

登陸后可評論

0條評論

shenhualong

男|高級講師

我要關(guān)注我要私信

TA的文章

Toxic-Host：羅馬尼亞VPS / 羅馬尼亞VDS 服務(wù)器起價每臺 $1.50/月起，羅馬尼亞

閱讀 1398·2021-10-19 11:42
虛擬主機的意思是什么-服務(wù)器與虛擬主機有什么區(qū)別？

閱讀 735·2021-09-22 16:04
BuyVM新增解鎖流媒體VPS主機,1Gbps不限流量$5/月起

閱讀 1886·2021-09-10 11:23
SugarHosts糖果主機云服務(wù)器管理安裝系統(tǒng)/備份/快照/防火墻

閱讀 1865·2021-07-29 14:48
騰訊云618活動,老用戶云服務(wù)器續(xù)費3折,新用戶2核4G內(nèi)存5M帶寬488元/年

閱讀 1265·2021-07-26 23:38
前端每日實戰(zhàn)：66# 視頻演示如何用純 CSS 創(chuàng)作一臺咖啡機

閱讀 2825·2019-08-30 15:54
html5 autocomplete='off' 解決 Chrome瀏覽器取消i

閱讀 1040·2019-08-30 11:25
FE.ES-理解ECMA Javascript作用域

閱讀 1709·2019-08-29 17:23

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

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

IaC 自動化配置與編排神器 - Terraform 深度解析

算法（第4版） Chapter 4.2 有向圖

Spark Streaming遇到問題分析

發(fā)表評論

0條評論

shenhualong

男|高級講師

TA的文章

Toxic-Host：羅馬尼亞VPS / 羅馬尼亞VDS 服務(wù)器起價每臺 $1.50/月起，羅馬尼亞

虛擬主機的意思是什么-服務(wù)器與虛擬主機有什么區(qū)別？

BuyVM新增解鎖流媒體VPS主機,1Gbps不限流量$5/月起

SugarHosts糖果主機云服務(wù)器管理安裝系統(tǒng)/備份/快照/防火墻

騰訊云618活動,老用戶云服務(wù)器續(xù)費3折,新用戶2核4G內(nèi)存5M帶寬488元/年

前端每日實戰(zhàn)：66# 視頻演示如何用純 CSS 創(chuàng)作一臺咖啡機

html5 autocomplete='off' 解決 Chrome瀏覽器取消i

FE.ES-理解ECMA Javascript作用域

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！