// Exercise 4.2.39 (Solution published at http://algs4.cs.princeton.edu/)
package algs42;
import stdlib.*;
import algs13.Queue;
/* ***********************************************************************
 *  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 XTopologicalQueue {
	private final Queue<Integer> order;     // vertices in topological order
	private final int[] indegree;           // indegree[v] = indegree of vertex v
	private final int[] rank;               // rank[v] = order where vertex v appers in order
	private int count;                // for computing the ranks

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

		// 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<>();
		for (int v = 0; v < G.V(); v++)
			if (indegree[v] == 0) queue.enqueue(v);

		while (!queue.isEmpty()) {
			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 element : indegree)
			if (element != 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.format("%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) {
		args = new String[] { "10", "20", "2" };

		// 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
		XTopologicalQueue topological = new XTopologicalQueue(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();
		}
	}

}