import java.util.*;
import java.awt.*;
import java.text.*;

public class DFS {
	
	int numNodes;               // number of nodes in graph
	int [][] adjacencyMatrix;   // 2D adjacency matrix representation of graph
	
	// Depth first search (DFS) related information.
	int [] dfsSequence;         // For each graph node i, dfsSequence[i] gives sequence 
                                // number of node i in DFS traversal
	boolean [] isNodeVisited;   // Keeps track of nodes visited during DFS traversal
	int dfsSequenceCounter;     // Keeps track of number of nodes traversed during DFS traversal
	
	public void initializeDFS(){
		dfsSequenceCounter = 0;
		for( int i = 0; i < numNodes; i++ ){
			dfsSequence[i] = -1;
			isNodeVisited[i] = false;
		}
	}
	
	public void doDfs(int nodeId){
		initializeDFS();
		doDfsRecursive(nodeId);
	}
	
	public void doDfsRecursive(int nodeId){

		// The method for recursive DFS traversal of the graph. 
		// TF will help complete this method in the lab.
		
		isNodeVisited[nodeId] = true;
		dfsSequence[nodeId] = dfsSequenceCounter;
		
		for( int i = 0; i < numNodes; i++ ){
			if( adjacencyMatrix[nodeId][i] == 1 && isNodeVisited[i] == false )
			{
				dfsSequenceCounter++;
				doDfsRecursive(i);
			}
		}
	}
	
	public boolean isGraphATree(){
		initializeDFS();
		
		if( checkCycleViaDFS(0, -1) )
			return false;
		
		for( int i = 0; i < numNodes; i++ ){
			if( !isNodeVisited[i] )
				return false;
		}
		return true;
	}
	
	public boolean checkCycleViaDFS(int currentNodeId, int previousNodeId){
		
		/*
		 Complete this method to return true if the graph has a cycle.
		 Inputs: currentNodeId is the current node in our DFS traversal
		         previousNodeId is the node previous to currentNodeId (parent node)
		         in the DFS traversal.  
		 
		 Output: True if graph has cycle, false otherwise.
		 
		 Algorithm:
		 Use DFS traversal similar to doDfsRecursive(). If any of the 
		 neighbor nodes of currentNodeId (other than previousNodeId) have already
		 been visited we return true, otherwise continue the DFS traversal. 
		 i.e., 
		  ( isNodeVisited[i] == true ), where i is a neighbor node of currentNodeId
		 	                          	and i != previousNodeId            	
		*/

		isNodeVisited[currentNodeId] = true;
		
		for( int i = 0; i < numNodes; i++ )
		{
			if( i != previousNodeId && adjacencyMatrix[currentNodeId][i] == 1 )
			{
				if( isNodeVisited[i] )
					return true;
				else if( checkCycleViaDFS(i, currentNodeId) )
					return true;
			}
		}
			
		return false;
	}
	
	
	// Other supporting methods for display and random graph generation.
	
	static Random rand = new Random(12345);
	int node_diameter = 40;
	Point [] node_coordinates;
	
	public void addGraphics(Graphics g, int window_w, int window_h){
		int y_offset = 90; 
		int nodeCircleRadius = (window_h - y_offset)/5;
		int nodeCircleCenterX = window_w / 2;
		int nodeCircleCenterY = y_offset + nodeCircleRadius;
		node_coordinates = new Point[numNodes];
		double theta = 2 * Math.PI / numNodes;
		for(int i = 0; i < numNodes; i++){
			int nodeX = nodeCircleCenterX + (int)(nodeCircleRadius * Math.sin(theta * i)) - node_diameter/2;
			int nodeY = nodeCircleCenterY - (int)(nodeCircleRadius * Math.cos(theta * i)) - node_diameter/2;
			node_coordinates[i] = new Point(nodeX, nodeY);
			drawNumberCircle(g, i, nodeX, nodeY, node_diameter);
		}
		for(int i = 0; i < numNodes; i++){
			for(int j = i+1; j < numNodes; j++){
				if( adjacencyMatrix[i][j] == 1 )
					drawLine(g, node_coordinates[i].x, node_coordinates[i].y, 
							node_coordinates[j].x, node_coordinates[j].y, node_diameter);
			}
		}
		int nodeCircleRadius2 = nodeCircleRadius + node_diameter;
		int cell_width = 28;
		for(int i = 0; i < numNodes; i++){
			int nodeX = nodeCircleCenterX + (int)(nodeCircleRadius2 * Math.sin(theta * i)) - cell_width/2;
			int nodeY = nodeCircleCenterY - (int)(nodeCircleRadius2 * Math.cos(theta * i)) - cell_width/2;
			g.setColor(Color.BLUE);
			g.drawRect(nodeX, nodeY, cell_width, cell_width );
			drawNumberCircle(g, dfsSequence[i], nodeX, nodeY, -cell_width);
		}
		
		y_offset = window_h/2+20;
		cell_width = 30;
		int x_offset = (window_w - cell_width * (numNodes + 1) )/2;
		for( int i = 0; i <= numNodes; i++ )
		{
			int x_offset2 = x_offset;
			for( int j = 0; j <= numNodes; j++ )
			{
				g.setColor(Color.ORANGE);
				if( i != 0 && j != 0 )
					g.drawRect(x_offset2, y_offset , cell_width, cell_width );
				g.setColor(Color.RED);
				g.setFont(new Font("Verdana",Font.BOLD,15));
				
				String str = "";
				if( i == 0 && j != 0 ){
					str = "" + (j - 1); g.setColor(Color.RED);
				}
				else if( j == 0 && i != 0 ){
					str = "" + (i - 1); g.setColor(Color.RED);
				}
				else if( i != 0 && j != 0 ){
					str = "" + adjacencyMatrix[i-1][j-1]; 
					if (adjacencyMatrix[i-1][j-1] == 1){ 
						g.setColor(Color.white);
						g.fillRect(x_offset2, y_offset , cell_width, cell_width );
					}
					g.setColor(Color.BLUE);
				}
				
				int x = x_offset2 + cell_width/2 - 6 * str.length();
				int y = y_offset + cell_width/2 + 5;
				g.drawString( str, x, y );
						
				x_offset2 += cell_width;
			}
			y_offset += cell_width;
		}
		y_offset += 30;
		g.drawString("Graph, DFS node squence and adjacency matrix", x_offset-50, y_offset);
	}
	
	void drawNumberCircle(Graphics g, int node_value, int node_x, int node_y, int diameter)
	{
		if( diameter > 0 ){
			g.setColor(Color.ORANGE);
			g.fillOval( node_x, node_y, diameter, diameter );
			g.setColor(Color.RED);
		} else {
			diameter = -diameter;
		}
		g.setFont(new Font("Verdana",Font.BOLD,15));
		String str = ""+node_value;
		g.drawString( ""+node_value, node_x + diameter/2 - 6 * str.length(), node_y + diameter/2 + 5 );
	}
	
	public int getNodeIndexMouseClick( Point clickPoint )
	{
		int radius = node_diameter / 2;
		for(int i = 0; i < numNodes; i++)
		{
			Point pt = node_coordinates[i];
			if( clickPoint.distance(pt.x + radius, pt.y + radius) < radius )
				return i;
		}
		return -1;
	}
	
	void drawLine( Graphics g, int node1_x, int node1_y, int node2_x, int node2_y, int diameter )
	{
		int radius = diameter / 2;
		int x1 = node1_x + radius;
		int y1 = node1_y + radius;
		int x2 = node2_x + radius;
		int y2 = node2_y + radius;
		double dist = Math.sqrt(Math.pow((x1 - x2), 2)+Math.pow((y1 - y2), 2));
		double alpha1 = radius / dist;
		double alpha2 = (dist - radius) / dist;
		int xn1 = (int)(alpha1 * x1 + (1 - alpha1) * x2);
		int yn1 = (int)(alpha1 * y1 + (1 - alpha1) * y2);
		int xn2 = (int)(alpha2 * x1 + (1 - alpha2) * x2);
		int yn2 = (int)(alpha2 * y1 + (1 - alpha2) * y2);

		g.drawLine(xn1, yn1, xn2, yn2);
	}
	
	DFS(){
		numNodes = 6 + rand.nextInt(5);
		adjacencyMatrix = new int[numNodes][numNodes];
		dfsSequence = new int[numNodes];
		isNodeVisited = new boolean[numNodes];
		
		int maxDegree = numNodes/5;
		
		for(int i = 0; i < numNodes; i++){
			int currentDegree = 0;
			dfsSequence[i] = -1;
			for(int j = 0; j < numNodes; j++){
				currentDegree += adjacencyMatrix[i][j]; 
			}
			int nodeDegree = 1 + rand.nextInt(maxDegree);
			int j = currentDegree;
			for( ; j <= nodeDegree ; j++ ){
				int connectNode = rand.nextInt(numNodes);
				if ( connectNode == i )
					continue;
				adjacencyMatrix[i][connectNode] = 1;
				adjacencyMatrix[connectNode][i] = 1;
			}
		}
	}
}