Create an adjaceny list graph using the following functions in C++:

graph.h

class GraphPathNotFound { }; // Exception class represents path-not-found condition

class GraphEdgeNotFound { }; // Exception class represents edge-not-found condition

class GraphVertexNotFound { }; // Exception class represents vertex-not-found condition

class GraphFull { }; // Exception class represents graph-full condition

struct VertexNode; // Forward declaration of VertexNode type

struct EdgeNode // Structure representing an edge { VertexNode* destination; // Pointer to destination vertex int weight; // Edge weight EdgeNode* nextEdge; // Pointer to next edge };

struct VertexNode // Structure representing a vertex { string vname; // Name of vertex bool mark; // Marked flag EdgeNode* edgePtr; // Pointer to list of outgoing edges VertexNode* nextVertex; // Pointer to next vertex in vertices list };

class Graph // Graph ADT using adjacency list representation { private: //***** Private class members below *****// VertexNode* vertices; // Linked list of vertex nodes

public: //***** Public members below *****//

Functions to be Completed Graph(); // Graph() // Constructor initializes vertices linked list to empty ~Graph(); // ~Graph() // For each VertexNode in the vertices list, Destructor deallocates all EdgeNodes before // deallocating the VertexNode itself void AddVertex(string v); // AddVertex() // Adds vertex to graph assuming vertex not already present

void AddEdge(string s, string d, int w); // AddEdge() // Adds edge from source S to destination D with specified weight W. // If there is not enough memory to add the edge, throw the GraphFull exception VertexNode* VertexExists(string v) const; // VertexExists() // Returns pointer to corresponding VertexNode if vertex V in graph // Returns NULL otherwise

EdgeNode* EdgeExists(string s, string d) const; // EdgeExists() // Returns pointer to edge node if edge from vertex s to vertex d exists in graph // Returns NULL otherwise int WeightIs(string s, string d); // WeightIs() // Returns weight of edge (s,d). Throws GraphEdgeNotFound if edge not present. void ClearMarks(); // ClearMarks() // Clears all vertex marks void MarkVertex(string v); // MarkVertex() // Marks vertex V as visited // Throws GraphVertexNotFound if not present bool IsMarked(string v); // IsMarked() // Returns true if vertex V is marked, false if not marked // Throws GraphVertexNotFound if not present

void GetToVertices(string V, queue& q); // GetToVertices() // Returns queue Q of vertex names of those vertices adjacent to vertex V // The queue here is from the Standard Template Library // Throws GraphVertexNotFound if not present void DepthFirstSearch(string startVertex, string endVertex, queue& path); // DepthFirstSearch() // Notes: //