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 &Theta;(<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 &Theta;(<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 ******************************************************************************/