import java.io.*;

/*
 * CGraph.java  --- mixed adjacency matrix / adjacency list implementation

   Author   Timothy Rolfe
            loosely based on Robert Sedgewick's Algorithms in C++

   CGraph classes in use:
   (1) CGraph   --- the map itself
   (2) CVertex  --- the cities in the map (in GrUtility.h)
   (3) CEdge    --- the roads connecting them (in GrUtility.h)

   The graph is represented by a vector of objects representing the
   vertices (cities in the map), and a matrix of objects representing
   the edges (roads connecting the cities).  These are considered to
   be parallal arrays:  subscript k refers to a particular city in
   the vertex array, and refers to the same city as row and column
   subscripts in the edge matrix.

   Each vertex contains a string with the town name and a int flag field
   for traversal.  Some algorithms may require additional entries
   (for instance, those required for the single-source shortest path
   determination by Dijkstra's algorithm).  The vertex also contains
   the reference of the first edge object in its adjacency list.

   The two-dimensional array contains objects representing the edges
   (roads in the map).  A null reference indicates that there is no
   edge connecting the two vertices.  Each edge object contains
   just an integer identifying the destination vertex, an integer
   giving the weight (length of the road between the two cities), and
   the reference to the next city in its adjacency list.  Conceivably it
   might have a string giving the highway name.

   Presumed input:
   (1) Number of vertices (cities)
   (2) THAT NUMBER of lines giving the city names
   (3) Remaining entries:  three fields:
       two vertex designations (city names) and the weight (road length).
   EOF marks the end of edge information

   Additional utility classes (in GrUtility.java):
   (1) CPair   --- an ordered pair to represent an edge (source,dest)
   (2) DeQueue --- double-ended queue, to be used either in stack
                   mode (depth-first) or queue mode (breadth-first)
   (3) MinHeap --- used by Prim's and Dijkstra's algorithms
   ___________________________________________________________

   Details about class CGraph

   Supported public functions:

      constructor --- default destructor only (empty graph)
      fillGraph receives the istream with the data
      nCities() and nRoads() --- "get" functions
      validCity(String) --- test whether the city is in the graph
      distance(String, String) --- distance between two cities if there
                                 is a road, else zero as error flag

   Assorted traversal functions and their utilities:

      depthRecur  Recursive implementation
      depth1st    User-stack-driven implementation
      breadth1st  Nearly identical, but with a queue, not a stack
      Prim        Prim's algorithm for minimum spanning tree
      Dijkstra    Dijkstra's algorithm for 1-source shortest path

      edgeList    List the edges used in the spanning tree

   Attributes

      Weight matrix: 2-D dynamic array of CEdge objects
      Array of vertices (holding city names)
      Array holding the sequence of edges
      Number of cities in the graph
      Number of roads
*/
public class CGraph
{//All fields initialized to 0/null.  No constructor required.

// ********************* instance-scope fields ********************* //

   protected CEdge[][] m_Road = null;   // Array of edges
   protected CVertex[] m_City = null;   // Array of vertices
   protected CPair[]   m_Sequence= null;// Sequence of edges
   protected int       m_Size = 0;      // Number of cities
   protected int       m_NRoads = 0;
   protected int       m_NextEdge = 0;  // Used in filling m_Sequence

// Class-scope constant:

   static final int UNVISITED=0;// Only used in CGraph