(C++)

A graph is comprised of a set of vertices and a set of edges. Each edge represents a connection between two vertices. Two vertices are neighbors if they are connected by an edge, and the degree of a vertex is its number of neighbors. Graph-processing algorithms generally first build an internal representation of a graph by adding edges, then process it by iterating over the vertices and over the vertices adjacent to a given vertex. For this lab assignment, you will implement a standard template library (STL) GRAPH data structure. You may use the implementation discussed in the lecture video, or implement your own code from scratch using the Linked List representation (as we did in the lecture video). Shown below is a sample representation of an undirected graph using the adjacency linked list representation: B B B m D mo B Undirected Graph Adjacency List As shown, we have a linked list (adjacency list) for each node. From vertex A, we have edges to vertices B, C and D. Thus these nodes are linked to node A in the corresponding adjacency list. For this lab assignment, you will also need to add weights along each edge to represent the cost between two nodes. You may use the following Graph class as a start, providing at a minimum the member functions listed (you may need to add more helper functions to support these main member functions)" #include #include template class Vertex { public: S data; // data to store at each vertex int ID; // ID of the vertex list=double> weights; // list of weights for all edges connected to vertex vector edge; // list of all vertices connected to this vertex static count_vertices; // use to keep count of how many vertices are added to the graph private: Vertex(S); S getdata() const; list=double> getweights(); // Not constant because we may want to change the weights vector getedge(); // Not constant because we may want to change the edges void setdata(S &); void addedge(Vertex *); void addweight(double ); int get_degree() const; // return the degree of a vertex ETC...(you may need to add additional member functions to implement this class) template class Graph { private: vector *> start; public: Graph(); Graph(string filename); // initialize graph from a file - you define the format of the file void dftraverse(); // depth first traversal vector *> shortest_path(int start, int end, double &s); // start = ID of starting vertex // end = ID of ending vertex // w is the total cost from start to end vector *> get_start() const; // get the starting vertex of the graph double compute_cost(vector *>); // compute cost given path of vertices void add_vertex(Vertex *); // add a vertex to the graph void print_path(vector *) const; Vertex * find_vertex(int ID); // find the vertex given its ID ETC... (you may need to add additional member functions to implement this class) }