深入浅出的实践大数据 DAG 图

前言   

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 个问题：

1. 有方向，连线只能从上一个节点的输出桩（下面）连接到当前节点的输入桩（上面）；

2. 无环，输出桩发起的连线不能成环，即当前节点不能连接自己，不能连接自己上面所有连接过的节点。

综合以上问题只要在 defaultConfig 中配置连线校验逻辑即可：

至此，一个简单的 DAG 图就已经完成了。

进阶

学过计算机网络的知道计算机网络中有一个拓扑结构，要实现 DAG 图多顶点的拓扑序列执行任务的功能，可以使用拓扑排序算法，拓扑排序算法的时间复杂度为 O（n+e）。

Js 实现拓扑排序算法

笔者在这里提供了另一种思路：

把每一个节点看作一个对象，因此只要关心两件事就可以解决 DAG 图多顶点的拓扑结构执行任务的功能。

1. 遍历每个节点，把它放到事件订阅里边，执行订阅器；

2. 每隔一秒检查一下，如果当前节点已经在运行，则跳过；当前节点是否有上级节点，没有就是顶点节点，顶点直接运行；有上级节点，上级节点是否有运行结果，所有上级节点都有运行结果就运行当前节点；当前节点有运行结果，从订阅器里删除当前节点；当前节点运行报错，从订阅器里删除当前节点；上级节点有报错，删除当前节点；最后订阅器里就空了，所有的任务也就执行完了。 

前车之鉴

在 vue3.x+vite2.x 中使用 x6 必然是要趟过很多坑的，下面是开发过程中遇到的一些问题：

1.使用 "@antv/x6-vue-shape"来注册 vue 组件，需要 vue 在运行时进行编译，在 vite 别名中添加 

2.开发阶段 @antv/x6，@antv/x6-vue-shape 引入报错，开发阶段修改别名

小结

本文由浅入深介绍了 DAG 图基于 X6 实现，以及拓展了解决 DAG 图多顶点的拓扑结构执行任务的另外一种思路，相信你已经很清楚地知道怎么实现一个 DAG 图了。

感谢阅读，如有不足之处，欢迎指出。

end