C++ create test for the graphs in the header files in the main cpp file.

Thoroughly test each function of each class.

Test creating at least 20 vertices and 20 edges for each class.

// main.cpp //

#include "stdafx.h" #include "CSC382Graph_NodeBased.h" #include "CSC382Graph_AdjacencyList.h"

using namespace std;

bool Testing_NodeBased() { // Test CSC382Graph_NodeBased Constructor(s)

// Test functions of the CSC382Graph_NodeBased class and affiliated classes // Test creating lots of nodes and edges

return false; }

bool Testing_AdjacencyList() { // Test CSC382Graph_AdjacencyList Constructor(s)

// Test functions of the CSC382Graph_AdjacencyList class

// Test creating lots of nodes and edges return false; }

int main() { // Call testing functions

return 0; }

//////////////////////////////////

///NodeBased.h

#include "stdafx.h" #include #include #include

using namespace std;

template class CSC382Graph_Vertex { private: T data; list*>* connected_vertices; public: CSC382Graph_Vertex() { connected_vertices = new list*>(); data = NULL; }

CSC382Graph_Vertex(T node_data) { connected_vertices = new list*>(); data = node_data; }

~CSC382Graph_Vertex() { delete connected_vertices; }

void AddEdge(CSC382Graph_Vertex* vertex_connection) { if (vertex_connection != this) { connected_vertices->push_back(vertex_connection); } }

bool VertexConnected(CSC382Graph_Vertex* vertex_to_find) { for(CSC382Graph_Vertex* i : *connected_vertices) { if(i == vertex_to_find) { return true; } } return false; }

void RemoveEdge(CSC382Graph_Vertex* edge_to_remove) { if (edge_to_remove != nullptr) { connected_vertices->remove(edge_to_remove); } }

T GetData() { return data; }

void SetData(T data_param) { data = data_param; }

};

template class CSC382Graph_NodeBased { private: list*>* graph;

public: CSC382Graph_NodeBased() { graph = new list*>; }

CSC382Graph_NodeBased(CSC382Graph_Vertex* initial_vertex) { graph = new list*>; Insert(initial_vertex); }

~CSC382Graph_NodeBased() { for (CSC382Graph_Vertex* iter : *graph) { if (iter != nullptr && iter != NULL) { delete iter; } } delete graph; }

CSC382Graph_Vertex* Insert(CSC382Graph_Vertex* vertex) { graph->push_back(vertex); return vertex; }

CSC382Graph_Vertex* Insert(T data) { CSC382Graph_Vertex* new_node = new CSC382Graph_Vertex(data); return Insert(new_node); }

void RemoveVertex(T data) { CSC382Graph_Vertex* vertex_to_remove = FindVertex(data); RemoveVertex(vertex_to_remove); }

void RemoveVertex(CSC382Graph_Vertex* vertex_to_remove) { graph->remove(vertex_to_remove); }

void AddEdge(CSC382Graph_Vertex* start_vertex, CSC382Graph_Vertex* end_vertex) { start_vertex->AddEdge(end_vertex); }

void RemoveEdge(CSC382Graph_Vertex* start_vertex, CSC382Graph_Vertex* end_vertex) { start_vertex->RemoveEdge(end_vertex); }

bool IsEdge(CSC382Graph_Vertex* vertex_to_search_in, CSC382Graph_Vertex* edge_to_check_for) { return vertex_to_search_in->VertexConnected(edge_to_check_for); }

CSC382Graph_Vertex* FindVertex(T data_to_find) { for (CSC382Graph_Vertex* iter : *graph) { if (iter->GetData() == data_to_find) { return iter; } } return nullptr; }

CSC382Graph_Vertex* FindVertex(CSC382Graph_Vertex* node_to_find) { for(CSC382Graph_Vertex* iter : *graph) { if(iter == node_to_find) { return iter; } } return nullptr; }

int Size() { return graph->size(); } };

/////////////////////////////////////////////////

//AdjacencyList.h

#pragma once template class CSC382Graph_AdjacencyList { public: CSC382Graph_AdjacencyList() { graph_adjacencylist = new vector*>(); }

~CSC382Graph_AdjacencyList() { for (list* iter : *graph_adjacencylist) { if (iter != nullptr) { delete iter; } } delete graph_adjacencylist; }

list* AddVertex(T data) { // Attempt to find if (IsVertex(data)) { cout << "Vertex is already in the graph. Duplicate NOT added." << endl; return nullptr; } else {

list* new_vertex = new list(); // Create new list to house the vertex and its edges new_vertex->push_back(data); // Data is added as the first element in the list graph_adjacencylist->push_back(new_vertex); // list pointer is added to the graph return new_vertex; } }

bool AddEdge(list* vertex, T data) { if(!IsVertex(vertex)) { cout << "Vertex specified does not exist. Cannot add edge to a non-existant vertex." return false; } if (!IsVertex(data)) // Data must be an existing vertex or it will need to be created. { vertex->push_back(data); return true; } else { list* new_vertex = AddVertex(data); new_vertex->push_back(data); return true; } }

bool AddEdge(list* starting_vertex, list* ending_vertex) { if(!IsVertex(starting_vertex) || !IsVertex(ending_vertex)) { cout << "Cannot AddEdge because one of the specified vertices does not exist in the graph." << endl; return false; } if (!IsEdge(starting_vertex, ending_vertex->front())) // Prevent adding duplicate edges { starting_vertex->push_back(ending_vertex->front()); return true; } return false; }

bool IsVertex(T data) { for (list* iter : *graph_adjacencylist) { // Check the first value in the list which is the primary vertex if (iter->front() == data) { return true; } } return false; }

bool IsVertex(list* vertex_to_find) { for (list* iter : *graph_adjacencylist) { if (iter == vertex_to_find) { return true; } } return false; }

bool IsEdge(T edge_to_find) { for (list* iter : *graph_adjacencylist) { if (IsEdge(iter, edge_to_find)) { return true; } } return false; }

bool IsEdge(list* vertex, T edge_to_find) { for (T i : *vertex) { // skip checking the primary vertex and only check edges if (vertex->front() == i) { continue; } if (i == edge_to_find) { return true; } } return false; }

list* FindVertex(T data) { for (list* iter : *graph_adjacencylist) { if (iter->front() == data) { return iter; } } return nullptr; }

void PrintAdjacencyList() { for (list* iter : *graph_adjacencylist) { for (T i : *iter) { // skip checking the primary vertex and only check edges if (iter->front() == i) // Prints the Vertex { cout << "Vertex = " << i << " Edges = "; } else // Prints the Edges { cout << i << " "; } } cout << endl; } }

int NumberOfEdges(T vertex_data) { list* vertex = FindVertex(vertex_data);

if(vertex != nullptr) { return NumberOfEdges(vertex); } return -1; }

int NumberOfEdges(list* vertex) { return vertex->size(); }

int GraphSize() { return graph_adjacencylist->size(); }

private: vector*>* graph_adjacencylist; };