GraphLite.java

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

/******************************************************************************
 *  Compilation:  javac GraphLite.java
 *  Execution:    java GraphLite
 *  Dependencies: ST.java SET.java StdOut.java
 *
 *  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
 *
 ******************************************************************************/

public class GraphLite {

    // symbol table: key = string vertex, value = set of neighboring vertices
    private ST<String, SET<String>> st;

    // create an empty graph
    public GraphLite() {
        st = new ST<String, SET<String>>();
    }

    // add w to v's set of neighbors, and add v to w's set of neighbors
    public void addEdge(String v, String w) {
        if (!hasVertex(v)) addVertex(v);
        if (!hasVertex(w)) addVertex(w);
        st.get(v).add(w);
        st.get(w).add(v);
    }

    // add a new vertex v with no neighbors (if vertex does not yet exist)
    public void addVertex(String v) {
        if (!hasVertex(v)) st.put(v, new SET<String>());
    }

    // return iterator over all vertices in graph
    public Iterable<String> vertices() {
        return st;
    }

    // return an iterator over the neighbors of vertex v
    public Iterable<String> adjacentTo(String v) {
        if (!hasVertex(v)) return new SET<String>();   // empty set
        return st.get(v);
    }

    // is v a vertex in the graph?
    public boolean hasVertex(String v) {
        return st.contains(v);
    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        for (String v : st) {
            s.append(v + ": ");
            for (String w : st.get(v)) {
                s.append(w + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }


    public static void main(String[] args) {
        GraphLite G = new GraphLite();
        G.addEdge("A", "B");
        G.addEdge("A", "C");
        G.addEdge("C", "D");
        G.addEdge("D", "E");
        G.addEdge("D", "G");
        G.addEdge("E", "G");
        G.addVertex("H");

        // print out graph
        StdOut.println(G);

        // print out graph again by iterating over vertices and edges
        for (String v : G.vertices()) {
            StdOut.print(v + ": ");
            for (String w : G.adjacentTo(v)) {
                StdOut.print(w + " ");
            }
            StdOut.println();
        }

    }

}