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