// modifications from Spring 2003 to handle topo sort
// 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 LinkedList labels; // Vertex Names (for topo sort)
    private int edgeCount; // number of edges
    
    public Digraph( ) {
	verticies = new LinkedHashMap();  // helps to maintain order in which nodes are created
	labels = new LinkedList();
    }
    
    // Add vertex to map; key is its name; val is the vertex:
    public void addVertex(Object name) { 
	verticies.put(name, new Vertex(name));
	labels.addFirst(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
	d.setPrev(s);
	s.setOutDegree(1+s.getOutDegree());
	d.setInDegree(1+d.getInDegree());
	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;
    }
 
    // Want vertex iterator to do things to each Vertex in hashtable:
    public Iterator getVertexIterator() {
	return verticies.values().iterator();
    }

    // Check if graph is cyclic:
    public boolean isCyclic() {

	// copy verticies and vertex labels:
	LinkedHashMap verticies = new LinkedHashMap(this.verticies);
	LinkedList labels = new LinkedList(this.labels);

	// topo-sorted labels:
	LinkedList topolist = toposort(verticies, labels);
	System.out.println(topolist);

	// could actually use result from removeFreeVertex to test, but
	// let's see if topo sort actually worked:
	if (topolist.size() == this.verticies.size()) return true;
	return false;
    }    

    // Topological sort returns sorted list of verticies:
    public LinkedList toposort(Map verticies, LinkedList labels) {
	LinkedList topolabels = new LinkedList();
	// iterate over ALL verticies to sort each one:
	for (int i=0; i < verticies.size() && removeFreeVertex(verticies, labels, topolabels); i++);
	return topolabels;
    }

    // Search for ONE "free" vertex to delete (see C&S 29.14):
    // - try to find a vertex with no dest
    // - delete it if found and return true
    // - otherwise, nothing found, so return false
    private boolean removeFreeVertex(Map verticies, LinkedList labels, LinkedList topolabels) {
	int count;
	for (count = 0; count < verticies.size(); count++) {
	    String vertexName = (String) labels.getFirst(); 
	    Vertex vertex = (Vertex) verticies.get(vertexName); 
	    System.out.println(vertexName);
	    if (vertex.getOutDegree() == 0) {

		// must decrease OutDegree for all Source vertices
		// creates simulation of deleting the current vertex from graph
		// look for all sources for this current vertex:
		for (int i = 0; i < labels.size(); i++) {
		    Vertex testVertex = (Vertex) verticies.get(labels.get(i)); // get each vertex

		    if (!testVertex.equals(vertex)) { // just being safe (OutDegree should take care of this)

			if (testVertex.equals(vertex.getPrev())) // look at each source for current vertex
			    testVertex.setOutDegree(testVertex.getOutDegree()-1);
		    }
		}
		// verticies.remove(vertexName);
		labels.remove(vertexName);
		topolabels.addFirst(vertexName);
		return true;
	    }
	    labels.remove(vertexName);
	}
	if (count == 0) return true; // iterated thru all verticies, so OK
	return false;
    }

    public void resetVerticies() {
	for (Iterator vi = getVertexIterator() ; vi.hasNext() ; ) {
	    Vertex v = (Vertex) vi.next();
	    v.unvisit();
	    v.setCost(0);
	    v.setPrev(null);
	}
    }

    public SeqStructure getBFS(Object origin) {
	
	resetVerticies();
	SeqStructure toDo = new QueueAsList();
	SeqStructure path = new QueueAsList();
	 
	Vertex originVertex = (Vertex)verticies.get(origin);
	originVertex.visit();
	toDo.put(originVertex);
	path.put(originVertex);

	while(!toDo.isEmpty()) {
	    Vertex currentVertex = (Vertex)toDo.get();

	    for (Iterator edges = currentVertex.getEdgeIterator(); edges.hasNext(); ) {
		Edge currentEdge = (Edge) edges.next();
		Vertex nextVertex = currentEdge.getDest();
		
		if(!nextVertex.isVisited()) {
		    nextVertex.visit();
		    toDo.put(nextVertex);
		    path.put(nextVertex);
		}
	    }

	}
	
	return path;

    }
   
    public SeqStructure getDFS(Object origin) {
	
	resetVerticies();
	SeqStructure toDo = new StackAsList();
	SeqStructure path = new QueueAsList();
	 
	Vertex originVertex = (Vertex)verticies.get(origin);
	originVertex.visit();
	toDo.put(originVertex);
	path.put(originVertex);

	while(!toDo.isEmpty()) {
	    // take top of stack, but might have to put it back if it terminates:
	    Vertex currentVertex = (Vertex)toDo.get();

	    // try to find unvisited neighbor:
	    Iterator edges = currentVertex.getEdgeIterator();
	    boolean found = false;
	    Vertex nextVertex = null;
	    while (!found && edges.hasNext()) {
		Edge currentEdge = (Edge) edges.next();
		Vertex trialVertex = currentEdge.getDest();
		if(!trialVertex.isVisited()) {
		    found = true;
		    nextVertex = trialVertex;
		}
	    }
	    
	    // unvisited vertex found! visit vertex and record doing so:
	    // otherwise, we leave currentVertex removed from stack because it had no unvisited neighbors
	    if (nextVertex != null) {
		toDo.put(currentVertex); // put currentVertex back because path didn't terminate here
		nextVertex.visit();
		toDo.put(nextVertex); // next node to process
		path.put(nextVertex); // save path
	    }
	}

	return path;

    }

    public boolean search(Object o) {
	if (verticies.get(o)==null)
	    return false;
	return true;
    }
	
    public SeqStructure unweightedShortestPath(Object origin,Object end) {
	
	resetVerticies();
	boolean done = false;
	SeqStructure toDo = new QueueAsList();
	SeqStructure path = new StackAsList();
	
	Vertex originVertex = (Vertex)verticies.get(origin);
	Vertex endVertex = (Vertex)verticies.get(end);
	originVertex.visit();
	toDo.put(originVertex);

	while(!done && !toDo.isEmpty()) {
	    Vertex currentVertex = (Vertex)toDo.get();

	    for (Iterator edges = currentVertex.getEdgeIterator(); !done && edges.hasNext(); ) {
		Edge currentEdge = (Edge) edges.next();
		Vertex nextVertex = currentEdge.getDest();
		
		if(!nextVertex.isVisited()) {
		    nextVertex.visit();
		    nextVertex.setCost(1+currentVertex.getCost());
		    nextVertex.setPrev(currentVertex);
		    toDo.put(nextVertex);
		}

		if (nextVertex.equals(endVertex))
		    done = true;
		
	    } // end for
	    
	} // end while

	path.put(endVertex);
	while(endVertex.hasPrev()) {	
	    endVertex = endVertex.getPrev();
	    path.put(endVertex);
	}
	
	return path;

    }



}