Sorting objects with one-way dependency using Topological Sort with Directed Graphs

Suppose there are a bunch of objects to be evaluated, each of which might depend on a number of other objects being evaluated first before it can be evaluated. The objects being depended on might depend on other objects. There is no cyclic dependency that object A depends on object B, and object B depends on object C, and object C depends on object A.

To solve this problem, we want to sort these objects such that when traversing through these objects, they should be ready for evaluation and their dependencies, if applicable, should have been evaluated. The sorting algorithm and data structure that are applicable for this problem is Topological Sort with Directed Graphs.

If the edges in a graph have a direction, the graph is called a directed graph, as shown above. The arrows in the figure show the direction of the edges. We also include two vertices here to represent isolated objects that don't depend on other objects.

The arrows in the figure represent evaluation direction. For example, to evaluate E, we must first evaluate A and B. To evaluate H, we might want a sorted collection like this:

ADBECFDGH or ADGBECFH

There are many other possible ordering, depending on the approach you take to implement the topological sort.

DirectedGraph.java

import java.util.*;

public class DirectedGraph<T> implements Iterable<T> {

    // key is a Node, value is a set of Nodes connected by outgoing edges from the key
    private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();

    public boolean addNode(T node) {
        if (graph.containsKey(node)) {
            return false;
        }

        graph.put(node, new HashSet<T>());
        return true;
    }

    public void addNodes(Collection<T> nodes) {
        for (T node : nodes) {
            addNode(node);
        }
    }

    public void addEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        // Add the edge by adding the dest node into the outgoing edges
        graph.get(src).add(dest);
    }

    public void removeEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        graph.get(src).remove(dest);
    }

    public boolean edgeExists(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        return graph.get(src).contains(dest);
    }

    public Set<T> edgesFrom(T node) {
        // Check that the node exists.
        Set<T> edges = graph.get(node);
        if (edges == null)
            throw new NoSuchElementException("Source node does not exist.");

        return Collections.unmodifiableSet(edges);
    }

    public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }

    public int size() {
        return graph.size();
    }

    public boolean isEmpty() {
        return graph.isEmpty();
    }

    private void validateSourceAndDestinationNodes(T src, T dest) {
        // Confirm both endpoints exist
        if (!graph.containsKey(src) || !graph.containsKey(dest))
            throw new NoSuchElementException("Both nodes must be in the graph.");
    }

}

TolopogicalSort.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class TopologicalSort {

    public static <T> List<T> sort(DirectedGraph<T> graph) {
        DirectedGraph<T> reversedGraph = reverseGraph(graph);

        List<T> result = new ArrayList<T>();
        Set<T> visited = new HashSet<T>();

        /* We'll also maintain a third set consisting of all nodes that have
         * been fully expanded.  If the graph contains a cycle, then we can
         * detect this by noting that a node has been explored but not fully
         * expanded.
         */
        Set<T> expanded = new HashSet<T>();

        // Fire off a Depth-First Search from each node in the graph
        for (T node : reversedGraph)
            explore(node, reversedGraph, result, visited, expanded);

        return result;
    }


    /**
     * Recursively performs a Depth-First Search from the specified node, marking all nodes
     * encountered by the search.
     *
     * @param node     The node to begin the search from.
     * @param graph    The graph in which to perform the search.
     * @param result   A list holding the topological sort of the graph.
     * @param visited  A set of nodes that have already been visited.
     * @param expanded A set of nodes that have been fully expanded.
     */
    private static <T> void explore(T node, DirectedGraph<T> graph, List<T> result, Set<T> visited, Set<T> expanded) {
        if (visited.contains(node)) {
            // if this node has already been expanded, then it's already been assigned a
            // position in the final topological sort and we don't need to explore it again.
            if (expanded.contains(node)) return;

            // if it hasn't been expanded, it means that we've just found a node that is currently being explored,
            // and therefore is part of a cycle.  In that case, we should report an error.
            throw new IllegalArgumentException("A cycle was detected within the Graph when exploring node " + node.toString());
        }

        visited.add(node);

        // recursively explore all predecessors of this node
        for (T predecessor : graph.edgesFrom(node))
            explore(predecessor, graph, result, visited, expanded);

        result.add(node);
        expanded.add(node);
    }

    private static <T> DirectedGraph<T> reverseGraph(DirectedGraph<T> graph) {
        DirectedGraph<T> result = new DirectedGraph<T>();

        // Add all the nodes from the original graph
        for (T node : graph) {
            result.addNode(node);
        }

        // Scan over all the edges in the graph, adding their reverse to the reverse graph.
        for (T node : graph) {
            for (T endpoint : graph.edgesFrom(node)) {
                result.addEdge(endpoint, node);
            }
        }

        return result;
    }

}

Below demonstrate the setup of the directed graph and will print out the sorted result.

    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph()
        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("D");
        graph.addNode("E");
        graph.addNode("F");
        graph.addNode("G");
        graph.addNode("H");
        graph.addNode("I");
        graph.addNode("J");

        graph.addEdge("A", "D");
        graph.addEdge("A", "E");
        graph.addEdge("B", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "G");
        graph.addEdge("E", "H");
        graph.addEdge("F", "H");
        graph.addEdge("G", "H");

        List sorted = TopologicalSort.sort(graph)

        System.out.println(sorted)
    }