package graphs;
import java.util.*;

public class AdjacencyListGraph {

	LinkedList<Integer> [] g; // g[v] contains a list of all the vertices w such that the edge (v,w) is in the graph

	// Constructors go here -- e.g., the book has a constructor that reads from a file


	public void dfs(int s) {
		boolean [] visited = new boolean [g.length];
		Stack<Integer> postOrderStack = new Stack<Integer>();
		dfsHelper(s, visited, postOrderStack);
		// popping things out of this stack will give me the topological sort of the subgraph that starts at s
	}

	private void dfsHelper(int v, boolean [] visited, Stack<Integer> s) {
		visited[v] = true;
		// do what you need to the node -- depends on the purpose of the dfs

		// now visited very neighbor of the node
		for (Integer w : g[v]) {
			if (!visited[w])
				dfsHelper (w, visited, s);
			s.push(v);
		}
	}

	public void bfs(int s) {
		boolean [] visited = new boolean [g.length];
		int lastHopTo[] = new int [g.length];
		Queue<Integer> q = new LinkedList<Integer>();

		visited[s] = true;
		q.add(s);
		while (!q.isEmpty()) {
			int v = q.remove(); // dequeue
			// do what you need to the node -- depends on the purpose of the bfs

			// now visit very neighbor of the node
			for (Integer w : g[v]) {
				if (!visited[w]) {
					visited[w]=true;
					q.add(w);

					// here we can add a line of code to compute distance of w from s
					// if we know distance of v from s

					// we can also add a "last hop" array that keeps track
					// of the last hop on the path from s to w
					// tracing back through this array will give you the entire path
					lastHopTo[w] = v;
				}
			}
		}
	}

	// then there is no edge from w to v
	// Such a thing is possible if and only if the graph has no cycles
	// If the graph has cycles, returns null

	Iterable<Integer> topologicalSort () {

		boolean [] removed = new boolean[g.length];
		Queue<Integer> output = new LinkedList<Integer>();
		int [] numIncomingEdges = new int [g.length];
		Queue<Integer> readyQueue = new LinkedList<Integer>(); 

		// initialize numIncomingEdges
		for (int v = 0; v<g.length; v++)
			for (int w : g[v])
				numIncomingEdges[w]++;

		for (int w = 0; w<g.length; w++)
			if (numIncomingEdges[w]==0)
				readyQueue.add(w);

		for (int i = 0; i<g.length; i++) {
			if (readyQueue.isEmpty())
				return null;
			
			int v = readyQueue.remove();
			output.add(v);
			removed[v]=true;
			for (int w : g[v])  { // if there is an edge between v and w then certainly w hasn't been removed yet
				numIncomingEdges[w]--;
				if (numIncomingEdges[w]==0)
					readyQueue.add(w);
			}
		}			
		return output;
	}


}