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 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.

Graph.h:

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