Below is the syntax highlighted version of EdgeWeightedDirectedCycle.java.
/****************************************************************************** * Compilation: javac EdgeWeightedDirectedCycle.java * Execution: java EdgeWeightedDirectedCycle V E F * Dependencies: EdgeWeightedDigraph.java DirectedEdge.java Stack.java * * Finds a directed cycle in an edge-weighted digraph. * Runs in O(E + V) time. * * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code EdgeWeightedDirectedCycle} class represents a data type for * determining whether an edge-weighted digraph has a directed cycle. * The <em>hasCycle</em> operation determines whether the edge-weighted * digraph has a directed cycle and, if so, the <em>cycle</em> operation * returns one. * <p> * This implementation uses <em>depth-first search</em>. * 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 * edge-weighted digraph). * <p> * See {@link Topological} to compute a topological order if the * edge-weighted digraph is acyclic. * <p> * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/44sp">Section 4.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class EdgeWeightedDirectedCycle { private boolean[] marked; // marked[v] = has vertex v been marked? private DirectedEdge[] edgeTo; // edgeTo[v] = previous edge on path to v private boolean[] onStack; // onStack[v] = is vertex on the stack? private Stack<DirectedEdge> cycle; // directed cycle (or null if no such cycle) /** * Determines whether the edge-weighted digraph {@code G} has a directed cycle and, * if so, finds such a cycle. * @param G the edge-weighted digraph */ public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) { marked = new boolean[G.V()]; onStack = new boolean[G.V()]; edgeTo = new DirectedEdge[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); // check that digraph has a cycle assert check(); } // check that algorithm computes either the topological order or finds a directed cycle private void dfs(EdgeWeightedDigraph G, int v) { onStack[v] = true; marked[v] = true; for (DirectedEdge e : G.adj(v)) { int w = e.to(); // short circuit if directed cycle found if (cycle != null) return; // found new vertex, so recur else if (!marked[w]) { edgeTo[w] = e; dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<DirectedEdge>(); DirectedEdge f = e; while (f.from() != w) { cycle.push(f); f = edgeTo[f.from()]; } cycle.push(f); return; } } onStack[v] = false; } /** * Does the edge-weighted digraph have a directed cycle? * @return {@code true} if the edge-weighted digraph has a directed cycle, * {@code false} otherwise */ public boolean hasCycle() { return cycle != null; } /** * Returns a directed cycle if the edge-weighted digraph has a directed cycle, * and {@code null} otherwise. * @return a directed cycle (as an iterable) if the edge-weighted digraph * has a directed cycle, and {@code null} otherwise */ public Iterable<DirectedEdge> cycle() { return cycle; } // certify that digraph is either acyclic or has a directed cycle private boolean check() { // edge-weighted digraph is cyclic if (hasCycle()) { // verify cycle DirectedEdge first = null, last = null; for (DirectedEdge e : cycle()) { if (first == null) first = e; if (last != null) { if (last.to() != e.from()) { System.err.printf("cycle edges %s and %s not incident\n", last, e); return false; } } last = e; } // cycle() contains no edges if (first == null || last == null) { System.err.printf("cycle contains no edges\n"); return false; } // first and last edges in cycle are not incident if (last.to() != first.from()) { System.err.printf("cycle edges %s and %s not incident\n", last, first); return false; } } return true; } /** * Unit tests the {@code EdgeWeightedDirectedCycle} data type. * * @param args the command-line arguments */ public static void main(String[] args) { // create random DAG with V vertices and E edges; then add F random edges int V = Integer.parseInt(args[0]); int E = Integer.parseInt(args[1]); int F = Integer.parseInt(args[2]); EdgeWeightedDigraph G = new EdgeWeightedDigraph(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.uniformInt(V); w = StdRandom.uniformInt(V); } while (v >= w); double weight = StdRandom.uniformDouble(0.0, 1.0); G.addEdge(new DirectedEdge(v, w, weight)); } // add F extra edges for (int i = 0; i < F; i++) { int v = StdRandom.uniformInt(V); int w = StdRandom.uniformInt(V); double weight = StdRandom.uniformDouble(0.0, 1.0); G.addEdge(new DirectedEdge(v, w, weight)); } StdOut.println(G); // find a directed cycle EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G); if (finder.hasCycle()) { StdOut.print("Cycle: "); for (DirectedEdge e : finder.cycle()) { StdOut.print(e + " "); } StdOut.println(); } // or give topological sort else { StdOut.println("No directed cycle"); } } } /****************************************************************************** * 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. ******************************************************************************/