// Exercise 4.4.12 (Solution published at http://algs4.cs.princeton.edu/)
package algs42;
import stdlib.*;
import algs44.EdgeWeightedDigraph;
import algs44.EdgeWeightedDirectedCycle;
/* ***********************************************************************
 *  Compilation:  javac Topoological.java
 *  Dependencies: Digraph.java DepthFirstOrder.java DirectedCycle.java
 *                EdgeWeightedDigraph.java EdgeWeightedDirectedCycle.java
 *  Data files:   http://algs4.cs.princeton.edu/42directed/jobs.txt
 *
 *  Compute topological ordering of a DAG or edge-weighted DAG.
 *  Runs in O(E + V) time.
 *
 *  % java Topological jobs.txt "/"
 *  Calculus
 *  Linear Algebra
 *  Introduction to CS
 *  Programming Systems
 *  Algorithms
 *  Theoretical CS
 *  Artificial Intelligence
 *  Machine Learning
 *  Neural Networks
 *  Robotics
 *  Scientific Computing
 *  Computational Biology
 *  Databases
 *
 *
 *************************************************************************/

public class Topological {
  private Iterable<Integer> order;    // topological order

  // topological sort in a digraph
  public Topological(Digraph G) {
    DirectedCycle finder = new DirectedCycle(G);
    if (!finder.hasCycle()) {
      DepthFirstOrder dfs = new DepthFirstOrder(G);
      order = dfs.reversePost();
    }
  }

  // topological sort in an edge-weighted digraph
  public Topological(EdgeWeightedDigraph G) {
    EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
    if (!finder.hasCycle()) {
      DepthFirstOrder dfs = new DepthFirstOrder(G);
      order = dfs.reversePost();
    }
  }

  // return topological order if a DAG; null otherwise
  public Iterable<Integer> order() {
    return order;
  }

  // does digraph have a topological order?
  public boolean hasOrder() {
    return order != null;
  }


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

    String filename  = args[0];
    String delimiter = args[1];
    SymbolDigraph sg = new SymbolDigraph(filename, delimiter);
    StdOut.println (sg);
    Topological topological = new Topological(sg.G());
    for (int v : topological.order()) {
      StdOut.println(sg.name(v));
    }
  }

}