Step 1: Inspect Vertex.h, Edge.h, and DirectedGraph.h

Inspect the Vertex class declaration in the Vertex.h file. Access Vertex.h by clicking on the orange arrow next to main.cpp at the top of the coding window. The Vertex class represents a graph vertex and has a string for the vertex label.

Inspect the Edge class declaration in the Edge.h file. The edge class represents a directed graph edge and has pointers to a from-vertex and a to-vertex.

Inspect the DirectedGraph abstract class declaration in the DirectedGraph.h file. DirectedGraph is an abstract base class for a directed, unweighted graph.

Step 2: Inspect AdjacencyListGraph.h and AdjacencyListVertex.h

The AdjacencyListGraph class inherits from DirectedGraph and is declared in AdjacencyListGraph.h. The vertices member variable is a vector of AdjacencyListVertex pointers. The vector contains all the graph's vertices.

The AdjacencyListVertex class inherits from Vertex and is declared in the read only AdjacencyListVertex.h file. The adjacent member variable is a vector of pointers to adjacent vertices.

Step 3: Inspect AdjacencyMatrixGraph.h

The AdjacencyMatrixGraph class inherits from DirectedGraph and is declared in AdjacencyMatrixGraph.h. The vertices member variable is a vector of Vertex pointers. The vector contains all the graph's vertices. The matrixRows member variable is a vector of matrix rows. Each row itself is a vector of bool values. If matrixRows[X][Y] is true, then an edge exists from vertices[X] to vertices[Y].

Indices in vertices correspond to indices in matrixRows. So if vertex "C" exists at index 2 in vertices, then row 2 and column 2 in the matrix correspond to vertex "C".

Step 4: Implement the AdjacencyListGraph class

Implement the required member functions in AdjacencyListGraph. Each function has a comment indicating the required functionality. The vertices vector must be used to store the graph's vertices and must not be removed. New member functions can be added, if needed, but existing function signatures must not change.

Step 5: Implement the AdjacencyMatrixGraph class

Implement the required member functions in AdjacencyMatrixGraph. Each function has a comment indicating the required functionality. The vertices and matrixRows vectors must be used to store the graph's vertices and adjacency matrix, respectively. Both must not be removed. New member functions can be added, if needed, but existing function signatures must not change.

Step 6: Test in develop mode, then submit

File main.cpp contains test cases for each graph operation. The test operations are first run on an AdjacencyListGraph. Then the same test operations are run on an AdjacencyMatrixGraph. Running code in develop mode displays the test results.

After each member function is implemented and all tests pass in develop mode, submit the code. The unit tests run on submitted code are similar, but use different graphs and perform direct verification of the graphs internal data members. Can you edit AdjacencyListGraph.h and AdjacencyMatrixGraph.h?

AdjacencyListGraph.h: #ifndef ADJACENCYLISTGRAPH_H #define ADJACENCYLISTGRAPH_H #include "DirectedGraph.h" #include "AdjacencyListVertex.h" class AdjacencyListGraph : public DirectedGraph { protected: std::vector vertices; public: virtual ~AdjacencyListGraph() { for (AdjacencyListVertex* vertex : vertices) { delete vertex; } } // Creates and adds a new vertex to the graph, provided a vertex with the // same label doesn't already exist in the graph. Returns the new vertex on // success, nullptr on failure. virtual Vertex* AddVertex(std::string newVertexLabel) override { // Your code here (remove placeholder line below) return nullptr; } // Adds a directed edge from the first to the second vertex. If the edge // already exists in the graph, no change is made and false is returned. // Otherwise the new edge is added and true is returned. virtual bool AddDirectedEdge(Vertex* fromVertex, Vertex* toVertex) override { // Your code here (remove placeholder line below) return false; } // Returns a vector of edges with the specified fromVertex. virtual std::vector GetEdgesFrom(Vertex* fromVertex) override { // Your code here (remove placeholder line below) return std::vector(); } // Returns a vector of edges with the specified toVertex. virtual std::vector GetEdgesTo(Vertex* toVertex) override { // Your code here (remove placeholder line below) return std::vector(); } // Returns a vertex with a matching label, or nullptr if no such vertex // exists virtual Vertex* GetVertex(std::string vertexLabel) override { // Your code here (remove placeholder line below) return nullptr; } // Returns true if this graph has an edge from fromVertex to toVertex virtual bool HasEdge(Vertex* fromVertex, Vertex* toVertex) override { // Your code here (remove placeholder line below) return false; } }; #endif AdjacencyMatrixGraph.h: #ifndef ADJACENCYMATRIXGRAPH_H #define ADJACENCYMATRIXGRAPH_H #include "DirectedGraph.h" class AdjacencyMatrixGraph : public DirectedGraph { protected: std::vector vertices; // If matrixRows[X][Y] is true, then an edge exists from vertices[X] to // vertices[Y] std::vector<:vector>> matrixRows; // Your additional code here, if desired public: virtual ~AdjacencyMatrixGraph() { for (Vertex* vertex : vertices) { delete vertex; } } // Creates and adds a new vertex to the graph, provided a vertex with the // same label doesn't already exist in the graph. Returns the new vertex on // success, nullptr on failure. virtual Vertex* AddVertex(std::string newVertexLabel) override { // Your code here (remove placeholder line below) return nullptr; } // Adds a directed edge from the first to the second vertex. If the edge // already exists in the graph, no change is made and false is returned. // Otherwise the new edge is added and true is returned. virtual bool AddDirectedEdge(Vertex* fromVertex, Vertex* toVertex) override { // Your code here (remove placeholder line below) return false; } // Returns a vector of edges with the specified fromVertex. virtual std::vector GetEdgesFrom(Vertex* fromVertex) override { // Your code here (remove placeholder line below) return std::vector(); } // Returns a vector of edges with the specified toVertex. virtual std::vector GetEdgesTo(Vertex* toVertex) override { // Your code here (remove placeholder line below) return std::vector(); } // Returns a vertex with a matching label, or nullptr if no such vertex // exists virtual Vertex* GetVertex(std::string vertexLabel) override { // Your code here (remove placeholder line below) return nullptr; } // Returns true if this graph has an edge from fromVertex to toVertex virtual bool HasEdge(Vertex* fromVertex, Vertex* toVertex) override { // Your code here (remove placeholder line below) return false; } }; #endif \#ifndef ADJACENCYLISTVERTEX_H \#define ADJACENCYLISTVERTEX_H \#include \#include "Vertex.h" class AdjacencyListVertex : public Vertex \{ public: // vector of vertices adjacent to this vertex. For each vertex V in this // vector, V is adjacent to this vertex, meaning an edge from this vertex to //V exists in the graph. std: :vector adjacent; AdjacencyListVertex(const std::string label) : Vertex(label) \{ \} virtual AdjacencyListVertex() \{ \} \} ; \#endif \#ifndef DIRECTEDGRAPH_H \#define DIRECTEDGRAPH_H \#include \#include \#include "Vertex.h" \#include "Edge.h" // Abstract base class for a directed, unweighted graph class DirectedGraph \{ public: virtual DirectedGraph() \{ \} // Creates and adds a new vertex to the graph, provided a vertex with the // same label doesn't already exist in the graph. Returns the new vertex on // success, nullptr on failure. virtual Vertex* AddVertex(std::string newVertexLabel) =0; // Adds a directed edge from the first to the second vertex. No change is // made and false is returned if the edge already exists in the graph. // Otherwise the new edge is added and true is returned. virtual bool AddDirectedEdge(Vertex* fromVertex, Vertex* toVertex) =0; // Returns a vector of edges with the specified fromVertex. virtual std::vector GetEdgesFrom(Vertex* fromVertex) = 0; // Returns a vector of edges with the specified tovertex virtual std::vector GetEdgesTo(Vertex* toVertex) =0; // Returns a vertex with a matching label, or nullptr if no such vertex // exists virtual Vertex* GetVertex(std::string vertexLabel) = 0; // Returns true if this graph has an edge from fromvertex to tovertex virtual bool HasEdge(Vertex* fromVertex, Vertex* toVertex) = 0; \}; \#endif \#ifndef EDGE_H \#define EDGE_H \#include \#include "Vertex.h" class Edge \{ public: Vertex* fromVertex; Vertex* toVertex; Edge(Vertex* from, Vertex* to) \{ fromVertex = from; toVertex = to; \} bool operator == (const Edge\& other) const \{ return fromVertex == other.fromVertex && toVertex == other.toVertex; \} bool operator!=(const Edge\& other) const \{ return ! (*this == other); \} // Prints this edge in the form "A to B ", where " A " is fromVertex's label // and " B " is toVertex's Label. void Print(std::ostream\& output) const \{ fromVertex->Print(output); output Print(output); \} \}; is marked as read only Current file: main.cpp \#include \#include \#include \#include "DirectedGraph.h" \#include "AdjacencyListVertex.h" \#include "AdjacencyListGraph.h" \#include "AdjacencyMatrixGraph.h" \#include "GraphCommands.h" using namespace std; bool TestGraph(ostream\& testFeedback, DirectedGraph\& graph); int main(int argc, char *argv[]) \{ // Test AdjacencyListGraph first AdjacencyListGraph graph1; cout = TestGraph(cout, graph2); // Print test results cout commands ={ new AddVertexCommand("A", true), new AddVertexCommand("B", true), // Verify that vertices A and B exist, but not C,D, or E new GetVertexCommand("C", false), new GetVertexCommand("A", true), new GetVertexCommand("B", true), new GetVertexCommand("E", false), new GetVertexCommand("D", false), // Add remaining vertices new AddVertexCommand("C", true), new AddVertexCommand("D", true), new AddVertexCommand("E", true), // Add edges new AddEdgeCommand("B", "C", true), new AddEdgeCommand("C", "A", true), new AddEdgeCommand("C", "D", true), new AddEdgeCommand("C", "E", true), new AddEdgeCommand("D", "C", true), new AddEdgeCommand("E", "A", true), new AddEdgeCommand("E", "D", true), // Attempts to add a duplicate edge should fail new AddEdgeCommand("C", "E", false), new AddEdgeCommand("D", "C", false), new VerifyEdgesFromCommand("A", \{\} ), new VerifyEdgesFromCommand("B", { "C" \}), new VerifyEdgesFromCommand("C", { "A", "D", "E" \}), new VerifyEdgesFromCommand("D", {"C"}), new VerifyEdgesFromCommand("E", { "A", "D" \}), new VerifyEdgesToCommand("A", \{ "C", "E" \}), new VerifyEdgesToCommand("B", \{\} ), new VerifyEdgesToCommand("C", \{ "B", "D" \}), new VerifyEdgesToCommand("D", \{ "C", "E" \}), new VerifyEdgesToCommand("E", {"C"}), // Verify some edges new HasEdgeCommand("A", "C", false), new HasEdgeCommand("A", "E", false), new HasEdgeCommand("B", "C", true), new HasEdgeCommand("C", "A", true), new HasEdgeCommand("C", "B", false), new HasEdgeCommand("C", "D", true), new HasEdgeCommand("C", "E", true), new HasEdgeCommand("D", "C", true), new HasEdgeCommand("E", "A", true), new HasEdgeCommand("E", "C", false), new HasEdgeCommand("E", "D", true) \} ; // Execute each test command, stopping if any command fails for (DirectedGraphTestCommand* command : commands) \{ bool pass = command->Execute(testFeedback, graph); delete command; if (!pass) \{ return false; \} \} return true; \#ifndef VERTEX_H \#define VERTEX_H \#include \#include class Vertex \{ protected: std::string label; public: Vertex(const std::string vertexLabel) \{ label = vertexLabel; \} virtual Vertex() \{ \} virtual std::string GetLabel() \{ return label; \} // Prints this vertex's Label virtual void Print(std::ostream\& output) \{ output