import java.util.*;

/**
 * A class for a graph of words, with two words adjacent if and only if
 * they are the same length and differ in exacly one letter
 * All words must be converted to lower case before being inserted into the graph
 *
 * 
 * Used in HW07 of Boston University CAS CS 112, Fall 2011
 *
 *
 */
public class WordGraph implements Iterable<WordGraph.Vertex> {

    // ADD AND MODIFY CODE BELOW AS NEEDED


	// Inner classes
	/**
	 * A single vertex of WordGraph; can be constructed and modified
	 * only by the WordGraph class -- public methods are accessors only.
	 * Any methods that construct or modify are private
	 */
	public static class Vertex {
    
        
        /**
		 * @return The name of the vertex
		 */
		public String toString() {
			return ""; // MODIFY
		}
		
		public LinkedList<Vertex> getNeighbors () {
			return null; // MODIFY
		}
		
		public int getDegree () {
            return 0; // MODIFY
		}

	} // End of inner class Vertex


	private class VertexIterator implements Iterator<Vertex> {
		public boolean hasNext() {return false;} // MODIFY
		public Vertex next() {return null;} // MODIFY
		public void remove () {throw new UnsupportedOperationException();}
	}
	

	// Beginning of the WordGraph class itself

	/**
	 * Constructs a graph that can hold at most maxSize vertices
	 * (adding any more vertices will cause a costly reallocation)
	 * @param maxSize maximum number of anticipated vertices
	 */
	public WordGraph (int maxSize) {
		// FILL IN HERE
	}
	
	public Iterator<Vertex> iterator () {
		return new VertexIterator();
	}

	/**
	 * Adds a vertex to the graph, connecting it to its neighbors, and its neighbors to it
	 * Finds the neighbors by trying all possible one-letter substitutes
	 * addVertex calls must be on distinct vertices and in alphabetical order
	 * @param name the name of the vertex to be added, should be in lowercase
	 */
	public void addVertex(String name) {
        // FILL IN HERE
	}


	/**
	 * Finds a vertex by name in the graph
	 * @param name the name of the vertex 
	 * @return the vertex itself, or null if no vertex by such name is in the graph
	 */
	public Vertex find (String name) {
        // MODIFY
        return null;
	}


	/**
	 * Uses breadth-first-search to find the path with the fewest intermediate points
	 * from vertex begin to vertex end.  Returns a stack with begin on top,
	 * followed by nodes of the path in order, followed by end, if a path exists.
	 * Returns null if no path exists.
	 * 
	 * @param begin the node to start at
	 * @param end the node to end up at
	 * @return stack of the path from begin to end, with begin on top, or null if no path
	 */
	public Stack<Vertex> bfs(Vertex begin, Vertex end) {		
        return null; // MODIFY
	}
	
	
}