sparse adjacency list assignment Graph that is defined in the header file Graph.h. The dynamic arrays that store the neighbor lists are implemented in a second class, EntryList, which is defined in EntryList.h. Thus, to complete the Graph class, you must first implement the EntryList class.

Additionally, you must write a test program that fully exercises your implementations of both classes. The test program must be named mytest.cpp.

Graph.h

#ifndef _GRAPH_H_ #define _GRAPH_H_ #include "EntryList.h" // Uses EntryList objects for ajacency lists #include // Standard screen i/o stuff #include // For invalid_argument exceptions #include // For tuple template using std::ostream; using std::tuple; using std::pair; class Graph { friend class Grader; public: // // Constructors and memory management // // Graph constructor; must give number of vertices (n). Throws // invalid_argument if n <= 0. Graph(int n); // Graph copy constructor, assignment operator, destructor Graph(const Graph& G); const Graph& operator=(const Graph& rhs); ~Graph(); // // Basic operations // // Return number of vertices int numVert() const; // Return number of edges int numEdge() const; // Add an edge between u and v with weight x. Throws // invalid_argument if u or v is not a valid vertex number. void addEdge(int u, int v, weight_t x); // Remove the edge (u, v). Returns 'true' if an edge is removed; // 'false' if there is no edge (u,v). Throws invalid_argument if u // or v is not a valid vertex number bool removeEdge(int u, int v); // print out data structure for debugging void dump() const; // // Iterators // // Edge Iterator inner class class EgIterator { public: // Edge Iterator constructor. // If Gptr is nullptr, create an unitialized iterator. // If Gptr points to a host Graph object: // If enditr == false, create a begin() iterator. // If enditr == true, create an end() iterator. EgIterator(Graph *Gptr = nullptr, bool enditr = false); // Compare two iterators. Mainly used to end a for loop using the // iterator. bool operator!= (const EgIterator& rhs); // Advanced the iterator to the next edge; if already at the end() // iterator, leave unchanged. Throws invalid_argument if the // iterator is uninitialized. void operator++(int dummy); // Return edge at iterator location as a tuple (u, v, weight). // Throws invalid_argument if the iterator is uninitialized or if // derefrence of _itr failes. tuple operator*(); private: Graph *_Gptr; // Pointer to host Graph int _row; // Current row of the matrix EntryList::Iterator _itr; // Iterator to current row }; // Create an initial edge Iterator. EgIterator egBegin(); // Create an end edge Iterator. EgIterator egEnd(); // Neighbor Iterator inner class class NbIterator { public: // Constructor for iterator for vertices adjacent to vertex v. // If Gptr == nullptr, creat an uninitialized iterator. // If Gptr points to a host Graph object: // If enditr == true, create an end iterator for row v. // If enditr == false, crete a begin iterator for row v. // Throws invalid_argument if v is not a valid vertex number. NbIterator(Graph *Gptr = nullptr, int v = 0, bool enditr = false); // Compare iterators. bool operator!=(const NbIterator& rhs); // Advance iterator to the next neighbor. void operator++(int dummy); // Return neighbor and weight at current iterator position. Throws // invalid_argument if the iterator is null or invalid. pair operator*(); private: Graph *_Gptr; // Pointer to host Graph int _row; // Row (source vertex) over which we // are iterating EntryList::Iterator _itr; // Iterator to the current row (which // is an EntryList) }; // Make an initial neighbor iterator for row v. Throws // invalid_argument if v is not a valid node index. NbIterator nbBegin(int v); // Make an end neighbor iterator. Throws invalid_argument if v is // not a valid node index. NbIterator nbEnd(int v); private: EntryList **_rows; // Array of pointers to EntryLists. _rows[i] // points to an EntryList object, the adjacency // list for vertex i. int _numVert; // number of vertices in the graph int _numEdge; // number of edges in the graph }; 

Graph.cpp

#include #include "Graph.h" using std::cout; using std::endl; using std::exception; using std::invalid_argument; // Constructor - DO NOT MODIFY Graph::Graph(int n) { if (n <= 0) throw invalid_argument("Graph::Graph(): number of vertices must be positive"); _rows = new EntryList*[n]; for (int i = 0; i < n; i++) { _rows[i] = new EntryList(); } _numVert = n; _numEdge = 0; } Graph::Graph(const Graph& G) { } const Graph& Graph::operator=(const Graph& rhs) { } Graph::~Graph() { } // Number of vertices - DO NOT MODIFY int Graph::numVert() const { return _numVert; } // Number of edges - DO NOT MODIFY int Graph::numEdge() const { return _numEdge; } void Graph::addEdge(int u, int v, weight_t x) { } bool Graph::removeEdge(int u, int v) { } // Dump the graph - DO NOT MODIFY void Graph::dump() const { cout << "Dump of graph (numVert = " << _numVert << ", numEdge = " << _numEdge << ")" << endl; for (int i = 0; i < _numVert; i++) { cout << "Row " << i << ": "; _rows[i]->dump(); } } Graph::EgIterator::EgIterator(Graph *Gptr, bool enditr) { } tuple Graph::EgIterator::operator*() { } bool Graph::EgIterator::operator!=(const EgIterator& rhs) { } void Graph::EgIterator::operator++(int dummy) { } Graph::EgIterator Graph::egBegin() { } Graph::EgIterator Graph::egEnd() { } Graph::NbIterator::NbIterator(Graph *Gptr, int v, bool enditr) { } bool Graph::NbIterator::operator!=(const NbIterator& rhs) { } void Graph::NbIterator::operator++(int dummy) { } pair Graph::NbIterator::operator*() { } Graph::NbIterator Graph::nbBegin(int v) { } Graph::NbIterator Graph::nbEnd(int v) { }

EntryList.h

#ifndef _ENTRY_LIST #define _ENTRY_LIST #include // Standard screen i/o stuff using std::ostream; typedef float weight_t; // typedef for edge weights class EntryList { friend class Grader; public: // Default (initial) size of _array. The array starts at this size // and should never be "shrunk" below this size. const int DEFAULT_SIZE = 10; // Nested Entry class. EntryList stores an array of Entry objects. // An Entry object stores a vertex number and an edge weight; it has // basic getter/setter methods. class Entry { friend EntryList; public: Entry(int vertex = 0, weight_t weight = 0) { _vertex = vertex; _weight = weight; } int getVertex() const { return _vertex; } weight_t getWeight() const { return _weight; } void setWeight(weight_t w) { _weight = w; } friend ostream& operator<<(ostream& sout, const Entry& e); private: int _vertex; // A vertex number weight_t _weight; // An edge weight }; // // Constructors and memory management // // Default constructor. Creates an EntryList with capacity // DEFAULT_SIZE. EntryList(); // Copy constructor, assignment operator, destructor EntryList(const EntryList& rhs); const EntryList& operator=(const EntryList& rhs); ~EntryList(); // // Basic operations // // Insert the entry e. The elements of the list must be kept in // increasing order by vertex. If inserting the new element would // exceed the capacity of the EntryList, then the array must be // expanded, doubling the capacity. Returns 'true' if new entry // inserted, 'false' if there is already an entry with the same // vertex as e. bool insert(const Entry& e); // Update the entry e; return 'true' if an entry with the same // vertex as e exists and was updated, 'false' if there is not entry // with the same vertex as e. bool update(const Entry& e); // Get the entry with given vertex value; return the entry in ret. // Returns 'true' if an entry with the specified vertex was found, // 'false' if there is no entry with the specified vertex. bool getEntry(int vertex, Entry &ret); // Remove the entry with given vertex value; return the entry that // was removed in ret. If, after successfully removing an Entry, the // number of Entries is *less than* 1/4 of the capacity, then the // EntryList array must be shrunk, halving its capacity. The // capacity must never be reduced below DEFAULT_SIZE, a constant // defined EntryList.h. Returns 'true' if an entry with the same // vertex as e exists and was removed, returns 'false' if there is // no entry with the specified vertex. bool remove(int vertex, Entry &ret); // Access an element of the EntryList by index. Throws range_error // if indx is not a valid index into the EntryList's array. // // WARNING: at() allows modification of an Entry, but changing the // vertex value could ruin the ordering of the entries! Entry& at(int indx) const; // Get the size (numer of Entries actually stored) int size() const { return _size; } // Get the capacity (size of _array; number of Entries that could be // stored without resizing). int capacity() const { return _capacity; } // Dump the contents of _array. For debugging. void dump(); // EntryList Iterator class class Iterator { public: // Constructor for iterator for vertices adjacent to vertex v; // indx can be used to set _indx for begin and end iterators. Iterator(EntryList *EList = nullptr, int indx = 0); // Comparison operators for EntryList iterators bool operator!=(const Iterator& rhs); bool operator==(const Iterator& rhs); // Advance iterator to next neighbor; if the iterator is already // at the end, leave it unchanged void operator++(int dummy); // Return neighbor (Entry) at the current iterator position EntryList::Entry operator*(); private: EntryList *_ELptr; // pointer to the associated EntryList int _indx; // current index in the EntryList }; // Create an initial iterator EntryList::Iterator begin(); // Create an end iterator EntryList::Iterator end(); private: Entry *_array; int _capacity; int _size; // ***************************************** // Private function declarations belong here // ***************************************** }; #endif

EntryList.cpp

#include "EntryList.h" using std::cout; using std::endl; using std::range_error; // Constructor - DO NOT MODIFY EntryList::EntryList() { _array = new Entry[DEFAULT_SIZE]; _capacity = DEFAULT_SIZE; _size = 0; } EntryList::EntryList(const EntryList& rhs) { } const EntryList& EntryList::operator=(const EntryList& rhs) { } EntryList::~EntryList() { } bool EntryList::insert(const Entry& e) { } bool EntryList::update(const Entry& e) { } bool EntryList::getEntry(int vertex, Entry &ret) { } bool EntryList::remove(int vertex, Entry &ret) { } EntryList::Entry& EntryList::at(int indx) const { } // dump data structure - DO NOT MODIFY void EntryList::dump() { for (int i = 0; i < _size; i++) { cout << " " << _array[i] << endl; } } EntryList::Iterator::Iterator(EntryList *EList, int indx) { } bool EntryList::Iterator::operator!=(const EntryList::Iterator& rhs) { } bool EntryList::Iterator::operator==(const EntryList::Iterator& rhs) { } void EntryList::Iterator::operator++(int dummy) { } EntryList::Entry EntryList::Iterator::operator*() { } EntryList::Iterator EntryList::begin() { } EntryList::Iterator EntryList::end() { } // Insertion operator for Entry objects - DO NOT MODIFY ostream& operator<<(ostream& sout, const EntryList::Entry& e) { sout << e._vertex << ": " << e._weight; return sout; } // A convenient way to write test code for a single class is to write // a main() function at the bottom of the .cpp file. Just be sure to // comment-out main() once you are done testing! // Following is example test code. There is no guarantee that it is // complete -- you are responsbile for thoroughly testing your code. // In particular, passing these tests does not mean your // implementation will pass all grading tests. // int main() { // EntryList el; // EntryList::Entry e; // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 1; i < 13; i++) { // el.insert( EntryList::Entry((i*5)%13, i) ); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 1; i < 13; i+=2) { // el.remove(i, e); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 2; i < 13; i+=2) { // el.update( EntryList::Entry(i, 2*i) ); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 3; i < 13; i*=2) { // el.remove(i, e); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // cout << " Print using iterator: "; // for (auto itr = el.begin(); itr != el.end(); itr++) { // cout << *itr << endl; // } // return 0; // }