/**
 * Rishi Verma
 * rktios@gmail.com
 * 21-March-2015
 * Common graph implementations in Java
 */
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

class GraphNode {
	private HashMap<Integer, LinkedList<Integer>> adjList = null;
	private HashMap<Integer, Boolean> visited = null;
	public Stack<Integer> topologicalSortStack = new Stack<Integer>();

	enum BIPARTITECOLOR {
		NOTVISITED, RED, BLUE
	}

	private HashMap<Integer, BIPARTITECOLOR> bipartiteColor = null;

	public void initializeBipartiteColor() {

		bipartiteColor = new HashMap<Integer, BIPARTITECOLOR>();

		for (int node : adjList.keySet()) {
			bipartiteColor.put(node, BIPARTITECOLOR.NOTVISITED);
		}
	}

	public GraphNode(int node[]) {
		System.out.println("GraphNode.GraphNode()");

		adjList = new HashMap<Integer, LinkedList<Integer>>();

		for (int i : node) {
			adjList.put(i, new LinkedList<Integer>());
		}

	}

	void checkBipartite(int source) {
		initializeBipartiteColor();
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(source);
		bipartiteColor.put(source, BIPARTITECOLOR.RED);
		System.out.println(doCheckBipartite(q));

	}

	boolean doCheckBipartite(Queue<Integer> q) {

		if (false == q.isEmpty()) {

			int currentNode = q.remove();
			BIPARTITECOLOR color = bipartiteColor.get(currentNode);
			LinkedList<Integer> neighbours = findNeighbour(currentNode);

			for (Integer neighbour : neighbours) {
				if (bipartiteColor.get(neighbour) == BIPARTITECOLOR.NOTVISITED) {
					q.add(neighbour);
					if (color == BIPARTITECOLOR.RED) {
						bipartiteColor.put(neighbour, BIPARTITECOLOR.BLUE);
					} else {
						bipartiteColor.put(neighbour, BIPARTITECOLOR.RED);
					}
				} else {
					if (color == bipartiteColor.get(neighbour)) {
						return false;
					}
				}
			}
			return doCheckBipartite(q);

		}
		return true;
	}

	public void addEdge(int source, int destination) {

		adjList.get(source).add(destination);

	}

	public LinkedList<Integer> findNeighbour(int node) {
		// System.out.println("GraphNode.findNeighbour() source: " + node);

		LinkedList<Integer> neighbours = adjList.get(node);

		for (Integer i : neighbours) {
			// System.out.println(i);
		}

		return neighbours;
	}

	public void initializeVisitedMap() {
		System.out.println("GraphNode.dfs()");
		// Creating Visited hashmap
		visited = new HashMap<Integer, Boolean>();
		Set<Integer> key = adjList.keySet();
		for (int i : key) {
			visited.put(i, false);
		}

		// doDfs(source);

	}

	public void dfs(int source) {

		if (true == visited.get(source)) {
			return;
		}
		visited.put(source, true);
		System.err.println("GraphNode.doDfs() " + source);

		LinkedList<Integer> neighbours = findNeighbour(source);
		for (int neighbour : neighbours) {
			dfs(neighbour);

		}
	}

	public void bfs(int source) {

		Queue<Integer> bfsq = new LinkedList<Integer>();
		bfsq.add(source);
		visited.put(source, true);
		doBfs(bfsq);
	}

	private void doBfs(Queue<Integer> q) {
		if (q.isEmpty() == false) {
			Integer currentNode = q.remove();

			System.err.println("GraphNode.bfs() " + currentNode);

			LinkedList<Integer> neighbours = findNeighbour(currentNode);
			for (Integer i : neighbours) {
				if (false == visited.get(i)) {
					visited.put(i, true);
					q.add(i);
				}

			}
			doBfs(q);
		}
	}

	private void topologicalSortOnEachNode(int source) {
		if (true == visited.get(source)) {
			return;
		}
		visited.put(source, true);
		LinkedList<Integer> neighbours = adjList.get(source);
		for (Integer i : neighbours) {
			topologicalSortOnEachNode(i);
		}
		topologicalSortStack.push(source);

	}

	public void topologicalSort() {

		Set<Integer> nodes = adjList.keySet();
		for (Integer node : nodes) {
			System.out.println("GraphNode.topologicalSort() " + node);
			topologicalSortOnEachNode(node);
		}

	}

	public void printTopologicalSortStack() {
		System.out.println("GraphNode.printTopologicalSortStack()");

		/*
		 * for (Integer i : topologicalSortStack) { System.out.println(i); }
		 */

		while (topologicalSortStack.isEmpty() == false) {
			System.out.println(topologicalSortStack.pop());
		}
	}

	/**
	 *
	 * 
	 * @param source
	 * @param parent
	 */
	public boolean isCyclic(int source, int parent) {

		if (true == visited.get(source)) {
			return true;
		}
		visited.put(source, true);

		LinkedList<Integer> neighbours = findNeighbour(source);
		for (int neighbour : neighbours) {
			if (parent != neighbour && true == visited.get(neighbour)) {
				System.out.println("isCyclic() TRUE Source" + source
						+ " Parent " + parent + "Neighbour" + neighbour);
				return true;
			}

			return isCyclic(neighbour, source);

		}
		return false;
	}

}

class Graph {

	public static void main(String[] args) {
		System.out.println("Graph.main()");
		// GraphNode graphNode = createGraphExampleForDfs();

		GraphNode graphNode = createGraphExampleForCycle();
		// GraphNode graphNode = createGraphExampleForTopologicalSort();
		// GraphNode graphNode = createGraphExampleForBiPartite();
		// graphNode.findNeighbour(1);
		graphNode.initializeVisitedMap();
		// graphNode.topologicalSort();
		// graphNode.printTopologicalSortStack();
		// graphNode.dfs(2);
		System.out.println("IS cyclic " + graphNode.isCyclic(3, 3));
		// graphNode.bfs(4);
		// graphNode.checkBipartite(4);
	}

	private static GraphNode createGraphExampleForBiPartite() {

		int node[] = { 0, 1, 2, 3, 4 };
		GraphNode graphNode = new GraphNode(node);

		graphNode.addEdge(0, 1);
		graphNode.addEdge(0, 4);

		graphNode.addEdge(1, 0);
		graphNode.addEdge(1, 2);

		graphNode.addEdge(2, 1);
		graphNode.addEdge(2, 3);

		graphNode.addEdge(3, 2);
		graphNode.addEdge(3, 4);

		graphNode.addEdge(4, 0);
		graphNode.addEdge(4, 3);

		return graphNode;
	}

	private static GraphNode createGraphExampleForTopologicalSort() {
		int nodeList[] = { 0, 1, 2, 3, 4, 5 };
		// Ref graph
		// http://c...content-available-to-author-only...g.com/images/topologicalsort.png
		GraphNode graphNode = new GraphNode(nodeList);

		graphNode.addEdge(2, 3);

		graphNode.addEdge(3, 1);

		graphNode.addEdge(4, 0);
		graphNode.addEdge(4, 1);

		graphNode.addEdge(5, 0);
		graphNode.addEdge(5, 2);

		return graphNode;
	}

	private static GraphNode createGraphExampleForDfs() {
		int nodeList[] = { 0, 1, 2, 3, 4 };
		// Ref graph
		/*
		 * http://d...content-available-to-author-only...t.net/wp-content/uploads/
		 * graph_representation12.png
		 */
		GraphNode graphNode = new GraphNode(nodeList);
		graphNode.addEdge(0, 1);
		graphNode.addEdge(0, 4);

		graphNode.addEdge(1, 0);
		graphNode.addEdge(1, 2);
		graphNode.addEdge(1, 3);
		graphNode.addEdge(1, 4);

		graphNode.addEdge(2, 1);
		graphNode.addEdge(2, 3);

		graphNode.addEdge(3, 1);
		graphNode.addEdge(3, 2);
		graphNode.addEdge(3, 4);

		graphNode.addEdge(4, 0);
		graphNode.addEdge(4, 1);
		graphNode.addEdge(4, 3);

		return graphNode;
	}

	// For testing cycleGraph
	private static GraphNode createGraphExampleForCycle() {
		int nodeList[] = { 0, 1, 2, 3, 4, 5 };
		// Ref graph
		/*
		 * http://d...content-available-to-author-only...t.net/wp-content/uploads/cycleGraph-300
		 * x156.png
		 */GraphNode graphNode = new GraphNode(nodeList);
		graphNode.addEdge(0, 1);
		graphNode.addEdge(0, 3);
		graphNode.addEdge(0, 5);

		graphNode.addEdge(1, 0);
		graphNode.addEdge(1, 2);

		graphNode.addEdge(2, 1);
		graphNode.addEdge(2, 5);

		graphNode.addEdge(3, 0);
		graphNode.addEdge(3, 4);

		graphNode.addEdge(4, 3);

		graphNode.addEdge(5, 0);
		graphNode.addEdge(5, 2);

		return graphNode;
	}
}