// Adapted from Carrano&Savitch, Data Structures and Abstractions With Java
// Providing ways to manually create a graph AND use adjacency list

import java.util.*;

public class Digraph {
    
    private Map verticies; // key-val pairs of (VertexName,Vertex)
                           // each Vertex points to its adjacency list
    private int edgeCount; // number of edges
    
    public Digraph( ) {
	verticies = new LinkedHashMap();  // helps to maintain order in which nodes are created
    }
    
    // Add vertex to map; key is its name; val is the vertex:
    public void addVertex(Object name) { 
	verticies.put(name, new Vertex(name));
    }
    
    // Adds edge assuming source and dest verticies exist:
    public void addEdge(Object source, Object dest, int weight) { 
	Vertex s = (Vertex)verticies.get(source); // get source index
	Vertex d = (Vertex)verticies.get(dest);   // get dest index
	s.addEdge(new Edge(s,d,weight));          // add edge to source's adjacency list
	edgeCount++;
    }
    public void addEdge(Object source, Object dest) {
	addEdge(source,dest,0);
    }

    // Empty graph?
    public boolean isEmpty() {	return verticies.isEmpty(); }

    // Return number of vertices:
    public int getVertexCount() { return verticies.size(); }

    // Return number of edges:
    public int getEdgeCount() { return edgeCount; }

    // Stringify by returning edges with their adjacency lists:
    public String toString() {
	String s = "";
	Iterator it=verticies.keySet().iterator();
	while(it.hasNext()) {
	    Object key = it.next();                    // current vertex label
	    Vertex val = (Vertex) verticies.get(key);  // current Vertex
	    s += "[" + val + "]" + "-->";
	    s += val.getEdges();
	    s += "\n";
	}
	return s;
    }
    
}