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}