// Header file for the Graph class // // Graph has two nested iterator classes: // (1) EgIterator - edge iterator // (2) NbIterator - neighbor iterator #ifndef _GRAPH_H_ #define _GRAPH_H_ #include...

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.

// Header file for the Graph class // // Graph has two nested iterator classes: // (1) EgIterator - edge iterator // (2) NbIterator - neighbor iterator #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.=""> 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 }; #endif // Header file for EntryList class // // An EntryList is a dynamically-resized array storing Entry objects. // The Entry objects are stored in ascending order by vertex. // // EntryList has one nested class, Entry, which defines the objects // stored in an EntryList. #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 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="">