import java.util.*;

	public class MollyListGraph
	{
		protected String[] names;	// 1-d array to store the vertices
		protected StringLinkList[] 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 MollyListGraph( )		
		{			
			this(1);
		}

		// Constructor that sets aside as much capacity as specified by the user
		public MollyListGraph(int capacity)	
		{			
			names = new String[capacity];
			Edges = new StringLinkList[capacity];
			for (int i = 0 ; i < capacity ; i ++) {
				Edges[i] = new StringLinkList();
			}

		}
		
		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 Edges. Can make it larger or smaller, depending
		// on what newSize is. 
		protected StringLinkList[] resize (StringLinkList[] array, int newSize)
		{
			StringLinkList[] temp = new StringLinkList[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 StringLinkList();

			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;
		}


		// 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;
	        	}

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


			numEdges++;
		}

		// Prints the neighbors of the given vertex
		public void printAdjacencyList (String 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 
		// String array
	        public String[] getNeighbors(String 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].copyIntoArray();
	        }

	        // returns the indices of all the neighbors of a given vertex. The
	        // vertex is specified as an index and the neighbors are returned
		// in an int array 
	        public int[] getNeighbors(int index)
	        {
	                if((index < 0) || (index >= numVertices))
	                {
	                        System.out.print("getNeighbors failed: Index");
	                        System.out.print(index);
	                        System.out.println(" is out of bounds.");
	                        return null;
	                }

			// Call the earlier getNeighbors function to get the names of
			// neighbors
	                String[] nbrNames = getNeighbors(names[index]);

			// Turn the array of neighbor names into an array
			// of neighbor indices
			int[] nbrIndices = new int[nbrNames.length];
			for(int i = 0; i < nbrIndices.length; i++)
				nbrIndices[i] = getIndex(nbrNames[i]);

			return nbrIndices;
	        }



	        // 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)
	        {
			return Edges[index].size();

	        }

		// Boolean method that tells us if {v1, v2} is an edge in the graph
		public boolean isEdge(String vertex1, String 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.
		public double clusteringCoefficient(int i)
		{

			// Copy the adjacency list into an array, for easy access
			// copyIntoArray is a new method in the GenericLinkList class
			String[] 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.
	        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
		// added on 2/23
		public double clusteringCoefficient()
		{
			double sum = 0;
			for(int i = 0; i < numVertices; i++)
				sum =  sum + clusteringCoefficient(i);

			return sum/numVertices;
		}		

		// Checks whether the graph is connected or not by calling breadthFirstSearch
		public boolean isConnected()
		{
			// Perform breadth first search
			int[] bfsTree = breadthFirstSearch(names[0]);

			// Scan the bfsTree array, looking for -1. The graph
			// is not connected if there is -1 in this array
			for(int i = 0; i < bfsTree.length; i++)
				if(bfsTree[i] == -1)
					return false;
		
			return true;
		}


		// Returns a 2-d array of vertex names representing the connected components
		// of the graph. Each row in the 2-d array is a connected component.
		public String[][] connectedComponents()
		{
			// The maximum number of connected components equals the number
			// of vertices; so start by allocating this many rows.
			String[][] cc = new String[numVertices][];

			// Keeps track of which vertices have been visited by repeated
			// calls to bfs
			boolean[] visited = new boolean[numVertices];
			for(int i = 0; i < numVertices; i++)
				visited[i] = false;

			// Keeps track of the number of vertices have been visited by repeated
			// calls to bfs
			int numVisited = 0;

			// Keeps track of the number of connected components
			int numComponents = 0;

			// Repeat bfs until all vertices have been visited
			while(numVisited < numVertices)
			{
				// Scan visited until an unvisited vertex is found
				// and start bfs at that source
				int source;
				for(source = 0; source < numVisited; source++)
					if(!visited[source])
						break;

				// Compute the bfsTree starting at this source
				int[] bfsTree = breadthFirstSearch(names[source]);

				// Scan bfsTree to count number of newly visited vertices
				int countNewVisited = 0;
				for(int i = 0; i < numVertices; i++)
					if(bfsTree[i] != -1)
						countNewVisited++;
				
				// Allocate a row of size countNewVisited in the current row of
				// cc to store the new connected component
				cc[numComponents] = new String[countNewVisited];

				// Scan bfsTree again, this time to copy the newly visited
				// vertices into cc and set them as visited
				countNewVisited = 0;
				for(int i = 0; i < numVertices; i++)
					if(bfsTree[i] != -1)
					{
						cc[numComponents][countNewVisited++] = names[i];
						visited[i] = true;
					}

				// Update numVisited	
				numVisited = numVisited + countNewVisited;

				// Update numComponents
				numComponents++;
				
			} // end while 
						
			// Resize cc to have exactly as mamy rows as numComponents
			String[][] newCC = new String[numComponents][];
			for(int i = 0; i < numComponents; i++)
				newCC[i] = cc[i];	

			return newCC;
				

		}

		// Breadth first search function; returns  a breadth first search tree
		// stored in an array of integers with the entry in slot i containing
		// the index of the parent of the vertex with index i
		public int[] breadthFirstSearch(String 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;
	                }
			
			// Initialize the bfsTree array; the entry -1 means
			// not yet visited.
			int[] bfsTree = new int[numVertices];
			for(int i = 0; i < numVertices; i++)
				bfsTree[i] = -1;

			// The parent of the tree root is itself
			bfsTree[sourceIndex] = sourceIndex;

			// 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
			Queue Q = new Queue(numVertices);
			Q.enqueue(sourceIndex);

			while(!Q.isEmpty())
			{
				// get the index of the vertex first in line
				int current = Q.dequeue();

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

				// Scan the neighbors
				for(int i = 0; i < neighbors.length; i++)
				{
					// Get the index of the current neighbor
					int currentNeighbor = neighbors[i];
				
					// Check if the neighbor is new, i.e., not visited
					// If so, mark the neighbor as visited, enqueue the neighbor, and 
					// set the neighbor's parent in bfsTree
					if(!visited[currentNeighbor])
					{
						visited[currentNeighbor] = true;
						Q.enqueue(currentNeighbor);
						bfsTree[currentNeighbor] = current;
					}

				} // end-scanning neighbors

			} // end-while Q is not empty

			return bfsTree;

		}	
		
		public String[] shortestPath(String source, String destination)
		{
			//MollyListGraph shortPath = new MollyListGraph();
			int[] readIn = breadthFirstSearch(source);
			String[] path = new String[readIn.length];
			String[] toReturn = new String[numVertices];
			
			for(int e=0; e< readIn.length; e++)
			{
				path[e] = names[e];
			}
		
			int counter = 0;
			int ind = getIndex(destination);
			while(readIn[ind] != getIndex(source))
			{
				toReturn[counter] = path[ind];
				ind = readIn[ind];
				counter++;
			}
			
			toReturn = resize(toReturn, counter);
			return toReturn;
		}
	} // end of class