C++ Program Graph DFS

You should write a DFS function to perform Depth First Search on a graph and print out the vertices using the DFS traversal (comma-separated, in one line). Implement the recursive version of the DFS. You also need to modify main function to call dfs function on the input graph.

Required member functions

public: void dfs(); private: void dfs_visit(Vertex &); 

The tasks for this lab are as follows:

Read a graph from a file.

Construct the corresponding graph in memory. The graph must be represented by adjacent lists. You are required to use STL lists for this. Here is a resource for the STL list class and Pair template. We will also discuss the use of an STL map for more efficient graph construction. Here is a resource for STL map. Run Breadth First Search(BFS) on the graph, annotating each node with its level, i.e. the lowest number of hops the node is from the start vertex. Output the annotated graph in .dot format. Display the graph .dot file in dotty. Input File Format: The input file is in the following format:

The first line gives the number of nodes N and the second line the number of edges M ( both positive integer s). You can assume the following: N is at most MaxN = 50 M is at most maxM = 200. The next N lines contain node labels, one per line. Each node's label is a string of at most maxNameLength = 15 characters(spaces not allowed). Note: The first node in the input file is assumed to be the start vertex for the graph when traversing it. The next M lines contain edges e = (u,v,c) described by the source vertex label u followed by the sink vertex label v followed by the cost c of going from vertex u to v. Graph Structure: You should organize your program into the following files/classes.

Graph.h - Graph class

The following data members/member functions should be present.

vector vertices - A vector containing all of the vertices in the graph. The start vertex is in the first position in the vector.

Graph(ifstream& ifs) - Reads the graph input file and instantiates a graph object.

void output_graph(const string & filename) - Outputs graph object to a .dot file, then makes a system call that calls dotty on this file. In the dotty file, each node should include vertex label and its distance value.

void dfs()- Depth First Search.

Vertex.h - Vertex class

The following data members should be present. Initially distance should be INT_MAX for all vertices. Distance gets updated during BFS traversal. - int distance - Distance the vertex is from the start vertex. - list > neighbors - An STL list of STL pairs. For each int,int pair , the integer values are the neighboring vertex's position in the graph object's vector vertices and the cost of the edge to that neighbor. - string label - Individual vertex's label. - vertex* prev - A pointer to the previous vertext in BFS traversal. Initially prev is null for all vertices.

Provided files

Sample input files can be accessed from the following link. Also header files, main.cpp file is provided in this link: https://drive.google.com/drive/folders/0B2yW_TPa-9oiLWpFSnIzeDhhQTg