Please only use GIVEN ARRAYS and program it using arrays and no changes to the graph.h file are allowed

So how can we store our adjacency matrix without wasting space? We will use compressed sparse row format. Let N denote the number of vertices in the graph and NNZ the number of non-zero entries in our adjacency matrix. We can store the adjacency matrix efficiently with three arrays:

1. nz an integer array of length NNZ storing all the non-zero entries in row-major order. The first elements of nz are the non-zero elememnts of row 0, followed by the non-zero elements of row 1, etc. The data for each row should be stored in order of increasing column index.
2. re an integer array of length N+1 indicating where each row's data starts in nz. That is, the data for row u starts at index re[u] of nz. The last element of re should always be equal to NNZ.
3. ci an integer array of length NNZ storing the column indices for the elements in nz.

The adjacency matrix A for our example graph would be encoded as follows:

 nz = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} re = {0, 3, 6, 8, 10, 14} ci = {1, 3, 4, 0, 2, 4, 1, 4, 0, 4, 0, 1, 2, 3} 

Assignment

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.

Specifications

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: per our course coding standards, your code must compile with g++ on the GL servers without using any compilation flags.

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.

These are the member functions of the Graph class (not including the member functions of the inner classes).

• Graph(int n) ;

  This is the constructor for the Graph class. The Graph class does not have a default constructor, because we want the programmer to specify the number of vertices in the graph using the parameter n. If the n given is zero or negative, throw an out_of_range exception.

  The constructor must dynamically allocate space for the three arrays required by the sparse matrix format. The constructor does not know how large the m_nz and m_ci arrays will need to be, but it is reasonable to create them each with n elements; if more space is needed, the arrays will be dynamically resized by the addEdge function (see below).

• Graph(const Graph& G) ;

  This is the copy constructor for the Graph class. It should make a complete (deep) copy of the Graph object G given in the parameter. The target of the copy is the host object.

  You should not call the assignment operator from the copy constructor (or vice versa). The objective of these two member functions are sufficiently different that you should implement them separately.

• const Graph& operator= (const Graph& rhs) ;

  This is the overloaded assignment operator for the Graph class. It is called when the compiler sees an assignment like:

  A = B ;

  where both A and B are Graph objects. The object A becomes the host object of the function and B is passed to the function as rhs.

  Remember to check for self-assignment and to free all dynamically allocated data members of the host. You should not use the copy constructor in the implementation of the assignment operator.

• ~Graph() ;

  This is the destructor for the Graph class. All dynamically allocated memory associated with the host object must be deallocated. You should use valgrind on GL to check for memory leaks.

• int numVert() ;

  This function returns the number of vertices in the graph.

• int numEdge() ;

  This function returns the number of edges in the graph.

• void addEdge(int u, int v, int w) ;

  This function should add an edge between vertices u and v with weight w. Note that you will need to add entries for both the (u, v) and (v, u) positions of the adjacency matrix. If the value for u or v is invalid, throw an out_of_rangeexception.

  If the m_nz and m_ci arrays are full when addEdge is called, the function must dynamically resize the arrays by creating new arrays with twice the capacity, copying the data from the existing m_nz and m_ci arrays to the new arrays, deleting the old arrays, and assigning the new arrays to the class variables m_nz and m_ci. The function can tell if a resize is necessary by checking the m_cap class variable.

  You must not create duplicate edges in the data structure. If addEdge(u, v, w) is called and the edge (u, v) already exists, then the function should just set the weight of the existing edge to w.

• void dump() ;

  This member function is used for debugging. It should print out the number of vertices, number of edges, and current capacity of m_nz (the array of non-zero entries). In adddition, it must print the contents of three arrays m_nz, m_re, and m_ci.

  Note: you should not use the neighbor iterator in dump(), because dump() is supposed to help you debug your program when the iterators are not working!

• EgIterator egBegin() ; EgIterator egEnd() ;

  These two functions call the EgIterator constructor to create iterators that can be used in for loops to iterate through the edges of the graph. (See example above.)

• NbIterator nbBegin(int v) ; NbIterator nbEnd(int v) ;

  These two functions call the NbIterator constructor to create iterators that can be used in for loops to iterate through the neighbors of vertex v. (See example above.)

These are the member functions of the edge iterator class EgIterator:

• EgIterator(Graph *Gptr = nullptr, int indx = 0) ;

  This is the constructor for the EgIterator class. It is a default constructor, since each parameter has a default value. The constructor should allow an EgIterator to be declared without any arguments.

  If called with no arguments, the constructor may leave m_row unitialized since there is no graph associated to the iterator. However, if a pointer to a Graph object is provided in Gptr, the constructor should initialized m_indx to zero (or the value of indx, if specified) and set m_row to the row corresponding to the value of m_indx. Note that it is possible for rows to have no edges, so the correct value of m_row must be computed by the constructor.

• bool operator!= (const EgIterator& rhs) ;

  This overloaded operator compares two EgIterator objects. It will only be used to compare an EgIterator against the end iterator and must return false when the end is reached. All other uses are unspecified.

• void operator++(int dummy) ;

  The post increment ++ operator should advance the iterator to the next viable edge. The dummy parameter indicates this is a post increment operator and not a preincrement operator. The dummy parameter is not actually used as a parameter.

  The ++ operator should have no effect if applied to an iterator that is already at the end.

• std::tuple operator*() ;

  This is the overloaded dereference operator. It returns a three-tuple (u, v, w) of integers using the tuple class from the standard library where u and v are the source and destiation vertices and w is the edge weight. The tuple returned is the edge that the iterator is currently visiting. Throw an out_of_range exception if the dereference operator is applied to an iterator that has reached the end. See Implementation Notes below for further comments.

These are the member functions of the neighbor iterator class NbIterator. They are analogous to the functions forEgIterator.

• NbIterator(Graph *Gptr = NULL, int v = 0, int indx = 0) ;

  This is the constructor for the NbIterator class. It is a default constructor, since each parameter has a default value. The constructor should allow an NbIterator to be declared without any arguments.

  The parameter v specifies that we wish to iterate over the neighbors of vertex v. The class variable m_nrow should be initialized to the value of v.

  A value of indx may be provided, in which case m_indx should be set to the value of indx; this would typically only be done to create an nbEnd iterator.

  If a pointer to a Graph object is provided in Gptr, the constructor should initialize m_row to the value of v and m_indx to the index of the first element of row m_row in the m_nz array.

• bool operator!= (const NbIterator& rhs) ;

  As before, the only intended use of the != operator is to compare an NbIterator object against the end iterator.

• void operator++(int dummy) ;

  The ++ operator advances the iterator to the next neighbor of m_row. All neighbors are viable, so this ++ operator should be simpler to implement than the one for EgIterator.

  The ++ operator should have no effect if applied to an iterator that is already at the end.

• int operator*() ;

  This dereference operator should return the neighbor that the iterator is currently visiting. Throw an out_of_rangeexception if the dereference operator is applied to an iterator that has reached the end.

Graph.h file

#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