//--------------------------------------------------------------------
//
//  Laboratory 14                                            wtgraph.C
//
//  SOLUTION: Adjacency matrix implementation of the Weighted
//            Graph ADT
//
//--------------------------------------------------------------------

#include <iostream.h>
#include <string.h>
#include <assert.h>
#include "wtgraph.h"

//--------------------------------------------------------------------

WtGraph:: WtGraph ( int maxNumber )

// Creates an empty graph. Allocates enough memory for maxNumber
// vertices (defaults to defMaxGraphSize).

  : maxSize(maxNumber),
    size(0)
{
    vertexList = new Vertex [ maxSize ];
    assert ( vertexList != 0 );

    adjMatrix = new int [ maxSize*maxSize ];
    assert ( adjMatrix != 0 );
}

//--------------------------------------------------------------------

WtGraph:: ~WtGraph ()

// Frees the memory used by a graph.

{
    delete [] vertexList;
    delete [] adjMatrix;
}

//--------------------------------------------------------------------

void WtGraph:: insertVertex ( Vertex newVertex )

// Inserts newVertex into a graph. If a vertex with the same label
// as newVertex already exists in the graph, then updates that
// vertex's data with newVertex's data.

{
    int pos,   // Position of the vertex in the vertex list
        j;     // Loop counter

    assert ( size != maxSize );   // Requires that graph is not full

    pos = index(newVertex.label);
    vertexList[pos] = newVertex;

    if ( pos == size )            // New vertex
    {
       size++;
       for ( j = 0 ; j < size ; j++ )
       {
           edge(size-1,j) = infiniteEdgeWt;
           edge(j,size-1) = infiniteEdgeWt;
       }
    }
}

//--------------------------------------------------------------------

void WtGraph:: insertEdge ( char *v1, char *v2, int wt )

// Insert an edge with the specified weight between vertices
// v1 and v2.

{
    int idx_v1 = index(v1),   // Index of vertex v1
        idx_v2 = index(v2);   // Index of vertex v2

    assert ( idx_v1 != size  &&  idx_v2 != size );

    edge(idx_v1,idx_v2) = wt;
    edge(idx_v2,idx_v1) = wt;
}

//--------------------------------------------------------------------

int WtGraph:: retrieveVertex ( char *v, Vertex &vData ) const

// Searches a graph for vertex v. If the vertex is found, then copies
// the vertex data to vData and returns 1. Otherwise, returns 0 with
// vData undefined.

{
    int pos,      // Position of the vertex in the vertex list
        result;   // Result returned

    pos = index(v);
    if ( pos != size )
    {
       vData = vertexList[pos];
       result = 1;
    }
    else
       result = 0;

    return result;
}

//--------------------------------------------------------------------

int WtGraph:: edgeWeight ( char *v1, char *v2, int &wt )

// If there is an edge connecting vertices v1 and v2, then returns 1
// with wt returning the weight of the edge. Otherwise, returns 0
// with wt undefined.

{
    int idx_v1 = index(v1),   // Index of vertex v1
        idx_v2 = index(v2);   // Index of vertex v2

    assert ( idx_v1 != size  &&  idx_v2 != size );

    wt = edge(idx_v1,idx_v2);
    return ( wt != infiniteEdgeWt );
}

//--------------------------------------------------------------------

void WtGraph:: removeVertex ( char *v )

// Removes vertex v from a graph.

{
    int idx_v = index(v),   // Index of vertex v
        j, k;               // Loop counters

    assert ( idx_v != size );

    for ( j = idx_v ; j < size-1 ; j++ )     // Shift vertex list up
        vertexList[j] = vertexList[j+1];

    for ( j = idx_v ; j < size-1 ; j++ )     // Shift rows up
        for ( k = 0 ; k < size ; k++ )
            edge(j,k) = edge(j+1,k);

    for ( j = idx_v ; j < size-1 ; j++ )     // Shift columns left
        for ( k = 0 ; k < size ; k++ )
            edge(k,j) = edge(k,j+1);

    size--;
}

//--------------------------------------------------------------------

void WtGraph:: removeEdge ( char *v1, char *v2 )

// Removes the edge between vertices v1 and v2 from a graph.

{
    int idx_v1 = index(v1),   // Index of vertex v1
        idx_v2 = index(v2);   // Index of vertex v2

    assert ( idx_v1 != size  &&  idx_v2 != size );

    edge(idx_v1,idx_v2) = infiniteEdgeWt;
    edge(idx_v2,idx_v1) = infiniteEdgeWt;
}

//--------------------------------------------------------------------

void WtGraph:: clear ()

// Removes all the vertices and edges from a graph.

{
    size = 0;
}

//--------------------------------------------------------------------

int WtGraph:: empty () const

// Returns 1 if a graph is empty. Otherwise, returns 0.

{
    return ( size == 0 );
}

//--------------------------------------------------------------------

int WtGraph:: full () const

// Returns 1 if a graph is full. Otherwise, returns 0.

{
    return ( size == maxSize );
}

//--------------------------------------------------------------------

void WtGraph:: showStructure ()

// Outputs a graph's vertex list and adjacency matrix. This operation
// is intended for testing/debugging purposes only.

{
    int wt,         // Edge weight
        row, col;   // Loop counters

    if ( size == 0 )
       cout << "Empty graph" << endl;
    else
    {
       cout << endl << "Vertex list : " << endl;
       for ( row = 0 ; row < size ; row++ )
           cout << row << '\t' << vertexList[row].label << endl;

       cout << endl << "Edge matrix : " << endl << '\t';
       for ( col = 0 ; col < size ; col++ )
           cout << col << '\t';
       cout << endl;
       for ( row = 0 ; row < size ; row++ )
       {
           cout << row << '\t';
           for ( col = 0 ; col < size ; col++ )
           {
               wt = edge(row,col);
               if ( wt == infiniteEdgeWt )
                  cout << "- \t";
               else
                  cout << wt << '\t';
           }
           cout << endl;
       }
    }
}

//--------------------------------------------------------------------
//
//  Facilitator functions
//

int WtGraph:: index ( char *v ) const

// Returns the adjacency matrix index for vertex v. Returns size if
// the vertex does not exist.

{
    int j;  // Loop counter

    for ( j = 0 ;
          j < size  &&  strcmp(vertexList[j].label,v) != 0 ;
          j++ );
    return j;
}

//--------------------------------------------------------------------

int& WtGraph:: edge ( int row, int col )

// Gets/sets adjMatrix[row][col].

{
    return adjMatrix[maxSize*row+col];
}

//--------------------------------------------------------------------
//
//                         In-lab operation
//
//--------------------------------------------------------------------