有向无环图

任务的执行有依赖关系，如下图所示：

可以使用DAG（有向无环图）来维护这种依赖关系；

定义task

@Data
@NoArgsConstructor
public class NodeTask {
    private String id;
    private Set<String> dependences = Sets.newConcurrentHashSet);  //依赖的taskID

    public NodeTaskString id) {
        this.id = id;
    }

    public NodeTask addDependenceString nodeTaskId) {
        this.dependences.addnodeTaskId);
        return this;
    }
}

Graph

package com.ssslinppp.graph.directd;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Queues;
import com.google.common.graph.GraphBuilder;
import com.google.common.graph.MutableGraph;

import java.util.List;
import java.util.Map;
import java.util.Queue;

public class TaskGraph {
    private MutableGraph<NodeTask> taskGraph = GraphBuilder.directed).allowsSelfLoopsfalse).build);

    /**
     * 转换节点任务为Graph
     *
     * @param nodeTasks
     */
    public void parseNodeTasksToGraphMap<String, NodeTask> nodeTasks) {
        for NodeTask nodeTask : nodeTasks.values)) {
            if !taskGraph.nodes).containsnodeTask)) {
                taskGraph.addNodenodeTask);
            }

            for String dependence : nodeTask.getDependences)) {
                taskGraph.putEdgenodeTask, nodeTasks.getdependence));
            }
        }
    }

    /**
     * 判断是否为DAGDirected Acyclic Graph）有向无环图
     * <p>
     * 算法思路：
     * <ul>
     * <li>1. 根据"拓扑排序"算法判断：拓扑排序之后，若还剩有点，则表示有环</li>
     * <li>2. 拓扑排序算法：找到图中所有入度为0的点，放入序列，删除这些点和以这些点为出度的边，再找所有入度为0的点，依次循环</li>
     * </ul>
     *
     * @return
     */
    public boolean isDAGraph) {
        Map<String, Integer> nodeInDegreeMap = Maps.newHashMap);
        Queue<NodeTask> queue = Queues.newArrayDeque);
        List<String> topologicalSortList = Lists.newArrayList); //拓扑排序列表维护

        // 获取所有入度为0的节点
        for NodeTask nodeTask : taskGraph.nodes)) {
            int indegree = taskGraph.inDegreenodeTask);
            nodeInDegreeMap.putnodeTask.getId), indegree);
            if indegree == 0) {
                queue.addnodeTask);
                topologicalSortList.addnodeTask.getId));
            }
        }

        while !queue.isEmpty)) {
            NodeTask preNode = queue.poll); //获取并删除

            for NodeTask successorNode : taskGraph.successorspreNode)) {
                int indegree = nodeInDegreeMap.getsuccessorNode.getId));
                if --indegree == 0) {//-1：等效删除父节点以及相应的边
                    queue.offersuccessorNode); //insert
                    topologicalSortList.addsuccessorNode.getId));
                }
                nodeInDegreeMap.putsuccessorNode.getId), indegree);
            }
        }

        System.out.println"拓扑排序（topologicalSortList）:" + topologicalSortList);

        if topologicalSortList.size) != taskGraph.nodes).size)) {
            return false;
        }

        return true;
    }

    /**
     * 打印Graph中task的依赖关系
     */
    public void print) {
        System.out.println"=============NodeTask count: " + taskGraph.nodes).size));
        for NodeTask nodeTask : taskGraph.nodes)) {
            System.out.println"-------- NodeTask: " + nodeTask.getId) + "--------");
            System.out.print"Dependent on: ");
            taskGraph.successorsnodeTask).forEachv) -> System.out.printv.getId) + ", "));
            System.out.println);
            System.out.print"all predecessors: ");
            taskGraph.predecessorsnodeTask).forEachv) -> System.out.printv.getId) + ", "));
            System.out.println);
            System.out.println);
        }
    }
}

Test

package com.ssslinppp.graph.directd;

import com.google.common.collect.Maps;
import org.junit.Test;

import java.util.Map;

public class TaskGraphTest {
    /**
     * 测试依赖关系
     */
    @Test
    public void testDependence) {
        Map<String, NodeTask> nodeTaskMap = Maps.newConcurrentMap);
        NodeTask nodeTaskA = new NodeTask"nodeTaskA");
        NodeTask nodeTaskB = new NodeTask"nodeTaskB");
        NodeTask nodeTaskC = new NodeTask"nodeTaskC").addDependence"nodeTaskA");
        NodeTask nodeTaskD = new NodeTask"nodeTaskD").addDependence"nodeTaskB");
        NodeTask nodeTaskE = new NodeTask"nodeTaskE").addDependence"nodeTaskC").addDependence"nodeTaskD");
        NodeTask nodeTaskF = new NodeTask"nodeTaskF").addDependence"nodeTaskE");
        NodeTask nodeTaskG = new NodeTask"nodeTaskG").addDependence"nodeTaskE");
        nodeTaskMap.putnodeTaskA.getId), nodeTaskA);
        nodeTaskMap.putnodeTaskB.getId), nodeTaskB);
        nodeTaskMap.putnodeTaskC.getId), nodeTaskC);
        nodeTaskMap.putnodeTaskD.getId), nodeTaskD);
        nodeTaskMap.putnodeTaskE.getId), nodeTaskE);
        nodeTaskMap.putnodeTaskF.getId), nodeTaskF);
        nodeTaskMap.putnodeTaskG.getId), nodeTaskG);

        TaskGraph taskGraph = new TaskGraph);
        taskGraph.parseNodeTasksToGraphnodeTaskMap);
        System.out.println"======== DAG（有向无环图）判断 ===========");
        if taskGraph.isDAGraph)) {
            System.out.println"is DAG");
        } else {
            System.out.println"Not DAG");
        }

        System.out.println"=============== print ===========");
        taskGraph.print);
    }


    /**
     * 判断是否为有向无环图
     */
    @Test
    public void testDAG) {
        // E依赖D, D依赖B, B依赖E ==>B,E,G)为一个环
        Map<String, NodeTask> nodeTaskMap = Maps.newConcurrentMap);
        NodeTask nodeTaskA = new NodeTask"nodeTaskA");
        NodeTask nodeTaskB = new NodeTask"nodeTaskB");
//        nodeTaskB.addDependence"nodeTaskE");  // 在这里控制是否有环，进行测试
        NodeTask nodeTaskC = new NodeTask"nodeTaskC").addDependence"nodeTaskA");
        NodeTask nodeTaskD = new NodeTask"nodeTaskD").addDependence"nodeTaskB");
        NodeTask nodeTaskE = new NodeTask"nodeTaskE").addDependence"nodeTaskC").addDependence"nodeTaskD");
        NodeTask nodeTaskF = new NodeTask"nodeTaskF").addDependence"nodeTaskE");
        NodeTask nodeTaskG = new NodeTask"nodeTaskG").addDependence"nodeTaskE");
        nodeTaskMap.putnodeTaskA.getId), nodeTaskA);
        nodeTaskMap.putnodeTaskB.getId), nodeTaskB);
        nodeTaskMap.putnodeTaskC.getId), nodeTaskC);
        nodeTaskMap.putnodeTaskD.getId), nodeTaskD);
        nodeTaskMap.putnodeTaskE.getId), nodeTaskE);
        nodeTaskMap.putnodeTaskF.getId), nodeTaskF);
        nodeTaskMap.putnodeTaskG.getId), nodeTaskG);

        TaskGraph taskGraph = new TaskGraph);
        taskGraph.parseNodeTasksToGraphnodeTaskMap);
        System.out.println"======== DAG（有向无环图）判断 ===========");
        if taskGraph.isDAGraph)) {
            System.out.println"It is DAG");
        } else {
            System.out.println"Not DAG");
        }
    }
}

pom

<dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter</artifactId>
        </dependency>

        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>23.0</version>
        </dependency>

        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <optional>true</optional>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>
    </dependencies>

源码

源码Github