import java.util.*;

public class myGraph
{
	protected String[] Vertices;	// 1-d array to store the vertices
	protected double[][] Edges;		// 2-d array to store adjacencies between vertices,
									// the value is the distance between the 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)	
	{			
		Vertices = new String[capacity];
		Edges = new double[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 double[i+1];			
			for(int j = 0; j < i; j++)
				Edges[i][j] = 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 the array of adjacencies. Can make it larger or smaller, depending
    // on what newSize is.
    protected double[][] resize(double[][] array, int newSize)
    {
        double[][] temp = new double[newSize][];
        int smallerSize = newSize;
        if(array.length < smallerSize)
        	smallerSize = array.length;

		for(int i = 0; i < newSize; i++)
		{
			temp[i] = new double[i+1];
        	for(int j = 0; j < i+1; j++)
			{
            	if (i < smallerSize)
					temp[i][j] = array[i][j];
				else
					temp[i][j] = 0;
			}
        }
        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
	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 (i>=j) Edges[i][j] = distance;
        else Edges[j][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;
		}

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

		for(int j = 0; j < i; j++)
		{
			// For every edge incident on vertex i, decrement numEdges
			if(Edges[i][j] > 0)
				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] > 0)
				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] = 0;

		numVertices--;

	}

	// 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] != 0)
        	{
        		Edges[i][j] = 0;
        		numEdges--;
        	}
        }
        else 
        {
        	if (Edges[j][i] != 0)
        	{
        		Edges[j][i] = 0;
        		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++)
		{
			double distance=0;
			if (j <= source) distance = Edges[source][j];
			else distance = Edges[j][source];
			
			if(distance > 0)
				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
	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] > 0)
            	numNeighbors++;
        
        for (int j = index+1; j < numVertices; j++)
        	if(Edges[j][index] > 0)
        		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++)
        {
        	double distance=0;
        	if (j <= index) distance = Edges[index][j];
			else distance = Edges[j][index];

        	if(distance > 0)
            	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 s = new Stack();
		s.push(new Integer(sourceIndex));

		// The traversal can go on while the stack 
		// contains a vertex to process
		while(!s.empty())
		{
			// Peek at the current vertex			
			int currentVertex = ((Integer)(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
				// 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;
				}

				j++;
			}

			if (!found)
				s.pop();
		} // end of while-stack-not-empty loop

	} // end of function

} // end of class