如何从零开始绘制DAG作业依赖图的分层布局算法？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1072个文字，预计阅读时间需要5分钟。
概述：当我们确定设计脚本和选择技术方案后，便着手绘制依赖图。依赖图的组成最简单，即节点Node和节点之间的连线。本节我们要处理的重点是节点位置信息。
概述
当我们把设计稿和技术选型定下来之后，接下来就要开始着手画这个依赖图了。依赖图的组成最简单的就是节点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，如果很熟悉这个算法的话，还是很简单的，同时要观察一些实际情况，做一些优化即可！
本文由华为云发布。
本文共计1072个文字，预计阅读时间需要5分钟。
概述：当我们确定设计脚本和选择技术方案后，便着手绘制依赖图。依赖图的组成最简单，即节点Node和节点之间的连线。本节我们要处理的重点是节点位置信息。
概述
当我们把设计稿和技术选型定下来之后，接下来就要开始着手画这个依赖图了。依赖图的组成最简单的就是节点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，如果很熟悉这个算法的话，还是很简单的，同时要观察一些实际情况，做一些优化即可！
本文由华为云发布。