У меня есть класс Task, который зависит от других задач перед выполнением. Я хочу сгруппировать задачи, которые можно распараллелить, и упорядочить их. Я решил, что сначала его можно представить как DAG, и пытаюсь использовать JGrapht. Сначала я просматриваю входной список задач, чтобы получить все задачи с их зависимостями и собрать их в один список. Затем для каждой задачи я создаю вершину в графе.
DirectedAcyclicGraph<Task, DefaultEdge> d = new DirectedAcyclicGraph<>(DefaultEdge.class);
Set<Task> all = collectAllTasks(tasks);
all.forEach(d::addVertex);
затем, используя тот же список, я пытаюсь создать грани между узлами.
all.forEach(task -> {
Set<TaskName> predecessors = task.getPredecessors();
predecessors.forEach(name -> {
Task predecessor = taskService.getTaskByName(name);
d.addEdge(predecessor, task);
});
});
Потом пытаюсь сгруппировать задачи
private Set<Set<TaskId>> groupTasks(DirectedAcyclicGraph<TaskId, DefaultEdge> dag) {
Set<Set<TaskId>> groups = new LinkedHashSet<>();
Iterator<TaskId> iterator = new TopologicalOrderIterator<>(dag);
iterator.forEachRemaining(taskId -> {
//source?
if (dag.incomingEdgesOf(taskId).isEmpty()) {
if (groups.isEmpty()) {
Set<TaskId> set = new HashSet<>();
set.add(taskId);
groups.add(set);
} else {
groups.iterator().next().add(taskId);
}
}
Set<TaskId> tasks = new HashSet<>(Graphs.successorListOf(dag, taskId));
//sink?
if (tasks.isEmpty()) {
return;
}
groups.add(featuresGroup);
});
return groups;
}
Таким образом, результат - это упорядоченные и сгруппированные задачи, например для графа
Результат будет A, B, {C, D}, E.
Однако он полностью нарушает тот случай, когда B также является предшественником E, как в этом примере.
Как я могу добиться порядка A, B, {C, D}, E для графика, подобного предыдущему? Есть ли какой-то конкретный алгоритм, который я могу найти, или как я могу добиться этого лучше? Спасибо.
