Multi Connected Graph in C++ Assignment Sample
You need to complete the functions in the classes provided. It uses STL vectors rather than fixed-sized arrays, so you don’t need to worry about allocating additional space. You need to add test functions in the grader class to check for an exact match, an unordered match, and iterators for the set of neighbors, and edges. It is not necessary for the neighbor iterator to return the neighbors in any particular order. You are required to check for all the error cases listed in errors.txt and will receive marks for each error detected correctly. The testCSRExact checks for the column and row order which should be in increasing order. The testCSRUnordered checks without considering the ordering of the rows and columns. More C++ assignment help can be provided if you contact us for details.
Solution:
BaselineGraph.cpp
#include
#include “BaselineGraph.h”
namespace Baseline
{
//graph constructor
Graph::Graph(int n)
{
if (n <= 0)
throw std::out_of_range(“The argument must be more than 0”);
m_re.resize(n + 1, 0);
m_numVert = n;
m_numEdge = 0;
currEdge = 0;
}
//return graph vertex
int Graph::numVert()
{
return m_numVert;
}
//return graph edge
int Graph::numEdge()
{
return m_numEdge / 2;
}
//add edge (u,v) to graph with weight x
void Graph::addEdge(int u, int v, int x)
{
if ((v < -1) || (v > m_numVert – 1) || (u < 0) || (u > m_numVert – 1)) {
throw std::out_of_range(“(u, v) must lower than number of vertices and >= 0”);
}
// check for already existing data
for (int i = m_re[u]; i < m_re[u + 1]; i++)
{
if (m_ci[i] == v)
{
m_nz[i] = x;
// do it for (v,u) as well
for (int j = m_re[v]; j < m_re[v + 1]; j++)
{
if (m_ci[j] == u)
{
m_nz[j] = x;
break;
}
}
return; // no need to proceed further
}
}
//the edge does not exist yet
//Insert u
int k = m_re[u + 1];
for (int i = m_re[u]; i < m_re[u + 1]; ++i) {
if (m_ci[i] > v) {
k = i;
break;
}
}
//insert till k
m_nz.insert(m_nz.begin() + k, x);
m_ci.insert(m_ci.begin() + k, v);
for (int i = u + 1; i != m_numVert + 1; ++i)
m_re[i]++;
m_numEdge++;
//Insert v
k = m_re[v + 1];
for (int i = m_re[v]; i < m_re[v + 1]; ++i) {
if (m_ci[i] > u) {
k = i;
break;
}
}
m_nz.insert(m_nz.begin() + k, x);
m_ci.insert(m_ci.begin() + k, u);
for (int i = v + 1; i != m_numVert + 1; ++i)
m_re[i]++;
m_numEdge++;
}
//dump graph info
void Graph::dump()
{
std::cout << “Dump of graph (numVert = ” << numVert() << “, numEdge = ” << numEdge() << “)” << std::endl;
std::cout << “m_re:”;
//m_re info
for (int i = 0; i < m_numVert + 1; i++)
{
std::cout << ” ” << m_re[i];
}
std::cout << std::endl;
//m_mz info
std::cout << “m_nz:”;
for (int i = 0; i < m_numEdge; i++)
{
if (m_nz[i] > 0)
{
std::cout << ” ” << m_nz[i];
}
}
std::cout << std::endl;
//m_ci info
std::cout << “m_ci:”;
for (int i = 0; i < m_numEdge; i++)
{
if (m_ci[i] >= 0)
{
std::cout << ” ” << m_ci[i];
}
}
std::cout << std::endl;
}
//neighbor != operator
bool Graph::NbIterator::operator!=(const NbIterator &r)
{
return m_indx != r.m_indx;
}
//neighbor ++ operator
void Graph::NbIterator::operator++(int dummy)
{
NbIterator EndofITR = m_Gptr->nbEnd(m_row);
if (m_indx != EndofITR.m_indx)
m_indx++;
}
//neighbor * operator
int Graph::NbIterator::operator*()
{
NbIterator EndofITR = m_Gptr->nbEnd(m_row);
if (m_indx >= EndofITR.m_indx)
{
throw(std::out_of_range(“iterator out of range”));
}
return m_Gptr->m_ci[m_indx];
}
//neighbor end
Graph::NbIterator Graph::nbEnd(int v)
{
return NbIterator(this, v, m_re[v + 1]);
}
//Edge iterator
Graph::EgIterator::EgIterator(Graph *Gptr, int indx)
{
m_Gptr = Gptr;
int i, j, n = 0;
if (Gptr)
{
m_indx = indx;
m_row = 0;
for (i = 0; i != Gptr->m_numVert; i++)
{
for (j = Gptr->m_re[i]; j < Gptr->m_re[i + 1]; j++)
{
if (i < Gptr->m_ci[j]) {
if (n == m_indx) {
m_row = i;
return;
}
++n;
}
}
}
}
}
//edge != operator
bool Graph::EgIterator::operator!=(const EgIterator &rhs)
{
return m_indx != rhs.m_indx;
}
//edge ++ operator
void Graph::EgIterator::operator++(int dummy)
{
EgIterator endIt = m_Gptr->egEnd();
if (m_indx != endIt.m_indx)
m_indx++;
}
//edge * operator
std::tuple Graph::EgIterator::operator*()
{
EgIterator endIt = m_Gptr->egEnd();
if (m_indx >= endIt.m_indx)
throw std::out_of_range(“The iterator is out of range”);
int n = 0, i, j;
for (i = 0; i != m_Gptr->m_numVert; i++)
{
for (j = m_Gptr->m_re[i]; j != m_Gptr->m_re[i + 1]; j++)
{
if (i < m_Gptr->m_ci[j])
{
if (n == m_indx)
return std::make_tuple(i, m_Gptr->m_ci[j], m_Gptr->m_nz[j]);
++n;
}
}
}
return std::make_tuple(0, 0, 0);
}
//neighbor constructor
Graph::NbIterator::NbIterator(Graph *Gptr, int v, int indx)
{
m_Gptr = Gptr;
m_row = v;
m_indx = indx;
}
//edge begin
Graph::EgIterator Graph::egBegin()
{
return EgIterator(this, 0);
}
//edge end
Graph::EgIterator Graph::egEnd()
{
EgIterator endIt(this, m_numEdge / 2);
currEdge = 0;
return endIt;
}
//neighbor begin
Graph::NbIterator Graph::nbBegin(int v)
{
return NbIterator(this, v, m_re[v]);
}
} // namespace Baseline
BaselineGraph.h
#ifndef _BASELINEGRAPH_H_
#define _BASELINEGRAPH_H_
#include // For throwing out_of_range exceptions
#include // Edges are represented as tuple
#include // m_nz, m_ci, and m_re are of type vector
class Grader; // Forward declaration needed for ‘friend’
namespace Baseline {
class Graph {
public:
friend Grader; // Allows Grader class to access private variables
// Graph constructor; must give number of vertices
Graph(int n);
// return number of vertices
int numVert();
// return number of edges
int numEdge();
// add edge between u and v with weight x
void addEdge(int u, int v, int x);
// print out data structure for debugging
void dump();
// Edge Iterator inner class
class EgIterator {
public:
// Edge Iterator constructor; indx can be used to
// set m_indx for begin and end iterators.
EgIterator(Graph *Gptr = nullptr, int indx = 0);
// Compare iterators; only makes sense to compare with
// end iterator
bool operator!= (const EgIterator& rhs);
// Move iterator to next printable edge
void operator++(int dummy); // post increment
// return edge at iterator location
std::tuple operator*();
private:
Graph *m_Gptr; // pointer to associated Graph
int m_indx; // index of current edge in m_nz
int m_row; // corresponding row of m_nz[m_indx]
};
// Make an initial edge Iterator
EgIterator egBegin();
// Make an end iterator for edge iterator
EgIterator egEnd();
// Neighbor Iterator inner class
class NbIterator {
public:
// Constructor for iterator for vertices adjacent to vertex v;
// indx can be used to set m_indx for begin and end iterators
NbIterator(Graph *Gptr = nullptr, int v = 0, int indx = 0);
// Compare iterators; only makes sense to compare with
// end iterator
bool operator!=(const NbIterator& rhs);
// Move iterator to next neighbor
void operator++(int dummy);
// Return neighbor at current iterator position
int operator*();
private:
Graph *m_Gptr; // pointer to the associated Graph
int m_row; // row (source) for which to find neighbors
int m_indx; // current index into m_nz of Graph
};
// Make an initial neighbor iterator
NbIterator nbBegin(int v);
// Make an end neighbor iterator
NbIterator nbEnd(int v);
private:
std::vector m_nz; // non-zero elements array
std::vector m_ci; // column index array
std::vector m_re; // row extent array
int currEdge;
int m_numVert; // number of vertices
int m_numEdge; // number of edges
};
}
#endif
Grader.cpp
#include “Grader.h”
#include “BaselineGraph.h”
#include “Graph.h”
#include
//Grader constructor
Grader::Grader(string name) {
m_name = name;
}
//reseting queue so popping error
void Grader::resetErrorQueue() {
while (!m_errors.empty())
m_errors.pop();
}
//print all errors
void Grader::printAllErrors(){
int sum = 0;
while (!m_errors.empty()) {
cout << m_errors.front() << endl; //print queue from front
sum += m_errors.front().getDeduction(); //adding total deduction
m_errors.pop();
}
//show total deductions
cout << endl << “Total Deductions: ” << sum;
}
// Formatted output of Error object:
// deduction: (id) description
ostream& operator<<(ostream& outStream, const Error& err) {
//writting error description
if (err.m_deduction > 0) {
outStream << “-” << err.m_deduction << “: (” << err.m_id
<< “) ” << err.m_description;
}
else
{ //writting error description
outStream << err.m_deduction << “: (” << err.m_id
<< “) ” << err.m_description;
}
return outStream;
}
// define testCSRExact fn
bool Grader::testCSRExact(int numVert, vector edgeSeq) {
Graph IGraph(numVert);
Baseline::Graph BGraph(numVert);
int i = 0;
set errors;
//edge seq started
for (vector::iterator it = edgeSeq.begin(); it != edgeSeq.end(); ++it) {
//add edges to both graph IGraph,BGraph
IGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
BGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
//if error not found then check
if (errors.find(101) == errors.end()) {
//loop till number of vertics
for (i = 0; i <= numVert; ++i) {
//if m_re not same
if (IGraph.m_re[i] != BGraph.m_re[i]) {
///push error info
m_errors.push(Error(5, 101, “Incorrect values in m_re”));
errors.insert(101);
break;
}
}
}
//if error not found then check
if (errors.find(102) == errors.end()) {
//loop till number of edge
for (i = 0; i < BGraph.m_numEdge; ++i) {
//if m_nz not same
if (IGraph.m_nz[i] != BGraph.m_nz[i]) {
///push error info
m_errors.push(Error(5, 102, “Incorrect values in m_nz”));
errors.insert(102);
break;
}
}
}
//if error not found then check
if (errors.find(103) == errors.end()) {
//loop till number of edge
for (i = 0; i < BGraph.m_numEdge; ++i) {
//if m_ci not same
if (IGraph.m_ci[i] != BGraph.m_ci[i]) {
///push error info
m_errors.push(Error(5, 103, “Incorrect values in m_ci”));
errors.insert(103);
break;
}
}
}
}
//if no error
if (errors.empty())
m_errors.push(Error(0, 100, “No errors in testCSRExact()”));
//return error as empty
return errors.empty();
return true;
}
bool Grader::testCSRUnordered(int numVert, vector edgeSeq) {
Graph IGraph(numVert);
Baseline::Graph BGraph(numVert);
int i = 0;
set errors;
//edge seq started
for (vector::iterator it = edgeSeq.begin(); it != edgeSeq.end(); ++it) {
//add edges to both graph IGraph,BGraph
IGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
BGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
///loop till number of vertics
for (int i = 0; i <= numVert; ++i) {
//if m_re not match
if (IGraph.m_re[i] != BGraph.m_re[i]) {
//push error info
m_errors.push(Error(10, 201, “Incorrect m_re; cannot perform unordered test”));
return false;
}
}
///loop till number of vertics
for (int uVetex = 0; uVetex < numVert; ++uVetex) {
set colsIGraph; //col of IGraph
set colsBGraph; //col of BGraph
//inserting col of every edge into both set
for (int vVetex = BGraph.m_re[uVetex]; vVetex < BGraph.m_re[uVetex + 1]; ++vVetex) {
colsIGraph.insert(IGraph.m_ci[vVetex]);
colsBGraph.insert(BGraph.m_ci[vVetex]);
}
//if cols not match
if (colsIGraph != colsBGraph) {
//push info
m_errors.push(Error(10, 202, “Failure of undordered test of CSR”));
return false;
}
}
}
//no error
if (errors.empty())
m_errors.push(Error(0, 200, “No errors in testCSRUnordered()”));
return errors.empty();
return true;
}
bool Grader::testNbIterator(int numVert, vector edgeSeq) {
Graph IGraph(numVert);
Baseline::Graph BGraph(numVert);
int i = 0;
set errors;
//error seq start to end
for (vector::iterator it = edgeSeq.begin(); it != edgeSeq.end(); ++it) {
//add edges to both graph IGraph,BGraph
IGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
BGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
}
//loop till vertex
for (int i = 0; i < numVert; ++i) {
set setIGraph;
set setBGraph;
//insert neighbour info of both type graph
for (Graph::NbIterator itr = IGraph.nbBegin(i); itr != IGraph.nbEnd(i); itr++)
setIGraph.insert(*itr);
for (Baseline::Graph::NbIterator itr = BGraph.nbBegin(i); itr != BGraph.nbEnd(i); itr++)
setBGraph.insert(*itr);
//graph set size not same then push error info
if (errors.find(301) == errors.end()) {
if (setIGraph.size() != setBGraph.size()) {
m_errors.push(Error(5, 301, “Incorrect neighbor set size”));
errors.insert(3001);
}
}
if (errors.find(302) == errors.end()) {
//if value of neighbour not same
if (setIGraph != setBGraph) {
m_errors.push(Error(5, 302, “Incorrect values from neighbor iterator”));
errors.insert(302);
}
}
}
//no error
if (errors.empty())
m_errors.push(Error(0, 300, “No errors in testNbIterator()”));
return errors.empty();
return true;
}
bool Grader::testEgIterator(int numVert, vector edgeSeq) {
Graph IGraph(numVert);
Baseline::Graph BGraph(numVert);
int i = 0;
//error seq start to end
set errors;
for (vector::iterator it = edgeSeq.begin(); it != edgeSeq.end(); ++it)
{ //add edges to both graph IGraph,BGraph
IGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
BGraph.addEdge(get<0>(*it), get<1>(*it), get<2>(*it));
}
multiset EdgeIGraph;
multiset EdgeBGraph;
//inserting edge to both graph
for (Graph::EgIterator eit = IGraph.egBegin(); eit != IGraph.egEnd(); eit++)
EdgeIGraph.insert(*eit);
for (Baseline::Graph::EgIterator eit = BGraph.egBegin(); eit != BGraph.egEnd(); eit++)
EdgeBGraph.insert(*eit);
//if edge size of both graph not same then push error info
if (errors.find(401) == errors.end()) {
if (EdgeIGraph.size() != EdgeBGraph.size()) {
m_errors.push(Error(5, 401, “Incorrect edge set size”));
errors.insert(401);
}
}
//if edge are not same in both graph then push error info
if (errors.find(402) == errors.end()) {
for (multiset::iterator it = EdgeIGraph.begin(); it != EdgeIGraph.end(); it++) {
if (EdgeBGraph.count(*it) + EdgeBGraph.count(Edge(get<1>(*it), get<0>(*it), get<2>(*it))) == 1)
continue;
m_errors.push(Error(5, 402, “Incorrect values from edge iterator”));
errors.insert(402);
break;
}
}
//no error
if (errors.empty())
m_errors.push(Error(0, 400, “No errors in testEgIterator()”));
return errors.empty();
return true;
}
bool Grader::testExceptions(int numVert, vector edgeSeq) {
bool bIsExceptionNotOccur = true;
try {
//create graph with n=0
Baseline::Graph BGraph(0);
//push error info
m_errors.push(Error(5, 511, “Constructor with n = 0 did not throw an exception”));
}
catch (const std::out_of_range& oor){
//push error info
m_errors.push(Error(0, 510, “No errors in testExceptions(), construtor with n = 0”));
bIsExceptionNotOccur = false;
}
catch (…) {
//push error info
m_errors.push(Error(2, 512, “Constructor with n = 0 threw incorrect exception”));
bIsExceptionNotOccur = false;
}
try {
//create graph with n=-10
Baseline::Graph BGraph(-10);
//push error info
m_errors.push(Error(5, 521, “Constructor with n < 0 did not throw an exception”));
}
catch (const std::out_of_range& oor){
//push error info
m_errors.push(Error(0, 520, “No errors in testExceptions(), construtor with n < 0”));
bIsExceptionNotOccur = false;
}
catch (…) {
//push error info
m_errors.push(Error(2, 522, “Constructor with n < 0 threw incorrect exception”));
bIsExceptionNotOccur = false;
}
try {
//create graph with n=numVert and edge destination not valid
Baseline::Graph BGraph(numVert);
BGraph.addEdge(0, -10, 1);
BGraph.addEdge(0, numVert + 1, 1);
//push error info
m_errors.push(Error(5, 531, “addEdge() with bad destination vertex did not throw an exception”));
}
catch (const std::out_of_range& oor){
//push error info
m_errors.push(Error(0, 530, “No errors in testExceptions(), addEdge() with bad destination vertex”));
bIsExceptionNotOccur = false;
}
catch (…) {
//push error info
m_errors.push(Error(2, 532, “addEdge() with bad destination vertex threw incorrect exception”));
bIsExceptionNotOccur = false;
}
try {
//create graph with n=numVert and edge source not valid
Baseline::Graph BGraph(numVert);
BGraph.addEdge(-10, 0, 10);
BGraph.addEdge(numVert + 1, 0, 1);
//push error info
m_errors.push(Error(5, 541, “addEdge() with bad source vertex did not throw an exception”));
}
catch (const std::out_of_range& oor){
//push error info
m_errors.push(Error(0, 540, “No errors in testExceptions(), addEdge() with bad source vertex”));
bIsExceptionNotOccur = false;
}
catch (…) {
//push error info
m_errors.push(Error(2, 542, “addEdge() with bad source vertex threw incorrect exception”));
bIsExceptionNotOccur = false;
}
try {
//create graph with n=numVert and end iterator
Baseline::Graph BGraph(numVert);
*(BGraph.nbEnd(0));
//push error info
m_errors.push(Error(5, 551, “Dereference of neighbor end iterator threw no exception”));
}
catch (const std::out_of_range& oor){
//push error info
m_errors.push(Error(0, 550, “No errors in testExceptions(), dereference of neighbor end iterator”));
bIsExceptionNotOccur = false;
}
catch (…) {
//push error info
m_errors.push(Error(2, 552, “Dereference of neighbor end iterator threw incorrect exception”));
bIsExceptionNotOccur = false;
}
try {
//create graph with n=numVert and end edge iterator
Baseline::Graph BGraph(numVert);
*(BGraph.egEnd());
//push error info
m_errors.push(Error(5, 561, “Dereference of edge end iterator threw no exception”));
}
catch (const std::out_of_range& oor){
//push error info
m_errors.push(Error(0, 560, “No errors in testExceptions(), dereference of edge end iterator”));
bIsExceptionNotOccur = false;
}
catch (…) {
//push error info
m_errors.push(Error(2, 562, “Dereference of edge end iterator threw incorrect exception”));
bIsExceptionNotOccur = false;
}
//is exception occur or not return
return bIsExceptionNotOccur;
}
Grader.h
// File: Grader.h
//
// CMSC 341 Spring 2019
//
// Header file for Grader class
//
#ifndef _GRADER_H
#define _GRADER_H
#include
#include // for throwing out_of_range exceptions
#include // Edges are respresented as tuple
#include // Errors and decuctions are saved in a queue
#include // Vectors are used to store Edge sequences and
// may be used in test implementations
#include // Sets may be used in test implementations
using namespace std;
typedef tuple Edge; // Edge type definition
// Error – a small class to organize error messages and deductions.
// Defined in-line.
class Error {
public:
// Constructor. deductions must be >= 0
Error(int deduct = 0, int id = 0, string description = “”) {
if (deduct < 0) {
throw std::out_of_range(“deduction for error must be non-negative”);
}
m_deduction = deduct;
m_id = id;
m_description = description;
}
// deduction getter
int getDeduction() { return m_deduction; }
// id getter
int getId() { return m_id; }
// description getter
string getDescription() { return m_description; }
// formatted output of Errors
friend ostream& operator<<(ostream& outStream, const Error& err);
private:
int m_deduction; // points to deduct
int m_id; // id number of error
string m_description; // description of error
};
class Grader {
public:
// Constructor; may provide optional descriptive name
Grader(string name = “”);
// In the following test functions, the parameters are:
//
// int numVert: number of vertices in test graph
//
// vector edgeSeq: a sequence of edges to insert in the
// graph
// Test for *exact* correctness of m_re, m_nz, and m_ci. Assume
// that m_re is initialized to all zeroes
bool testCSRExact(int numVert, vector edgeSeq);
// Test for *unordered* correctness of m_re, m_nz, and m_ci. An
// implementation passes if (1) the values in m_re are correct, and
// (2) the values in m_nz and m_ci for each row are correct, but not
// necessarily ordered by increasing m_ci values.
bool testCSRUnordered(int numVert, vector edgeSeq);
// Test that for *every* vertex in the Graph, NbIterator produces
// the correct list of neighbor vertices.
bool testNbIterator(int numVert, vector edgeSeq);
// Test that the edge iterator returns the correct list of edges.
// Each edge should occur exactly once even though it is represented
// twice in the data structure; that is, only one of (u, v, w) and
// (v, u, w) should be included in the list produced by the
// iterator.
bool testEgIterator(int numVert, vector edgeSeq);
// Test that operations that are supposed to throw an out_of_range
// exception do so.
bool testExceptions(int numVert, vector edgeSeq);
// Print all the deductions and errors in the error queue and total
// deductions. The queue should be empty after the call.
void printAllErrors();
// Clear the error queue
void resetErrorQueue();
private:
string m_name; // Optional descriptive name
std::queue m_errors; // Queue to hold errors and
// deductions
// ******************************************************//
// You may add private helper functions here. They must //
// be declared inside the private section of the class. //
//*******************************************************//
};
#endif
Graph.cpp
#include”Graph.h”
#include
// Graph constructor Implementation; gives number of vertices
Graph::Graph(int n)
{
if (n < 0) throw std::out_of_range(“The argument must not be less than 0”);
m_nz = new int[n];
m_re = new int[n + 1];
m_ci = new int[n];
int i = 0;
for (; i < n; i++)
{
m_nz[i] = 0;
m_re[i] = 0;
m_ci[i] = 0;
}
m_re[i] = 0;
m_numVert = m_cap = n;
m_numEdge = 0;
}
// Graph copy constructor
Graph::Graph(const Graph & obj)
{
m_cap = obj.m_cap;
m_numVert = obj.m_numVert;
m_numEdge = obj.m_numEdge;
m_nz = new int[m_cap];
m_re = new int[m_numVert + 1];
m_ci = new int[m_cap];
int i = 0;
for (; i != m_numVert + 1; i++)
m_re[i] = obj.m_re[i];
for (i = 0; i != m_cap; i++) {
m_nz[i] = obj.m_nz[i];
m_ci[i] = obj.m_ci[i];
}
}
//assignment operator implementation
const Graph & Graph::operator=(const Graph & obj)
{
if (m_cap != obj.m_cap){
m_cap = obj.m_cap;
delete[] m_nz;
delete[] m_ci;
m_nz = new int[m_cap];
m_ci = new int[m_cap];
}
if (obj.m_numVert != m_numVert)
{
m_numVert = obj.m_numVert;
delete[] m_re;
m_re = new int[m_numVert + 1];
}
m_numEdge = obj.m_numEdge;
int i = 0;
for (; i != m_numVert + 1; i++)
m_re[i] = obj.m_re[i];
for (i = 0; i != m_cap; i++) {
m_nz[i] = obj.m_nz[i];
m_ci[i] = obj.m_ci[i];
}
return *this;
}
int Graph::numVert()
{
return m_numVert;
}
int Graph::numEdge()
{
return m_numEdge / 2;
}
//add edge (u,v) to graph with weight x
void Graph::addEdge(int u, int v, int x)
{
if ((v < -1) || (v > m_numVert – 1) || (u < 0) || (u > m_numVert – 1)) {
throw std::out_of_range(“(u, v) must lower than number of vertices and >= 0”);
}
int i, j;
// check for already existing data
for (int i = m_re[u]; i < m_re[u + 1]; i++)
{
if (m_ci[i] == v)
{
m_nz[i] = x;
// do it for (v,u) as well
for (int j = m_re[v]; j < m_re[v + 1]; j++)
{
if (m_ci[j] == u)
{
m_nz[j] = x;
break;
}
}
return; // no need to proceed further
}
}
// check for reallocation
if ((m_numEdge + 2) >= m_cap)
{
m_nz = new int[m_cap + 2 * m_numVert];
m_ci = new int[m_cap + 2 * m_numVert];
if (m_nz == NULL || m_ci == NULL)
{
throw std::runtime_error(“could not allocate enough memory”);
}
// update the new values as well
for (int i = m_cap; i < (m_cap + 2 * m_numVert); i++)
{
m_nz[i] = 0;
m_ci[i] = -1;
}
m_cap += 2 * m_numVert;
}
// check for first edge for the node u
if (m_ci[m_re[u]] == -1)
{
m_ci[m_re[u]] = v;
m_nz[m_re[u]] = x;
}
else
{
int i_idx = m_re[u];
// push back the old data
int prev_nz = m_nz[m_re[u]];
int prev_ci = m_ci[m_re[u]];
for (int i = m_re[u] + 1; i < m_cap; i++)
{
int tmp = m_nz[i];
m_nz[i] = prev_nz;
prev_nz = tmp;
tmp = m_ci[i];
m_ci[i] = prev_ci;
prev_ci = tmp;
}
for (int i = u + 1; i <= m_numVert; i++)
{
m_re[i]++;
}
// add the u,v edge
m_nz[i_idx] = x;
m_ci[i_idx] = v;
}
// do the same for v
if (m_ci[m_re[v]] == -1)
{
m_ci[m_re[v]] = u;
m_nz[m_re[v]] = x;
}
else
{
int i_idx = m_re[v];
// push back the old data
int prev_nz = m_nz[m_re[v]];
int prev_ci = m_ci[m_re[v]];
for (int i = m_re[v] + 1; i < m_cap; i++)
{
int tmp = m_nz[i];
m_nz[i] = prev_nz;
prev_nz = tmp;
tmp = m_ci[i];
m_ci[i] = prev_ci;
prev_ci = tmp;
}
for (int i = v + 1; i <= m_numVert; i++)
{
m_re[i]++;
}
// add the v,v edge
m_nz[i_idx] = x;
m_ci[i_idx] = u;
}
m_numEdge += 2;
}
//dump info of graph
void Graph::dump()
{
std::cout << “Dump of graph (numVert = ” << numVert() << “, numEdge = ” << numEdge() << “, m_cap = ” << m_cap << “)” << std::endl;
std::cout << “m_re:”;
//m_re info
for (int i = 0; i < m_numVert + 1; i++)
{
std::cout << ” ” << m_re[i];
}
std::cout << std::endl;
//m_nz info
std::cout << “m_nz:”;
for (int i = 0; i < m_numEdge; i++)
{
if (m_nz[i] > 0)
{
std::cout << ” ” << m_nz[i];
}
}
std::cout << std::endl;
//m_ci info
std::cout << “m_ci:”;
for (int i = 0; i < m_numEdge; i++)
{
if (m_ci[i] >= 0)
{
std::cout << ” ” << m_ci[i];
}
}
std::cout << std::endl;
}
//edge constructor
Graph::EgIterator::EgIterator(Graph *Gptr, int indx)
{
m_row = indx;
m_indx = indx;
m_Gptr = Gptr;
if (m_Gptr == nullptr)
{
return;
}
// find the proper index
for (;;)
{
bool take_next = false;
for (int rx = 0; rx < m_Gptr->m_numVert – 1; rx++)
{
if (m_indx >= m_Gptr->m_re[rx] && m_indx < m_Gptr->m_re[rx + 1])
{
m_row = rx;
int cix = m_Gptr->m_ci[m_indx];
if (cix == -1)
{
take_next = true;
}
break;
}
}
if (!take_next)
{
break;
}
m_indx++;
}
}
//edge != operator
bool Graph::EgIterator::operator!=(const Graph::EgIterator &rhs)
{
if (rhs.m_Gptr == nullptr)
{
return true;
}
return rhs.m_Gptr->m_re[m_row + 1] > m_indx;
}
//edge ++operator
void Graph::EgIterator::operator++(int dummy)
{
if (m_Gptr == nullptr)
{
return;
}
EgIterator endIt = m_Gptr->egEnd();
if (m_indx != endIt.m_indx)
m_indx++;
}
//edge * operator
std::tuple Graph::EgIterator::operator*()
{
return std::make_tuple(
m_row,
m_Gptr->m_ci[m_indx],
m_Gptr->m_nz[m_indx]);
}
//edge begin
Graph::EgIterator Graph::egBegin()
{
return EgIterator(this);
}
//edge end
Graph::EgIterator Graph::egEnd()
{
return EgIterator(this);
}
//constructor
Graph::NbIterator::NbIterator(Graph *Gptr, int v, int indx)
{
m_Gptr = Gptr;
m_row = v;
m_indx = indx;
}
//neighbor at != operator
bool Graph::NbIterator::operator!=(const Graph::NbIterator &rhs)
{
//if neighbor not less than
return (rhs.m_Gptr->m_re[m_row] + m_indx) < rhs.m_Gptr->m_re[m_row + 1];
}
//neighbor at ++ operator
void Graph::NbIterator::operator++(int dummy)
{
//index increment
m_indx++;
}
//neighbor at* operator
int Graph::NbIterator::operator*()
{
int cix = m_Gptr->m_re[m_row] + m_indx;
//if out of range then throw exception
if (cix >= m_Gptr->m_re[m_row + 1])
{
throw std::out_of_range(“index out of range”);
}
return m_Gptr->m_ci[cix];
}
//neighbor begin
Graph::NbIterator Graph::nbBegin(int v)
{
return NbIterator(this, v);
}
//neighbor end
Graph::NbIterator Graph::nbEnd(int v)
{
return NbIterator(this, v);
}
// Graph destructor
Graph::~Graph()
{
delete[] m_re;
delete[] m_nz;
delete[] m_ci;
}
Graph.h
// File: Graph.h
//
// CMSC 341 Spring 2019
//
// Header file for Graph class
//
#ifndef _GRAPH_H_
#define _GRAPH_H_
#include // for throwing out_of_range exceptions
#include // for tuple template
class Grader; // Forward declaration needed for ‘friend’
class Graph {
public:
friend Grader; // Allows Grader class to access private variables
// Graph constructor; must give number of vertices
Graph(int n);
// Graph copy constructor
Graph(const Graph& G);
// Graph destructor
~Graph();
// Graph assignment operator
const Graph& operator= (const Graph& rhs);
// return number of vertices
int numVert();
// return number of edges
int numEdge();
// add edge between u and v with weight x
void addEdge(int u, int v, int x);
// print out data structure for debugging
void dump();
// Edge Iterator inner class
class EgIterator {
public:
// Edge Iterator constructor; indx can be used to
// set m_indx for begin and end iterators.
EgIterator(Graph *Gptr = nullptr, int indx = 0);
// Compare iterators; only makes sense to compare with
// end iterator
bool operator!= (const EgIterator& rhs);
// Move iterator to next printable edge
void operator++(int dummy); // post increment
// return edge at iterator location
std::tuple operator*();
private:
Graph *m_Gptr; // pointer to associated Graph
int m_indx; // index of current edge in m_nz
int m_row; // corresponding row of m_nz[m_indx]
};
// Make an initial edge Iterator
EgIterator egBegin();
// Make an end iterator for edge iterator
EgIterator egEnd();
// Neighbor Iterator inner class
class NbIterator {
public:
// Constructor for iterator for vertices adjacent to vertex v;
// indx can be used to set m_indx for begin and end iterators
NbIterator(Graph *Gptr = nullptr, int v = 0, int indx = 0);
// Compare iterators; only makes sense to compare with
// end iterator
bool operator!=(const NbIterator& rhs);
// Move iterator to next neighbor
void operator++(int dummy);
// Return neighbor at current iterator position
int operator*();
private:
Graph *m_Gptr; // pointer to the associated Graph
int m_row; // row (source) for which to find neighbors
int m_indx; // current index into m_nz of Graph
};
// Make an initial neighbor iterator
NbIterator nbBegin(int v);
// Make an end neighbor iterator
NbIterator nbEnd(int v);
private:
int *m_nz; // non-zero elements array
int *m_re; // row extent array
int *m_ci; // column index array
int m_cap; // capacity of m_nz and m_ci
int m_numVert; // number of vertices
int m_numEdge; // ptr to number of edges
};
#endif
test1bg.cpp
// File: test1bg.cpp
//
// CMSC 341 Spring 2019
// Project 2
//
// Basic testing of Baseline::Graph class
//
#include
#include
using namespace std;
#include “BaselineGraph.h”
int main() {
// G has 5 vertices numbered 0 thru 4
Baseline::Graph G(5);
// add some edges
G.addEdge(3, 4, 11);
G.addEdge(1, 4, 12);
G.addEdge(0, 3, 13);
G.addEdge(0, 4, 14);
G.addEdge(0, 1, 15);
G.addEdge(1, 2, 16);
G.addEdge(2, 4, 17);
// dump out data structure
G.dump();
// Test neighbor iterator
Baseline::Graph::NbIterator nit;
cout << “\nThe neighbors of vertex 4 are:\n”;
for (nit = G.nbBegin(4); nit != G.nbEnd(4); nit++) {
cout << *nit << ” “;
}
cout << endl;
// Test edge iterator
Baseline::Graph::EgIterator eit;
std::tuple edge;
cout << “\nThe edges in the graph are:\n”;
for (eit = G.egBegin(); eit != G.egEnd(); eit++) {
edge = *eit; // get current edge
cout << “(” << get<0>(edge) << “, ”
<< get<1>(edge) << “, ”
<< get<2>(edge) << “) “;
}
cout << endl;
}