/* File: graph.cpp
 *
 * The local functions for graph abstract datatype implemented as a class
 */

#include "graph.h"                          // the interface

/*
 * Graph() - the constructor for the graph object.  Takes a size which is the
 *    number of vertices, allocates memory for the matrices and initializes
 *    the adjacency matrix to no edges.
 */
Graph::Graph(int size)
{
    int i, j;

    matrix  = new bool * [size];          // space for the adjacency matrix
    lengths = new int * [size];           // space for the length matrix
    for (i = 0; i < size; i++)
    {
        matrix[i]  = new bool[size];      // the rows of each matrix
        lengths[i] = new int[size];
        for (j = 0; j < size; j++)
            matrix[i][j] = false;         // initialize adjacency matrix
    }
    num_vertices = size;
}

/*
 * ~Graph() - the deconstructor.  Deallocates the space used by the matrices
 */
Graph::~Graph()
{
    int i;

    for (i = 0; i < num_vertices; i++)    // deallocate each row of a matrix
    {
        delete[] matrix[i];
        delete[] lengths[i];
    }

    delete[] matrix;                      // and deallocate the matrices
    delete[] lengths;
}

/*
 * add_edge() - add an edge from x to y with the given length
 */
void Graph::add_edge(int x, int y, int length)
{
    if (not_a_vertex(x) || not_a_vertex(y))  // check for an error
        throw Bad_vertex();
    matrix[x][y] = true;                     // an edge from x to y
    lengths[x][y] = length;                  // with the appropriage length
}

/*
 * is_adjacent() - returns true if there is an edge from x to y
 */
bool Graph::is_adjacent(int x, int y)
{
    if (not_a_vertex(x) || not_a_vertex(y))  // check for errors
        throw Bad_vertex();
    return matrix[x][y];                     // else return if there is an edge
}

/*
 * edge_length() - return the length of the edge from x to y
 */
int Graph::edge_length(int x, int y)
{
    if (not_a_vertex(x) || not_a_vertex(y))  // check for bad vertex
        throw Bad_vertex();
    if (!matrix[x][y])                       // or bad edge
        throw No_edge();
    return lengths[x][y];                    // else return length
}

/*
 * not_a_vertex() - returns true if x is not a legal vertex
 */
bool Graph::not_a_vertex(int x)
{
    return ((x < 0) || (x >= num_vertices)); // outside range of vertex values
}