关于程序员:从零开始画自己的DAG作业依赖图二分层布局算法

2次阅读

共计 2613 个字符，预计需要花费 7 分钟才能阅读完成。

概述

当咱们把设计稿和技术选型定下来之后，接下来就要开始着手画这个依赖图了。依赖图的组成最简略的就是节点 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，如果很相熟这个算法的话，还是很简略的，同时要察看一些理论状况，做一些优化即可！