Create a C++ Graph class for undirected weighted graphs

Graphs are stored as adjacency matrices. Vertexes are non-negative integers. Assume a graph will not have more than 100 vertexes. Weights are positive integers.

The private section should contain 1) the matrix representing the graph, and 2) the vertexes in the graph.

The public section should contain a default constructor. When a graph is created, a 100 by 100 integer matrix for it is created and its components are all set to zeros, and the set of vertexes in the graph is set to empty

Use a 100 component boolean array to specify if a given vertex is in the graph or not. (E.g.,to see if vertex i is in the graph, check if the component at index i is true.) So initially this array would have all values set to false.

Additional member functions should be included as follows:

void addVertex (int vertex) adds vertex to the graph

void addEdge (int vertex1, int vertex2, int weight) adds an edge between vertex1 and vertex2 with the specified integer weight.

void removeEdge (int vertex1, int vertex2) removes the edge between vertex1 and vertex2.

void removeVertex (int vertex) removes vertex from the graph.

bool isEdge (int vertex1, int vertex2) returns true if there is an edge between vertex1 and vertex2.

int edgeWeight (int vertex1, int vertex2) returns the weight of the edge between vertex1 and vertex2 or zero if there is no edge.

bool isNeighbor (int vertex1, int vertex2) returns true if the graph contains an edge from vertex1 to vertex2.

string toString() converts the graph to a printable string representation, listing all vertex names followed by the start/finish of all edges with a dash between the 2 followed by the weight in parentheses, such as "{0, 1, 2, 3: 0-1 (13), 1-2 (20), 1-3 (11), 2-3 (53)}" for the graph.

Add a member function called minSpanningTree that takes a graph and a vertex X in the graph as its only parameters and returns a minimum spanning tree rooted at X for the graph.

Add a member function called treeSum that takes a tree as its only parameter and returns the sum of all the edges of the tree

Add a member function shortestPathTree which takes 2 parameters: a graph and a vertex X in the graph, and returns a shortest path tree from X to the other vertexes in the graph.

Add a member function path which takes 3 parameters: a shortest path tree T, the root of the tree X, and a vertex Y, and returns the path from X to Y in the shortest path tree T. (note: a path is a graph)

Add a member Function pathLength which takes a single parameter: a path produced by the above path function and returns the sum of the weights of all the edges in the path.

Add a member function readGraph which takes a path specifying the location of a text file as its only parameter, and creates an instance of a graph. The format of the text file consists of a sequence of ordered triples of the form (vertex1, vertex2, weight). Each triple specifies that vertex1 and vertex2 are vertexes in the graph and that there is an edge between them with the specified weight. E.G., (2 5 80) indicates that there is an edge with a weight of 80 that extends between vertexes 2 and 5.

This is the graph.txt file

(1 8 21) (9 10 18) (0 2 49) (3 4 92) (7 8 75) (3 7 9) (3 6 87) (2 3 18) (8 9 33) (6 7 19) (2 7 98) (4 8 90) (0 7 56) (2 6 32) (0 5 52) (1 2 75) (2 5 0) (5 6 44) (0 4 25) (0 3 51) (4 5 44) (1 4 47) (0 1 34) (1 5 57) (2 4 3)

endfile

a. Determine a minimal spanning tree for the graph rooted at vertex 0 and print it out (using the member function toString) along with the sum of the weights in the tree

b. Determine a shortest path tree for the graph showing all the shortest paths from vertex 1 and print it out.

c. Print out the path from vertex 1 to vertex 7 in the tree produced by part b along with the total length of the path(the sum of the weights of all the edged in the path).