UAHCode/CPE212/Project_06/graph.cpp

#include "graph.h"


// Graph 
Graph::Graph()
// Constructor initializes vertices linked list to empty
{
    vertices = NULL;
}

//~Graph()
Graph::~Graph()
// For each VertexNode in the vertices list, Destructor deallocates all EdgeNodes before
// deallocating the VertexNode itself
{
    VertexNode* delV = vertices;
    EdgeNode* delE = delV->edgePtr;
    

    while (delV != NULL)
    {
        while (delE != NULL)
        {
            delE = NULL;
            delE = delE->nextPtr;
        }
        delV = NULL;
        delV = delV->nextVertex;
    }
}

// Graph::AddVertex() - adds vertex name to vertices array; assumes space is available
void Graph::AddVertex(string v)
{
    VertexNode* newVert = new VertexNode; // creates memeory for newVert
    newVert->vname = v;  // assigns the vertex name to v
    newVert->edgePtr = NULL; // sets edgePtr to NULL
    newVert->nextVertex = NULL; //  Sets nextVertex to NULL
}

// Graph::AddEdge() - adds edge from source to destination vertex with specified weight
//                    assuming source and destination are already in vertices array
void Graph::AddEdge(string s, string d, int w)
{
    VertexNode* Vertex_S = WhereIs(s);
    VertexNode* Vertex_D = WhereIs(d);

    // Initialize newEdge
    EdgeNode* newEdge = new EdgeNode;
    newEdge->destination = Vertex_D;
    newEdge->weight = w;
    newEdge->nextPtr = NULL;
    if (Vertex_S->edgePtr == NULL)
    {
        Vertex_S->edgePtr = newEdge;
    }
    else
    {
        // Go the the end of edgePtr and add the newEdge to it 
        while (Vertex_S->edgePtr->nextPtr != NULL)
        {
            Vertex_S->edgePtr = Vertex_S->edgePtr->nextPtr;
        }
        Vertex_S->edgePtr->nextPtr = newEdge;
    }
}

// Graph::IsPresent() - returns true if vertex in graph, false otherwise
bool Graph::IsPresent(string v)
{
    VertexNode* vertPresent = vertices;

    //Traverse vertices
    while (vertPresent != NULL)
    {
        if (vertPresent->vname == v)
            return true;  // found
        vertPresent = vertPresent->nextVertex; // advance through graph
    }
    
    // not found
    return false;
}

// WhereIs() - returns pointer to specified vertex, throws exception if vertex not present
VertexNode* Graph::WhereIs(string v)
{
    VertexNode* tempVertex = vertices;
    

    // If found
    while (tempVertex != NULL)
    {
        if (tempVertex->vname == v)
            return tempVertex;  // Found
        tempVertex = tempVertex->nextVertex;
    }
    
    // If not found
    throw GraphVertexNotFound();
}

// Graph::WeightIs() -- returns edge weight if it exists; otherwise, throws GraphEdgeNotFound
int Graph::WeightIs(string s, string d)
{
    VertexNode* sourceV = WhereIs(s);
    VertexNode* destV = WhereIs(d);

    // search through edge nodes
    while (sourceV->edgePtr != NULL)
    {
        if (sourceV->edgePtr->destination == destV)
        {
            return sourceV->edgePtr->weight;
        }
        sourceV->edgePtr = sourceV->edgePtr;
    }

    throw GraphEdgeNotFound();
}

void Graph::MarkVertex(string v)
{
    // MarkVertex()
    // Marks vertex V as visited
    VertexNode* vistedV = WhereIs(v);
    vistedV->mark = true;
}

// Graph::IsMarked() - returns mark status of vertex; assumes vertex is present
bool Graph::IsMarked(string v)
{
    VertexNode* markedV = WhereIs(v);
    return markedV->mark;
}

// Graph::GetToVertices() - returns a queue q of vertices adjacent to vertex named s
void Graph::GetToVertices(string s, queue<string>& q)
{
    VertexNode* tempV = WhereIs(s);
    tempV = tempV->nextVertex;

    while (tempV != NULL)
    {
        q.push(tempV->vname);
        tempV = tempV->nextVertex;
    }
}

// DepthFirstSearch() - Finds path through graph from start vertex to destination vertex
void Graph::DepthFirstSearch(string startVertex, string endVertex, queue<string>& path)
{
    stack<string> s;
    queue<string> q;
  
    if ( !( IsPresent(startVertex) && IsPresent(endVertex) ) )
        throw GraphVertexNotFound();
    
    bool found = false;
    string vertex;
    string item;

  // more here if required
}