//
// COMP102
// Example 6:  Undirected Graph Class
//              
// Paul E. Dunne 25/10/99
//
public class Graph
  {
  //
  // Fields
  //
  private Object [][] matrix;     // This will record the definition
                                  // of the Graph structure.
                                  //
                                  // N.B. Declaration as 2-D array of Object
                                  // so that the graph edges may be associated
                                  // with both primitive types (via Wrappers) and
                                  // Compound types. Typical instantiations might
                                  // be as Boolean (matrix[v][w] is TRUE if and
                                  // only if there is an edge between vertex v and
                                  // vertex w); Integer (so that the values stored
                                  // represent the `distance' separating two
                                  // vertices); String (so that edges are
                                  // associated with `text')
                                  //
  private int order;              // The number of vertices in this Graph Instance.
  private int size;               // The number of edges in this Graph Instance.
                                  // This value is dynmaically updated when
                                  // the effect of relevant Instance methods
                                  // results in a change in the size of the Graph.
                                  //
  private Object NonEdge = null;  // It is useful to have a distinctive value that
                                  // can indicate if no edge is present between 
                                  // {v,w} in the Graph. Here we give a default
                                  // setting to the null Object. In specific
                                  // instantiations, however, this could be set
                                  // appropriately depending on the application
                                  // used, e.g. as the Boolean FALSE if using the
                                  // basic Boolean representation above; as the
                                  // largest (smallest) possible Integer where
                                  // edges are associated with `distances'; as the
                                  // empty String ("") in a labelling context, etc.
  //***************************************************//
  // Constructor Definition                            //
  //***************************************************//
  // The single Constructor provided, allocates storage//
  // for an n-vertex Graph.                            //
  // The 2-dimensional array matrix[][] is configured  //
  // so that it comprises n-1 rows, the k'th row (k<n) //
  // containing exactly one fewer column than the      //
  // (k-1)'st                                          //
  //***************************************************//
  // Access and modification to this array can ONLY BE //
  // performed via the Instance methods defined below  //
  // cf. Presence of private modifier in the field     //
  // definition of matrix[][]                          //
  //***************************************************//
  public Graph(int n)
    {
    order = n; size=0;
    matrix = new Object[n-1][];       // the number of `rows' for n vertices
    //
    for (int i=0; i<n-1; i++)
      matrix[i] = new Object[n-i-1];  // the number of `columns' for each row.
    //
    for (int i=0; i<n-1; i++)
      for (int j=0; j<n-i-1; j++)
        matrix[i][j] = NonEdge;        // assumes no edges are present.
     }
  //*********************************************************************//
  //                    Instance Methods                                 //
  //*********************************************************************//
  // The following methods provide access to the settings of `simple'    //
  // Class fields.                                                       //
  //*********************************************************************//
  //  public int OrderOf() : Provides access to value of the order field //
  //                         i.e. the number of vertices in this Graph.  //
  //*********************************************************************//
  //  public int SizeOf()  : Access to the field holding the number of   //
  //                         edges in this Graph.                        //
  //*********************************************************************//
  //  public Object NoEdge(): Access the current setting of the Non-edge //
  //                          Object value.                              //
  //*********************************************************************//
  public int OrderOf()
    {
    return order;
    };
  //
  public int SizeOf()
   {
   return size;
   }
  //
  public Object NoEdge()
    {
    if (!(NonEdge==null))           // We have to test this, in order to
      return NonEdge;               // avoid a NullPointerException error
    else                            // which would occur in this
      return "null";                  // particular case.
    }
  //*********************************************************************//
  // Given two (distinct) vertices (v and w) with 1<= v,w <= order,      //
  // return true if this graph contains an edge connecting them.         //
  //*********************************************************************//
  // N.B. Applications using the Graph Class do not have to be aware of  //
  // the storage as a 2-dimensional array. In this, and other methods,   //
  // the values v and w are transalated to give the correct `cell' of    //
  // the 2-dimensional array structure indicating the current state of   //
  // the `edge' {v,w}.                                                   //
  //*********************************************************************//
  public boolean IsEdge( int v, int w)
    {
    if (v<w)
      return !(matrix[v-1][w-v-1]==NonEdge); // Data concerning vertex v
                                             // w.r.t `higher' numbered
                                             // vertices is in row `v-1'
    else
      return !(matrix[w-1][v-w-1]==NonEdge);
    }
  //*********************************************************************//
  // Change the setting of the Object used to indicate that an edge is   //
  // NOT present between two vertices updating the Graph representation  //
  // so that the new Object value is stored.                             //
  //*********************************************************************//
  public void SetNonEdgeValue ( Object no_edge )
    {
    if ( (no_edge.toString()).equalsIgnoreCase("null") ) // Can't pass null
      {                                      // reference directly and
      for (int i=1; i<order; i++)            // so we use the String encoding 
        for (int j=i+1; j<order+1; j++)      // to indicate this setting.
          if (!IsEdge(i,j))
            matrix[i-1][j-i-1] = null;
      NonEdge=null;                          // Do AFTER updating matrix[][]!
      }
    else
      {
      for (int i=1; i<order; i++)            // Same procedure but where a
        for (int j=i+1; j<order+1; j++)      // non-null setting is being used.
          if (!IsEdge(i,j))
            matrix[i-1][j-i-1] = no_edge;
      NonEdge = no_edge;
      };
    }
  //*********************************************************************//
  // The main Instance method for defining a particular graph structure. //
  //*********************************************************************//
  // This allows edges to be added to the Graph and to be removed:       //
  //  To add an edge {v,w} supply an edge setting that is different from //
  // the current NonEdge setting.                                        //
  // To remove an edge {v,w} invoke the method with edge_val instantiated//
  // to the current NonEdge Object value.                                //
  //*********************************************************************//
  public void SetEdge ( Object edge_val, int v, int w)
   {
   if (v==w) 
     matrix[v-1][w-v-1] = null;           // This is a bit clumsy. Will force an
                                          // ArrayOutofBoundsException, 
                                          // which is what's needed.
   else if (v<w) 
     {
     if (!IsEdge(v,w))                    // If there's no edge {v,w}
       {
       if ( !(edge_val.equals(NonEdge)) ) // and we're about to add it then
         {
         size = size+1;                   // the number of edges increases by 1.
         };
       }
     else                                // If there IS an edge {v,w}
       {
       if ( edge_val.equals(NonEdge) )   // and we're about to remove it then
         {
         size=size-1;                    // the number of edges decreases by 1.
         };
       };
     matrix[v-1][w-v-1] = new Object();  // Probably not needed (a precaution).
     matrix[v-1][w-v-1] = edge_val;      // Store the new value.
     }
   else
     this.SetEdge(edge_val,w,v);         // Can't expect applications to ensure
                                         // {v,w} are supplied with v<w so arrange
                                         // this properly.
                                         // Note that if v=w is NOT caught then
                                         // this Method will recurse indefinitely.
                                         // (Don't have to worry about this
                                         // in IsEdge(v,w)
                                         // because an Array bound exception
                                         // will be raised
                                         // by the run-time system if v=w).
   }
  //******************************************************************//
  // Obtain the value of the Object associated with edge {v,w}        //
  //******************************************************************//
  public Object GetEdge (int v, int w)
    {
   if (v==w) 
     return matrix[v-1][w-v-1];      // See similar remarks re. SetEdge
    else if (v<w)
      if (IsEdge(v,w))               // if there's a `real' edge then
        return matrix[v-1][w-v-1];   // just return the associated Object.
      else                           // If there's not a `real' edge
        if (NonEdge==null)           // have to make sure a NullPointerException
                                     // isn't generated.
          return "null";
        else
          return NonEdge.toString(); // Returns the current NonEdge object value.
    else
      return this.GetEdge(w,v);
    }
  //*********************************************************************//
  // Convert the Graph structure to a String form that is suitable for   //
  // output. The edges {v,w} are stored in a String in which newline     //
  // characters separate the different vertex details.                   //
  // The printing form is as order-1 distinct lines, the k'th line       //
  // containing exactly one fewer item than the (k-1)'st line. Hence     //
  //                                                                     //
  // Line 1: Status of edges {1,2} {1,3} {1,4} ... {1,order}             //
  //      2:                 {2,3} {2,4} {2,5} ... {2,order}             //
  //              ...                                                    //
  //      k:                 {k,k+1} {k,k+2}   ... {k,order}             //
  //              ...                                                    //
  //    order-1              {order-1,order}                             //
  //*********************************************************************//
  public String toString()
    {
    String res=new String();
    for (int i=1; i<order; i++)
      {
      for (int j=i+1; j<order+1; j++)
        {
        res = res+GetEdge(i,j).toString()+" ";
        };
        res = res+"\n";
      };
    return res;
    }
  }