TopologicalQueue.java

Below is the syntax highlighted version of TopologicalQueue.java from §4.2 Directed Graphs.

/*************************************************************************
 *  Compilation:  javac TopologicalQueue.java
 *  Execution:    java TopologicalQueue V E F
 *  Dependencies: Queue.java
 *
 *  Compute topological ordering of a DAG using queue-based algorithm.
 *  Runs in O(E + V) time.
 *
 *
 *************************************************************************/

public class TopologicalQueue {
    private Queue<Integer> order;     // vertices in topological order
    private int[] indegree;           // indegree[v] = indegree of vertex v
    private int[] rank;               // rank[v] = order where vertex v appers in order
    private int count;                // for computing the ranks

    public TopologicalQueue(Digraph G) {
        indegree = new int[G.V()]; 
        rank = new int[G.V()]; 
        order = new Queue<Integer>();

        // compute indegrees
        for (int v = 0; v < G.V(); v++) {
            for (int w : G.adj(v)) {
                indegree[w]++;
            }
        }

        // initialize queue to contain all vertices with indegree = 0
        Queue<Integer> queue = new Queue<Integer>();
        for (int v = 0; v < G.V(); v++)
            if (indegree[v] == 0) queue.enqueue(v);

        for (int j = 0; !queue.isEmpty(); j++) {
            int v = queue.dequeue();
            order.enqueue(v);
            rank[v] = count++;
            for (int w : G.adj(v)) {
                indegree[w]--;
                if (indegree[w] == 0) queue.enqueue(w);
            }
        }
    }

    // is G a directed acyclic graph?
    public boolean isDAG() {
        for (int v = 0; v < indegree.length; v++)
            if (indegree[v] != 0) return false;
        return true;
    }

    // the vertices in topological order (assuming G is a DAG)
    public Iterable<Integer> order() {
        return order;
    }


    // the rank of vertex v in topological order
    public int rank(int v) {
        return rank[v];
    }

    // certify that digraph is acyclic
    private boolean check(Digraph G) {

        // digraph is acyclic
        if (isDAG()) {
            // check that ranks are a permutation of 0 to V-1
            boolean[] found = new boolean[G.V()];
            for (int i = 0; i < G.V(); i++) {
                found[rank(i)] = true;
            }
            for (int i = 0; i < G.V(); i++) {
                if (!found[i]) {
                    System.err.println("No vertex with rank " + i);
                    return false;
                }
            }

            // check that ranks provide a valid toplogical order
            for (int v = 0; v < G.V(); v++) {
                for (int w : G.adj(v)) {
                    if (rank(v) > rank(w)) {
                        System.err.printf("%d-%d: rank(%d) = %d, rank(%d) = %d\n",
                                          v, w, v, rank(v), w, rank(w));
                        return false;
                    }
                }
            }

            // check that order() is consistent with rank()
            int r = 0;
            for (int v : order()) {
                if (rank(v) != r) {
                    System.err.println("order() and rank() inconsistent");
                    return false;
                }
                r++;
            }
        }


        return true;
    }

    public static void main(String[] args) {

        // create random DAG with V vertices and E edges; then add F random edges
        int V = Integer.parseInt(args[0]);
        int E = Integer.parseInt(args[1]);
        int F = Integer.parseInt(args[2]);
        Digraph G = new Digraph(V);
        int[] vertices = new int[V];
        for (int i = 0; i < V; i++) vertices[i] = i;
        StdRandom.shuffle(vertices);
        for (int i = 0; i < E; i++) {
            int v, w;
            do {
                v = StdRandom.uniform(V);
                w = StdRandom.uniform(V);
            } while (v >= w);
            G.addEdge(vertices[v], vertices[w]);
        }

        // add F extra edges
        for (int i = 0; i < F; i++) {
            int v = (int) (Math.random() * V);
            int w = (int) (Math.random() * V);
            G.addEdge(v, w);
        }

        StdOut.println(G);

        // find a directed cycle
        TopologicalQueue topological = new TopologicalQueue(G);
        if (!topological.isDAG()) {
            StdOut.println("Not a DAG");
        }

        // or give topologial sort
        else {
            StdOut.print("Topological order: ");
            for (int v : topological.order()) {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }
    }

}