前言 DAG 是有向无环图(Directed Acyclic Graph)的简称。在大数据处理中,DAG 计算经常指的是将计算工作在外部合成成为若干个子工作,将这些子工作之间的逻辑关系或程序构建成 DAG(有向无环图)构造。
X6 在 DAG 图中的实际 X6 是一款开源的图编辑引擎,vue3.x+vite2.x 是目前较火的前端开发组合,当初用他们来实现一个 DAG 图;X6 分为画布(Graph)、基类(cell)、节点(node)、边(edge)、连贯桩(port)等元素,以及图的相干操作(如交互监听、元素操作、渲染等),因而只须要把握画布、节点、边的增删改查,应用 x6 就轻松加欢快了。基于 x6 封装一个类 GraphCroe
应用 vue 组件注册 x6 自定义节点
注册 x6 自定义边
在 GraphCore 类中增加节点,边的操作方法
在 vue 组件中创立画布
提供创立节点数据办法
以上步骤就能够实现在画布中创立节点的性能,如下图:
要做一个有向无环图还须要解决以下 2 个问题:有方向,连线只能从上一个节点的输入桩(上面)连贯到以后节点的输出桩(下面);无环,输入桩发动的连线不能成环,即以后节点不能连贯本人,不能连贯本人下面所有连贯过的节点。综合以上问题只有在 defaultConfig 中配置连线校验逻辑即可:
至此,一个简略的 DAG 图就曾经实现了。进阶学过计算机网络的晓得计算机网络中有一个拓扑构造,要实现 DAG 图多顶点的拓扑序列执行工作的性能,能够应用拓扑排序算法,拓扑排序算法的工夫复杂度为 O(n+e)。
Js 实现拓扑排序算法
笔者在这里提供了另一种思路:把每一个节点看作一个对象,因而只有关怀两件事就能够解决 DAG 图多顶点的拓扑构造执行工作的性能。遍历每个节点,把它放到事件订阅里边,执行订阅器;每隔一秒检查一下,如果以后节点曾经在运行,则跳过;以后节点是否有下级节点,没有就是顶点节点,顶点间接运行;有下级节点,下级节点是否有运行后果,所有下级节点都有运行后果就运行以后节点;以后节点有运行后果,从订阅器里删除以后节点;以后节点运行报错,从订阅器里删除以后节点;下级节点有报错,删除以后节点;最初订阅器里就空了,所有的工作也就执行完了。
前事不忘; 后事之师在 vue3.x+vite2.x 中应用 x6 必然是要趟过很多坑的,上面是开发过程中遇到的一些问题:1. 应用 “@antv/x6-vue-shape” 来注册 vue 组件,须要 vue 在运行时进行编译,在 vite 别名中增加
2. 开发阶段 @antv/x6,@antv/x6-vue-shape 引入报错,开发阶段批改别名
小结本文由浅入深介绍了 DAG 图基于 X6 实现,以及拓展了解决 DAG 图多顶点的拓扑构造执行工作的另外一种思路,置信你曾经很分明地晓得怎么实现一个 DAG 图了。感激浏览,如有不足之处,欢送指出。