001// Exercise 4.4.12 (Solution published at http://algs4.cs.princeton.edu/)
002package algs44;
003import stdlib.*;
004import algs13.Stack;
005/* ***********************************************************************
006 *  Compilation:  javac EdgeWeightedDirectedCycle.java
007 *  Execution:    java EdgeWeightedDirectedCycle V E F
008 *  Dependencies: EdgeWeightedDigraph.java DirectedEdge Stack.java
009 *
010 *  Finds a directed cycle in an edge-weighted digraph.
011 *  Runs in O(E + V) time.
012 *
013 *
014 *************************************************************************/
015
016public class EdgeWeightedDirectedCycle {
017        private final boolean[] marked;             // marked[v] = has vertex v been marked?
018        private final DirectedEdge[] edgeTo;        // edgeTo[v] = previous edge on path to v
019        private final boolean[] onStack;            // onStack[v] = is vertex on the stack?
020        private Stack<DirectedEdge> cycle;    // directed cycle (or null if no such cycle)
021
022        public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) {
023                marked  = new boolean[G.V()];
024                onStack = new boolean[G.V()];
025                edgeTo  = new DirectedEdge[G.V()];
026                for (int v = 0; v < G.V(); v++)
027                        if (!marked[v]) dfs(G, v);
028
029                // check that digraph has a cycle
030                assert check(G);
031        }
032
033
034        // check that algorithm computes either the topological order or finds a directed cycle
035        private void dfs(EdgeWeightedDigraph G, int v) {
036                onStack[v] = true;
037                marked[v] = true;
038                for (DirectedEdge e : G.adj(v)) {
039                        int w = e.to();
040
041                        // short circuit if directed cycle found
042                        if (cycle != null) return;
043
044                        //found new vertex, so recur
045                        else if (!marked[w]) {
046                                edgeTo[w] = e;
047                                dfs(G, w);
048                        }
049
050
051                        // trace back directed cycle
052                        else if (onStack[w]) {
053                                cycle = new Stack<>();
054                                while (e.from() != w) {
055                                        cycle.push(e);
056                                        e = edgeTo[e.from()];
057                                }
058                                cycle.push(e);
059                        }
060                }
061
062                onStack[v] = false;
063        }
064
065        public boolean hasCycle()             { return cycle != null;   }
066        public Iterable<DirectedEdge> cycle() { return cycle;           }
067
068
069        // certify that digraph is either acyclic or has a directed cycle
070        private boolean check(EdgeWeightedDigraph G) {
071
072                // edge-weighted digraph is cyclic
073                if (hasCycle()) {
074                        // verify cycle
075                        DirectedEdge first = null, last = null;
076                        for (DirectedEdge e : cycle()) {
077                                if (first == null) first = e;
078                                if (last != null) {
079                                        if (last.to() != e.from()) {
080                                                System.err.format("cycle edges %s and %s not incident\n", last, e);
081                                                return false;
082                                        }
083                                }
084                                last = e;
085                        }
086
087                        if (last.to() != first.from()) {
088                                System.err.format("cycle edges %s and %s not incident\n", last, first);
089                                return false;
090                        }
091                }
092
093
094                return true;
095        }
096
097        public static void main(String[] args) {
098
099                // create random DAG with V vertices and E edges; then add F random edges
100                int V = Integer.parseInt(args[0]);
101                int E = Integer.parseInt(args[1]);
102                int F = Integer.parseInt(args[2]);
103                EdgeWeightedDigraph G = new EdgeWeightedDigraph(V);
104                int[] vertices = new int[V];
105                for (int i = 0; i < V; i++) vertices[i] = i;
106                StdRandom.shuffle(vertices);
107                for (int i = 0; i < E; i++) {
108                        int v, w;
109                        do {
110                                v = StdRandom.uniform(V);
111                                w = StdRandom.uniform(V);
112                        } while (v >= w);
113                        double weight = Math.random();
114                        G.addEdge(new DirectedEdge(v, w, weight));
115                }
116
117                // add F extra edges
118                for (int i = 0; i < F; i++) {
119                        int v = (int) (Math.random() * V);
120                        int w = (int) (Math.random() * V);
121                        double weight = Math.random();
122                        G.addEdge(new DirectedEdge(v, w, weight));
123                }
124
125                StdOut.println(G);
126
127                // find a directed cycle
128                EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
129                if (finder.hasCycle()) {
130                        StdOut.print("Cycle: ");
131                        for (DirectedEdge e : finder.cycle()) {
132                                StdOut.print(e + " ");
133                        }
134                        StdOut.println();
135                }
136
137                // or give topologial sort
138                else {
139                        StdOut.println("No directed cycle");
140                }
141        }
142
143}