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}