Source code

001package algs41;
002import stdlib.*;
003import algs13.Stack;
004/* ***********************************************************************
005 *  Compilation:  javac Cycle.java
006 *  Dependencies: Graph.java Stack.java
007 *
008 *  Identifies a cycle.
009 *  Runs in O(E + V) time.
010 *
011 *************************************************************************/
012
013public class Cycle {
014        private boolean[] marked;
015        private int[] edgeTo;
016        private Stack<Integer> cycle;
017
018        public Cycle(Graph G) {
019                if (hasSelfLoop(G)) return;
020                if (hasParallelEdges(G)) return;
021                marked = new boolean[G.V()];
022                edgeTo = new int[G.V()];
023                for (int v = 0; v < G.V(); v++)
024                        if (!marked[v] && hasCycleFrom(G, -1, v))
025                                return;
026        }
027
028        // Assuming there is no self loop or parallel edges, does this graph have a cycle?
029        private boolean hasCycleFromSimple(Graph G, int u, int v) {
030                marked[v] = true; 
031                for (int w : G.adj(v)) {
032                        if (w == u) continue; // skip the back edge: edgeTo[v] = u
033                        if (marked[w]) return true; // been here before
034                        if (hasCycleFromSimple (G, v, w)) return true; // search recursively
035                }
036                return false;
037        }
038
039        // Assuming there is no self loop or parallel edges, does this graph have a cycle?
040        // side effect: initialize cycle field
041        private boolean hasCycleFrom(Graph G, int u, int v) {
042                //StdOut.format ("dfs(%d, %d)\n", u, v);
043                marked[v] = true;
044                edgeTo[v] = u;
045                for (int w : G.adj(v)) {
046                        if (w == u) continue; // skip the back edge
047                        if (marked[w]) {                                
048                                cycle = new Stack<>();
049                                cycle.push(w);
050                                for (int         x = v; x != w; x = edgeTo[x])
051                                        cycle.push(x);
052                                cycle.push(w);
053                                return true;
054                        }
055                        if (hasCycleFrom (G, v, w)) return true;
056                }
057                return false;
058        }
059        private boolean TEXTBOOKhasCycleFrom(Graph G, int u, int v) {
060                marked[v] = true;
061                edgeTo[v] = u;
062                for (int w : G.adj(v)) {
063                        if ((marked[w] && w != u) || (!marked[w] && hasCycleFrom (G, v, w))) {
064                                if (cycle == null) {
065                                        cycle = new Stack<>();
066                                        cycle.push(w);
067                                        for (int x = v; x != w; x = edgeTo[x])
068                                                cycle.push(x);
069                                        cycle.push(w);
070                                }
071                                return true;
072                        }
073                }
074                return false;
075        }
076        // does this graph have a self loop?
077        // side effect: initialize cycle field
078        private boolean hasSelfLoop(Graph G) {
079                for (int v = 0; v < G.V(); v++) {
080                        for (int w : G.adj(v)) {
081                                if (v == w) {
082                                        cycle = new Stack<>();
083                                        cycle.push(v);
084                                        cycle.push(v);
085                                        return true;
086                                }
087                        }
088                }
089                return false;
090        }
091
092        // does this graph have two parallel edges?
093        // side effect: initialize cycle field
094        private boolean hasParallelEdges(Graph G) {
095                for (int v = 0; v < G.V(); v++) {
096                        boolean[] marked = new boolean[G.V()];
097                        for (int w : G.adj(v)) {
098                                if (!marked[w]) {
099                                        marked[w] = true;
100                                } else {
101                                        // edge occurs twice
102                                        cycle = new Stack<>();
103                                        cycle.push(v);
104                                        cycle.push(w);
105                                        cycle.push(v);
106                                        return true;
107                                }
108                        }
109                }
110                return false;
111        }
112
113        public boolean hasCycle()        { return cycle != null; }
114        public Iterable<Integer> cycle() { return cycle;         }
115
116        // test client
117        public static void main(String[] args) {
118                //              args = new String [] { "10", "5" };
119                //              final int V = Integer.parseInt(args[0]);
120                //              final int E = Integer.parseInt(args[1]);
121                //              final Graph G = GraphGenerator.simple(V, E);
122                //              StdOut.println(G);
123
124                //args = new String [] { "data/tinyAG.txt" };
125                args = new String [] { "data/tinyG.txt" };
126                In in = new In(args[0]);
127                Graph G = GraphGenerator.fromIn (in);
128                StdOut.println(G);
129                G.toGraphviz ("g.png");
130
131                Cycle finder = new Cycle(G);
132                if (finder.hasCycle()) {
133                        for (int v : finder.cycle()) {
134                                StdOut.print(v + " ");
135                        }
136                        StdOut.println();
137                }
138                else {
139                        StdOut.println("Graph is acyclic");
140                }
141        }
142
143
144}
145