import java.util.*;

public class myGenericListGraph<E>
{
	protected E[] names;			// 1-d array to store the vertices
	protected GenericLinkList<E>[] Edges;	// 1-d array to store adjacencies between vertices,
	protected int numVertices;	
	protected int numEdges;

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

	// Constructor that sets aside as much capacity as specified by the user
	public myGenericListGraph(int capacity)	
	{			
		names = (E []) new Object[capacity];
		Edges = (GenericLinkList<E>[]) new GenericLinkList[capacity];
		for (int i = 0 ; i < capacity ; i ++) {
			Edges[i] = new GenericLinkList<E>();
		}

	}
	
	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(E 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 E[] resize(E[] array, int newSize)
	{
		E[] temp = (E []) new Object[newSize];
		
		int smallerSize = newSize;
		if(array.length < smallerSize)
			smallerSize = array.length;

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

		return temp;
	}

	protected GenericLinkList<E>[] resize (GenericLinkList<E>[] array, int newSize)
	{
		GenericLinkList<E>[] temp = (GenericLinkList<E>[]) new GenericLinkList[newSize];
		
		int smallerSize = newSize;
		if(array.length < smallerSize)
			smallerSize = array.length;

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

		for (int i = smallerSize ; i < temp.length ; i ++)
			temp [i] = new GenericLinkList<E>();

		return temp;
	}

	// Adds a new vertex
	public void addVertex(E 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;
	}


	// Adds a new edge
	public void addEdge(E vertex1, E 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;
        	}

		Edges[i].insertFirst(names[j]);
		Edges[j].insertFirst(names[i]);


		numEdges++;
	}

	public void printAdjacencyList (E vertex)
	{
		int i = getIndex(vertex);
		if(i == -1)
		{
			System.out.print("addEdge failed: ");
			System.out.print(vertex);
			System.out.println(" does not exist.");
            		return;
        	}

		System.out.print (vertex + " is connected to ");
		Edges [i].displayList();		
	}


        // returns the names of all the neighbors of a given vertex in a linked
	//  list
	// added on 2/22; modified on 2/23
        public GenericLinkList<E> getNeighbors(E vertex)
        {
                int source = getIndex(vertex);
                if(source == -1)
                {
                        System.out.print("getNeighbors failed: Vertex ");
                        System.out.print(vertex);
                        System.out.println(" does not exist.");
                        return null;
                }

		return Edges[source].copy();
        }

        // returns the degree of a vertex with given name
	// added on 2/22
        public int degree(E 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)
        {
		return Edges[index].size();

        }

	// Method to compute average degree of the graph
	// added on 2/22
	public double averageDegree()
	{
		double sum = 0;
		for(int i = 0; i < numVertices; i++)
			sum = sum + degree(i);

		return sum/numVertices;
	}


        // Method to compute maximum degree of the graph
	// added on 2/22
        public int maximumDegree()
        {
                int maxDegree = -1;
		int temp;
                for(int i = 0; i < numVertices; i++)
		{
			temp  =  degree(i);
                        if(temp  > maxDegree)
				maxDegree = temp;
		}

                return maxDegree;
        }

		
        // Method to compute minimum degree of the graph
	// added on 2/22
        public int minimumDegree()
        {
                int minDegree = numVertices;
                int temp;
                for(int i = 0; i < numVertices; i++)
                {
                        temp  =  degree(i);
                        if(temp  < minDegree)
                                minDegree = temp;
                }
                
                return minDegree;
        }

	// Boolean method that tells us if {v1, v2} is an edge in the graph
	// added on 2/23
	public boolean isEdge(E vertex1, E vertex2)
	{
                int i = getIndex(vertex1);
                if(i == -1)
                {
                        System.out.print("isEdge failed: ");
                        System.out.print(vertex1);
                        System.out.println(" does not exist.");
                        return false;
                }

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

		// if vertex2 exists in the adjacency list of
		// vertex1, then return true
		return (Edges[i].find(vertex2) != null);
	}
		

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

		// Copy the adjacency list into an array, for easy access
		// copyIntoArray is a new method in the GenericLinkList class
		E[] temp = Edges[i].copyIntoArray();

		// initialize 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 < temp.length; j++)
			for(int k = 0; k < j; k++)
				if(isEdge(temp[j], temp[k]))
					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(temp.length <= 1)
			return 1;
		else 
			return edgesInNbd*2.0/(temp.length*(temp.length-1));

	}

        // Computes the clustering coefficient of a vertex. This is the
        // version that takes a vertex name as argument.
	// added on 2/23
        public double clusteringCoefficient(E 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
	// added on 2/23
	public double clusteringCoefficient()
	{
		double sum = 0;
		for(int i = 0; i < numVertices; i++)
			sum =  sum + clusteringCoefficient(i);

		return sum/numVertices;
	}		

	// computes the average path lenth of the graph
	// by repeatedly calling BFS and getting the distance
	// array
	public double averagePathLength()
	{
		// The average path length is infinity if the
		// graph is disconnected
		if(!isConnected())
			return -1;

		// For connected graphs, just do a BFS from every 
		// vertex, add all distances, and finally divide by
		// number of ordered pairs, i.e., n(n-1)
		double distanceSum = 0;
		for(int i = 0; i < numVertices; i++)
		{
			int[] d = breadthFirstSearch(names[i]);
			for(int j = 0; j < numVertices; j++)
				distanceSum = distanceSum + d[j];
		}
	
		return distanceSum/(numVertices*(numVertices - 1));

	}


	// determines if the graph is connected
	// by calling breadth-first search
	public boolean isConnected()
	{
		if(numVertices == 0)
			return false;

		// get the distance array by calling bfs
		// using the first vertex as source
		int[] d	= breadthFirstSearch(names[0]);

		// scan the distance array looking for -1
		// if there is a -1 the graph is not connected
		for(int i = 0; i < numVertices; i++)
			if(d[i] == -1)
				return false;

		return true;
	}
	
	
	// Breadth first search function; returns  a distance array
	public int[] breadthFirstSearch(E source)
	{
		int sourceIndex = getIndex(source);	
		if(sourceIndex == -1)
                {
                        System.out.print("breadthFirstSearch failed: ");
                        System.out.print(source);
                        System.out.println(" does not exist.");
                        return null;
                }

		// Initialization
		// First initialize the distance array
		// -1 means infinity
		int[] distances = new int[numVertices];
		for(int i = 0; i < numVertices; i++)
			distances[i] = -1;

		distances[sourceIndex] = 0;	

		// Then initialize the visited array
		boolean[] visited = new boolean[numVertices];
		for(int i = 0; i < numVertices; i++)
			visited[i] = false;

		visited[sourceIndex] = true;

		// Then initialize the queue
		GenericQueue<E> Q = new GenericQueue<E>(numVertices);
		Q.enqueue(source);

		while(!Q.isEmpty())
		{
			E current = Q.dequeue();
			int currentIndex = getIndex(current);

			GenericLinkList<E> neighbors = getNeighbors(current);
			while(!neighbors.isEmpty())
			{
				E aNeighbor = neighbors.deleteFirst();
				int neighborsIndex = getIndex(aNeighbor);
			
				if(!visited[neighborsIndex])
				{
					visited[neighborsIndex] = true;
					distances[neighborsIndex] = distances[currentIndex] + 1;
					Q.enqueue(aNeighbor);
				}

			} // end-while-scanning neighbors

		} // end-while Q is not empty

		return distances;
		
	}	

} // end of class