001package algs42; 002import stdlib.*; 003import algs13.Stack; 004/* *********************************************************************** 005 * Compilation: javac ShortestDirectedCycle.java 006 * Execution: java DirectedCycle < input.txt 007 * Dependencies: Digraph.java BreadthFirstDirectedPaths.java Stack.java StdOut.java In.java 008 * Data files: http://algs4.cs.princeton.edu/42directed/tinyDG.txt 009 * http://algs4.cs.princeton.edu/42directed/tinyDAG.txt 010 * 011 * Finds a shortest directed cycle in a digraph. 012 * Runs in O(V * (E + V)) time. 013 * 014 * % java ShortestDirectedCycle tinyDG.txt 015 * Shortest directed cycle: 2 3 2 016 * 017 * % java ShortestDirectedCycle tinyDAG.txt 018 * No cycle 019 * 020 *************************************************************************/ 021 022public class XShortestDirectedCycle { 023 private Stack<Integer> cycle; // directed cycle (or null if no such cycle) 024 private int length; 025 026 public XShortestDirectedCycle(Digraph G) { 027 Digraph R = G.reverse(); 028 length = G.V() + 1; 029 for (int v = 0; v < G.V(); v++) { 030 BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(R, v); 031 for (int w : G.adj(v)) { 032 if (bfs.hasPathTo(w) && (bfs.distTo(w) + 1) < length) { 033 length = bfs.distTo(w) + 1; 034 cycle = new Stack<>(); 035 for (int x : bfs.pathTo(w)) 036 cycle.push(x); 037 cycle.push(v); 038 } 039 } 040 } 041 } 042 043 044 public boolean hasCycle() { return cycle != null; } 045 public Iterable<Integer> cycle() { return cycle; } 046 public int length() { return length; } 047 048 public static void main(String[] args) { 049 args = new String[] { "data/tinyDG.txt" }; 050 051 Digraph G; 052 if (args.length == 1) { 053 In in = new In(args[0]); 054 G = DigraphGenerator.fromIn(in); 055 } else { 056 int V = Integer.parseInt(args[0]); 057 int E = Integer.parseInt(args[1]); 058 G = DigraphGenerator.simple(V, E); 059 } 060 061 XShortestDirectedCycle finder = new XShortestDirectedCycle(G); 062 if (finder.hasCycle()) { 063 StdOut.print("Shortest directed cycle: "); 064 for (int v : finder.cycle()) { 065 StdOut.print(v + " "); 066 } 067 StdOut.println(); 068 } 069 070 else { 071 StdOut.println("No cycle"); 072 } 073 } 074 075}