In: Computer Science
In this assignment we are not allowed to make changes to Graph.h it cannot be changed! I need help with the Graph.cpp and the Driver.cpp.
Your assignment is to implement a sparse adjacency matrix data structure Graph that is defined in the header file Graph.h. The Graph class provides two iterators. One iterator produces the neighbors for a given vertex. The second iterator produces each edge of the graph once.
Additionally, you must implement a test program that fully exercises your implementation of the Graph member functions. Place this program in the main() function in a file named Driver.cpp.
The purpose of an iterator is to provide programmers a uniform way to iterate through all items of a data structure using a forloop. For example, using the Graph class, we can iterate thru the neighbors of vertex 4 using:
Graph::NbIterator nit ; for (nit = G.nbBegin(4); nit != G.nbEnd(4) ; nit++) { cout << *nit << " " ; } cout << endl ;
The idea is that nit (for neighbor iterator) starts at the beginning of the data for vertex 4 in nz and is advanced to the next neighbor by the ++ operator. The for loop continues as long as we have not reached the end of the data for vertex 4. We check this by comparing against a special iterator for the end, nbEnd(4). This requires the NbIterator class to implement the ++, !=and * (dereference) operators.
Similarly, the Graph class allows us to iterate through all edges of a graph using a for loop like:
Graph::EgIterator eit ; tuple<int,int,int> edge ; 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 ;
Note that each edge should be printed only once, even though it is represented twice in the sparse adjacency matrix data structure.
Since a program may use many data structures and each data structure might provide one or more iterators, it is common to make the iterator class for a data structure an inner class. Thus, in the code fragments above, nit and eit are declared asGraph::NbIterator and Graph::EgIterator objects, not just NbIterator and EgIterator objects.
Here are the specifics of the assignment, including a description for what each member function must accomplish.
Requirement: your implementation must dynamically resize the m_nz and m_ci arrays. See the descriptions of Graph(constructor) and addEdge, below.
Requirement: other than the templated tuple class, you must not use any classes from the Standard Template Library or other sources, including vector and list. All of the data structure must be implemented by your own code.
Requirement: your code must compile with the original Graph.h header file. You are not allowed to make any changes to this file. Yes, this prevents you from having useful helper functions. This is a deliberate limitation of this project. You may have to duplicate some code.
Requirement: a program fragment with a for loop that uses your NbIterator must have worst case running time that is proportional to the number of neighbors of the given vertex.
Requirement: a program fragment with a for loop that uses your EgIterator must have worst case running time that is proportional to the number of vertices in the graph plus the number of edges in the graph.
Graph.h:
#ifndef _GRAPH_H_ #define _GRAPH_H_ #include <stdexcept> // for throwing out_of_range exceptions #include <tuple> // for tuple template class Graph { public: // 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<int,int,int> 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; // number of edges }; #endif
Driver.cpp
#include "Graph.h"
#include <iostream>
#include <utility>
using namespace std;
int main()
{
// G has 5 vertices numbered 0 thru 4
Graph G(5) ;
Graph G2(4);
// add some edges
G.addEdge(3,4) ;
G.addEdge(1,4) ;
G.addEdge(2,1);
G.addEdge(0,3) ;
G.addEdge(0,4) ;
G2.addEdge(0,1) ;
G2.addEdge(1,2) ;
G2.addEdge(2,3) ;
G2.addEdge(0,3);
G2.addEdge(3,1);
// dump out data structure
G.dump() ;
// Test neighbor iterator
//
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
//
Graph::EgIterator eit ;
pair<int,int> edge ;
cout << "\nThe edges in the graph are:\n" ;
for (eit = G.egBegin() ; eit != G.egEnd() ; eit++) {
edge = *eit ; // get current edge
// the two data members of a pair are first and second
//
cout << "(" << edge.first << ", " <<
edge.second << ") " ;
}
cout << endl ;
cout << endl;
G2.dump();
// Test neighbor iterator
//
Graph::NbIterator nit2 ;
cout << "\nThe neighbors of vertex 2 are:\n" ;
for (nit2 = G2.nbBegin(2); nit2 != G2.nbEnd(2) ; nit2++) {
cout << *nit2 << " " ;
}
cout << endl ;
Graph::EgIterator eit2 ;
pair<int,int> edge2 ;
cout << "\nThe edges in the graph are:\n" ;
for (eit2 = G2.egBegin() ; eit2 != G2.egEnd() ; eit2++) {
edge2 = *eit2 ; // get current edge
// the two data members of a pair are first and second
//
cout << "(" << edge2.first << ", " <<
edge2.second << ") " ;
}
cout << endl ;
cout << endl;
Graph G3(G2);
cout << "Graph G3(G2) dump" << endl;
G3.dump();
cout << endl;
cout << "G3 = G dump" << endl;
G3 = G;
G3.dump();
cout << endl;
cout << "G size: " << G.size() << endl
<< "G2 size: " << G2.size() << endl
<< "G3 size: " << G3.size() << endl;
return 0;
}
Graph.cpp
#include "Graph.h"
#include <iostream>
using namespace std;
//Graph constructor
Graph::Graph(int n)
{
if(n <= 0)
{
throw out_of_range("Not enough Vectors");
}
else
{
m_size = n;
//initialize adjLists array as an array of size m_size
m_adjLists = new AdjListNode*[m_size]();
}
}
//Graph Copy Constructor
Graph::Graph(const Graph &G)
{
m_size = G.m_size; // set m_size to the size of Graph you want to
copy
m_adjLists = new AdjListNode*[m_size]; // initialize array to this
size
AdjListNode ptr, curr;
//for each linked list
for(int i = 0; i < m_size; i++)
{
//look at node in Graph you want to copy
curr = G.m_adjLists[i];
//if node in other Graph is NULL
if(curr == NULL)
{
//set same node in this Graph to NULL
m_adjLists[i] = NULL;
}
else
{
//create Node for neighbor of current node
ptr = new AdjListNode(curr->m_vertex);
m_adjLists[i] = ptr;
curr = curr->next;
while(curr != NULL)
{
ptr->next = new AdjListNode(curr->m_vertex);
curr = curr->next;
ptr = ptr->next;
}
}
}
}
//Graph Destructor
Graph::~Graph()
{
AdjListNode prev, curr;
//for each list in array
for(int i = 0; i < m_size; i++)
{
//set curr to first node in list
curr = m_adjLists[i];
//for everycnode
while(curr != NULL)
{
prev = curr;
curr = curr->next;
prev->next = NULL;
delete prev;
}
}
delete [] m_adjLists;
}
const Graph &Graph::operator= (const Graph &rhs)
{
//protect against self assignment
if(&rhs == this) return *this;
//clear graph
this->~Graph();
m_size = rhs.m_size;
m_adjLists = new AdjListNode*[m_size];
AdjListNode ptr, curr;
//copy rhs Graph
for(int i = 0; i < m_size; i++)
{
curr = rhs.m_adjLists[i];
if(curr == NULL)
{
m_adjLists[i] = NULL;
}
else
{
ptr = new AdjListNode(curr->m_vertex);
m_adjLists[i] = ptr;
curr = curr->next;
while(curr != NULL)
{
ptr->next = new AdjListNode(curr->m_vertex);
curr = curr->next;
ptr = ptr->next;
}
}
}
return *this;
}
//Return size of the graph
int Graph::size()
{
return m_size;
}
void Graph::addEdge(int u, int v)
{
//if the vectors are within the size of the graph
if( u < m_size && v < m_size)
{
//adds v as neighbor of u
AdjListNode *newNode = new AdjListNode(v);
newNode->next = m_adjLists[u];
m_adjLists[u] = newNode;
//adds u as neighbor of v
newNode = new AdjListNode(u);
newNode->next = m_adjLists[v];
m_adjLists[v] = newNode;
}
else
{
throw out_of_range("The vertex does not exist");
}
}
//AdjListNode Constructor
Graph::AdjListNode::AdjListNode(int v, AdjListNode *ptr)
{
m_vertex = v;
next = ptr;
}
//Prints Adjacency List
void Graph::dump()
{
AdjListNode *curr;
cout << "Dump out graph ( size = " << m_size << "
):" << endl;
for(int i = 0; i < m_size; ++i)
{
cout << "[ " << i << "]: ";
curr = m_adjLists[i];
while( curr != NULL)
{
cout << curr->m_vertex << " ";
curr = curr->next;
}
cout << endl;
}
}
//Neighbor Iterator Implementation
Graph::NbIterator::NbIterator(Graph *Gptr, int v, bool
isEnd)
{
m_Gptr = Gptr;
m_source = v;
if(m_Gptr == NULL)
{
return;
}
if(isEnd)
{
m_where = NULL;
return;
}
m_where = m_Gptr->m_adjLists[m_source];
}
// Neighbor Iterator Begin
Graph::NbIterator Graph::nbBegin(int v)
{
return NbIterator(this, v);
}
//Neighbor Iterator End
Graph::NbIterator Graph::nbEnd(int v)
{
return NbIterator(this, v, true);
}
// Overlaoded != operator
bool Graph::NbIterator::operator!=(const NbIterator& rhs)
{
return(m_Gptr != rhs.m_Gptr
|| m_where != rhs.m_where);
}
//Overloaded ++ operator
void Graph::NbIterator::operator++(int dummy)
{
if( m_Gptr == NULL || m_where == NULL)
{
return;
}
m_where = m_where->next;
}
//overloaded * operator
int Graph::NbIterator::operator*()
{
if(m_where == NULL)
{
throw out_of_range("NbIterator dereference error.");
}
return m_where->m_vertex;
}
// Edge Iterator Implementation
Graph::EgIterator::EgIterator(Graph *Gptr, bool isEnd)
{
m_Gptr = Gptr;
if(m_Gptr == NULL)
{
return;
}
if(isEnd)
{
m_source = m_Gptr->m_size;
m_where = NULL;
return;
}
m_source = 0;
m_where = m_Gptr->m_adjLists[0];
while(m_where == NULL)
{
m_source++;
if(m_source == m_Gptr->m_size)
{
break;
}
m_where = m_Gptr->m_adjLists[m_source];
}
}
Graph::EgIterator Graph::egBegin()
{
return EgIterator(this, false);
}
Graph::EgIterator Graph::egEnd()
{
return EgIterator(this, true);
}
bool Graph::EgIterator::operator!= (const EgIterator&
rhs)
{
return(m_Gptr != rhs.m_Gptr
|| m_source != rhs.m_source
|| m_where != rhs.m_where);
}
void Graph::EgIterator::operator++(int dummy)
{
if(m_Gptr == NULL || m_where == NULL)
{
return;
}
do
{
m_where = m_where->next;
while( m_where == NULL)
{
m_source++;
if( m_source == m_Gptr->m_size)
{
break;
}
m_where = m_Gptr->m_adjLists[m_source];
}
if(m_where == NULL)
{
break;
}
}
while( m_source > m_where->m_vertex);
}
pair<int,int> Graph::EgIterator::operator*()
{
if (m_where == NULL)
{
throw out_of_range("EgIterator dereference error");
}
return pair<int,int>(m_source, m_where->m_vertex);
}
Graph.h
#ifndef GRAPH_H
#define GRAPH_H
#include <stdexcept> // for throwing out_of_range exceptions
#include <utility> // for pair template
class Graph {
class AdjListNode ; // forward inner class declaration
public:
// 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 size() ;
// add edge between u and v
void addEdge(int u, int v) ;
// print out data structure for debugging
void dump() ;
// Edge Iterator inner class
class EgIterator {
public:
// Edge Iterator constructor, isEnd true to create end
iterator
EgIterator(Graph *Gptr = NULL, bool isEnd = false) ;
// 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::pair<int,int> operator*() ;
private:
Graph *m_Gptr ; // pointer to Graph using this iterator
int m_source ; // source vertex of current location
AdjListNode *m_where ; // location in linked list of iterator
} ;
// 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
NbIterator(Graph *Gptr = NULL, int v = -1, bool isEnd = false)
;
// 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 ; // which graph?
int m_source ; // neighbor of which vertex?
AdjListNode *m_where ; // location in linked list
} ;
// Make an initial neighbor iterator
NbIterator nbBegin(int v) ;
// Make an end neighbor iterator
NbIterator nbEnd(int v) ;
private:
// Private inner Node class for linked list for
// adjacency lists
//
class AdjListNode {
// let all Graph class have access
friend class Graph ;
friend class EgIterator ;
friend class NbIterator ;
private:
// construct a node
AdjListNode(int v=-1, AdjListNode *ptr=NULL) ;
int m_vertex ; // holds one neighbor vertex
AdjListNode * next ; // next node
} ;
// pointer to a dynamically allocated array of linked lists
// of AdjListNodes
AdjListNode ** m_adjLists ;
// number of vertices in this graph
int m_size ;
} ;
#endif