Your assignment is to implement the sparse adjacency list data structureGraphthat is defined in the header fileGraph.h. The dynamic arrays that store the neighbor lists are implemented in a second class,EntryList, which is defined inEntryList.h. Thus, to complete theGraphclass, you must first implement theEntryListclass.
Additionally, you must write a test program that fully exercises your implementations of both classes. The test program must be namedmytest.cpp.
Be sure to read the function descriptions carefully — your implementation is expected to behave as described in this document. Following are additional project requirements.
Requirement:You may not use any Standard Template Library (STL) classes other thanpairandtuplein the implementation ofEntryListandGraph. You may use STL classes inmytest.cpp.
Requirement:your code must compile with the originalGraph.hheader file. You are not allowed to make any changes to this file.
Requirement:You may add private helper functions to theEntryListclass, but they must be declared inEntryList.h. No other modifications toEntryList.hare permitted.
Testing
Following is anon-exhaustivelist of tests to perform on your implementation.
EntryList
Basic tests ofinsert(),update(),remove(), andgetEntry:
- Create anEntryList; insert a number of entries; check that contents of the list are correct.
- Update some of the entries; check that the contents of the list are correct.
- getEntry()returns the desired entry in theretreference variable. Similarly,remove()returns the entry that was removed inret.
- Remove some of the entries; check that the contents are correct.
- Check that entries are ordered by increasing vertex after some combination of insertions and removals.
- Check that there are no duplicate vertex values in the entries after some combination of insertions and removals.
Tests of the copy constructor and assignment operator:
- Copy and assignment create a copy with the correct data.
- Copy and assignment create a deep copy.
- Copy and assignment function correctly when the source object is empty.
- Assignment protects against self-assignment.
Miscellaneous tests:
- All functions that return aboolstatus return the correct value.
- at(int indx)throwsrange_errorifindxis not a valid index.
- Expansion functions correctly. For example, insert 10 entries; check capacity; insert another entry; capacity should double.
- Contraction functions correctly. For example, insert 11 entries; check capacity; remove seven entries (so size falls to four); check capacity.
- Iterator-basedforloop lists entries in array order and terminates correctly.
- Iterator-basedforloop functions correctly for an emptyEntryList.
- *begin()returns first element of non-emptyEntryList;begin() != end()unless theEntryListis empty.
- Test for memory leaks and errors usingValgrind.
Graph
Basic tests of constructor,addEdge(), andremoveEdge():
- Constructor throwsinvalid_argumentifn≤0" role="presentation" style="background: none 0px 0px repeat scroll transparent; border: 0px; margin: 0px; padding: 1px 0px; vertical-align: baseline; display: inline-block; line-height: 0; font-size: 17.44px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative;">n≤0n≤0.
- Perform combinations of insertions and deletions, checking that the contents of the data structure are correct.
- addEdge()andremoveEdge()throwinvalid_argumentif passed an invalid vertex number.
Tests of the copy constructor and assignment operator:
- Copy and assignment create a copy with the correct data.
- Copy and assignment create a deep copy.
- Copy and assignment function correctly when the source object is empty.
- Assignment protects against self-assignment.
Tests of the edge iterator:
- Edge iterator functions correctly when every vertex has one or more neighbors.
- Edge iterator functions correctly when one or more vertex has no neighbors; includes the possibility of two or moreconsecutivevertices having no neighbors.
- Dereference and increment throwinvalid_argumentwhen applied to an uninitialized iterator.
- *egBegin()returns first edge of a non-emptyGraph;egBegin() != egEnd()unless theGraphhas no edges.
Tests of the neighbor iterator:
- Neighbor iterator functions correctly for vertices having one or more neighbors.
- Neighbor iterator functions correctly for vertices havingnoneighbors.
- Dereference and increment throwinvalid_argumentwhen applied to an uninitialized iterator.
- *nbBegin()returns first neighbor of a vertex;nbBegin() != nbEnd()unless the vertex has no neighbor