I need help with my C++ list graph representation. I need help finishing the add
ID: 3583115 • Letter: I
Question
I need help with my C++ list graph representation. I need help finishing the add, remove, GetEdgeWeight and both of the traversal functions in the List Header and Implemented in the *.cpp File.
/*************************GraphInterface Header File*************************/
// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
// Listing 20-1.
/** An interface for the ADT undirected, connected graph.
@file GraphInterface.h */
#ifndef GRAPH_INTERFACE_
#define GRAPH_INTERFACE_
template
class GraphInterface
{
public:
/** Gets the number of vertices in this graph.
@return The number of vertices in the graph. */
virtual int getNumVertices() const = 0;
/** Gets the number of edges in this graph.
@return The number of edges in the graph. */
virtual int getNumEdges() const = 0;
/** Creates an undirected edge in this graph between two vertices
that have the given labels. If such vertices do not exist, creates
them and adds them to the graph before creating the edge.
@param start A label for the first vertex.
@param end A label for the second vertex.
@param edgeWeight The integer weight of the edge.
@return True if the edge is created, or false otherwise. */
virtual bool add(LabelType start, LabelType end, int edgeWeight) = 0;
/** Removes an edge from this graph. If a vertex is left with no other edges,
it is removed from the graph since this is a connected graph.
@param start A label for the vertex at the beginning of the edge.
@param end A label for the vertex at the end of the edge.
@return True if the edge is removed, or false otherwise. */
virtual bool remove(LabelType start, LabelType end) = 0;
/** Gets the weight of an edge in this graph.
@param start A label for the vertex at the beginning of the edge.
@param end A label for the vertex at the end of the edge.
@return The weight of the specified edge.
If no such edge exists, returns a negative integer. */
virtual int getEdgeWeight(LabelType start, LabelType end) const = 0;
/** Performs a depth-first search of this graph beginning at the given
vertex and calls a given function once for each vertex visited.
@param start A label for the beginning vertex.
@param visit A client-defined function that performs an operation on
or with each visited vertex. */
virtual void depthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;
/** Performs a breadth-first search of this graph beginning at the given
vertex and calls a given function once for each vertex visited.
@param start A label for the beginning vertex.
@param visit A client-defined function that performs an operation on
or with each visited vertex. */
virtual void breadthFirstTraversal(LabelType start, void visit(LabelType&)) = 0;
/** Destroys this graph and frees its assigned memory. */
virtual ~GraphInterface() { }
}; // end GraphInterface
#endif
/*************************List Header File*************************/
#ifndef List_GRAPH_
#define List_GRAPH_
#include
#include
#include
#include "GraphInterface.h"
using namespace std;
const int LargestSize = 25;
struct ListNode
{
int Weight;
int index;
ListNode * Next;
};
template
class List : public GraphInterface
{
private:
ListNode * VertexList;
int ListSize;
bool * VisitedVertex;
void ResetVisited();
void DFTHelper(LabelType start, void visit(LabelType&));
void BFTHelper(LabelType start, void visit(LabelType&));
public:
List();
List(int aSize);
~List();
int getNumVertices() const;
int getNumEdges() const;
bool add(LabelType start, LabelType end, int edgeWeight);
bool remove(LabelType start, LabelType end);
int getEdgeWeight(LabelType start, LabelType end) const;
void depthFirstTraversal(LabelType start, void visit(LabelType&));
void breadthFirstTraversal(LabelType start, void visit(LabelType&));
};
template class List;
#endif /* LIST_GRAPH_ */
/*************************Implementation File*************************/
#include "ListGraph.h"
template
List::List()
: VertexList(NULL), ListSize(LargestSize)
{
VertexList = new ListNode[LargestSize];
VisitedVertex = new bool[LargestSize];
ResetVisited();
for(int i = 0; i < LargestSize; i++)
{
VertexList[i].Weight = -1;
VertexList[i].index = -1;
VertexList[i].Next = NULL;
}
}
template
List::List(int aSize)
: VertexList(NULL), ListSize(aSize)
{
VertexList = new ListNode[ListSize];
VisitedVertex = new bool[ListSize];
ResetVisited();
for(int i = 0; i < ListSize; i++)
{
VertexList[i].Weight = -1;
VertexList[i].index = -1;
VertexList[i].Next = NULL;
}
}
void deleteList(ListNode &data)
{
ListNode * tempPtr = data.Next;
if(tempPtr != NULL)
{
deleteList(*tempPtr);
delete tempPtr;
tempPtr = NULL;
}
}
template
List::~List()
{
for(int i = 0; i < ListSize; i++)
{
deleteList(VertexList[i]);
}
delete[] VertexList;
}
template
int List::getNumVertices() const
{
int VertexCounter = 0;
for(int i = 0; i < ListSize; i++)
{
if(VertexList[i].Next != NULL)
{
++VertexCounter;
}
}
return (VertexCounter/2);
}
template
int List::getNumEdges() const
{
ListNode * tempPtr = VertexList[0].Next;
int EdgesCounter = 0;
for(int i = 0; i < ListSize; i++)
{
tempPtr = VertexList[i].Next;
while(tempPtr != NULL)
{
++EdgesCounter;
tempPtr = tempPtr->Next;
}
}
return (EdgesCounter/2);
}
template
bool List::add(LabelType start, LabelType end, int edgeWeight)
{
ListNode * tempPtr = start->Next;
if(start >= ListSize || start < 0 || end >= ListSize || end < 0 || edgeWeight < 0)
{
return false;
}
//temp ptr equal to start sub next
//while temp ptr is not null, move to tempPtr sub next
//Before a move, set a second ptr equal to where it is before it moves
//WHile looping through the list, check if tempPtr sub index equals end (if we have one, return false)
//Make a new node with temp and data objects index = end and weight equal to edgeweight
//After new node created, previous node points to new node
//loop again but start at 'END' in the first step
if(VertexList[start][end] < 0 && VertexList[end][start] < 0)
{
VertexList[start][end] = edgeWeight;
VertexList[end][start] = edgeWeight;
return true;
}
return false;
}
template
bool List::remove(LabelType start, LabelType end)
{
//Loop through until it's not null, when data is found that needs to be removed, previous ptr and a next ptr (leap frog)
//set previous ptr to point to current pointer's next
//Do the same but call it on the end
if(start >= ListSize || start < 0 || end >= ListSize || end < 0)
{
return false;
}
if(VertexList[start][end] < 0 && VertexList[end][start] < 0)
{
return false;
}
VertexList[start][end] = -1;
VertexList[end][start] = -1;
return true;
}
template
int List::getEdgeWeight(LabelType start, LabelType end) const
{
if(start >= ListSize || start < 0 || end >= ListSize || end < 0)
{
return -1;
}
return VertexList[start][end];
}
template
void List::DFTHelper(LabelType start, void visit(LabelType&))
{
visit(start);
VisitedVertex[start] = true;
for(int i = 0; i < ListSize; i++)
{
if(VertexList[start][i] >= 0)
{
if(!VisitedVertex[i])
{
DFTHelper(i, visit);
}
}
}
//ResetVisited();
}
template
void List::depthFirstTraversal(LabelType start, void visit(LabelType&))
{
DFTHelper(start, visit);
ResetVisited();
}
template
void List::BFTHelper(LabelType start, void visit(LabelType&))
{
int currentVertex;
queue vertexQueue;
vertexQueue.push(start);
visit(start);
VisitedVertex[start] = true;
while(!vertexQueue.empty())
{
currentVertex = vertexQueue.front();
vertexQueue.pop();
for(int i = 0; i < ListSize; i++)
{
if(VertexList[currentVertex][i] >= 0)
{
if(!VisitedVertex[i])
{
visit(i);
VisitedVertex[i] = true;
vertexQueue.push(i);
}
}
}
}
}
template
void List::breadthFirstTraversal(LabelType start, void visit(LabelType&))
{
BFTHelper(start, visit);
ResetVisited();
}
template
void List::ResetVisited()
{
for(int i = 0; i < ListSize; i++)
{
VisitedVertex[i] = false;
}
}
/*
template
void List::
{
}
*/
/*************************Main File*************************/
#include "ListGraph.h"
static void visit(int& index);
int main()
{
return 0;
}
static void visit(int& index)
{
cout << "Visiting Node: " << index << endl;
}
Explanation / Answer
The implementation you have done so far is absolutely fine.
Now all you need is to call the functions you have made in the main function.
For adding:
bool add(LabelType start, LabelType end, int edgeWeight){
Vertex<LabelType>* startVertex = findOrCreateVertex(start);
Vertex<LabelType>* endVertex = findOrCreateVertex(end);
startVertex->connect(end, edgeWeight);
endVertex->connect(start, edgeWeight);
numberOfEdges++; // Each bidirectional edge counts as a single edgereturn true;
}
For removing:
bool remove(LabelType start, LabelType end)
{
bool successful = false;
Vertex<LabelType>* startVertex = vertices.getItem(start);
Vertex<LabelType>* endVertex = vertices.getItem(end);
successful = startVertex->disconnect(end);
if (successful)
{
successful = endVertex->disconnect(start);
if (successful)
{
numberOfEdges--;
// If either vertex no longer has a neighbor, remove it
if (startVertex->getNumberOfNeighbors() == 0)
vertices.remove(start);
if (endVertex->getNumberOfNeighbors() == 0)
vertices.remove(end);
}
else
successful = false; // Failed disconnect from endVertex
}
else
successful = false; // Failed disconnect from startVertex
return successful;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.