// Exercise 4.4.12 (Solution published at http://algs4.cs.princeton.edu/)
package algs44;
import stdlib.*;
import algs13.Stack;
/* ***********************************************************************
 *  Compilation:  javac EdgeWeightedDirectedCycle.java
 *  Execution:    java EdgeWeightedDirectedCycle V E F
 *  Dependencies: EdgeWeightedDigraph.java DirectedEdge Stack.java
 *
 *  Finds a directed cycle in an edge-weighted digraph.
 *  Runs in O(E + V) time.
 *
 *
 *************************************************************************/

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

  public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) {
    marked  = new boolean[G.V()];
    onStack = new boolean[G.V()];
    edgeTo  = new DirectedEdge[G.V()];
    for (int v = 0; v < G.V(); v++)
      if (!marked[v]) dfs(G, v);

    // check that digraph has a cycle
    assert check(G);
  }


  // check that algorithm computes either the topological order or finds a directed cycle
  private void dfs(EdgeWeightedDigraph G, int v) {
    onStack[v] = true;
    marked[v] = true;
    for (DirectedEdge e : G.adj(v)) {
      int w = e.to();

      // short circuit if directed cycle found
      if (cycle != null) return;

      //found new vertex, so recur
      else if (!marked[w]) {
        edgeTo[w] = e;
        dfs(G, w);
      }


      // trace back directed cycle
      else if (onStack[w]) {
        cycle = new Stack<>();
        while (e.from() != w) {
          cycle.push(e);
          e = edgeTo[e.from()];
        }
        cycle.push(e);
      }
    }

    onStack[v] = false;
  }

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


  // certify that digraph is either acyclic or has a directed cycle
  private boolean check(EdgeWeightedDigraph G) {

    // edge-weighted digraph is cyclic
    if (hasCycle()) {
      // verify cycle
      DirectedEdge first = null, last = null;
      for (DirectedEdge e : cycle()) {
        if (first == null) first = e;
        if (last != null) {
          if (last.to() != e.from()) {
            System.err.format("cycle edges %s and %s not incident\n", last, e);
            return false;
          }
        }
        last = e;
      }

      if (last.to() != first.from()) {
        System.err.format("cycle edges %s and %s not incident\n", last, first);
        return false;
      }
    }


    return true;
  }

  public static void main(String[] args) {

    // 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]);
    EdgeWeightedDigraph G = new EdgeWeightedDigraph(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);
      double weight = Math.random();
      G.addEdge(new DirectedEdge(v, w, weight));
    }

    // add F extra edges
    for (int i = 0; i < F; i++) {
      int v = (int) (Math.random() * V);
      int w = (int) (Math.random() * V);
      double weight = Math.random();
      G.addEdge(new DirectedEdge(v, w, weight));
    }

    StdOut.println(G);

    // find a directed cycle
    EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
    if (finder.hasCycle()) {
      StdOut.print("Cycle: ");
      for (DirectedEdge e : finder.cycle()) {
        StdOut.print(e + " ");
      }
      StdOut.println();
    }

    // or give topologial sort
    else {
      StdOut.println("No directed cycle");
    }
  }

}