DirectedEulerianCycle.java
9.24 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
/******************************************************************************
* Compilation: javac DirectedEulerianCycle.java
* Execution: java DirectedEulerianCycle V E
* Dependencies: Digraph.java Stack.java StdOut.java
* BreadthFirstPaths.java
* DigraphGenerator.java StdRandom.java
*
* Find an Eulerian cycle in a digraph, if one exists.
*
******************************************************************************/
package edu.princeton.cs.algs4;
import java.util.Iterator;
/**
* The {@code DirectedEulerianCycle} class represents a data type
* for finding an Eulerian cycle or path in a digraph.
* An <em>Eulerian cycle</em> is a cycle (not necessarily simple) that
* uses every edge in the digraph exactly once.
* <p>
* This implementation uses a nonrecursive depth-first search.
* The constructor runs in O(<Em>E</em> + <em>V</em>) time,
* and uses O(<em>V</em>) extra space, where <em>E</em> is the
* number of edges and <em>V</em> the number of vertices
* All other methods take O(1) time.
* <p>
* To compute Eulerian paths in digraphs, see {@link DirectedEulerianPath}.
* To compute Eulerian cycles and paths in undirected graphs, see
* {@link EulerianCycle} and {@link EulerianPath}.
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
* @author Nate Liu
*/
public class DirectedEulerianCycle {
private Stack<Integer> cycle = null; // Eulerian cycle; null if no such cylce
/**
* Computes an Eulerian cycle in the specified digraph, if one exists.
*
* @param G the digraph
*/
public DirectedEulerianCycle(Digraph G) {
// must have at least one edge
if (G.E() == 0) return;
// necessary condition: indegree(v) = outdegree(v) for each vertex v
// (without this check, DFS might return a path instead of a cycle)
for (int v = 0; v < G.V(); v++)
if (G.outdegree(v) != G.indegree(v))
return;
// create local view of adjacency lists, to iterate one vertex at a time
Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];
for (int v = 0; v < G.V(); v++)
adj[v] = G.adj(v).iterator();
// initialize stack with any non-isolated vertex
int s = nonIsolatedVertex(G);
Stack<Integer> stack = new Stack<Integer>();
stack.push(s);
// greedily add to putative cycle, depth-first search style
cycle = new Stack<Integer>();
while (!stack.isEmpty()) {
int v = stack.pop();
while (adj[v].hasNext()) {
stack.push(v);
v = adj[v].next();
}
// add vertex with no more leaving edges to cycle
cycle.push(v);
}
// check if all edges have been used
// (in case there are two or more vertex-disjoint Eulerian cycles)
if (cycle.size() != G.E() + 1)
cycle = null;
assert certifySolution(G);
}
/**
* Returns the sequence of vertices on an Eulerian cycle.
*
* @return the sequence of vertices on an Eulerian cycle;
* {@code null} if no such cycle
*/
public Iterable<Integer> cycle() {
return cycle;
}
/**
* Returns true if the digraph has an Eulerian cycle.
*
* @return {@code true} if the digraph has an Eulerian cycle;
* {@code false} otherwise
*/
public boolean hasEulerianCycle() {
return cycle != null;
}
// returns any non-isolated vertex; -1 if no such vertex
private static int nonIsolatedVertex(Digraph G) {
for (int v = 0; v < G.V(); v++)
if (G.outdegree(v) > 0)
return v;
return -1;
}
/**************************************************************************
*
* The code below is solely for testing correctness of the data type.
*
**************************************************************************/
// Determines whether a digraph has an Eulerian cycle using necessary
// and sufficient conditions (without computing the cycle itself):
// - at least one edge
// - indegree(v) = outdegree(v) for every vertex
// - the graph is connected, when viewed as an undirected graph
// (ignoring isolated vertices)
private static boolean hasEulerianCycle(Digraph G) {
// Condition 0: at least 1 edge
if (G.E() == 0) return false;
// Condition 1: indegree(v) == outdegree(v) for every vertex
for (int v = 0; v < G.V(); v++)
if (G.outdegree(v) != G.indegree(v))
return false;
// Condition 2: graph is connected, ignoring isolated vertices
Graph H = new Graph(G.V());
for (int v = 0; v < G.V(); v++)
for (int w : G.adj(v))
H.addEdge(v, w);
// check that all non-isolated vertices are conneted
int s = nonIsolatedVertex(G);
BreadthFirstPaths bfs = new BreadthFirstPaths(H, s);
for (int v = 0; v < G.V(); v++)
if (H.degree(v) > 0 && !bfs.hasPathTo(v))
return false;
return true;
}
// check that solution is correct
private boolean certifySolution(Digraph G) {
// internal consistency check
if (hasEulerianCycle() == (cycle() == null)) return false;
// hashEulerianCycle() returns correct value
if (hasEulerianCycle() != hasEulerianCycle(G)) return false;
// nothing else to check if no Eulerian cycle
if (cycle == null) return true;
// check that cycle() uses correct number of edges
if (cycle.size() != G.E() + 1) return false;
// check that cycle() is a directed cycle of G
// TODO
return true;
}
private static void unitTest(Digraph G, String description) {
StdOut.println(description);
StdOut.println("-------------------------------------");
StdOut.print(G);
DirectedEulerianCycle euler = new DirectedEulerianCycle(G);
StdOut.print("Eulerian cycle: ");
if (euler.hasEulerianCycle()) {
for (int v : euler.cycle()) {
StdOut.print(v + " ");
}
StdOut.println();
}
else {
StdOut.println("none");
}
StdOut.println();
}
/**
* Unit tests the {@code DirectedEulerianCycle} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
// Eulerian cycle
Digraph G1 = DigraphGenerator.eulerianCycle(V, E);
unitTest(G1, "Eulerian cycle");
// Eulerian path
Digraph G2 = DigraphGenerator.eulerianPath(V, E);
unitTest(G2, "Eulerian path");
// empty digraph
Digraph G3 = new Digraph(V);
unitTest(G3, "empty digraph");
// self loop
Digraph G4 = new Digraph(V);
int v4 = StdRandom.uniform(V);
G4.addEdge(v4, v4);
unitTest(G4, "single self loop");
// union of two disjoint cycles
Digraph H1 = DigraphGenerator.eulerianCycle(V/2, E/2);
Digraph H2 = DigraphGenerator.eulerianCycle(V - V/2, E - E/2);
int[] perm = new int[V];
for (int i = 0; i < V; i++)
perm[i] = i;
StdRandom.shuffle(perm);
Digraph G5 = new Digraph(V);
for (int v = 0; v < H1.V(); v++)
for (int w : H1.adj(v))
G5.addEdge(perm[v], perm[w]);
for (int v = 0; v < H2.V(); v++)
for (int w : H2.adj(v))
G5.addEdge(perm[V/2 + v], perm[V/2 + w]);
unitTest(G5, "Union of two disjoint cycles");
// random digraph
Digraph G6 = DigraphGenerator.simple(V, E);
unitTest(G6, "simple digraph");
// 4-vertex digraph
Digraph G7 = new Digraph(new In("eulerianD.txt"));
unitTest(G7, "4-vertex Eulerian digraph");
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/