import java.util.*;

/**
    An abstract class to represent graphs, consistent
      with either an adjacency list or an adjacency matrix
      representation.
    There is no explicit constructor provided, so the
      subclass constructors are responsible for
      initializing the instance variables.
*/



public abstract class Graph
{

   // the set of vertices in the graph
   protected Collection vertices;


   // a mapping from vertex names
   //   to integer indices for the vertices
   protected HashMap vertexMap;


   /**
      @return the number of vertices in the graph
   */

   public int getNumberOfVertices()                                          {
	 return vertices.size();                                                 }


   /**
       This method returns a list of the connected
       components of the greph, assuming methods
       <code>findAccessible</code> that find and mark
       all other vertices in the same component as a
       given vertex, and <code>unmarkAll</code> to
       unmark each vertex.
       @return a collection of collections, each of
        which contains the vertices in a connected
        component of the graph.
   */
   /* The algorithm traverses the vertex set, looking
      for an unvisited vertex.  When it finds one, it
      collects and marks as visited all vertices
      adjacent to it, forming a collection of these
      vertices that represents a component.  It then
      adds this component into the output list.
      It assumes that the set of vertices is well-formed,
      so that no classCastException can arise when it
      is traversed.
   */

   public Collection getComponents()                  {
     LinkedList output=new LinkedList();
     Iterator it=vertices.iterator();
     unmarkAll();
     while (it.hasNext())                           {
       Vertex v=(Vertex) it.next();
       if (!v.isMarked())                         {
         Collection component=findAccessible(v);
         output.add(component);                   } }
     return output;                                   }



  /////////////// abstract methods ////////////////


  /** Adds an edge, with no cost information, to the graph.
      @param x the name of one vertex
        (the source vertex in the directed case)
      @param y the name the other vertex
        (the destination vertex in the directed case)
  */

   public abstract void addEdge(String x, String y);



  /** Adds an edge, with cost information, to the graph.
      If the cost is negative, no edge is to be added
      @param x the name of one vertex
        (the source vertex in the directed case)
      @param y the name the other vertex
        (the destination vertex in the directed case)
      @cost cost the cost of the edge
  */

   public abstract void addEdge(String x, String y, int cost);


   /**
      @param x a vertex
      @return a list of all vertices in the same connected
       component as the given vertex.  For digraphs,
       the components may be strong or weak, depending on
       the subclass.
   */

   protected abstract LinkedList findAccessible(Vertex x);


   /**
      This method unmarks every vertex in the graph
   */
   protected abstract void unmarkAll();

   };