HybridCosimulation/DSL_SemanticAdaptation/be.uantwerpen.ansymo.semanticadaptation.cg.canonical/src/be/uantwerpen/ansymo/semanticadaptation/cg/canonical/graph/TopologicalSort.java

package be.uantwerpen.ansymo.semanticadaptation.cg.canonical.graph;

/******************************************************************************
 * File: TopologicalSort.java
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * A linear-time algorithm for computing a topological sort of a directed
 * acyclic graph.  A topological sort is an ordering of the nodes in a graph
 * such that for each node v, all of the ancestors of v appear in the ordering
 * before v itself.  Topological sorting is useful, for example, when computing
 * some function on a DAG where each node's value depends on its ancestors.
 * Running a topological sort and then visiting the nodes in the order
 * specified by this sorted order ensures that the necessary values for each
 * node are available before the node is visited.
 *
 * There are several algorithms for computing topological sorts.  The one used
 * here was first described in "Edge-Disjoint Spanning Trees and Depth-First
 * Search" by Robert Tarjan.  The algorithm is reminiscent of Kosaraju's SCC
 * algorithm.  We begin by constructing the reverse graph G^{rev} from the
 * source graph, then running a depth-first search from each node in the graph.
 * Whenever we finish expanding a node, we add it to a list of visited nodes.
 * The intution behind this algorithm is that a DFS in the reverse graph will
 * visit every node that is an ancestor of the given node before it finishes
 * expanding out any node.  Since those nodes will be added to the sorted order
 * before the expanded node, we have the desired property of the topological
 * sort.
 *
 * This process can be augmented to detect a cycle in the original graph.  As
 * we do the search, we'll maintain a set of nodes that we have visited and a
 * set of nodes that we have expanded.  If when doing the DFS we find a node
 * that has been visited but not expanded, it means that we have encountered a
 * cycle in the graph.  Moreover, if a cycle exists, we know that this will
 * occur, since the first time any node in the cycle is visited the DFS will
 * expand out the cycle.
 */

import java.util.*; // For List, Map.

public final class TopologicalSort {
    /**
     * Given a directed acyclic graph, returns a topological sorting of the
     * nodes in the graph.  If the input graph is not a DAG, throws an
     * IllegalArgumentException.
     *
     * @param g A directed acyclic graph.
     * @return A topological sort of that graph.
     * @throws IllegalArgumentException If the graph is not a DAG.
     */
    public static <T> List<T> sort(DirectedGraph<T> g) {
        /* Construct the reverse graph from the input graph. */
        DirectedGraph<T> gRev = reverseGraph(g);

        /* Maintain two structures - a set of visited nodes (so that once we've
         * added a node to the list, we don't label it again), and a list of
         * nodes that actually holds the topological ordering.
         */
        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 DFS from each node in the graph. */
        for (T node: gRev)
            explore(node, gRev, result, visited, expanded);

        /* Hand back the resulting ordering. */
        return result;
    }


    /**
     * Recursively performs a DFS from the specified node, marking all nodes
     * encountered by the search.
     *
     * @param node The node to begin the search from.
     * @param g The graph in which to perform the search.
     * @param ordering 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> g,
                                    List<T> ordering, Set<T> visited,
                                    Set<T> expanded) {
        /* Check whether we've been here before.  If so, we should stop the
         * search.
         */
        if (visited.contains(node)) {
            /* There are two cases to consider.  First, 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.  However, 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.
             */
            if (expanded.contains(node)) return;
            throw new IllegalArgumentException("Graph contains a cycle.");
        }
        
        /* Mark that we've been here */
        visited.add(node);

        /* Recursively explore all of the node's predecessors. */
        for (T predecessor: g.edgesFrom(node))
            explore(predecessor, g, ordering, visited, expanded);

        /* Having explored all of the node's predecessors, we can now add this
         * node to the sorted ordering.
         */
        ordering.add(node);

        /* Similarly, mark that this node is done being expanded. */
        expanded.add(node);
    }

    /**
     * Returns the reverse of the input graph.
     *
     * @param g A graph to reverse.
     * @return The reverse of that graph.
     */
    private static <T> DirectedGraph<T> reverseGraph(DirectedGraph<T> g) {
        DirectedGraph<T> result = new DirectedGraph<T>();

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

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

        return result;
    }
}