/*
 *  ==============================================================
 *  Compilation:  javac Graph.java
 *  Dependencies: SymbolTable.java AdjList.java
 *  
 *  Undirected graph data type implemented using a symbol table of
 *  vertices, where each vertex contains a list of its neighbors.
 *
 *  Limitations
 *  -----------
 *   - addEdgE(v, v) adds two copies of the self-loop v-v
 *   - the adjacency lists use independent copies of each string,
 *     which wastes memory
 *  ==============================================================
 */

public class Graph {

    // Symbol table of linked lists

    private SymbolTable st = new SymbolTable();

    // Add v to w's list of neighbors and w to v's list of neighbors
    // parallel edges allowed

    public void addEdge(String v, String w) {

        if (st.get(v) == null) addVertex(v);
        if (st.get(w) == null) addVertex(w);
        AdjList vlist = (AdjList) st.get(v);
        AdjList wlist = (AdjList) st.get(w);
        vlist.insert(w);
        wlist.insert(v);
    }

    // Add a new vertex v with no neighbors if vertex does not yet exist

    public void addVertex( String v ) {
        if ( st.get( v ) == null)
             st.put( v, new AdjList() );
    }

    // Return the degree of vertex v

    public int degree( String v ) {

        AdjList adjlist = (AdjList) st.get(v);
        if (adjlist == null)
            return 0;
        else
            return adjlist.size();
    }

    // Return the array of vertices incident to v

    public String[] neighbors( String v ) {
        AdjList adjlist = (AdjList) st.get(v);
        if (adjlist == null)
            return new String[0];
        else 
            return adjlist.toArray();
    }

    // Not very efficient, intended for debugging only

    public String toString() {

        String s = "\n";
        String[] vertices = st.keys();
        for (int v = 0; v < vertices.length; v++) {
            AdjList adjlist = (AdjList) st.get(vertices[v]);
            s += vertices[v] + ": " + adjlist + "\n";
        }
        return s;
    }

    public static void main(String[] args) {

        // Build graph of DC Metro System .....

        Graph G = new Graph();
        G.addEdge(        "College Park",          "Fort Totten");
        G.addEdge(           "Greenbelt",         "College Park");
        G.addEdge(         "Fort Totten",        "Silver Spring");
        G.addEdge(         "Fort Totten",  "Catholic University");
        G.addEdge( "Catholic University",    "Union Station");
        G.addEdge(   "Judiciary Sq",    "Union Station");
        G.addEdge(   "Judiciary Sq",      "Fort Totten");
        G.addEdge(   "Judiciary Sq",     "Metro Center");
        G.addEdge(   "Judiciary Sq", "National Airport");
        G.addEdge(  "DuPont Circle",     "Metro Center");

        // Build graph of DC Metro System .....

        System.out.println();
        System.out.println("Simple Model of DC Metro System");
        System.out.println("===============================");
        System.out.println( G.toString() );

        // Run breadth first search

        System.out.println();
        System.out.println("Source: College Park");
        System.out.println("Destination: Union Station");
        System.out.println("==========================");

        BFSearcher bfs1 = new BFSearcher(G, "Union Station");
        bfs1.showPath("College Park");

        System.out.println();
        System.out.println("Source: College Park");
        System.out.println("Destination: National Airport");
        System.out.println("=============================");

        BFSearcher bfs2 = new BFSearcher(G, "National Airport");
        bfs2.showPath("College Park");
    }
}