import java.util.*;

public class myGraph
{
	protected String[] names;	// 1-d array to store the vertices
	protected boolean[][] Edges;	// 2-d array to store adjacencies between vertices,

	protected int numVertices;	
	protected int numEdges;

	// Default constructor. Sets aside enough capacity for one vertex
	public myGraph( )		
	{			
		this(1);
	}

	// Constructor that sets aside as much capacity as specified by the user
	public myGraph(int capacity)	
	{			
		names = new String[capacity];
		Edges = new boolean[capacity][];

		// We use only the portion of the matrix below the main diagonal to store the edges
		for(int i = 0; i < Edges.length; i++)
		{
			Edges[i] = new boolean[i+1];			
			for(int j = 0; j < i; j++)
				Edges[i][j] = false;
		}
	}
	
	public int numberOfVertices()
   	{
       	         return numVertices;
        }

        public int numberOfEdges()
        {
       	         return numEdges;
        }

	// Finds the location at which a vertex is stored in Vertices. 
	// Returns -1 if vertex not found
	public int getIndex(String vertex)
	{
		for(int i = 0; i < numVertices; i++)
			if(vertex.equals(names[i]))
				return i;

		return -1;
	}

	// Resizes the array of vertices. Can make it larger or smaller, depending
	// on what newSize is. 
	protected String[] resize(String[] array, int newSize)
	{
		String[] temp = new String[newSize];
		
		int smallerSize = newSize;
		if(array.length < smallerSize)
			smallerSize = array.length;

		for(int i = 0; i < smallerSize; i++)
			temp[i] = array[i];

		return temp;
	}
			


        // Resizes the array of adjacencies. Can make it larger or smaller, depending
        // on what newSize is.
        protected boolean[][] resize(boolean[][] array, int newSize)
        {
                boolean[][] temp = new boolean[newSize][];
        	int smallerSize = newSize;
        	if(array.length < smallerSize)
        		smallerSize = array.length;

		for(int i = 0; i < newSize; i++)
		{
			temp[i] = new boolean[i+1];
        		for(int j = 0; j < i+1; j++)
			{
            			if (i < smallerSize)
					temp[i][j] = array[i][j];
				else
					temp[i][j] = false;
			}
        	}
        	return temp;
    	}


	// Adds a new vertex
	public void addVertex(String newVertex)
	{
		if(getIndex(newVertex) != -1)
		{
			System.out.print("addVertex: ");
			System.out.print(newVertex);
			System.out.println(" failed -- vertex already exists.");
			return;
		}
		
		// if array of vertices is full, we need to expand it and 
		// also expand Edges
		if (names.length == numVertices)
		{
			names = resize(names, 2*numVertices+1);
			Edges = resize(Edges, 2*numVertices+1);
		}
			
		names[numVertices++] = newVertex;
	}


	// delete the given vertex
	public void deleteVertex(String vertex)
	{
		int i = getIndex(vertex);
		if(i == -1)
		{
			System.out.print("deleteVertex: ");
			System.out.print(vertex);
			System.out.println(" failed -- it does not exist.");
			return;
		}

		// Move the last vertex up to fill the hole made by vertex i
		names[i] = names[numVertices-1];
		names[numVertices-1] = null;

		for(int j = 0; j < i; j++)
		{
			// For every edge incident on vertex i, decrement numEdges
			if(Edges[i][j])
				numEdges--;
			// Move the first i elements of the last row in the adj. matrix into the ith row		
			Edges[i][j] = Edges[numVertices-1][j];
		}
		
		for(int j = i+1; j < numVertices-1; j++)
		{
			// For every edge incident on vertex i, decrement numEdges
			if(Edges[j][i])
				numEdges--;
			// Move the remaining elements of the last row in the adj. matrix into the ith collumn
			Edges[j][i] = Edges[numVertices-1][j];
		}
		
		// Delete the last row in the matrix
		for(int k = 0; k<numVertices; k++)
			Edges[numVertices-1][k] = false;

		numVertices--;

	}
	// Adds a new edge
	public void addEdge(String vertex1, String vertex2)
	{
		int i = getIndex(vertex1);
		if(i == -1)
		{
			System.out.print("addEdge failed: ");
			System.out.print(vertex1);
			System.out.println(" does not exist.");
            		return;
        	}

		int j = getIndex(vertex2);
		if(j == -1)
		{
			System.out.print("addEdge failed: ");
			System.out.print(vertex2);
			System.out.println(" does not exist.");
            		return;
        	}

        	if (i>=j) Edges[i][j] = true;
        	else Edges[j][i] = true;

		numEdges++;
	}


	// deletes a given edge
	public void deleteEdge(String vertex1, String vertex2)
	{
		int i = getIndex(vertex1);
        if(i == -1)
        {
            System.out.print("deleteEdge failed: ");
            System.out.print(vertex1);
            System.out.println(" does not exist.");
            return;
        }

        int j = getIndex(vertex2);
        if(j == -1)
        {
            System.out.print("deleteEdge failed: ");
            System.out.print(vertex2);
            System.out.println(" does not exist.");
            return;
        }


        if (i>=j) 
        {
        	if (Edges[i][j])
        	{
        		Edges[i][j] = false;
        		numEdges--;
        	}
        }
        else 
        {
        	if (Edges[j][i])
        	{
        		Edges[j][i] = false;
        		numEdges--;
        	}
        }
	}

	// returns the names of all the neighbors of a given vertex in an array of Strings
	public String[] getNeighbors(String vertex)
	{
		String[] neighbors = new String[numVertices];
		int numNeighbors = 0;
		
		int source = getIndex(vertex);
		if(source == -1)
		{
			System.out.print("getNeighbors failed: Vertex ");
            		System.out.print(vertex);
            		System.out.println(" does not exist.");
            		return new String[0];
        	}

		for(int j = 0; j < numVertices; j++)
		{
			boolean edge = false;
			if (j <= source) edge = Edges[source][j];
			else edge = Edges[j][source];
			
			if(edge)
				neighbors[numNeighbors++] = new String(names[j]);
		}
		
		neighbors = resize(neighbors, numNeighbors);
		return neighbors;
	}

	// returns the degree of a vertex with given name
    	public int degree(String vertex)
    	{
		// Get the index of the vertex
		int i = getIndex(vertex);
		if(i == -1)
		{
			System.out.print("In degree: ");
			System.out.print(vertex);
			System.out.println(" does not exist.");
			return -1;
		}

		// Call the other degree function that returns the degree
		// of a vertex, given its index
		return degree(i);
    	}

		
	// returns the degree of a vertex with given index
	public int degree(int index)
	{
        	int numNeighbors = 0;

		// Scan the row corresponding to vertex in the adjacency
		// matrix, counting the number of neighbors
        	for (int j = 0; j <= index; j++)
        		if(Edges[index][j])
            			numNeighbors++;
        
        	for (int j = index+1; j < numVertices; j++)
        		if(Edges[j][index])
        			numNeighbors++;

		return numNeighbors;	
	}

    	// returns the indices of all the neighbors of a given vertex with index
    	public int[] getNeighbors(int index)
    	{
        	int numNeighbors = degree(index);
        	int[] neighbors = new int[numNeighbors];

		// Scan the row corresponding to vertex in the adjacency matrix 
        	numNeighbors = 0;
        
        	for(int j = 0; j < numVertices; j++)
        	{
        		boolean edge = false;
        		if (j <= index) edge = Edges[index][j];
				else edge = Edges[j][index];

        		if(edge)
            			neighbors[numNeighbors++] = j;
        	}
        	return neighbors;
    	}

	// Determines if there is an edge between a given pair
	// of vertices, specified by their indices
	private boolean isEdge(int i, int j)
	{
		
		if((i < 0)||(j < 0)||(i > numVertices-1)||(j > numVertices-1))
		{
			System.out.println("isEdge failed.");
			System.out.println("isEdge: index out of range.");
			return false;	
		}

		if(i >= j)
			return Edges[i][j];
		else
			return Edges[j][i];

	}

	// Determines if there is an edge between a given pair
	// of vertices, specified by their names
	public boolean isEdge(String u, String v)
	{
		int i = getIndex(u);
		int j = getIndex(v);
	
		return isEdge(i, j);	

	}

	// Computes the clustering coefficient of a vertex. This is the 
	// version that takes as input a vertex index.
	public double clusteringCoefficient(int i)
	{

		// Get the indices of the neighbors of vertex i
		int[] neighbors = getNeighbors(i);

		// initialize number of edges-in-neighborhood to 0
		int edgesInNbd = 0;

		// Scan pairs of neighbors and increment counter whenever
		// there is an edge
		for(int j = 0; j < neighbors.length; j++)
			for(int k = 0; k < j; k++)
			{
				// Give names to the indices of the jth neighbor and the kth neighbor
				int vj = neighbors[j];
				int vk = neighbors[k];

				// Check the appropriate slot of the Edges matrix to check
				// if there is an edge between vertices vj and vk
				if((vj >= vk)&&(Edges[vj][vk]))
					edgesInNbd++;
				if((vj < vk)&&(Edges[vk][vj]))
					edgesInNbd++;
					
			}

		// if there are no neighbors or one neighbor then, clustering 
		// coefficient is trivially defined to  be 1. Otherwise, 
		// compute the ratio of number of edges in neighborhood to 
		// the total number of pairs of neighbors
		if(neighbors.length <= 1)
			return 1;
		else 
			return edgesInNbd*2.0/(neighbors.length*(neighbors.length-1));

	}

        // Computes the clustering coefficient of a vertex. This is the
        // version that takes a vertex name (rather than index) as argument.
        public double clusteringCoefficient(String v)
        {
                int i = getIndex(v);
                if(i == -1)
                {
                        System.out.print("clusteringCoefficient failed: ");
                        System.out.print(v);
                        System.out.println(" does not exist.");
                        return 0;
                }
	
		return clusteringCoefficient(i);
	}

	// Computes the clustering coefficient of the entire graph
	public double clusteringCoefficient()
	{
		double sum = 0;
		for(int i = 0; i < numVertices; i++)
			sum =  sum + clusteringCoefficient(i);

		return sum/numVertices;
	}		

} // end of class