如何使用 Java 进行拓扑排序（依赖解析）

Question

描述

该问题的目的是实现一个接口，该接口将根据任务的依赖关系信息对任务列表进行排序。例如，如果任务 A 依赖于任务 B 和 C，则这意味着要开始处理任务 A，必须首先完成任务 B 和 C。我认为它应该像有向图结构。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * The task class represents a certain activities that must be done as the part of the project planning
 */
class Task {

    /**
     * Unique name of the activity
     */
    private String name;

    /**
     * A list of names of the activities that must be completed in order to be able to start the current activity
     */
    private List<String> predecessors;

    public Task(String name, List<String> predecessors) {
        this.name = name;
        this.predecessors = predecessors;
    }

    public String getName() {
        return name;
    }

    public List<String> getPredecessors() {
        return predecessors;
    }
}

该接口应将任务列表（以任何顺序定义）作为输入参数，并输出按执行顺序排序的任务列表。

/**
 * A scheduler interface is intended to process a random list of tasks with the information of their predecessors
 * and return a list of the same tasks but in order they may be executed according to their dependencies
 */
interface IScheduler {
    public List<Task> schedule(List<Task> tasks);
}

以下代码提供了如何使用该接口的示例。

public class Main {

    public static void main(String[] args) {
        /**
         * The following is the example of how the scheduler may be used
         */
        List<Task> tasks = Arrays.asList(
            new Task("E", Arrays.asList("B")),
            new Task("D", Arrays.asList("A", "B")),
            new Task("A", Arrays.asList()),
            new Task("B", Arrays.asList("A")),
            new Task("C", Arrays.asList("D", "B")),
            new Task("F", Arrays.asList("E"))
        );

        IScheduler scheduler = /* implementation here*/;
        List<Task> sortedTasks = scheduler.schedule(tasks);
        for (Task t: sortedTasks) {
            System.out.println(t.getName());
        }
    }
}

问题

如何实现对任务进行排序的接口？我需要使用类似的东西JGraphT还是Guava Graph有一些简单的方法？

Answer 1

我们可以使用拓扑排序来解决此类依赖性解析问题。
引用上面的链接

例如，图的顶点可以代表要执行的任务，边可以代表一项任务必须在另一项任务之前执行的约束；在此应用程序中，拓扑排序只是任务的有效序列。当且仅当图没有有向环时，拓扑排序才是可能的，即，如果它是有向无环图 (DAG)

JGraphT提供了DirectedAcyclicGraph，TopologicalOrderIterator可以轻松解决我们的问题。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

import org.jgrapht.Graph;
import org.jgrapht.graph.DirectedAcyclicGraph;
import org.jgrapht.traverse.TopologicalOrderIterator;

public class TopologicalSortExample {
    public static void main(String[] args) {
        // DirectAcyclicGraph to prevent circular dependency
        Graph<Task, DefaultEdge> directedGraph = new DirectedAcyclicGraph<>(DefaultEdge.class);
        List<Task> tasks = new ArrayList<Task>();
        tasks.add(new Task("E", Arrays.asList("B")));
        tasks.add(new Task("D", Arrays.asList("A", "B")));
        tasks.add(new Task("A", Arrays.asList()));
        tasks.add(new Task("B", Arrays.asList("A")));
        tasks.add(new Task("C", Arrays.asList("D", "B")));
        tasks.add(new Task("F", Arrays.asList("E")));
        Map<String, Task> taskNameToTaskMap = tasks.stream()
                .collect(Collectors.toMap(task -> task.getName(), task -> task));
        for (Task task : tasks) {
            directedGraph.addVertex(task);
            for (String predecessor : task.getPredecessors()) {
                Task predecessorTask = taskNameToTaskMap.get(predecessor);
                directedGraph.addVertex(predecessorTask);
                directedGraph.addEdge(predecessorTask, task);
            }
        }
        TopologicalOrderIterator<Task, DefaultEdge> moreDependencyFirstIterator = new TopologicalOrderIterator<>(
                directedGraph);
        moreDependencyFirstIterator.forEachRemaining(task -> System.out.println(task.getName()));
    }
}