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}