001/****************************************************************************** 002 * Compilation: javac DirectedEulerianCycle.java 003 * Execution: java DirectedEulerianCycle V E 004 * Dependencies: Digraph.java Stack.java StdOut.java 005 * BreadthFirstPaths.java 006 * DigraphGenerator.java StdRandom.java 007 * 008 * Find an Eulerian cycle in a digraph, if one exists. 009 * 010 ******************************************************************************/ 011 012package algs42; 013import algs13.Stack; 014import algs41.BreadthFirstPaths; 015import algs41.Graph; 016import stdlib.*; 017import java.util.Iterator; 018 019/** 020 * The {@code DirectedEulerianCycle} class represents a data type 021 * for finding an Eulerian cycle or path in a digraph. 022 * An <em>Eulerian cycle</em> is a cycle (not necessarily simple) that 023 * uses every edge in the digraph exactly once. 024 * <p> 025 * This implementation uses a nonrecursive depth-first search. 026 * The constructor takes Θ(<em>E</em> + <em>V</em>) time in the worst 027 * case, where <em>E</em> is the number of edges and <em>V</em> is the 028 * number of vertices 029 * Each instance method takes Θ(1) time. 030 * It uses Θ(<em>V</em>) extra space (not including the digraph). 031 * <p> 032 * To compute Eulerian paths in digraphs, see {@link DirectedEulerianPath}. 033 * To compute Eulerian cycles and paths in undirected graphs, see 034 * {@link algs41.EulerianCycle} and {@link algs41.EulerianPath}. 035 * <p> 036 * For additional documentation, 037 * see <a href="https://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of 038 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 039 * 040 * @author Robert Sedgewick 041 * @author Kevin Wayne 042 * @author Nate Liu 043 */ 044public class DirectedEulerianCycle { 045 private Stack<Integer> cycle = null; // Eulerian cycle; null if no such cylce 046 047 /** 048 * Computes an Eulerian cycle in the specified digraph, if one exists. 049 * 050 * @param G the digraph 051 */ 052 public DirectedEulerianCycle(Digraph G) { 053 054 // must have at least one edge 055 if (G.E() == 0) return; 056 057 // necessary condition: indegree(v) = outdegree(v) for each vertex v 058 // (without this check, DFS might return a path instead of a cycle) 059 for (int v = 0; v < G.V(); v++) 060 if (G.outdegree(v) != G.indegree(v)) 061 return; 062 063 // create local view of adjacency lists, to iterate one vertex at a time 064 @SuppressWarnings("unchecked") 065 Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()]; 066 for (int v = 0; v < G.V(); v++) 067 adj[v] = G.adj(v).iterator(); 068 069 // initialize stack with any non-isolated vertex 070 int s = nonIsolatedVertex(G); 071 Stack<Integer> stack = new Stack<Integer>(); 072 stack.push(s); 073 074 // greedily add to putative cycle, depth-first search style 075 cycle = new Stack<Integer>(); 076 while (!stack.isEmpty()) { 077 int v = stack.pop(); 078 while (adj[v].hasNext()) { 079 stack.push(v); 080 v = adj[v].next(); 081 } 082 // add vertex with no more leaving edges to cycle 083 cycle.push(v); 084 } 085 086 // check if all edges have been used 087 // (in case there are two or more vertex-disjoint Eulerian cycles) 088 if (cycle.size() != G.E() + 1) 089 cycle = null; 090 091 assert certifySolution(G); 092 } 093 094 /** 095 * Returns the sequence of vertices on an Eulerian cycle. 096 * 097 * @return the sequence of vertices on an Eulerian cycle; 098 * {@code null} if no such cycle 099 */ 100 public Iterable<Integer> cycle() { 101 return cycle; 102 } 103 104 /** 105 * Returns true if the digraph has an Eulerian cycle. 106 * 107 * @return {@code true} if the digraph has an Eulerian cycle; 108 * {@code false} otherwise 109 */ 110 public boolean hasEulerianCycle() { 111 return cycle != null; 112 } 113 114 // returns any non-isolated vertex; -1 if no such vertex 115 private static int nonIsolatedVertex(Digraph G) { 116 for (int v = 0; v < G.V(); v++) 117 if (G.outdegree(v) > 0) 118 return v; 119 return -1; 120 } 121 122 123 /************************************************************************** 124 * 125 * The code below is solely for testing correctness of the data type. 126 * 127 **************************************************************************/ 128 129 // Determines whether a digraph has an Eulerian cycle using necessary 130 // and sufficient conditions (without computing the cycle itself): 131 // - at least one edge 132 // - indegree(v) = outdegree(v) for every vertex 133 // - the graph is connected, when viewed as an undirected graph 134 // (ignoring isolated vertices) 135 private static boolean satisfiesNecessaryAndSufficientConditions(Digraph G) { 136 137 // Condition 0: at least 1 edge 138 if (G.E() == 0) return false; 139 140 // Condition 1: indegree(v) == outdegree(v) for every vertex 141 for (int v = 0; v < G.V(); v++) 142 if (G.outdegree(v) != G.indegree(v)) 143 return false; 144 145 // Condition 2: graph is connected, ignoring isolated vertices 146 Graph H = new Graph(G.V()); 147 for (int v = 0; v < G.V(); v++) 148 for (int w : G.adj(v)) 149 H.addEdge(v, w); 150 151 // check that all non-isolated vertices are conneted 152 int s = nonIsolatedVertex(G); 153 BreadthFirstPaths bfs = new BreadthFirstPaths(H, s); 154 for (int v = 0; v < G.V(); v++) 155 if (H.degree(v) > 0 && !bfs.hasPathTo(v)) 156 return false; 157 158 return true; 159 } 160 161 // check that solution is correct 162 private boolean certifySolution(Digraph G) { 163 164 // internal consistency check 165 if (hasEulerianCycle() == (cycle() == null)) return false; 166 167 // hashEulerianCycle() returns correct value 168 if (hasEulerianCycle() != satisfiesNecessaryAndSufficientConditions(G)) return false; 169 170 // nothing else to check if no Eulerian cycle 171 if (cycle == null) return true; 172 173 // check that cycle() uses correct number of edges 174 if (cycle.size() != G.E() + 1) return false; 175 176 // check that cycle() is a directed cycle of G 177 // TODO 178 179 return true; 180 } 181 182 183 private static void unitTest(Digraph G, String description) { 184 StdOut.println(description); 185 StdOut.println("-------------------------------------"); 186 StdOut.print(G); 187 188 DirectedEulerianCycle euler = new DirectedEulerianCycle(G); 189 190 StdOut.print("Eulerian cycle: "); 191 if (euler.hasEulerianCycle()) { 192 for (int v : euler.cycle()) { 193 StdOut.print(v + " "); 194 } 195 StdOut.println(); 196 } 197 else { 198 StdOut.println("none"); 199 } 200 StdOut.println(); 201 } 202 203 204 /** 205 * Unit tests the {@code DirectedEulerianCycle} data type. 206 * 207 * @param args the command-line arguments 208 */ 209 public static void main(String[] args) { 210 int V = Integer.parseInt(args[0]); 211 int E = Integer.parseInt(args[1]); 212 213 // Eulerian cycle 214 Digraph G1 = DigraphGenerator.eulerianCycle(V, E); 215 unitTest(G1, "Eulerian cycle"); 216 217 // Eulerian path 218 Digraph G2 = DigraphGenerator.eulerianPath(V, E); 219 unitTest(G2, "Eulerian path"); 220 221 // empty digraph 222 Digraph G3 = new Digraph(V); 223 unitTest(G3, "empty digraph"); 224 225 // self loop 226 Digraph G4 = new Digraph(V); 227 int v4 = StdRandom.uniform(V); 228 G4.addEdge(v4, v4); 229 unitTest(G4, "single self loop"); 230 231 // union of two disjoint cycles 232 Digraph H1 = DigraphGenerator.eulerianCycle(V/2, E/2); 233 Digraph H2 = DigraphGenerator.eulerianCycle(V - V/2, E - E/2); 234 int[] perm = new int[V]; 235 for (int i = 0; i < V; i++) 236 perm[i] = i; 237 StdRandom.shuffle(perm); 238 Digraph G5 = new Digraph(V); 239 for (int v = 0; v < H1.V(); v++) 240 for (int w : H1.adj(v)) 241 G5.addEdge(perm[v], perm[w]); 242 for (int v = 0; v < H2.V(); v++) 243 for (int w : H2.adj(v)) 244 G5.addEdge(perm[V/2 + v], perm[V/2 + w]); 245 unitTest(G5, "Union of two disjoint cycles"); 246 247 // random digraph 248 Digraph G6 = DigraphGenerator.simple(V, E); 249 unitTest(G6, "simple digraph"); 250 251// // 4-vertex digraph 252// Digraph G7 = new Digraph(new In("eulerianD.txt")); 253// unitTest(G7, "4-vertex Eulerian digraph"); 254 } 255 256} 257 258/****************************************************************************** 259 * Copyright 2002-2020, Robert Sedgewick and Kevin Wayne. 260 * 261 * This file is part of algs4.jar, which accompanies the textbook 262 * 263 * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, 264 * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. 265 * http://algs4.cs.princeton.edu 266 * 267 * 268 * algs4.jar is free software: you can redistribute it and/or modify 269 * it under the terms of the GNU General Public License as published by 270 * the Free Software Foundation, either version 3 of the License, or 271 * (at your option) any later version. 272 * 273 * algs4.jar is distributed in the hope that it will be useful, 274 * but WITHOUT ANY WARRANTY; without even the implied warranty of 275 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 276 * GNU General Public License for more details. 277 * 278 * You should have received a copy of the GNU General Public License 279 * along with algs4.jar. If not, see http://www.gnu.org/licenses. 280 ******************************************************************************/