In this assignment we are not allowed to make changes to Graph.hit cannot be changed! I need help with the Graph.cpp and theDriver.cpp.

Your assignment is to implement a sparse adjacency matrix datastructure Graph that is defined in the header file Graph.h. TheGraph class provides two iterators. One iterator produces theneighbors for a given vertex. The second iterator produces eachedge of the graph once.

Additionally, you must implement a test program that fullyexercises your implementation of the Graph member functions. Placethis program in the main() function in a file named Driver.cpp.

The purpose of an iterator is to provide programmers a uniformway to iterate through all items of a data structure using aforloop. For example, using the Graph class, we can iterate thruthe 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 neighboriterator) starts at the beginning of the data forvertex 4 in nz and is advanced to the next neighbor by the ++operator. The for loop continues as long as we have not reached theend of the data for vertex 4. We check this by comparing against aspecial iterator for the end, nbEnd(4). This requires theNbIterator class to implement the ++, !=and * (dereference)operators.

Similarly, the Graph class allows us to iterate through alledges of a graph using a for loop like:

Graph::EgIterator eit ; tuple edge ; for (eit= G.egBegin() ; eit != G.egEnd() ; eit++) { edge = *eit ; // getcurrent edge cout << \"(\" << get<0>(edge) <<\", \" << get<1>(edge) << \", \" <(edge) << \") \" ; } cout << endl ;

Note that each edge should be printed only once, even though itis represented twice in the sparse adjacency matrix datastructure.

Since a program may use many data structures and each datastructure might provide one or more iterators, it is common to makethe iterator class for a data structure an inner class. Thus, inthe code fragments above, nit and eit are declaredasGraph::NbIterator and Graph::EgIterator objects, not justNbIterator and EgIterator objects.

Here are the specifics of the assignment, including adescription for what each member function must accomplish.

Requirement: your implementation mustdynamically resize the m_nz and m_ci arrays. See the descriptionsof Graph(constructor) and addEdge, below.

Requirement: other than the templated tupleclass, you must not use any classes from the Standard TemplateLibrary or other sources, including vector and list. All of thedata structure must be implemented by your own code.

Requirement: your code must compile with theoriginal Graph.h header file. You are not allowed to make anychanges to this file. Yes, this prevents you from having usefulhelper functions. This is a deliberate limitation of this project.You may have to duplicate some code.

Requirement: a program fragment with a for loopthat uses your NbIterator must have worst case running time that isproportional to the number of neighbors of the given vertex.

Requirement: a program fragment with a for loopthat uses your EgIterator must have worst case running time that isproportional to the number of vertices in the graph plus the numberof edges in the graph.

Graph.h:

#ifndef _GRAPH_H_#define _GRAPH_H_#include  // for throwing out_of_range exceptions#include    // for tuple templateclass 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 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

Graph.cpp outline:

#include \"Graph.h\"

Graph::Graph(int n) {
}

Graph::Graph(const Graph& G) {
}

Graph::~Graph() {
}

const Graph& Graph::operator= (const Graph& rhs) {
  
}
// This Function will return the number of vertices in thegraph
int Graph::numVert() {
  
}

int Graph::numEdge() {
  
}

void Graph::addEdge(int u, int v, int x) {
  
}

void Graph::dump() {
  
}

Graph::EgIterator::EgIterator(Graph *Gptr = nullptr, int index =0) {
  
}

bool Graph::EgIterator::operator!= (const EgIterator& rhs){
  
}

void Graph::EgIterator::operator ++(int dummy) {
  
}

std::tuple Graph::EgIterator::operator *(){
  
}

Graph::EgIterator Graph::egBegin() {
  
}

Graph::EgIterator Graph::egEnd() {
  
}

Graph::NbIterator::NbIterator(Graph *Gptr = nullptr, int v = 0,int indx = 0) {
  
}

bool Graph::NbIterator::operator !=(const NbIterator& rhs){
  
}

void Graph::NbIterator::operator ++(int dummy) {
  
}

int Graph::NbIterator::operator *() {
  
}

Graph::NbIterator Graph::nbBegin(int v) {
  
}

Graph::NbIterator Graph::nbEnd(int v) {
  
}