001package algs42; 002import stdlib.*; 003import algs13.Stack; 004/* *********************************************************************** 005 * Compilation: javac DirectedCycle.java 006 * Execution: java DirectedCycle < input.txt 007 * Dependencies: Digraph.java Stack.java StdOut.java In.java 008 * Data files: http://algs.cs.princeton.edu/42digraph/tinyDG.txt 009 * http://algs.cs.princeton.edu/42digraph/tinyDAG.txt 010 * 011 * Finds a directed cycle in a digraph. 012 * Runs in O(E + V) time. 013 * 014 * % java DirectedCycle tinyDG.txt 015 * Cycle: 3 5 4 3 016 * 017 * % java DirectedCycle tinyDAG.txt 018 * No cycle 019 * 020 *************************************************************************/ 021 022public class DirectedCycle { 023 private boolean[] marked; // marked[v] = has vertex v been marked? 024 private int[] edgeTo; // edgeTo[v] = previous vertex on path to v 025 private boolean[] onStack; // onStack[v] = is vertex on the stack? 026 private Stack<Integer> cycle; // directed cycle (or null if no such cycle) 027 028 public DirectedCycle(Digraph G) { 029 marked = new boolean[G.V()]; 030 onStack = new boolean[G.V()]; 031 edgeTo = new int[G.V()]; 032 for (int v = 0; v < G.V(); v++) { 033 if (!marked[v] && hasCycleFrom(G, -1, v)) { 034 assert check(G); 035 return; 036 } 037 } 038 } 039 040 private boolean hasCycleFromSimple(Digraph G, int v) { 041 onStack[v] = true; 042 marked[v] = true; 043 for (int w : G.adj(v)) { 044 if (onStack[w]) return true; 045 if (marked[w]) continue; 046 if (hasCycleFromSimple (G, w)) return true; 047 } 048 onStack[v] = false; 049 return false; 050 } 051 052 // if the cycle is not interesting, then u is not necessary. 053 private boolean hasCycleFrom(Digraph G, int u, int v) { 054 onStack[v] = true; 055 marked[v] = true; 056 edgeTo[v] = u; 057 for (int w : G.adj(v)) { 058 if (onStack[w]) { 059 cycle = new Stack<>(); 060 cycle.push(w); 061 for (int x = v; x != w; x = edgeTo[x]) { 062 cycle.push(x); 063 } 064 cycle.push(w); 065 return true; 066 } 067 if (marked[w]) continue; 068 if (hasCycleFrom (G, v, w)) return true; 069 } 070 onStack[v] = false; 071 return false; 072 } 073 074 // if the cycle is not interesting, then u is not necessary. 075 private boolean TEXTBOOKhasCycleFrom(Digraph G, int u, int v) { 076 onStack[v] = true; 077 marked[v] = true; 078 edgeTo[v] = u; 079 for (int w : G.adj(v)) 080 if (onStack[w] || (!marked[w] && hasCycleFrom (G, v, w))) { 081 if (cycle == null) { 082 cycle = new Stack<>(); 083 cycle.push(w); 084 for (int x = v; x != w; x = edgeTo[x]) { 085 cycle.push(x); 086 } 087 cycle.push(w); 088 } 089 return true; 090 } 091 onStack[v] = false; 092 return false; 093 } 094 095 public boolean hasCycle() { return cycle != null; } 096 public Iterable<Integer> cycle() { return cycle; } 097 098 // certify that digraph is either acyclic or has a directed cycle 099 private boolean check(Digraph G) { 100 if (hasCycle()) { 101 // verify cycle 102 int first = -1, last = -1; 103 for (int v : cycle()) { 104 if (first == -1) first = v; 105 last = v; 106 } 107 if (first != last) { 108 System.err.format("cycle begins with %d and ends with %d\n", first, last); 109 return false; 110 } 111 } 112 return true; 113 } 114 115 public static void main(String[] args) { 116 args = new String[] { "data/tinyDG.txt" }; 117 //args = new String[] { "data/tinyDAG.txt" }; 118 119 In in = new In(args[0]); 120 Digraph G = DigraphGenerator.fromIn(in); 121 G.toGraphviz ("g.png"); 122 123 DirectedCycle finder = new DirectedCycle(G); 124 if (finder.hasCycle()) { 125 //if (finder.hasCycle(G)) { 126 StdOut.print("Cycle: "); 127 for (int v : finder.cycle()) { 128 StdOut.print(v + " "); 129 } 130 StdOut.println(); 131 } else { 132 StdOut.println("No cycle"); 133 } 134 } 135 136}