I have Task class that has a dependency on other tasks before execution. I want to group tasks that can be parallelized and order them. I decide that it can be represented as DAG first and trying to use JGrapht. First i'm traversing input list of tasks to get all the tasks with their dependancies and collecting them in one list. Then for each task I'm creating a vertex in the graph.
DirectedAcyclicGraph<Task, DefaultEdge> d = new DirectedAcyclicGraph<>(DefaultEdge.class);
Set<Task> all = collectAllTasks(tasks);
all.forEach(d::addVertex);
then using same list I'm trying to create edges between nodes.
all.forEach(task -> {
Set<TaskName> predecessors = task.getPredecessors();
predecessors.forEach(name -> {
Task predecessor = taskService.getTaskByName(name);
d.addEdge(predecessor, task);
});
});
Then I'm trying to group tasks
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;
}
So the outcome is ordered and grouped tasks, for example for graph
The outcome will be A, B, {C, D}, E.
However, it completely breaks on the case when B is also the predecessor of E like this example
How can I achieve order of A, B, {C, D}, E for graph like previous?
Is there any particular algorithm I can look or how I can achieve that in a better way? Thanks.

