package algs42;
import stdlib.*;
import algs13.Stack;
/* ***********************************************************************
 *  Compilation:  javac DirectedCycle.java
 *  Execution:    java DirectedCycle < input.txt
 *  Dependencies: Digraph.java Stack.java StdOut.java In.java
 *  Data files:   http://algs.cs.princeton.edu/42digraph/tinyDG.txt
 *                http://algs.cs.princeton.edu/42digraph/tinyDAG.txt
 *
 *  Finds a directed cycle in a digraph.
 *  Runs in O(E + V) time.
 *
 *  % java DirectedCycle tinyDG.txt
 *  Cycle: 3 5 4 3
 *
 *  %  java DirectedCycle tinyDAG.txt
 *  No cycle
 *
 *************************************************************************/

public class DirectedCycle {
	private boolean[] marked;    // marked[v] = has vertex v been marked?
	private int[] edgeTo;        // edgeTo[v] = previous vertex on path to v
	private boolean[] onStack;   // onStack[v] = is vertex on the stack?
	private Stack<Integer> cycle;      // directed cycle (or null if no such cycle)

	public DirectedCycle(Digraph G) {
		marked  = new boolean[G.V()];
		onStack = new boolean[G.V()];
		edgeTo = new int[G.V()];
		for (int v = 0; v < G.V(); v++) {
			if (!marked[v] && hasCycleFrom(G, -1, v)) {
				assert check(G);
				return;
			}
		}
	}

	private boolean hasCycleFromSimple(Digraph G, int v) {
		onStack[v] = true;
		marked[v] = true;
		for (int w : G.adj(v)) {
			if (onStack[w]) return true;
			if (marked[w]) continue;
			if (hasCycleFromSimple (G, w)) return true;
		}
		onStack[v] = false;
		return false;
	}
	
	// if the cycle is not interesting, then u is not necessary.
	private boolean hasCycleFrom(Digraph G, int u, int v) {
		onStack[v] = true;
		marked[v] = true;
		edgeTo[v] = u;
		for (int w : G.adj(v)) {
			if (onStack[w]) {
				cycle = new Stack<>();
				cycle.push(w);
				for (int x = v; x != w; x = edgeTo[x]) {
					cycle.push(x);
				}
				cycle.push(w);
				return true;
			} 
			if (marked[w]) continue;
			if (hasCycleFrom (G, v, w)) return true;
		}
		onStack[v] = false;
		return false;
	}
	
	// if the cycle is not interesting, then u is not necessary.
	private boolean TEXTBOOKhasCycleFrom(Digraph G, int u, int v) {
		onStack[v] = true;
		marked[v] = true;
		edgeTo[v] = u;
		for (int w : G.adj(v))
			if (onStack[w] || (!marked[w] && hasCycleFrom (G, v, w))) {
				if (cycle == null) {
					cycle = new Stack<>();
					cycle.push(w);
					for (int x = v; x != w; x = edgeTo[x]) {
						cycle.push(x);
					}
					cycle.push(w);
				}
				return true;
			}
		onStack[v] = false;
		return false;
	}

	public boolean hasCycle()        { return cycle != null;   }
	public Iterable<Integer> cycle() { return cycle;           }

	// certify that digraph is either acyclic or has a directed cycle
	private boolean check(Digraph G) {
		if (hasCycle()) {
			// verify cycle
			int first = -1, last = -1;
			for (int v : cycle()) {
				if (first == -1) first = v;
				last = v;
			}
			if (first != last) {
				System.err.format("cycle begins with %d and ends with %d\n", first, last);
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		args = new String[] { "data/tinyDG.txt" };
		//args = new String[] { "data/tinyDAG.txt" };

		In in = new In(args[0]);
		Digraph G = DigraphGenerator.fromIn(in);
		G.toGraphviz ("g.png");

		DirectedCycle finder = new DirectedCycle(G);
		if (finder.hasCycle()) {
			//if (finder.hasCycle(G)) {
			StdOut.print("Cycle: ");
			for (int v : finder.cycle()) {
				StdOut.print(v + " ");
			}
			StdOut.println();
		} else {
			StdOut.println("No cycle");
		}
	}

}