import java.util.*;

public class myGraph
{
	protected String[] Vertices;	// 1-d array to store the vertices
	protected boolean[][] Edges;	// 2-d boolean array to store adjacencies between vertices
	protected int[] dFTTree; 	// 1-d array to store parent info. in depth
					// first traversal tree

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

		for(int i = 0; i < capacity; i++)
			for(int j = 0; j < capacity; 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
	protected 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 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][newSize];

                int smallerSize = newSize;
                if(array.length < smallerSize)
                        smallerSize = array.length;

                for(int i = 0; i < newSize; i++)
                	for(int j = 0; j < newSize; j++)
			{
                        	if (i < smallerSize && j < 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(" 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
	public void addEdge(String vertex1, String vertex2)
	{
		int i = getIndex(vertex1);
		if(i == -1)
		{
			System.out.print("addEdge: ");
			System.out.print(vertex1);
			System.out.println(" does not exist.");
                        return;
                }

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

		Edges[i][j] = true;
		Edges[j][i] = true;
		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(" does not exist.");
			return;
		}

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

		for(int j = 0; j < numVertices; j++)
		{
			// For every edge incident on vertex i, decrement numEdges
			if(Edges[i][j])
				numEdges--;

			// Move the last row in the adj. matrix into the ith row
			Edges[i][j] = Edges[numVertices-1][j];
			Edges[numVertices-1][j] = false;

			// Move the last column in the adj. matrix into the ith column
			Edges[j][i] = Edges[j][numVertices-1];
			Edges[j][numVertices-1] = false;
		}

		numVertices--;

	}

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

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

		Edges[i][j] = false;
		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: ");
                        System.out.print(vertex);
                        System.out.println(" does not exist.");
                        return new String[0];
                }

		for(int j = 0; j < numVertices; j++)
		{
			
			if(Edges[source][j])
				neighbors[numNeighbors++] = new String(Vertices[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
	protected int degree(int vertex)
	{
                int numNeighbors = 0;

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

		return numNeighbors;	
	}

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

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

                return neighbors;
        }



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

		}
		while(more);

	} // end of function

} // end of class