Spark：有向无环图（DAG）检测

Spark背景介绍

Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环境，拥有Hadoop MapReduce所具有的优点;但不同于MapReduce的是——Job中间输出结果可以保存在内存中，从而不再需要读写HDFS，因此Spark能更好地适用于数据挖掘与机器学习等需要迭代的MapReduce的算法。

RDD，全称为Resilient Distributed Datasets，中文翻译弹性分布式数据集，是一个容错的、并行的数据结构，可以让用户显式地将数据存储到磁盘和内存中，并能控制数据的分区。RDD是Spark的灵魂，一个RDD代表一个可以被分区的只读数据集。RDD内部可以有许多分区(partitions)，每个分区又拥有大量的记录(records)。

RDD之间的依赖关系是靠有向无环图(DAG)表达的，下面看下有向无环图的基本理论和算法。

有向无环图(DAG)

在图论中，边没有方向的图称为无向图，如果边有方向称为有向图。在无向图的基础上，任何顶点都无法经过若干条边回到该点，则这个图就没有环路，称为有向无环图(DAG图)，如下图所示，4->6->1->2是一个路径，4->6->5也是一条路径，并且图中不存在顶点经过若干条边后能回到该点，可以得出下图为DAG。

 

 

入度

入度是图论算法中重要的概念之一。它通常指有向图中某点作为图中边的终点的次数之和，也就是项点的入边条数称为该项点的入度。如上图所示，顶点4的入度为0.

出度

对应于入度，顶点的出边条数称为该顶点的出度。如上图所示，顶点3的入度为2.

DAG应用的另一个例子

在一些任务安排和调度的问题里。不同的问题或者任务之间又一些依赖的关系，有的任务需要在某些任务完成之后才能做。就像一些学校的教学课程安排。设置某一门课程需要依赖于一个前置的课程，只有学生学习了前置课程之后才能取学习该课程。如果将一门课程当做一个节点，从它引出一个指针指向后序依赖它的课程。就可能有一个类似这样的图：

 

 

Algorithms课指向Theoretical CS，意思是选修后者需要先修完Algorithms这门课，Artificial Intelligence依赖Theoretical CS，Machine learning 依赖Artificial Intelligence，Neural Networks依赖Machine learning这门课，这称为一条路径。

还可以看到，上图中入度为0的节点有 Introduction to CS，这个节点在有向图遍历中具有重要意义，下面会说到。

如果上图有环，还正确吗?

 

 

如上所示，如果Machine learning再指向Theoretical CS，意思是选修Theoretical CS的同学需要先修Machine learning，这个就和原来的路径Artificial Intelligence依赖Theoretical CS，Machine learning 依赖Artificial Intelligence，违背!，并且也不合常理，Theoretical CS是一门基础性的理论课，怎么可能选修它之前要先修完machine learning呢?所以不能有环路，这个图是不正确的。所以，这个图必须为有向无环图!

有向图如何检测有、无环?

那么，如何检测一个有向图是否是DAG呢?

有向图的环检测，首先对照着无向图的环检测来理解，在无向图中，我们要检测一个图中间是否存在环，需要通过深度优先或广度优先的方式，对访问过的元素做标记。如果再次碰到前面访问过的元素，则说明可能存在环。只做标记，在有向图中检测环路的办法可行吗?

如下图所示，深度优先遍历方法，已经遍历了节点2和6，并marked了，现在遍历节点1的另一条边，依次遍历3,4,5,6，因为6已经遍历，所以说形成了环路，但是实际上并没有，因此，与实际不符合，只对访问过的元素做标记判断有无环路是错误的。

 

 

感觉是要加条件，加什么条件? 如果我们加一个数组保存当前节点是否位于递归栈onStack中，就可以排除上面的问题，因为2,6被标记后，依次递归出栈，然后到1，深度遍历1的另一条边(3->4->5->6)，所以6此时不在onStack上，第一次被检测到，所以没有环路。

因此，有向图的无环检测，需要同时借助两个限制条件：

对访问过的元素做标记
当前节点是否位于递归栈onStack中

在上图的基础上，增加节点7和8，如下图所示，可以预见，按照深度优先搜索到节点4时，会找到子节点5，节点5的其中一个边找到7，找到8，找到4,节点4此时已经位于onStack中，所以构成环路，是有环图。

 

 

 

 

总结，以上就是有向图有环，无环检测算法的基本思想。关于有向图有环判断检测的java版源码请参考github之spark文件夹中的directedCycle类(代码参考princeton源码)，