Please implement \"Insertvertext\" and \"InsertEdge\" //------------------------
ID: 3825825 • Letter: P
Question
Please implement "Insertvertext" and "InsertEdge"
//--------------------------------------------------------------------
//
// Laboratory 12 WeightedGraph.cpp
//
//--------------------------------------------------------------------
#ifndef WEIGHTEDGRAPH_CPP
#define WEIGHTEDGRAPH_CPP
using namespace std;
#include "WeightedGraph.h"
#include "config.h"
//--------------------------------------------------------------------
WeightedGraph::WeightedGraph(int maxNumber)
// Creates an empty graph. Allocates enough memory for maxNumber
// vertices (defaults to defMaxGraphSize).
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
WeightedGraph::WeightedGraph(const WeightedGraph& other)
// Creates an empty graph. Allocates enough memory for maxNumber
// vertices (defaults to defMaxGraphSize).
{
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
WeightedGraph& WeightedGraph:: operator= ( const WeightedGraph& other )
// Copies from another WeightedGraph.
{
return *this;
}
//--------------------------------------------------------------------
WeightedGraph:: ~WeightedGraph ()
// Frees the memory used by a graph.
{
}
//--------------------------------------------------------------------
void WeightedGraph:: insertVertex ( const Vertex& newVertex ) throw ( logic_error )
// 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.
{
}
//--------------------------------------------------------------------
void WeightedGraph:: insertEdge ( const string& v1, const string& v2, int wt )
throw ( logic_error )
// Insert an edge with the specified weight between vertices
// v1 and v2.
{
}
//--------------------------------------------------------------------
bool WeightedGraph:: retrieveVertex ( const string& 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.
{
return false;
}
//--------------------------------------------------------------------
bool WeightedGraph:: getEdgeWeight ( const string& v1, const string& v2, int &wt ) const
throw ( logic_error )
// 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.
{
return false;
}
//--------------------------------------------------------------------
void WeightedGraph:: removeVertex ( const string& v ) throw ( logic_error )
// Removes vertex v from a graph.
{
}
//--------------------------------------------------------------------
void WeightedGraph:: removeEdge ( const string& v1, const string& v2 ) throw ( logic_error )
// Removes the edge between vertices v1 and v2 from a graph.
{
}
//--------------------------------------------------------------------
void WeightedGraph:: clear ()
// Removes all the vertices and edges from a graph.
{
}
//--------------------------------------------------------------------
bool WeightedGraph:: isEmpty () const
// Returns 1 if a graph is empty. Otherwise, returns 0.
{
return (size == 0);
}
//--------------------------------------------------------------------
bool WeightedGraph:: isFull () const
// Returns 1 if a graph is full. Otherwise, returns 0.
{
return (size == maxSize);
}
//--------------------------------------------------------------------
void WeightedGraph:: showStructure () const
// Outputs a graph's vertex list and adjacency matrix. This operation
// is intended for testing/debugging purposes only.
{
if ( size == 0 ) {
cout << "Empty graph" << endl;
} else {
cout << endl << "Vertex list : " << endl;
for ( int row = 0 ; row < size ; row++ ) {
cout << row << ' ' << vertexList[row].getLabel();
#if LAB12_TEST2
cout << ' ' << vertexList[row].getColor();
#endif
cout << endl;
}
cout << endl << "Edge matrix : " << endl << ' ';
for ( int col = 0 ; col < size ; col++ )
cout << col << ' ';
cout << endl;
for ( int row = 0 ; row < size ; row++ )
{
cout << row << ' ';
for ( int col = 0 ; col < size ; col++ )
{
int wt = getEdge(row,col);
if ( wt == INFINITE_EDGE_WT )
cout << "- ";
else
cout << wt << ' ';
}
cout << endl;
}
}
}
//--------------------------------------------------------------------
//
// Facilitator functions
//
int WeightedGraph:: getIndex ( const string& v ) const
// Returns the adjacency matrix index for vertex v. Returns size if
// the vertex does not exist.
{
for (int j = 0; j < size; j++)
if (vertexList[j].getLabel() == v)
return j;
return -1;
}
//--------------------------------------------------------------------
int WeightedGraph:: getEdge ( int row, int col ) const
// Gets adjMatrix[row][col].
{
return -1;
}
void WeightedGraph:: setEdge ( int row, int col, int wt )
// sets adjMatrix[row][col].
{
}
#endif
Explanation / Answer
Implementation of "Insertvertext" and "InsertEdge" with explaination in the comments.
void WeightedGraph:: insertVertex ( const Vertex& newVertex ) throw ( logic_error )
// 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.
{
// Check if the vertex already exist in the graph.
int index = getIndex(newVertex.getLabel());
if (index < size) {
// vertex already exist in the graph. So update the vertex data.
vertexList[index] = newVertex;
} else {
// vertex doesn't exist. insert the new vertex into the graph
vertexList[size++] = newVertex;
}
}
void WeightedGraph:: insertEdge ( const string& v1, const string& v2, int wt )
throw ( logic_error )
// Insert an edge with the specified weight between vertices
// v1 and v2.
{
// Get indexes of the vertices.
int index1 = getIndex(v1);
int index2 = getIndex(v2);
// throw logic_error in case the vertices doesn't exist in the graph.
if (index1 == size || index2 == size) {
throw logic_error("Invalid Vertices: One or both vertices doesn't exist.");
}
// insert or set edge between the vertices.
setEdge(index1, index2);
}