package algs41;
import stdlib.*;
import algs13.Stack;
/* ***********************************************************************
 *  Compilation:  javac Cycle.java
 *  Dependencies: Graph.java Stack.java
 *
 *  Identifies a cycle.
 *  Runs in O(E + V) time.
 *
 *************************************************************************/

public class Cycle {
  private boolean[] marked;
  private int[] edgeTo;
  private Stack<Integer> cycle;

  public Cycle(Graph G) {
    if (hasSelfLoop(G)) return;
    if (hasParallelEdges(G)) return;
    marked = new boolean[G.V()];
    edgeTo = new int[G.V()];
    for (int v = 0; v < G.V(); v++)
      if (!marked[v] && hasCycleFrom(G, -1, v))
        return;
  }

  // Assuming there is no self loop or parallel edges, does this graph have a cycle?
  private boolean hasCycleFromSimple(Graph G, int u, int v) {
    marked[v] = true; 
    for (int w : G.adj(v)) {
      if (w == u) continue; // skip the back edge: edgeTo[v] = u
      if (marked[w]) return true; // been here before
      if (hasCycleFromSimple (G, v, w)) return true; // search recursively
    }
    return false;
  }

  // Assuming there is no self loop or parallel edges, does this graph have a cycle?
  // side effect: initialize cycle field
  private boolean hasCycleFrom(Graph G, int u, int v) {
    //StdOut.format ("dfs(%d, %d)\n", u, v);
    marked[v] = true;
    edgeTo[v] = u;
    for (int w : G.adj(v)) {
      if (w == u) continue; // skip the back edge
      if (marked[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 (hasCycleFrom (G, v, w)) return true;
    }
    return false;
  }
  private boolean TEXTBOOKhasCycleFrom(Graph G, int u, int v) {
    marked[v] = true;
    edgeTo[v] = u;
    for (int w : G.adj(v)) {
      if ((marked[w] && w != u) || (!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;
      }
    }
    return false;
  }
  // does this graph have a self loop?
  // side effect: initialize cycle field
  private boolean hasSelfLoop(Graph G) {
    for (int v = 0; v < G.V(); v++) {
      for (int w : G.adj(v)) {
        if (v == w) {
          cycle = new Stack<>();
          cycle.push(v);
          cycle.push(v);
          return true;
        }
      }
    }
    return false;
  }

  // does this graph have two parallel edges?
  // side effect: initialize cycle field
  private boolean hasParallelEdges(Graph G) {
    for (int v = 0; v < G.V(); v++) {
      boolean[] marked = new boolean[G.V()];
      for (int w : G.adj(v)) {
        if (!marked[w]) {
          marked[w] = true;
        } else {
          // edge occurs twice
          cycle = new Stack<>();
          cycle.push(v);
          cycle.push(w);
          cycle.push(v);
          return true;
        }
      }
    }
    return false;
  }

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

  // test client
  public static void main(String[] args) {
    //    args = new String [] { "10", "5" };
    //    final int V = Integer.parseInt(args[0]);
    //    final int E = Integer.parseInt(args[1]);
    //    final Graph G = GraphGenerator.simple(V, E);
    //    StdOut.println(G);

    //args = new String [] { "data/tinyAG.txt" };
    args = new String [] { "data/tinyG.txt" };
    In in = new In(args[0]);
    Graph G = GraphGenerator.fromIn (in);
    StdOut.println(G);
    G.toGraphviz ("g.png");

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


}