/*************************************************************************
 *  Kompilacja:  javac Topoological.java
 *  Zależności: Digraph.java DepthFirstOrder.java DirectedCycle.java
 *                EdgeWeightedDigraph.java EdgeWeightedDirectedCycle.java
 *
 *  Wyznacza porządek topologiczny grafów DAG.
 *  Złożoność O(E + V).
 *
 *
 *************************************************************************/

public class Topological {
    private Iterable<Integer> order;    // Porządek topologiczny.

    // Sortowanie topologiczne digrafu.
    public Topological(Digraph G) {
        DirectedCycle finder = new DirectedCycle(G);
        if (!finder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePostorder();
        }
    }

    // Sortowanie topologiczne digrafu ważonego.
    public Topological(EdgeWeightedDigraph G) {
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
        if (!finder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePostorder();
        }
    }

    // Zwraca porządek topologiczny grafu DAG (lub null).
    public Iterable<Integer> order() {
        return order;
    }

    // Czy w digrafie można wyznaczyć porządek topologiczny?
    public boolean hasOrder() {
        return order != null;
    }



    public static void main(String[] args) {

        // Tworzy losowy graf DAG o V wierzchołkach i E krawędziach.
        int V = Integer.parseInt(args[0]);
        int E = Integer.parseInt(args[1]);
        Digraph G = new Digraph(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);
            G.addEdge(vertices[v], vertices[w]);
        }

        System.out.println("Graf acykliczny G");
        System.out.println("-----------------");
        System.out.println(G);

        System.out.println();
        System.out.println("Wierzchołki w porządku topologicznym przy tworzeniu");
        System.out.println("---------------------------------------------------");
        for (int i = 0; i < V; i++) 
            System.out.print(vertices[i] + " ");
        System.out.println();
        System.out.println();

        // Wyznacza porządek topologiczny.
        // Może nie pasować do wcześniejszego, ponieważ może istnieć wiele porządków topologicznych.
        System.out.println("Wierzchołki w porządku topologicznym na podstawie algorytmu");
        System.out.println("-----------------------------------------------------------");
        Topological topological = new Topological(G);
        for (int v : topological.order()) {
            System.out.print(v + " ");
        }
        System.out.println();
    }

}
