//package gfgGraphs;

import java.util.*;
// this is a directed graph
// if you want undirected graph, add edges from v1->v2 && v2->v1
// use hashmap to construct adjacency list graph in java
 class Graph {

	HashMap<Integer, LinkedList<Integer>> adj; // adjacency hashmap
	HashMap<Integer,Boolean> visited; 
	
	// constructor to construct a graph from the nodes
	 public  Graph(int[] nodes){
		 adj = new HashMap<Integer,LinkedList<Integer>>();
		 visited = new HashMap<Integer,Boolean>();
		 
		 
		for(int i=0;i<nodes.length;i++){
			adj.put(nodes[i], new LinkedList<Integer>());
			visited.put(nodes[i], false);
		}
	}
	 // add edge from vertices v1 to v2
	 void addEdge(int v1,int v2){
		 adj.get(v1).add(v2);
	 }
	 
	 // get neighbors of a vertex
	 LinkedList<Integer> getNeighbors(int v){
		 return adj.get(v);
	 }
	// Breadth First Traversal of the Graph (Directed)
	// runtime: O(V+E) , no of vertices + edges
	 static void BFS(Graph g,int n){
		 Queue<Integer> q = new LinkedList<Integer>();
		 q.add(n);
		 
		while(!q.isEmpty()){
			n = q.peek();
			System.out.print(n+" ");
			g.visited.put(n, true);
			
			Iterator<Integer> i = g.adj.get(q.peek()).iterator(); // peek() returns the head of the queue without removing
			q.poll(); // poll() removes and returns the head of the queue
			while(i.hasNext() ){
				Integer l = i.next();
				if(!g.visited.get(l)){					
					g.visited.put(l, true);
					q.add(l);				
				}
			}
		}
		 
	 }
	 // runtime: O(V+E) , no of vertices + edges
	 static void DFS(Graph g, int n){
		 if(!g.visited.get(n)){
			 System.out.print(n+" ");
			 g.visited.put(n, true);
			 Iterator<Integer> i = g.adj.get(n).iterator();
			 while(i.hasNext()){
				 Integer l = i.next();
				 DFS(g,l);
			 }
		 }
	 }
	
	 // returns true even if one cycle is present
	 // run time: O(V), where V-no of vertices
	 static boolean isCyclic(Graph g,int n){
		 if(g.visited.get(n))
			 return true;
		 g.visited.put(n, true);
		 Integer k = null;
		 // try statement to return false if 
		 // k throws an exception:No such element exists
		 try{
		  k = g.adj.get(n).element();
		 }
		 catch(Exception e){
			 return false;
		 }
		 return isCyclic(g, k);
		 
	 }
	 
	 
	 /* comments from geeksforgeeks
	 Nice approach but there is a problem. I don't think isCyclic method works here. 
	 You need to have a cycleDetectionMap just like visited map. Initialize cycleDetectionMap to false 
	 in the constructor. Your isCyclic method should look something like below.

	boolean cyclesInGraph(Integer root){
	if (!(visitedMap.get(root))) {
	visitedMap.put(root, true);
	cycleDetectionMap.put(root, true);
	List<integer> adjacencyList = adjacencyMap.get(root);
	for(int i = 0; i < adjacencyList.size(); i++) {
	int current = adjacencyList.get(i);
	if(cyclesInGraph(current)){
	return true;
	} else if (cycleDetectionMap.get(current)) {
	return true;
	}
	}
	cycleDetectionMap.put(root, false);
	}
	return false;
	}

Also how about having a reset method in graph to clear visited and cycleDetection maps?
	 
	 */
	 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int ar[] = {10,41,62,83};
		int ar2[] = {1,2,3,4,5,6,7};
		int ar3[] = {1,2,3,4,5,6,7,8,9,10,11,12};
		Graph g = new Graph(ar); // BFS graph
		Graph g2 = new Graph(ar); // DFS graph
		Graph g3 = new Graph(ar);
		Graph g4 = new Graph(ar3);
		
		g.addEdge(10, 41);
	    g.addEdge(10, 62);
	    g.addEdge(41, 62);
	    g.addEdge(62, 10);
	    g.addEdge(62, 41);
	    g.addEdge(62, 83);
	    g.addEdge(83, 83);
	    
	   // System.out.println("BFS Neighbors"+g.getNeighbors(10));
	    System.out.print("BFS: ");
	    BFS(g,10);
	    System.out.println();
	    
	    // Depth first traversal
	    
	    
	    g2.addEdge(10, 41);
	    g2.addEdge(10, 62);
	    g2.addEdge(41, 62);
	 //   g2.addEdge(62, 41);
	    g2.addEdge(62, 10);
	    
	    g2.addEdge(62, 83);
	//    g2.addEdge(83, 83);
	  //  g2.addEdge(83, 41);
	    
	    System.out.print("DFS: ");
	    DFS(g2,62);
	    System.out.println();
	    
	    
	    // Cyclic graph
	    g3.addEdge(10, 41);
	    g3.addEdge(41, 62);
	   // g3.addEdge(62, 83);
	    g3.addEdge( 62,10);
	    //g3.addEdge(83,10);

	    boolean b = isCyclic(g3,10);
	    if(b)
	    	System.out.println("The graph is cyclic");
	    else
	    	System.out.println("Not a cyclic graph");
	    
	    g4.addEdge(1,2);
	    g4.addEdge(1,3);
	    g4.addEdge(1,4);
	    g4.addEdge(2,5);
	    g4.addEdge(2,6);
	    g4.addEdge(5,9);
	    g4.addEdge(5,10);
	    g4.addEdge(4,7);
	    g4.addEdge(4,8);
	    g4.addEdge(7,11);
	    g4.addEdge(7,12);
	    System.out.print("BFS: ");
	    BFS(g4,1);
	    System.out.println();
	    
	    
	    Graph g5 = new Graph(ar3);
	    
	    g5.addEdge(1,2);
	    g5.addEdge(1,7);
	    g5.addEdge(1,8);
	    g5.addEdge(2,3);
	    g5.addEdge(2,6);
	    g5.addEdge(3,4);
	    g5.addEdge(3,5);
	    g5.addEdge(8,9);
	    g5.addEdge(8,12);
	    g5.addEdge(9,10);
	    g5.addEdge(9,11);
	    System.out.print("DFS: ");
	    DFS(g5,1);
	    System.out.println();
	    
	}

}