``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 ``` ```// 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 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 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)); } } } ```