//========================================================================
// Project by:                 PJ Waskiewicz
// Project:                    Directed Graphs with adjacency matrices
// File:                       graph.cc
// Purpose:                    Definitions of the templated graph
//
// Date:                       4/14/99
//
//
//
/* This is an implementation of a directed graph.
   This is a parametrized, or templated version
   of the graph data structure.  This implementation
   makes use of an adjacency matrix to
   implement the graph.
*/
//========================================================================


#include <iostream.h>
#include <assert.h>
#include "graph.h"

template <class T>
Graph<T>::Graph(){
  // The constructor for a new Graph
  // Postcondition: A new, empty graph.
  
  size = 0;
  for(int i = 0; i < MAX; i++)
    for(int j = 0; j < MAX; j++)
      matrix[i][j] = 0;
  for(int i = 0; i < MAX; i++)
    vertex[i] = "";
}

template <class T>
int Graph<T>::Size() const{
  // Returns the number of vertices in the Graph
  return size;
}

template <class T>
int Graph<T>::Adjacent(T &p, T &q){
  // Returns true if two vertices are "adjacent,"
  // or have one edge connecting them.
  //assert((p < size) && (q < size));
  int i = Find(p);
  int j = Find(q);
  return matrix[i][j];
}

template <class T>
void Graph<T>::DeleteVertex(T &p){
  int k = Find(p);
  assert(k < size);
  // Shift the i-th row up
  for(int i = k; i < size - 1; i++)
    vertex[i] = vertex[i + 1];
}

template <class T>
void Graph<T>::DeleteEdge(T &p, T &q){
  int i = Find(p);
  int j = Find(q);
  assert((i < size) && (q < size));
  matrix[i][j] = 0;
}

template <class T>
void Graph<T>::InsertVertex(T &p){
  int i = 0;
  // Find the next available position in the vertex array
  while(vertex[i] != "")
    i++;
  vertex[i] = p;
  size++;
}

template <class T>
void Graph<T>::InsertEdge(T &p, T &q){
  assert(p != q);
  int i = Find(p);
  int j = Find(q);
  assert((i < size) && (j < size));
  matrix[i][j] = 1;
}

template <class T>
int Graph<T>::Find(T &e) const{
  // Find function to get the course in question.
  for(int i = 0; i < size; i++)
    if(vertex[i] == e)
      return i;
}