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}