ShortestDirectedCycle.java

Below is the syntax highlighted version of ShortestDirectedCycle.java from §4.2 Directed Graphs.

/******************************************************************************
 *  Compilation:  javac ShortestDirectedCycle.java
 *  Execution:    java DirectedCycle < input.txt
 *  Dependencies: Digraph.java BreadthFirstDirectedPaths.java Stack.java StdOut.java In.java
 *  Data files:   https://algs4.cs.princeton.edu/42digraph/tinyDG.txt
 *                https://algs4.cs.princeton.edu/42digraph/tinyDAG.txt
 *
 *  Finds a shortest directed cycle in a digraph.
 *  Runs in O(V * (E + V)) time.
 *
 *  % java ShortestDirectedCycle tinyDG.txt
 *  Shortest directed cycle: 2 3 2
 *
 *  %  java ShortestDirectedCycle tinyDAG.txt
 *  No directed cycle
 *
 ******************************************************************************/

public class ShortestDirectedCycle {
    private Stack<Integer> cycle;    // directed cycle (or null if no such cycle)
    private int length;

    public ShortestDirectedCycle(Digraph digraph) {
        Digraph reverse = digraph.reverse();
        length = digraph.V() + 1;
        for (int v = 0; v < digraph.V(); v++) {
            BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(reverse, v);
            // for each each v->w
            for (int w : digraph.adj(v)) {
                // check if there is a directed path from w to v
                // (or, equivalently, a directed path from v to w in the reverse digraph)
                // combining this path with the the v->w produces a directed cycle
                if (bfs.hasPathTo(w) && (bfs.distTo(w) + 1) < length) {
                    length = bfs.distTo(w) + 1;
                    cycle = new Stack<Integer>();
                    for (int x : bfs.pathTo(w))
                        cycle.push(x);
                    cycle.push(v);
                }
            }
        }
    }


    // does the digraph have a directed cycle?
    public boolean hasCycle() {
        return cycle != null;
    }

    // returns the cycle as in iterable of vertices (or null if no such cycle)
    public Iterable<Integer> cycle() {
        return cycle;
    }

    // returns the length of the directed cycle (or V+1 if no such cycle)
    public int length() {
        return length;
    }

    public static void main(String[] args) {
        Digraph digraph;
        if (args.length == 1) {
            In in = new In(args[0]);
            digraph = new Digraph(in);
        }
        else {
            int V = Integer.parseInt(args[0]);
            int E = Integer.parseInt(args[1]);
            digraph = DigraphGenerator.simple(V, E);
        }

        ShortestDirectedCycle finder = new ShortestDirectedCycle(digraph);
        if (finder.hasCycle()) {
            StdOut.print("Shortest directed cycle: ");
            for (int v : finder.cycle()) {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }

        else {
            StdOut.println("No directed cycle");
        }
    }

}