数据调度系统中有向无环图的无环检测

名词解释

• DAG,全称：Directed Acyclic Graph，中文：有向无环图
• 入度：有向图中某点作为图中边的终点的次数之和
• 出度： 对于有向图来说，顶点的出边条数即为该顶点的出度

调度系统中的有向无环图

数据调度系统中,多个任务之间的依赖关系，用图可以表示，如下图所示，每个顶点表示一个任务，箭头方向表示任务的执行顺序。任何顶点都无法经过边回到该顶点，则该图就是无环图，即为有向无环图（DAG图）。
图1

那么在有向图中，如果有环的存在,如图示：
图2

在有环的情况下，任务3的执行需要任务5完成，而5的执行又需要3，4依次执行完成，这样就会造成死循环，此调度任务永远无法成功执行。所以在调度系统中，对于无环的检测就非常重要。

无环检测

在调度系统中，检查图是否有环，分两种场景：1. 编辑图的过程中每一步操作都需要对其做无环检测；2. 对已经存在的图进行拓扑排序，检测是否有环。

编辑时检测

对于新创建的图来说，每增加一条边，都需要检测，这条边是否导致环的存在
思路：如图1到图2， 如果要加一条5到3的边，就从3开始遍历后续顶点，如果能回到顶点5的话就证明新加的边导致环的产生;如果不能回到5，证明新添加的边不会导致有环。
检测代码如下：

 /**
   * 判断增加边(fromVertex --> toVertex)是否合法,需要判断是否符合无环的约束
   *
   * @param fromVertex     起点
   * @param toVertex       终点
   * @param createVertex 是否创建结点
   * @return
   */
  private boolean isLegalAddEdge(Vertex fromVertex, Vertex toVertex, boolean isCreate) {
      if (fromVertex.equals(toVertex)) {
          logger.error("edge fromVertex({}) can't equals toVertex({})",fromVertex,toVertex);
          return false;
      }
      if (!isCreate) {
          if (!hasVertex(fromVertex) || !hasVertex(toVertex)){
              logger.error("edge fromVertex({}) or toVertex({}) is not in vertices map",fromVertex,toVertex);
              return false;
          }
      }
      Queue<Vertex> queue = new LinkedList<>();
      queue.add(toVertex);
      int verticesCount = getVerticesCount();
      //如果没有找到fromVertex, 表示无环;
      while (!queue.isEmpty() && verticesCount > 0) {
          verticesCount -= 1;
          Vertex key = queue.poll();
          // 遍历后续顶点
          for (Vertex subsequentVertex : getSubsequentNodes(key)) {
              if (subsequentVertex.equals(fromVertex)) {
                  return false;
              }
              queue.add(subsequentVertex);
          }
      }
      return true;
  }

拓扑排序检测

有向图的拓扑排序，思路如下：

1. 遍历图中所有的顶点，将入度为0的顶点入队列（如果多个顶点入度为0，取顶点顺序可能不一样，所以此处排序结果可能是多个）。
2. 从队列中poll出一个顶点，更新该顶点的邻接点的入度(减1)，如果邻接点的入度减1之后等于0，则将该邻接点入队列。
3. 一直执行第2步，直到队列为空。
4. 如果无法遍历完所有的结点，则意味着当前的图不是无环图。不存在拓扑排序。

例如图1 入度出度：

拓扑排序流程如下：

java实现如下：

  /**
   * 判断是否有环及拓扑排序结果
   *
   * 有向无环图(DAG)才有拓扑(topological)排序
   * 广度优先遍历的主要做法：
   *    1、遍历图中所有的顶点，将入度为0的顶点入队列。
   *    2、从队列中poll出一个顶点，更新该顶点的邻接点的入度(减1)，如果邻接点的入度减1之后等于0，则将该邻接点入队列。
   *    3、一直执行第2步，直到队列为空。
   * 如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。
   *
   *
   * @return key返回的是状态, 如果成功(无环)为true, 失败则有环， value为拓扑排序结果(可能是其中一种)
   */
  private Map.Entry<Boolean, List<Vertex>> topologicalSortImpl() {
    //入度为0的结点队列
    Queue<Vertex> zeroIndegreeVertexQueue = new LinkedList<>();
    //保存结果
    List<Vertex> topoResultList = new ArrayList<>();
    //保存入度不为0的结点
    Map<Vertex, Integer> notZeroIndegreeVertexMap = new HashMap<>();

    //扫描所有的顶点,将入度为0的顶点入队列
    for (Map.Entry<Vertex, VertexInfo> vertices : verticesMap.entrySet()) {
      Vertex vertex = vertices.getKey();
      int inDegree = getIndegree(vertex);

      if (inDegree == 0) {
        zeroIndegreeVertexQueue.add(vertex);
        topoResultList.add(vertex);
      } else {
        notZeroIndegreeVertexMap.put(vertex, inDegree);
      }
    }

    //扫描完后，没有入度为0的结点，说明有环，直接返回
    if(zeroIndegreeVertexQueue.isEmpty()){
      return new AbstractMap.SimpleEntry(false, topoResultList);
    }

    //采用topology算法, 删除入度为0的结点和它的关联边
    while (!zeroIndegreeVertexQueue.isEmpty()) {
      Vertex v = zeroIndegreeVertexQueue.poll();
      //得到相邻结点
      Set<Vertex> subsequentNodes = getSubsequentNodes(v);

      for (Vertex subsequentVertex : subsequentNodes) {

        Integer degree = notZeroIndegreeVertexMap.get(subsequentVertex);

        if(--degree == 0){
          topoResultList.add(subsequentVertex);
          zeroIndegreeVertexQueue.add(subsequentVertex);
          notZeroIndegreeVertexMap.remove(subsequentVertex);
        }else{
          notZeroIndegreeVertexMap.put(subsequentVertex, degree);
        }

      }
    }

    //notZeroIndegreeVertexMap如果为空, 表示没有环
    AbstractMap.SimpleEntry resultMap = new AbstractMap.SimpleEntry(notZeroIndegreeVertexMap.size() == 0 , topoResultList);
    return resultMap;

  }

}

输出每个顶点的同时还要删除以它为起点的边。如果图有V个顶点，E条边，则一般该算法的时间复杂度为O(V+E)。这里实现的算法最终key返回的是状态, 如果成功(无环)为true, 失败则有环， 无环时value为拓扑排序结果(可能是其中一种)。

今天的文章数据调度系统中有向无环图的无环检测分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。