摘要：判斷是否成環執行拓撲排序，如果序列中的頂點數不等于有向圖的頂點個數，則說明圖中存在環。如果訪問過，且不是其父節點，那么就構成環圖有向無環圖的最小路徑覆蓋圖存儲鄰接矩陣圖的鄰接矩陣存儲方式是用兩個數組來表示圖。

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

拓撲序列

圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。拓撲排序主要用來解決有向圖中的依賴問題
求一個DAG的一條拓撲序列：
1.找到當前所有的無直接前驅的節點(入度為0)，若沒有這樣的頂點，跳到3。若有，從中選一個v，標記為已訪問，加入到當前序列的尾部，繼續2。
2.將從v出發的有向邊全部刪除(這樣會得到一個新的有向圖G’)。
3.如果序列中的頂點數不等于有向圖G的頂點個數，則說明圖G中存在環；如果相等，則該序列即是所求的拓撲序列。

{ 1, 2, 4, 3, 5 }

判斷是否成環

1、執行拓撲排序，如果序列中的頂點數不等于有向圖G的頂點個數，則說明圖G中存在環。
2、深度優先遍歷該圖，如果在遍歷的過程中，發現某個節點有一條邊指向已經訪問過的節點，并且這個已訪問過的節點不是當前節點的父節點（這里的父節點表示dfs遍歷順序中的父節點），則表示存在環。
換種說法：1條深度遍歷路線中如果有結點被第二次訪問到，那么有環。

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)  //如果訪問過，且不是其父節點，那么就構成環
                return true;
        }
}

DAG圖（有向無環圖）的最小路徑覆蓋

鄰接矩陣

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

有向圖：

鄰接表

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

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

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

graphlib
graphlib提供表示圖的數據結構。它不做布局或渲染
darge
dagre執行節點，布局節點位置，其中所有節點通過一個graphlib圖表示的布局（x和y定位）。它不會渲染。
dagre-d3
dagre-d3使用dagre進行布局，并使用d3進行渲染。請注意，dagre-d3默認包含dagre和graphlib，如dagreD3.dagre和dagreD3.graphlib。
元素：

graph，即圖整體，我們可以對圖配置一些全局參數。
node，即頂點，dagre 在計算時并不關心 node 實際的形狀、樣式，只要求提供維度信息。
edge，即邊，edge 需要聲明其兩端的 node 以及本身方向。例如A -> B表示一條由 A 指向 B 的 edge。
rank，即層級，rank 是 DAG 布局中的核心邏輯單位，edge 兩端的 node 一定屬于不同的 rank，而同一 rank 中的 node 則會擁有同樣的深度坐標（例如在縱向布局的 graph 中 y 坐標相同）。
label，即標簽，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 |  
    +---+------------------->+---+

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

結點之間不能有重疊

連線之間盡量減少交差

結點之間是有基本的層次關系對齊的

主要分4個步驟：
1、消除圖中的環。
2、尋找最優的等級（分層）分配。
3、在同一個等級內，設置頂點的順序，使交叉數最小。
4、計算頂點的坐標。
dagre布局步驟：

removeSelfEdges // 刪除自環邊
acyclic.run // 反向設置成環的邊
rank // 計算最優的等級分配
order // 同層排序
insertSelfEdges // 插入自環邊
position // 計算頂點的坐標
acyclic.undo // 恢復反向邊設置

尋找成環的邊：

遍歷所有的節點，遞歸遍歷每個節點的出邊，把一條路徑上的所有節點按路徑順序入棧，當遍歷到某個出邊的目標點已經在這個路徑上遍歷過了，那么這條邊就是成環的邊，存下來，然后對所有成環邊反向。

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（網絡單純型） 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算法就是快速初始化一個層級關系，求出來的是一條路徑的盡頭都對齊，定為0，然后逆向路徑計算，都為負值。
深度優先遍歷

function longestPath(g) {
  var visited = {};
  // 深度優先
  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、任意節點的層級必須滿足邊的長度大于等于邊的minlen最小長度。
2、某條邊的松弛度被定義為其長度和最小長度之間的差值，邊的松弛度為0，則為緊湊的。

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

function tightTree(t, g) {
  function dfs(v) {
    // 遍歷v節點的所有邊，然后檢查邊的對點是否存在樹上，不存在且該邊是緊湊的即緊湊度是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

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

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

原始圖:

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

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

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

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

[
  [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行根據n-1行排序
      upLayerGraphs = buildLayerGraphs(g, _.range(maxRank - 1, -1, -1), "outEdges"); // 從下到上分層，n行根據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); // 掃描按權重排序
    layering = util.buildLayerMatrix(g); // 節點id的矩陣
    var cc = crossCount(g, layering); // 返回當前矩陣下交叉點個數
    if (cc < bestCC) {
      lastBest = 0;
      best = _.cloneDeep(layering);
      bestCC = cc;
    }
  }
  assignOrder(g, best);
}

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

1、依賴關系：
可視化項目依賴，組件依賴關系：比如打包編譯依賴的時候，把各種包的依賴關系按照拓撲序列排序，先引入排在前面的包，后引入排在后面的包。
2、調度流程：
自動化布局UML圖，workflow等。
事項流程：

spark任務執行：大規模數據處理計算引擎

UML類圖

兒茶酚胺合成代謝路徑

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

4、復雜人物關系鏈分析：紅樓夢

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