001package algs41; 002import stdlib.*; 003import algs13.Queue; 004import algs13.Stack; 005 006/****************************************************************************** 007 * Compilation: javac EulerianPath.java 008 * Execution: java EulerianPath V E 009 * Dependencies: Graph.java Stack.java StdOut.java 010 * 011 * Find an Eulerian path in a graph, if one exists. 012 * 013 ******************************************************************************/ 014 015/** 016 * The {@code EulerianPath} class represents a data type 017 * for finding an Eulerian path in a graph. 018 * An <em>Eulerian path</em> is a path (not necessarily simple) that 019 * uses every edge in the graph exactly once. 020 * <p> 021 * This implementation uses a nonrecursive depth-first search. 022 * The constructor runs in O(<em>E</em> + <em>V</em>) time, 023 * and uses O(<em>E</em> + <em>V</em>) extra space, 024 * where <em>E</em> is the number of edges and <em>V</em> the number of vertices 025 * All other methods take O(1) time. 026 * <p> 027 * To compute Eulerian cycles in graphs, see {@link EulerianCycle}. 028 * To compute Eulerian cycles and paths in digraphs, see 029 * {@link algs42.DirectedEulerianCycle} and {@link algs42.DirectedEulerianPath}. 030 * <p> 031 * For additional documentation, 032 * see <a href="https://algs4.cs.princeton.edu/41graph">Section 4.1</a> of 033 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 034 * 035 * @author Robert Sedgewick 036 * @author Kevin Wayne 037 * @author Nate Liu 038 */ 039public class EulerianPath { 040 private Stack<Integer> path = null; // Eulerian path; null if no suh path 041 042 // an undirected edge, with a field to indicate whether the edge has already been used 043 private static class Edge { 044 private final int v; 045 private final int w; 046 private boolean isUsed; 047 048 public Edge(int v, int w) { 049 this.v = v; 050 this.w = w; 051 isUsed = false; 052 } 053 054 // returns the other vertex of the edge 055 public int other(int vertex) { 056 if (vertex == v) return w; 057 else if (vertex == w) return v; 058 else throw new IllegalArgumentException("Illegal endpoint"); 059 } 060 } 061 062 /** 063 * Computes an Eulerian path in the specified graph, if one exists. 064 * 065 * @param G the graph 066 */ 067 public EulerianPath(Graph G) { 068 069 // find vertex from which to start potential Eulerian path: 070 // a vertex v with odd degree(v) if it exits; 071 // otherwise a vertex with degree(v) > 0 072 int oddDegreeVertices = 0; 073 int s = nonIsolatedVertex(G); 074 for (int v = 0; v < G.V(); v++) { 075 if (G.degree(v) % 2 != 0) { 076 oddDegreeVertices++; 077 s = v; 078 } 079 } 080 081 // graph can't have an Eulerian path 082 // (this condition is needed for correctness) 083 if (oddDegreeVertices > 2) return; 084 085 // special case for graph with zero edges (has a degenerate Eulerian path) 086 if (s == -1) s = 0; 087 088 // create local view of adjacency lists, to iterate one vertex at a time 089 // the helper Edge data type is used to avoid exploring both copies of an edge v-w 090 @SuppressWarnings("unchecked") 091 Queue<Edge>[] adj = new Queue[G.V()]; 092 for (int v = 0; v < G.V(); v++) 093 adj[v] = new Queue<Edge>(); 094 095 for (int v = 0; v < G.V(); v++) { 096 int selfLoops = 0; 097 for (int w : G.adj(v)) { 098 // careful with self loops 099 if (v == w) { 100 if (selfLoops % 2 == 0) { 101 Edge e = new Edge(v, w); 102 adj[v].enqueue(e); 103 adj[w].enqueue(e); 104 } 105 selfLoops++; 106 } 107 else if (v < w) { 108 Edge e = new Edge(v, w); 109 adj[v].enqueue(e); 110 adj[w].enqueue(e); 111 } 112 } 113 } 114 115 // initialize stack with any non-isolated vertex 116 Stack<Integer> stack = new Stack<Integer>(); 117 stack.push(s); 118 119 // greedily search through edges in iterative DFS style 120 path = new Stack<Integer>(); 121 while (!stack.isEmpty()) { 122 int v = stack.pop(); 123 while (!adj[v].isEmpty()) { 124 Edge edge = adj[v].dequeue(); 125 if (edge.isUsed) continue; 126 edge.isUsed = true; 127 stack.push(v); 128 v = edge.other(v); 129 } 130 // push vertex with no more leaving edges to path 131 path.push(v); 132 } 133 134 // check if all edges are used 135 if (path.size() != G.E() + 1) 136 path = null; 137 138 assert certifySolution(G); 139 } 140 141 /** 142 * Returns the sequence of vertices on an Eulerian path. 143 * 144 * @return the sequence of vertices on an Eulerian path; 145 * {@code null} if no such path 146 */ 147 public Iterable<Integer> path() { 148 return path; 149 } 150 151 /** 152 * Returns true if the graph has an Eulerian path. 153 * 154 * @return {@code true} if the graph has an Eulerian path; 155 * {@code false} otherwise 156 */ 157 public boolean hasEulerianPath() { 158 return path != null; 159 } 160 161 162 // returns any non-isolated vertex; -1 if no such vertex 163 private static int nonIsolatedVertex(Graph G) { 164 for (int v = 0; v < G.V(); v++) 165 if (G.degree(v) > 0) 166 return v; 167 return -1; 168 } 169 170 171 /************************************************************************** 172 * 173 * The code below is solely for testing correctness of the data type. 174 * 175 **************************************************************************/ 176 177 // Determines whether a graph has an Eulerian path using necessary 178 // and sufficient conditions (without computing the path itself): 179 // - degree(v) is even for every vertex, except for possibly two 180 // - the graph is connected (ignoring isolated vertices) 181 // This method is solely for unit testing. 182 private static boolean satisfiesNecessaryAndSufficientConditions(Graph G) { 183 if (G.E() == 0) return true; 184 185 // Condition 1: degree(v) is even except for possibly two 186 int oddDegreeVertices = 0; 187 for (int v = 0; v < G.V(); v++) 188 if (G.degree(v) % 2 != 0) 189 oddDegreeVertices++; 190 if (oddDegreeVertices > 2) return false; 191 192 // Condition 2: graph is connected, ignoring isolated vertices 193 int s = nonIsolatedVertex(G); 194 BreadthFirstPaths bfs = new BreadthFirstPaths(G, s); 195 for (int v = 0; v < G.V(); v++) 196 if (G.degree(v) > 0 && !bfs.hasPathTo(v)) 197 return false; 198 199 return true; 200 } 201 202 // check that solution is correct 203 private boolean certifySolution(Graph G) { 204 205 // internal consistency check 206 if (hasEulerianPath() == (path() == null)) return false; 207 208 // hashEulerianPath() returns correct value 209 if (hasEulerianPath() != satisfiesNecessaryAndSufficientConditions(G)) return false; 210 211 // nothing else to check if no Eulerian path 212 if (path == null) return true; 213 214 // check that path() uses correct number of edges 215 if (path.size() != G.E() + 1) return false; 216 217 // check that path() is a path in G 218 // TODO 219 220 return true; 221 } 222 223 private static void unitTest(Graph G, String description) { 224 StdOut.println(description); 225 StdOut.println("-------------------------------------"); 226 StdOut.print(G); 227 228 EulerianPath euler = new EulerianPath(G); 229 230 StdOut.print("Eulerian path: "); 231 if (euler.hasEulerianPath()) { 232 for (int v : euler.path()) { 233 StdOut.print(v + " "); 234 } 235 StdOut.println(); 236 } 237 else { 238 StdOut.println("none"); 239 } 240 StdOut.println(); 241 } 242 243 244 /** 245 * Unit tests the {@code EulerianPath} data type. 246 * 247 * @param args the command-line arguments 248 */ 249 public static void main(String[] args) { 250 int V = Integer.parseInt(args[0]); 251 int E = Integer.parseInt(args[1]); 252 253 254 // Eulerian cycle 255 Graph G1 = GraphGenerator.eulerianCycle(V, E); 256 unitTest(G1, "Eulerian cycle"); 257 258 // Eulerian path 259 Graph G2 = GraphGenerator.eulerianPath(V, E); 260 unitTest(G2, "Eulerian path"); 261 262 // add one random edge 263 Graph G3 = GraphGenerator.copy(G2); 264 G3.addEdge(StdRandom.uniform(V), StdRandom.uniform(V)); 265 unitTest(G3, "one random edge added to Eulerian path"); 266 267 // self loop 268 Graph G4 = new Graph(V); 269 int v4 = StdRandom.uniform(V); 270 G4.addEdge(v4, v4); 271 unitTest(G4, "single self loop"); 272 273 // single edge 274 Graph G5 = new Graph(V); 275 G5.addEdge(StdRandom.uniform(V), StdRandom.uniform(V)); 276 unitTest(G5, "single edge"); 277 278 // empty graph 279 Graph G6 = new Graph(V); 280 unitTest(G6, "empty graph"); 281 282 // random graph 283 Graph G7 = GraphGenerator.simple(V, E); 284 unitTest(G7, "simple graph"); 285 } 286}