How to do Topological Sort (Dependency Resolution) with Java

Question

Description

The purpose of the question is to implement an interface that will order a list of tasks according to the information about their dependencies. For example, if task A has a dependency on tasks B and C, this means that to start working on task A, tasks B and C have to be completed first. As I think it should be like directed graph structure.

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;
    }
}

The interface shall take a list of tasks (defined in any order) as the input parameter and output a list of tasks sorted in the order they may be executed.

/**
 * 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);
}

The following code provides an example of how the interface can be used.

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());
        }
    }
}

Question

How can I implement interface to sort tasks ? Am I need to use something like JGraphT or Guava Graph or there is some easy way ?

Answer 1

We can use topological sort for such dependency resolution problem.
Quoting from the above 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 which can solve our problem easily.

---

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()));
    }
}