如何使用 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

据我了解，您的问题可以使用 observer pattern

解决

The Observer pattern is used to monitor the state of a certain object, often in a group or one-to-many relationship. In such cases, most of the time, the changed state of a single object can affect the state of the rest, so there must be a system to note the change and alert the other objects.

这样您就可以在收到有关某个对象状态更改的警报时执行或启动某个任务。

Answer 2

我们可以使用 topological sort 解决这样的依赖关系问题。
引用上面link

For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG)

JGraphT provides DirectedAcyclicGraph and 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()));
    }
}

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

How to do Topological Sort (Dependency Resolution) with Java

java

graph

directed-graph

jgrapht

guava