001// Exercise 4.4.12 (Solution published at http://algs4.cs.princeton.edu/)
002package algs42;
003import stdlib.*;
004import algs44.EdgeWeightedDigraph;
005import algs44.EdgeWeightedDirectedCycle;
006/* ***********************************************************************
007 *  Compilation:  javac Topoological.java
008 *  Dependencies: Digraph.java DepthFirstOrder.java DirectedCycle.java
009 *                EdgeWeightedDigraph.java EdgeWeightedDirectedCycle.java
010 *  Data files:   http://algs4.cs.princeton.edu/42directed/jobs.txt
011 *
012 *  Compute topological ordering of a DAG or edge-weighted DAG.
013 *  Runs in O(E + V) time.
014 *
015 *  % java Topological jobs.txt "/"
016 *  Calculus
017 *  Linear Algebra
018 *  Introduction to CS
019 *  Programming Systems
020 *  Algorithms
021 *  Theoretical CS
022 *  Artificial Intelligence
023 *  Machine Learning
024 *  Neural Networks
025 *  Robotics
026 *  Scientific Computing
027 *  Computational Biology
028 *  Databases
029 *
030 *
031 *************************************************************************/
032
033public class Topological {
034        private Iterable<Integer> order;    // topological order
035
036        // topological sort in a digraph
037        public Topological(Digraph G) {
038                DirectedCycle finder = new DirectedCycle(G);
039                if (!finder.hasCycle()) {
040                        DepthFirstOrder dfs = new DepthFirstOrder(G);
041                        order = dfs.reversePost();
042                }
043        }
044
045        // topological sort in an edge-weighted digraph
046        public Topological(EdgeWeightedDigraph G) {
047                EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
048                if (!finder.hasCycle()) {
049                        DepthFirstOrder dfs = new DepthFirstOrder(G);
050                        order = dfs.reversePost();
051                }
052        }
053
054        // return topological order if a DAG; null otherwise
055        public Iterable<Integer> order() {
056                return order;
057        }
058
059        // does digraph have a topological order?
060        public boolean hasOrder() {
061                return order != null;
062        }
063
064
065        public static void main(String[] args) {
066                args = new String[] { "data/jobs.txt", "/" };
067
068                String filename  = args[0];
069                String delimiter = args[1];
070                SymbolDigraph sg = new SymbolDigraph(filename, delimiter);
071                StdOut.println (sg);
072                Topological topological = new Topological(sg.G());
073                for (int v : topological.order()) {
074                        StdOut.println(sg.name(v));
075                }
076        }
077
078}