import structure.*;
import java.util.Iterator;
import java.util.Collection;


public abstract class MyAbstractGraph implements MyGraph
{
	// returns the first vertex not visited
	protected int firstNotVisited( boolean[] visited, int size )
	{
		for( int i = 0; i < size; i++ )
		{
			if( visited[i] == false )
				return i;
		}
		
		return -1;
	}

	// traverse the vector starting at the vertex startAt
	public Vector depthFirstTraversal( Object startAt )
	{
		SinglyLinkedListElement listElement;
		int startIndex, size;
		boolean[] visited;
		Vector vec;
		
		size = numberOfVertices();
		vec = new Vector();
		if( size == 0 )
			return vec;
			
		// build a list of singly linked list elements
		for( int i = 0; i < size; i++ )
			vec.add( new SinglyLinkedListElement(null) );
			
		visited = new boolean[size];
		for( int i = 0; i < size; i++ )
			visited[i] = false;
		
		// start traversing at the start node
		startIndex = getIndex( startAt );    
                
		// after that, traverse from the first unvisited node
		while( startIndex != -1 )
		{
			listElement = (SinglyLinkedListElement)vec.get(startIndex);
			listElement.setValue( getMapItem(startIndex) );
			listElement.setNext( null );

			depthFirstTraversal( getMapItem(startIndex), visited, vec );
			startIndex = firstNotVisited( visited, size );		
		}
		
		return vec;
	}
	
	// the recursive version of above
	public void depthFirstTraversal( Object start, boolean[] visited, Vector vec )
	{
		SinglyLinkedListElement currentNbrElement;
		SinglyLinkedListElement thisElement;
		Object currentNbr;
		int currentNbrIndex;
		int thisIndex;
		
		// get the index and list element for the starting vertex
		thisIndex = getIndex( start );
		thisElement = (SinglyLinkedListElement)vec.get(thisIndex);

		// mark this vertex as visited
		visited[thisIndex] = true;

		// get all the neighbors of this vertex
		Vector nbrs = getNeighbors(start);
		int numNeighbors = nbrs.size();

		// set the value field of the current element to the start node
		thisElement.setValue( start );

		
		for( int i = 0; i < numNeighbors; i++ )
		{
			currentNbr = nbrs.get(i);
			currentNbrIndex = getIndex( currentNbr );

			if( !visited[getIndex(currentNbr)])
			{
				// get the list element for the neighbor we're about to traverse, and
				// set it's next (in this case, parent) field to the current element
				currentNbrElement = (SinglyLinkedListElement)vec.get( currentNbrIndex );
				currentNbrElement.setNext( thisElement );
			
				// do a recursive traversal from this new node
				depthFirstTraversal(currentNbr, visited, vec);
			}
		}
	}
}