从零开始画自己的DAG作业依赖图(二)--分层布局算法

举报
flowdeep 发表于 2020/12/19 20:31:38 2020/12/19
【摘要】 概述       当我们把设计稿和技术选型定下来之后,接下来就要开始着手画这个依赖图了。依赖图的组成最简单的就是节点Node 和节点之间的连线。这一节我们要处理的就是节点位置信息的处理。为了确定节点的位置信息,首先要给节点分层,分层的信息取决于节点之间的依赖关系。问题分析       当前我们默认图是从上到下布局方式,节点分层,最容易想到的就是拓扑排序,通过BFS 宽度优先遍历,计算每个节点...

概述

       当我们把设计稿和技术选型定下来之后,接下来就要开始着手画这个依赖图了。依赖图的组成最简单的就是节点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,如果很熟悉这个算法的话,还是很简单的,同时要观察一些实际情况,做一些优化即可!

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。