Below is the syntax highlighted version of Topological.java.
/****************************************************************************** * Compilation: javac Topological.java * Execution: java Topological filename.txt delimiter * Dependencies: Digraph.java DepthFirstOrder.java DirectedCycle.java * EdgeWeightedDigraph.java EdgeWeightedDirectedCycle.java * SymbolDigraph.java * Data files: https://algs4.cs.princeton.edu/42digraph/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 * Advanced Programming * Algorithms * Theoretical CS * Artificial Intelligence * Robotics * Machine Learning * Neural Networks * Databases * Scientific Computing * Computational Biology * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code Topological} class represents a data type for * determining a topological order of a <em>directed acyclic graph</em> (DAG). * A digraph has a topological order if and only if it is a DAG. * The <em>hasOrder</em> operation determines whether the digraph has * a topological order, and if so, the <em>order</em> operation * returns one. * <p> * This implementation uses depth-first search. * The constructor takes Θ(<em>V</em> + <em>E</em>) time in the * worst case, where <em>V</em> is the number of vertices and <em>E</em> * is the number of edges. * Each instance method takes Θ(1) time. * It uses Θ(<em>V</em>) extra space (not including the digraph). * <p> * See {@link DirectedCycle}, {@link DirectedCycleX}, and * {@link EdgeWeightedDirectedCycle} for computing a directed cycle * if the digraph is not a DAG. * See {@link TopologicalX} for a nonrecursive queue-based algorithm * for computing a topological order of a DAG. * <p> * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Topological { private Iterable<Integer> order; // topological order private int[] rank; // rank[v] = rank of vertex v in order /** * Determines whether the digraph {@code G} has a topological order and, if so, * finds such a topological order. * @param G the digraph */ public Topological(Digraph G) { DirectedCycle finder = new DirectedCycle(G); if (!finder.hasCycle()) { DepthFirstOrder dfs = new DepthFirstOrder(G); order = dfs.reversePost(); rank = new int[G.V()]; int i = 0; for (int v : order) rank[v] = i++; } } /** * Determines whether the edge-weighted digraph {@code G} has a topological * order and, if so, finds such an order. * @param G the edge-weighted digraph */ public Topological(EdgeWeightedDigraph G) { EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G); if (!finder.hasCycle()) { DepthFirstOrder dfs = new DepthFirstOrder(G); order = dfs.reversePost(); } } /** * Returns a topological order if the digraph has a topological order, * and {@code null} otherwise. * @return a topological order of the vertices (as an iterable) if the * digraph has a topological order (or equivalently, if the digraph is a DAG), * and {@code null} otherwise */ public Iterable<Integer> order() { return order; } /** * Does the digraph have a topological order? * @return {@code true} if the digraph has a topological order (or equivalently, * if the digraph is a DAG), and {@code false} otherwise */ public boolean hasOrder() { return order != null; } /** * Does the digraph have a topological order? * @return {@code true} if the digraph has a topological order (or equivalently, * if the digraph is a DAG), and {@code false} otherwise * @deprecated Replaced by {@link #hasOrder()}. */ @Deprecated public boolean isDAG() { return hasOrder(); } /** * The rank of vertex {@code v} in the topological order; * -1 if the digraph is not a DAG * * @param v the vertex * @return the position of vertex {@code v} in a topological order * of the digraph; -1 if the digraph is not a DAG * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int rank(int v) { validateVertex(v); if (hasOrder()) return rank[v]; else return -1; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = rank.length; if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } /** * Unit tests the {@code Topological} data type. * * @param args the command-line arguments */ public static void main(String[] args) { String filename = args[0]; String delimiter = args[1]; SymbolDigraph sg = new SymbolDigraph(filename, delimiter); Topological topological = new Topological(sg.digraph()); for (int v : topological.order()) { StdOut.println(sg.nameOf(v)); } } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/