SymbolDigraph.java
7.47 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
/******************************************************************************
* Compilation: javac SymbolDigraph.java
* Execution: java SymbolDigraph
* Dependencies: ST.java Digraph.java In.java
* Data files: http://algs4.cs.princeton.edu/42digraph/routes.txt
*
* % java SymbolDigraph routes.txt " "
* JFK
* MCO
* ATL
* ORD
* ATL
* HOU
* MCO
* LAX
*
******************************************************************************/
package edu.princeton.cs.algs4;
/**
* The {@code SymbolDigraph} class represents a digraph, where the
* vertex names are arbitrary strings.
* By providing mappings between string vertex names and integers,
* it serves as a wrapper around the
* {@link Digraph} data type, which assumes the vertex names are integers
* between 0 and <em>V</em> - 1.
* It also supports initializing a symbol digraph 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 Digraph} 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/42digraph">Section 4.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class SymbolDigraph {
private ST<String, Integer> st; // string -> index
private String[] keys; // index -> string
private Digraph graph; // the underlying digraph
/**
* Initializes a digraph 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 SymbolDigraph(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()) {
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());
}
}
// 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 digraph by connecting first vertex on each
// line to all others
graph = new Digraph(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 digraph 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)
* @return the name of the vertex associated with the integer {@code v}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public String nameOf(int v) {
validateVertex(v);
return keys[v];
}
/**
* Returns the digraph assoicated with the symbol graph. It is the client's responsibility
* not to mutate the digraph.
*
* @return the digraph associated with the symbol digraph
* @deprecated Replaced by {@link #digraph()}.
*/
@Deprecated
public Digraph G() {
return graph;
}
/**
* Returns the digraph assoicated with the symbol graph. It is the client's responsibility
* not to mutate the digraph.
*
* @return the digraph associated with the symbol digraph
*/
public Digraph digraph() {
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 SymbolDigraph} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String filename = args[0];
String delimiter = args[1];
SymbolDigraph sg = new SymbolDigraph(filename, delimiter);
Digraph graph = sg.digraph();
while (!StdIn.isEmpty()) {
String t = StdIn.readLine();
for (int v : graph.adj(sg.index(t))) {
StdOut.println(" " + sg.name(v));
}
}
}
}
/******************************************************************************
* 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.
******************************************************************************/