Introduction

In this project, you will complete a program to grade an implementation of the Graph class from Project 1. In order to test whether an implementation is correct, we need some way to know how a correct implementation would function. For example, suppose we construct a Graph object with the implementation we are testing and want to determine whether the m_nz, m_ci, and m_re arrays have been populated correctly. It would be nice if we had an implementation of Graph that we knew to be correct; then we could construct the same graph in our correct implementation and just compare the arrays in the the two objects.

We aren't allowed to have two different classes with exactly the same name. So how can we possibly run two versions of the class and compare them? Well, we could give one of them a different name. Or we can just put one of them in a different namespace. Our correct implementation will just be a re-working of the Graph class, contained in a namespace called Baseline:

In addition to being contained in a namespace, there are some other important differences between Baseline::Graph and the original Graph class:

1. It uses STL vectors instead of C-style arrays and, therefore, does not directly use dynamic memory allocation.
2. Since it does not use dynamic memory allocation, it does not need a destructor, copy constructor, or assignment operator.
3. Since vectors automatically resize themselves, you do not need to explicitly expand them in addEdge().
4. Since the vector container provides an insert() method, you will not have to shift elements of m_nz and m_ci when inserting a new edge.

Once you've got Baseline::Graph working and have a version of Graph to test, you're ready to start writing the required tests in the Grader class.

// File: 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 m_numVert; // number of vertices int m_numEdge; // number of edges }; } #endif 

// File: Grader.h #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  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 

// File: Graph.h #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 

First, you need to complete the implementation of Baseline::Graph. The requirements for the methods in Baseline::Graph are the same as in Project i and will not be repeated here. You can use testibg.cpp for basic testing of the class. There is no test2bg.cpp because the main purpose of test2.cpp in Project i was to to test the copy constructor and assignment operator, which are not needed for this implementation. Next, implement the methods of Grader Most of the work is in implementing the required test functions: Method Description of tests Tests exact correctness of the n-re, m-nz. and .c1 arrays. Since n_az and _c1 should be ordered by increasing column index, there is a single correct configuration of the arrays. The test should check correctness of the arrays after any edge is inserted testCSRExact() testCSRUnordered) Tests correctness of the re,m nz, and ciarrays, without regard to ordering within each row That is, if the values for each row are correct but are not ordered by increasing column index, this test should pass. testNbitetTests that the NbIlterator produces the correct set of neighbors for every vertex in the graph. testegitertorTests that the egiterator produces a valid listing of the edges of the graph. All edges must be testExceptionsTests that an out of range exception is thrown for every operations specified to do so in the Projedt included and none may be repeated. 1 description. Must check if some other exception is thrown, or no excaption at all. Each of these test functions can generate Error objects, defined in Grader.h. Each Error object consists of a point deduction, error id, and error description. Whenever an Error is produced, it is pushed onto a queue, a private variable of the Grader class. Somewhat counter-intuitively, there are error types that correspond to passing a test (i.e. no error this allows success messages to be pushed into the error queue and printed at the end of the test program. The complete list of errors that the test functions can produce is described in errors.txt. Grader has three methods in addition to the test functions: Method Description of method Grader(string naneThe Grader constructor accepts an optional descriptive name for the object. Print all the errors in the error queue and the total point deductions; leaves the queue empty Removes all entries from the error queue resetErrorucuc) To test your implementation of Grader, youll need a version of Graph.cpp from Project 1. Your own submission should be sufficient to get started. It is not difficult to modify your Project i code to produce specific errors. However, you will be provided with some sample Graph implementations with which to test your code after the final submission deadline for Project i. Specifications Requirement: You may not modify Graph.h or BaselineGraph.h. You may add private helper functions to the Grader class, but you may not change anything else in Grader.h Requirement: Your Baseline: :Graph class must satisfy all the requirements of Project i except those specifically excluded due to the use of vectors rather than C arrays (e.g. no destructor, copy constructor, or assignment operator). Requirement: You must use atleast one STL container class in addition to vector and queue, and the the third container must be used within one of the test methods of Grader. Good candidates for the third container are set or multiset. Requirement: The testcSRExact() and testCSRUnordered() functions shall test the correctness of the arrays whenever an edge is added to the graph. Ifat any point, one of the arrays is incorrect, then the implementation fails the test and the appropriate Error shall be pushed onto the queue. Requirement: No error (identified by the unique error id) shall be pushed into the error queue more than once. Suppose testCSRExact() checks the correctness of n nz after each call to addEdge() and finds that the array is incorrect after each insertion; the error with id 102 should still only be pushed onto the quene once. Requirement: Contradictory errors shall not be pushed onto the Error queue. For example, only one of errors 510, 511 and 512 can occur, only one should appear in the queue. Requirement: "No error errors (e.g. 100, 200, 300, etc.) shall be pushed onto the queue whenever appropriate. Requirement: You must use the provided operatork