概述
當我們把設計稿和技術選型定下來之后，接下來就要開始著手畫這個依賴圖了，依賴圖的組成最簡單的就是節點Node 和節點之間的連線，這一節我們要處理的就是節點位置資訊的處理，為了確定節點的位置資訊，首先要給節點分層，分層的資訊取決于節點之間的依賴關系，
問題分析
當前我們默認圖是從上到下布局方式，節點分層，最容易想到的就是拓撲排序，通過BFS 寬度優先遍歷，計算每個節點的步長，
自頂向下BFS
如上圖，我們如果是普通的BFS，我們會發現D 節點應該是第二層，實際上D應該是第三層，所以，實際上每個節點應該取最大的步長，實作如下
function calcLayer(nodes){
var queue = [];
var maxLayer = 1;
var nodesT = nodes;
// 入度為0 的點放入佇列
for (var i = 0; i < nodesT.length; i++) {
if (nodesT[i].inputNode.length === 0) {
nodesT[i].layer = 1;
queue.push(nodesT[i]);
}
}
while(queue.length > 0){
var tNode = queue.shift();
if (tNode.outputNode && tNode.outputNode.length > 0) {
for (var j = 0; j < tNode.outputNode.length; j++) {
var outputNodeIndex = getNodeIndex(tNode.outputNode[j], nodesT);
if(outputNodeIndex < 0) continue;
if (nodesT[outputNodeIndex].layer === -1) {
nodesT[outputNodeIndex].layer = tNode.layer + 1;
}else{
nodesT[outputNodeIndex].layer = Math.max(nodesT[outputNodeIndex].layer,tNode.layer + 1);
}
// 更新節點層次，選擇最大值
maxLayer = Math.max(maxLayer, nodesT[outputNodeIndex].layer);
queue.push(nodesT[outputNodeIndex]);
}
}
}
}
至此分層基本完成，但是發現另外一種情況，如下：
如果是按照剛才那種分發，入度為0 的節點必然在第一層，其實這種，我們可能更希望 G在第三層，F 在第二層，例如下圖展示的
這樣展示，圖會更緊湊一點，觀察圖可知，在鏈路中間的節點，它的層級就是固定的，例如D節點，但是一些沒有上游節點的，例如G，F 的位置確實可以多種選擇的，在觀察，我們可以知道，如果從E往上BFS，我們會發現，G,F節點就是我們需要的層次了，所以，這時候，我們需要自底向上再進行一次BFS，得到新的層級，并且用自底向上的結果去矯正自上而下的結果，這一點很關鍵，
自底向上BFS
function bottomToTop (nodes){
var queue = [];
var maxLayer = 1;
for (var i = 0; i <nodes.length; i++) {
if (nodes.outputNode.length === 0) {
nodes[i].layer = 1;
queue.push(nodes[i]);
}
}
while(queue.length > 0){
var tNode = queue.shift();
if (tNode.inputNode && tNode.inputNode.length > 0) {
for (var j = 0; j < tNode.inputNode.length; j++) {
var inputNodeIndex = getNodeIndex(tNode.inputNode[j], nodes);
if(inputNodeIndex < 0) continue;
if (nodes[inputNodeIndex].layer === -1) {
nodes[inputNodeIndex].layer = tNode.layer + 1;
}else{
nodes[inputNodeIndex].layer = Math.max(nodes[inputNodeIndex].layer,tNode.layer + 1);
}
maxLayer = Math.max(maxLayer, nodes[inputNodeIndex].layer);
queue.push(nodes[inputNodeIndex]);
}
}
}
// 計數從下到上的，這里要轉換成從上到下
for(var i = 0; i < nodes.length; i++){
nodes[i].layer = maxLayer + 1 - nodes[i].layer;
}
}
修正結果集
function fixLayer (nodesT, nodes){
for(var i = 0; i < nodesT.length; i++){
if(nodesT[i].inputNode.length === 0){
var minL = maxLayer;
var minT = maxLayer;
if(nodesT[i].outputNode && nodesT[i].outputNode.length > 0){
for(var j = 0; j < nodesT[i].outputNode.length; j++){
var inputNodeIndex = getNodeIndex(nodesT[i].outputNode[j], nodes);
var inputNodeIndexT = getNodeIndex(nodesT[i].outputNode[j], nodesT);
if(inputNodeIndex < 0) continue;
if(inputNodeIndexT < 0) continue;
// 注意，矯正的結果不能該節點比它子節點的層級還要高，這里要和它子節點做一次比較
minL = Math.min(minL, nodes[inputNodeIndex].layer - 1);
minT = Math.min(minT, nodesT[inputNodeIndexT].layer - 1);
}
}
nodesT[i].layer = Math.min(minL,minT);
}
}
}
總結
這里主要用到了BFS，如果很熟悉這個演算法的話，還是很簡單的，同時要觀察一些實際情況，做一些優化即可！
本文由華為云發布，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/454643.html
標籤：其他