For this computer assignment, you are to write a C++ program to implement several graph algorithms on simple graphs. These graphs are implemented with adjacency list representation.

The graph is created from a text file that contains the adjacency matrix representation of a graph. The first line of the file is an integer n indicating the number of vertices in the graph. Next there is a (n+1)(n+1) table where the first row and the first column are names of vertices. The table records edges of the graph. Integer 1 indicates an edge exists between a pair of vertices. Integer 0 indicates no edge.

For a given graph size, each vertex of a graph can be referenced by index values 0, 1, , ( size 1 ); however, vertices of a graph are labeled consecutively by capital letters, starting from A, which corresponds to the index value 0. Use index values when you refer to a vertex in a graph in implementing the algorithms; use vertex labels only in printing. The edges are recorded in the data member adj_list, which is a vector object. The vertex labels are recorded in the data member labels, which is also a vector object. For example, you can use labels[0] to get the name of the first vertex, and adj_list[0] to get the list of edges (recorded as integer indexes of destination vertices) from the first vertex as the source.

#include #include #include #include using namespace std;

class graph { private: int size; std::vector< std::list > adj_list; std::vector< char > labels; void depth_first(int); public: graph(const char* filename); ~graph(); int get_size() const; void traverse(); void print() const; };

graph::graph(const char* filename) //This is the constructor. It reads from the input file of the graph with //adjacency matrix representation and builds the graph with adjacency list representation.

void graph::depth_first(int v) //This private function is used to traverse a graph in the depth - first traversal //search algorithm starting at the vertex with the index value of v.To implement this //method(and together with the traverse method below), you may need several global variable and objects

void graph::traverse() //This public function is used to traverse a graph and invokes //the above depth_first method. You will also need to display traverse result:

void graph::print() const //This function prints the adjacency list for the graph. The following //line is an example from an output.

int main(int argc, char** argv) { if ( argc < 2 ) { cerr << "args: input-file-name "; return 1; } graph g(argv[1]);

g.print(); g.traverse();

return 0; }

inpute :

7 A B C D E F G A 0 1 0 0 0 0 1 B 1 0 0 1 1 0 0 C 0 0 0 0 0 1 0 D 0 1 0 0 1 0 0 E 0 1 0 1 0 0 0 F 0 0 1 0 0 0 0 G 1 0 0 0 0 0 0