001// Exercise 4.2.39 (Solution published at http://algs4.cs.princeton.edu/)
002package algs42;
003import stdlib.*;
004import algs13.Queue;
005/* ***********************************************************************
006 *  Compilation:  javac TopologicalQueue.java
007 *  Execution:    java TopologicalQueue V E F
008 *  Dependencies: Queue.java
009 *
010 *  Compute topological ordering of a DAG using queue-based algorithm.
011 *  Runs in O(E + V) time.
012 *
013 *
014 *************************************************************************/
015
016public class XTopologicalQueue {
017        private final Queue<Integer> order;     // vertices in topological order
018        private final int[] indegree;           // indegree[v] = indegree of vertex v
019        private final int[] rank;               // rank[v] = order where vertex v appers in order
020        private int count;                // for computing the ranks
021
022        public XTopologicalQueue(Digraph G) {
023                indegree = new int[G.V()];
024                rank = new int[G.V()];
025                order = new Queue<>();
026
027                // compute indegrees
028                for (int v = 0; v < G.V(); v++) {
029                        for (int w : G.adj(v)) {
030                                indegree[w]++;
031                        }
032                }
033
034                // initialize queue to contain all vertices with indegree = 0
035                Queue<Integer> queue = new Queue<>();
036                for (int v = 0; v < G.V(); v++)
037                        if (indegree[v] == 0) queue.enqueue(v);
038
039                while (!queue.isEmpty()) {
040                        int v = queue.dequeue();
041                        order.enqueue(v);
042                        rank[v] = count++;
043                        for (int w : G.adj(v)) {
044                                indegree[w]--;
045                                if (indegree[w] == 0) queue.enqueue(w);
046                        }
047                }
048        }
049
050        // is G a directed acyclic graph?
051        public boolean isDAG() {
052                for (int element : indegree)
053                        if (element != 0) return false;
054                return true;
055        }
056
057        // the vertices in topological order (assuming G is a DAG)
058        public Iterable<Integer> order() {
059                return order;
060        }
061
062
063        // the rank of vertex v in topological order
064        public int rank(int v) {
065                return rank[v];
066        }
067
068        // certify that digraph is acyclic
069        private boolean check(Digraph G) {
070
071                // digraph is acyclic
072                if (isDAG()) {
073                        // check that ranks are a permutation of 0 to V-1
074                        boolean[] found = new boolean[G.V()];
075                        for (int i = 0; i < G.V(); i++) {
076                                found[rank(i)] = true;
077                        }
078                        for (int i = 0; i < G.V(); i++) {
079                                if (!found[i]) {
080                                        System.err.println("No vertex with rank " + i);
081                                        return false;
082                                }
083                        }
084
085                        // check that ranks provide a valid toplogical order
086                        for (int v = 0; v < G.V(); v++) {
087                                for (int w : G.adj(v)) {
088                                        if (rank(v) > rank(w)) {
089                                                System.err.format("%d-%d: rank(%d) = %d, rank(%d) = %d\n",
090                                                                v, w, v, rank(v), w, rank(w));
091                                                return false;
092                                        }
093                                }
094                        }
095
096                        // check that order() is consistent with rank()
097                        int r = 0;
098                        for (int v : order()) {
099                                if (rank(v) != r) {
100                                        System.err.println("order() and rank() inconsistent");
101                                        return false;
102                                }
103                                r++;
104                        }
105                }
106
107
108                return true;
109        }
110
111        public static void main(String[] args) {
112                args = new String[] { "10", "20", "2" };
113
114                // create random DAG with V vertices and E edges; then add F random edges
115                int V = Integer.parseInt(args[0]);
116                int E = Integer.parseInt(args[1]);
117                int F = Integer.parseInt(args[2]);
118                Digraph G = new Digraph(V);
119                int[] vertices = new int[V];
120                for (int i = 0; i < V; i++) vertices[i] = i;
121                StdRandom.shuffle(vertices);
122                for (int i = 0; i < E; i++) {
123                        int v, w;
124                        do {
125                                v = StdRandom.uniform(V);
126                                w = StdRandom.uniform(V);
127                        } while (v >= w);
128                        G.addEdge(vertices[v], vertices[w]);
129                }
130
131                // add F extra edges
132                for (int i = 0; i < F; i++) {
133                        int v = (int) (Math.random() * V);
134                        int w = (int) (Math.random() * V);
135                        G.addEdge(v, w);
136                }
137
138                StdOut.println(G);
139
140                // find a directed cycle
141                XTopologicalQueue topological = new XTopologicalQueue(G);
142                if (!topological.isDAG()) {
143                        StdOut.println("Not a DAG");
144                }
145
146                // or give topologial sort
147                else {
148                        StdOut.print("Topological order: ");
149                        for (int v : topological.order()) {
150                                StdOut.print(v + " ");
151                        }
152                        StdOut.println();
153                }
154        }
155
156}