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

public class XShortestDirectedCycle {
	private Stack<Integer> cycle;    // directed cycle (or null if no such cycle)
	private int length;

	public XShortestDirectedCycle(Digraph G) {
		Digraph R = G.reverse();
		length = G.V() + 1;
		for (int v = 0; v < G.V(); v++) {
			BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(R, v);
			for (int w : G.adj(v)) {
				if (bfs.hasPathTo(w) && (bfs.distTo(w) + 1) < length) {
					length = bfs.distTo(w) + 1;
					cycle = new Stack<>();
					for (int x : bfs.pathTo(w))
						cycle.push(x);
					cycle.push(v);
				}
			}
		}
	}


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

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

		Digraph G;
		if (args.length == 1) {
			In in = new In(args[0]);
			G = DigraphGenerator.fromIn(in);
		} else {
			int V = Integer.parseInt(args[0]);
			int E = Integer.parseInt(args[1]);
			G = DigraphGenerator.simple(V, E);
		}

		XShortestDirectedCycle finder = new XShortestDirectedCycle(G);
		if (finder.hasCycle()) {
			StdOut.print("Shortest directed cycle: ");
			for (int v : finder.cycle()) {
				StdOut.print(v + " ");
			}
			StdOut.println();
		}

		else {
			StdOut.println("No cycle");
		}
	}

}