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