Graph.java


Below is the syntax highlighted version of Graph.java from §4.5 Case Study: Small World.


/******************************************************************************
 * Compilation: javac Graph.java
 * Execution: java Graph < input.txt
 * Dependencies: ST.java SET.java In.java StdOut.java
 * Data files: https://introcs.cs.princeton.edu/java/45graph/tinyGraph.txt
 *
 * Undirected graph data type implemented using a symbol table
 * whose keys are vertices (String) and whose values are sets
 * of neighbors (SET of Strings).
 *
 * Remarks
 * -------
 * - Parallel edges are not allowed
 * - Self-loop are allowed
 * - Adjacency lists store many different copies of the same
 * String. You can use less memory by interning the strings.
 *
 * % java Graph < tinyGraph.txt
 * A: B C G H
 * B: A C H
 * C: A B G
 * G: A C
 * H: A B
 *
 * A: B C G H
 * B: A C H
 * C: A B G
 * G: A C
 * H: A B
 *
 ******************************************************************************/
/**
 * The {@code Graph} class represents an undirected graph of vertices
 * with string names.
 * It supports the following operations: add an edge, add a vertex,
 * get all the vertices, iterate over all the neighbors adjacent
 * to a vertex, is there a vertex, is there an edge between two vertices.
 * Self-loops are permitted; parallel edges are discarded.
 * <p>
 * For additional documentation,
 * see <ahref="https://introcs.cs.princeton.edu/45graph">Section 4.5</a> of
 * <i>Computer Science: An Interdisciplinary Approach</i>
 * by Robert Sedgewick and Kevin Wayne.
 */
publicclassGraph{
// symbol table: key = string vertex, value = set of neighboring vertices
privateST<String, SET<String>> st;
// number of edges
privateint E;
/**
 * Initializes an empty graph with no vertices or edges.
 */
publicGraph(){
 st =new ST<String, SET<String>>();
}
/**
 * Initializes a graph from the specified file, using the specified delimiter.
 *
 * @param filename the name of the file
 * @param delimiter the delimiter
 */
publicGraph(String filename,String delimiter){
 st =new ST<String, SET<String>>();
In in =newIn(filename);
while(in.hasNextLine()){
String line = in.readLine();
 String[] names = line.split(delimiter);
for(int i =1; i < names.length; i++){
addEdge(names[0], names[i]);
}
}
}
/**
 * Returns the number of vertices in this graph.
 *
 * @return the number of vertices in this graph
 */
publicintV(){
return st.size();
}
/**
 * Returns the number of edges in this graph.
 *
 * @return the number of edges in this graph
 */
publicintE(){
return E;
}
// throw an exception if v is not a vertex
privatevoidvalidateVertex(String v){
if(!hasVertex(v))thrownewIllegalArgumentException(v +" is not a vertex");
}
/**
 * Returns the degree of vertex v in this graph.
 *
 * @param v the vertex
 * @return the degree of {@code v} in this graph
 * @throws IllegalArgumentException if {@code v} is not a vertex in this graph
 */
publicintdegree(String v){
validateVertex(v);
return st.get(v).size();
}
/**
 * Adds the edge v-w to this graph (if it is not already an edge).
 *
 * @param v one vertex in the edge
 * @param w the other vertex in the edge
 */
publicvoidaddEdge(String v,String w){
if(!hasVertex(v))addVertex(v);
if(!hasVertex(w))addVertex(w);
if(!hasEdge(v, w)) E++;
 st.get(v).add(w);
 st.get(w).add(v);
}
/**
 * Adds vertex v to this graph (if it is not already a vertex).
 *
 * @param v the vertex
 */
publicvoidaddVertex(String v){
if(!hasVertex(v)) st.put(v,new SET<String>());
}
/**
 * Returns the vertices in this graph.
 *
 * @return the set of vertices in this graph
 */
publicIterable<String>vertices(){
return st.keys();
}
/**
 * Returns the set of vertices adjacent to v in this graph.
 *
 * @param v the vertex
 * @return the set of vertices adjacent to vertex {@code v} in this graph
 * @throws IllegalArgumentException if {@code v} is not a vertex in this graph
 */
publicIterable<String>adjacentTo(String v){
validateVertex(v);
return st.get(v);
}
/**
 * Returns true if v is a vertex in this graph.
 *
 * @param v the vertex
 * @return {@code true} if {@code v} is a vertex in this graph,
 * {@code false} otherwise
 */
publicbooleanhasVertex(String v){
return st.contains(v);
}
/**
 * Returns true if v-w is an edge in this graph.
 *
 * @param v one vertex in the edge
 * @param w the other vertex in the edge
 * @return {@code true} if {@code v-w} is a vertex in this graph,
 * {@code false} otherwise
 * @throws IllegalArgumentException if either {@code v} or {@code w}
 * is not a vertex in this graph
 */
publicbooleanhasEdge(String v,String w){
validateVertex(v);
validateVertex(w);
return st.get(v).contains(w);
}
/**
 * Returns a string representation of this graph.
 *
 * @return string representation of this graph
 */
publicStringtoString(){
StringBuilder s =newStringBuilder();
for(String v : st){
 s.append(v +": ");
for(String w : st.get(v)){
 s.append(w +" ");
}
 s.append('\n');
}
return s.toString();
}
/**
 * Unit tests the {@code Graph} data type.
 *
 * @param args the command-line arguments
 */
publicstaticvoidmain(String[] args){
// create graph
Graph graph =newGraph();
while(!StdIn.isEmpty()){
String v = StdIn.readString();
String w = StdIn.readString();
 graph.addEdge(v, w);
}
// print out graph
 StdOut.println(graph);
// print out graph again by iterating over vertices and edges
for(String v : graph.vertices()){
 StdOut.print(v +": ");
for(String w : graph.adjacentTo(v)){
 StdOut.print(w +" ");
}
 StdOut.println();
}
}
}

AltStyle によって変換されたページ (->オリジナル) /


Copyright © 2000–2022, Robert Sedgewick and Kevin Wayne.
Last updated: Sat Nov 26 11:29:53 EST 2022.