说明
该问题的目的是实现一个接口，该接口将根据有关其依赖项的信息对任务列表进行排序。例如，如果任务 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之类的东西，或者有一些简单的方法？
对于这样的依赖解析问题，我们可以使用拓扑排序。
引用上面的链接
例如，图的顶点可以表示要执行的任务，边可以表示一个任务必须在另一个任务之前执行的约束;在此应用程序中，拓扑排序只是任务的有效序列。拓扑排序是可能的，当且仅当图没有有向循环时，也就是说，如果它是有向无环图 (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()));
}
}
据我所知，您的问题可以使用观察者模式解决
观察者模式用于监视特定对象的状态，通常处于组或一对多关系中。在这种情况下，大多数情况下，单个对象的更改状态会影响其余对象的状态，因此必须有一个系统来记录更改并提醒其他对象。
因此，您可以在收到有关该对象状态更改的警报时执行或启动该任务。