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}