/******************************************************************************
 *  Compilation:  javac Digraph.java
 *  Execution:    java Digraph
 *  Dependencies: ST.java SET.java StdOut.java
 *
 *  Directed graph data type implemented using a symbol table
 *  whose keys are strings and whose values are sets of strings.
 *
 ******************************************************************************/

public class Digraph {

    // symbol table of linked lists
    private ST<String, SET<String>> st;

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

    // add v to w's list of neighbors; self-loops allowed
    public void addEdge(String v, String w) {
        if (!st.contains(v)) addVertex(v);
        if (!st.contains(w)) addVertex(w);
        st.get(v).add(w);
    }

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

    // return the degree of vertex v
    public int degree(String v) {
        if (!st.contains(v)) return 0;
        else                 return st.get(v).size();
    }

    // return the array of vertices incident to v
    public Iterable<String> adjacentTo(String v) {
        if (!st.contains(v)) return new SET<String>();
        else                 return st.get(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) {
        Digraph G = new Digraph();
        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");
        StdOut.println(G);
    }

}