SymbolGraph.java
8.51 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
/******************************************************************************
* Compilation: javac SymbolGraph.java
* Execution: java SymbolGraph filename.txt delimiter
* Dependencies: ST.java Graph.java In.java StdIn.java StdOut.java
* Data files: http://algs4.cs.princeton.edu/41graph/routes.txt
* http://algs4.cs.princeton.edu/41graph/movies.txt
* http://algs4.cs.princeton.edu/41graph/moviestiny.txt
* http://algs4.cs.princeton.edu/41graph/moviesG.txt
* http://algs4.cs.princeton.edu/41graph/moviestopGrossing.txt
*
* % java SymbolGraph routes.txt " "
* JFK
* MCO
* ATL
* ORD
* LAX
* PHX
* LAS
*
* % java SymbolGraph movies.txt "/"
* Tin Men (1987)
* Hershey, Barbara
* Geppi, Cindy
* Jones, Kathy (II)
* Herr, Marcia
* ...
* Blumenfeld, Alan
* DeBoy, David
* Bacon, Kevin
* Woodsman, The (2004)
* Wild Things (1998)
* Where the Truth Lies (2005)
* Tremors (1990)
* ...
* Apollo 13 (1995)
* Animal House (1978)
*
*
* Assumes that input file is encoded using UTF-8.
* % iconv -f ISO-8859-1 -t UTF-8 movies-iso8859.txt > movies.txt
*
******************************************************************************/
package edu.princeton.cs.algs4;
/**
* The {@code SymbolGraph} class represents an undirected graph, where the
* vertex names are arbitrary strings.
* By providing mappings between string vertex names and integers,
* it serves as a wrapper around the
* {@link Graph} data type, which assumes the vertex names are integers
* between 0 and <em>V</em> - 1.
* It also supports initializing a symbol graph from a file.
* <p>
* This implementation uses an {@link ST} to map from strings to integers,
* an array to map from integers to strings, and a {@link Graph} to store
* the underlying graph.
* The <em>indexOf</em> and <em>contains</em> operations take time
* proportional to log <em>V</em>, where <em>V</em> is the number of vertices.
* The <em>nameOf</em> operation takes constant time.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/41graph">Section 4.1</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class SymbolGraph {
private ST<String, Integer> st; // string -> index
private String[] keys; // index -> string
private Graph graph; // the underlying graph
/**
* Initializes a graph from a file using the specified delimiter.
* Each line in the file contains
* the name of a vertex, followed by a list of the names
* of the vertices adjacent to that vertex, separated by the delimiter.
* @param filename the name of the file
* @param delimiter the delimiter between fields
*/
public SymbolGraph(String filename, String delimiter) {
st = new ST<String, Integer>();
// First pass builds the index by reading strings to associate
// distinct strings with an index
In in = new In(filename);
// while (in.hasNextLine()) {
while (!in.isEmpty()) {
String[] a = in.readLine().split(delimiter);
for (int i = 0; i < a.length; i++) {
if (!st.contains(a[i]))
st.put(a[i], st.size());
}
}
StdOut.println("Done reading " + filename);
// inverted index to get string keys in an aray
keys = new String[st.size()];
for (String name : st.keys()) {
keys[st.get(name)] = name;
}
// second pass builds the graph by connecting first vertex on each
// line to all others
graph = new Graph(st.size());
in = new In(filename);
while (in.hasNextLine()) {
String[] a = in.readLine().split(delimiter);
int v = st.get(a[0]);
for (int i = 1; i < a.length; i++) {
int w = st.get(a[i]);
graph.addEdge(v, w);
}
}
}
/**
* Does the graph contain the vertex named {@code s}?
* @param s the name of a vertex
* @return {@code true} if {@code s} is the name of a vertex, and {@code false} otherwise
*/
public boolean contains(String s) {
return st.contains(s);
}
/**
* Returns the integer associated with the vertex named {@code s}.
* @param s the name of a vertex
* @return the integer (between 0 and <em>V</em> - 1) associated with the vertex named {@code s}
* @deprecated Replaced by {@link #indexOf(String)}.
*/
@Deprecated
public int index(String s) {
return st.get(s);
}
/**
* Returns the integer associated with the vertex named {@code s}.
* @param s the name of a vertex
* @return the integer (between 0 and <em>V</em> - 1) associated with the vertex named {@code s}
*/
public int indexOf(String s) {
return st.get(s);
}
/**
* Returns the name of the vertex associated with the integer {@code v}.
* @param v the integer corresponding to a vertex (between 0 and <em>V</em> - 1)
* @return the name of the vertex associated with the integer {@code v}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
* @deprecated Replaced by {@link #nameOf(int)}.
*/
@Deprecated
public String name(int v) {
validateVertex(v);
return keys[v];
}
/**
* Returns the name of the vertex associated with the integer {@code v}.
* @param v the integer corresponding to a vertex (between 0 and <em>V</em> - 1)
* @throws IllegalArgumentException unless {@code 0 <= v < V}
* @return the name of the vertex associated with the integer {@code v}
*/
public String nameOf(int v) {
validateVertex(v);
return keys[v];
}
/**
* Returns the graph assoicated with the symbol graph. It is the client's responsibility
* not to mutate the graph.
* @return the graph associated with the symbol graph
* @deprecated Replaced by {@link #graph()}.
*/
@Deprecated
public Graph G() {
return graph;
}
/**
* Returns the graph assoicated with the symbol graph. It is the client's responsibility
* not to mutate the graph.
* @return the graph associated with the symbol graph
*/
public Graph graph() {
return graph;
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertex(int v) {
int V = graph.V();
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
/**
* Unit tests the {@code SymbolGraph} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String filename = args[0];
String delimiter = args[1];
SymbolGraph sg = new SymbolGraph(filename, delimiter);
Graph graph = sg.graph();
while (StdIn.hasNextLine()) {
String source = StdIn.readLine();
if (sg.contains(source)) {
int s = sg.index(source);
for (int v : graph.adj(s)) {
StdOut.println(" " + sg.name(v));
}
}
else {
StdOut.println("input not contain '" + source + "'");
}
}
}
}
/******************************************************************************
* 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.
******************************************************************************/