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