import java.util.*;

public class myGraph
{
	protected String[] Vertices;	// 1-d array to store the vertices
	protected LinkList[] Edges;	// adjacency list representation
	protected int numVertices;	// tracks the number of vertices	
	protected int numEdges;		// tracks the number of edges
	protected int[] dFTTree;	// Stores the depth first tree

	// 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)	
	{			
		Vertices = new String[capacity];
		Edges = new LinkList[capacity];

		// Construct the LinkList object in each slot in Edges
		for(int i = 0; i < capacity; i++)
			Edges[i] = new LinkList();
		
		numVertices = 0;
		numEdges = 0;
	}
	
	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(Vertices[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 Edges, the array of linked lists. Can make it 
	// larger or smaller, depending on what newSize is.
        protected LinkList[] resize(LinkList[] array, int newSize)
        {
                LinkList[] temp = new LinkList[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 < newSize; i++)
			temp[i] = new LinkList();

                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 (Vertices.length == numVertices)
		{
			Vertices = resize(Vertices, 2*numVertices+1);
			Edges = resize(Edges, 2*numVertices+1);
		}
			
		Vertices[numVertices++] = newVertex;
	}

	// Adds a new edge, wittht no given weight
	public void addEdge(String vertex1, String vertex2)
	{
		addEdge(vertex1, vertex2, 0);
	}

	// Adds a new edge
	public void addEdge(String vertex1, String vertex2, double distance)
	{
		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(Edges[i].find(j) == null)
		{
			Edges[i].insertFirst(j, distance);
			Edges[j].insertFirst(i, distance);
			numEdges++;
		}
	}


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

		// Remember the degree of the vertex
		int degree = Edges[i].size();

		// First, let us delete this vertex from the adacency lists
		// of each of its neighbors
		int[] neighbors = getNeighbors(i);
		for(int j = 0; j < neighbors.length; j++)
			Edges[neighbors[j]].delete(i);

		// Move the last vertex up to occupy the hole
		// left by the departure of vertex i
		Vertices[i] = Vertices[numVertices-1];
		Edges[i] = Edges[numVertices-1];
		Edges[numVertices-1] = new LinkList();

		// Change all occurances of the index numVertices-1 to i
		neighbors = getNeighbors(i);
		for(int j = 0; j < neighbors.length; j++)
		{
			Link temp = Edges[neighbors[j]].find(numVertices-1);
			temp.iData = i;
		}
		
		// Update the number of vertices and the number of edges
		numVertices--;
		numEdges = numEdges - degree;
	}

	// 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(Edges[i].delete(j) != null)
		{
			numEdges--;
			Edges[j].delete(i);
		}
	}

	// returns the names of all the neighbors of a given vertex in an array of Strings
	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 new String[0];
        	}

		int[] neighborsIndices = getNeighbors(source);
		String[] neighbors = new String[neighborsIndices.length];

		for(int j = 0; j < neighbors.length; j++)
			neighbors[j] = Vertices[neighborsIndices[j]];
		
		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;
		}

		return Edges[i].size();
    	}

		
	// returns the degree of a vertex with given index
	public int degree(int index)
	{
		return Edges[index].size();
	}


    	// returns the indices of all the neighbors of a given vertex with index
    	public int[] getNeighbors(int index)
    	{
		return Edges[index].toArray();
    	}

	public void depthFirstTraversal(String source)
	{

		// Getting the index of the source vertex and
		// checking if the vertex really exists
		int sourceIndex = getIndex(source);
		if(sourceIndex == -1)
		{
			System.out.print("In depthFirstTraversal: vertex ");
			System.out.print(source);
			System.out.println(" is missing.");
			return;
		}

		// Defining and initializing the visited array
		boolean[] visited = new boolean[numVertices];
		for(int j = 0; j < numVertices; j++)
			visited[j] = false;	
		visited[sourceIndex] = true;
		
		// Defining and initializing the stack 
		Stack<Integer> s = new Stack<Integer>();
		s.push(new Integer(sourceIndex));

		// Initializing the depth first traversal tree
		dFTTree = new int[numVertices];
		for(int j = 0; j < numVertices; j++)
			dFTTree[j] = j;

		boolean more;
		do
		{
			// The traversal can go on while the stack 
			// contains a vertex to process
			while(!s.empty())
			{
				// Peek at the current vertex
				int currentVertex = (s.peek()).intValue();

				System.out.println(Vertices[currentVertex]);

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

				// Scan the neighbors of the current vertex, looking
				// for an unvisited neighbor
				int j = 0;
				boolean found = false;
				while (j < neighbors.length && !found)
				{
					// If an unvisited neighbor has been found,
					// then push it into the stack, mark it visited,
					// make the current vertex its parent,
					// and get out of the while-loop by setting found
					// to true
					if(!visited[neighbors[j]])	
					{
						s.push(new Integer(neighbors[j]));
						visited[neighbors[j]] = true;
						found = true;
						dFTTree[neighbors[j]] = currentVertex;
					}

					j++; // scan the next vertex
				}

				// If no unvisited vertices have been found, it is time
				// to backtrack
				if (!found)
					s.pop();
			} // end of while-stack-not-empty loop

			// Determine if there are more unvisited vertices
			// by scanning the visited array and looking for the
			// first unvisited vertex
			more = false;
			int j = 0;
			while(j < numVertices && !more)
			{
				if(!visited[j])
					more = true;
				j++;
			}	

			// Push a vertex from the next connected component
			// into the graph
			if(more)
				s.push(new Integer(j-1));

		}
		while(more);

	} // end of function

} // end of class