22.10 Lab 10: C++ Program Graph DFS You should write a DFS function to perform D

Question

22.10 Lab 10: 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

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

Explanation / Answer

main.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include "Graph.H"
#include "Vertex.H"

using namespace std;

int main() {

    Graph g1;

    ifstream InFile("input.txt");
    g1.build_graph(InFile);
    g1.bfs();
    //g1.print();

    ofstream ofs("output.dot");
    if(!ofs) {
        cout << "output.dot could not be opened." << endl;
        exit(1);
    }

    ofs << "// Digraph // lab 7 // output.dot // cs014_16sum1 //" << endl << endl;
    ofs << "digraph G { //nodes" << endl;

    //vector<Vertex*>::iterator it=g1.vertices.begin();
    //it++;

   // while (it != g1.vertices.end()) {
    int length = g1.vertices.size();

    for (int i=1; i<length; i++) {
       ofs << i << " [color = orange, peripheries=2, style = filled, label="key=" << (g1.vertices[i])->label;
       ofs << ", distance=" << (g1.vertices[i])->distance << ""];" << endl;

       int numNeighbors = ((g1.vertices[i])->neighbors).size();
       for (int j=0; j<numNeighbors; j++) {
           ofs << i << " -> " << ((g1.vertices[i])->neighbors)[j] << endl;
       }

    }

    ofs << endl << "}" << endl;

    return 0;
}

Graph.h

#ifndef GRAPH_H_
#define GRAPH_H_

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include "Vertex.H"

using namespace std;

class Graph {
   public:
       Graph();
       ~Graph();
       vector< Vertex* > vertices;
       void build_graph(ifstream& ifs);
       void output_graph();
       void bfs();
       void print();
       int getLocation( string );
   private:
       int numNodes;
       int numEdges;
};

#endif

Graph.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <sstream>
#include <limits>
#include "Graph.H"
#include "Vertex.H"

#define MaxN 50
#define MaxM 200
#define INFINITY numeric_limits<int>::max()

using namespace std;

Graph::Graph() {

   numNodes=0;
   numEdges=0;

}

Graph::~Graph() {

   while (!vertices.empty()) {
       //cout << "Deleting: " << (vertices.back())->label << endl;
       delete vertices.back();
       vertices.pop_back();
   }

}

void Graph::build_graph(ifstream& ifs) {

   string line;
   string node, neighbor;
   string parameter;
   map <string, vector<string> > graphMap;

   // Read in Number of Nodes and Number of Edges
       ifs >> parameter;
       numNodes = stoi(parameter);
       ifs >> parameter;
       numEdges = stoi(parameter);

   // Read in all of the nodes and their neighbors to a map
   while( getline(ifs, line) ) {
       istringstream iss(line);
       iss >> node;
       graphMap[node].push_back("");
       while ( iss >> neighbor ) {
           graphMap[node].push_back(neighbor);
       }
   }

   // Iterate through all of the keys in the map to get each unique vertex
   for (map< string, vector<string> >::iterator it=graphMap.begin(); it != graphMap.end(); it++) {
        Vertex* newVertex = new Vertex( it->first );
       vertices.push_back(newVertex);
    }

    // Extrapolate the Neighbors from the map and place them in neighbors vector of the
    // appropriate vertex
    for ( vector< Vertex* >::iterator it1=vertices.begin(); it1 != vertices.end(); it1++ ) {
        for (map< string, vector<string> >::iterator it2=graphMap.begin(); it2 != graphMap.end(); it2++ ) {          
            if ( (it2->first) == (*it1)->label) {              
               for ( vector<string>::iterator it3=(it2->second).begin(); it3 != (it2->second).end(); it3++ ) {
                   int location = getLocation(*it3);
                   if (location != -1 && location != 0) {
                       ((*it1)->neighbors).push_back( location );
                   }
               }
           }
        }
    }

}

int Graph::getLocation( string node ) {

   int i=0;
   for ( vector< Vertex* >::iterator iter=vertices.begin(); iter != vertices.end(); iter++ ) {
       if ( (*iter)->label == node ) {
           return i;
       }
       i++;
   }
   return -1;

}

void Graph::bfs() {

   Vertex* root = vertices[1];
  
   // Create an Empty Queue
   queue< Vertex* > Q;

   root->distance = 0;
   Q.push(root);

   while (!Q.empty()) {
       Vertex* current = Q.front();
       Q.pop();

       int numNeighbors = (current->neighbors).size();
       for (int i=0; i<numNeighbors; i++) {
           int neighbor = (current->neighbors)[i];
           if (vertices[neighbor]->distance == INFINITY) {
               vertices[neighbor]->distance = current->distance + 1;
               Q.push(vertices[neighbor]);
           }
       }
   }

}

void Graph::print() {

   cout << "Graph: " << endl;
   for ( vector<Vertex*>::iterator it=vertices.begin(); it != vertices.end(); ++it ) {
       cout << "Node: " << (*it)->label << endl;
       cout << "Distance: " << (*it)->distance << endl;
       cout << "Neighbors: " << endl;
       for ( vector<int>::iterator NB=((*it)->neighbors).begin(); NB != ((*it)->neighbors).end(); NB++ ) {
           cout << *NB << endl;
       }
   }  

}

Vertex.h

#ifndef VERTEX_H_
#define VERTEX_H_

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <list>

using namespace std;

class Vertex {
   public:
       Vertex();
       Vertex(string);
       ~Vertex();
       string label;
       int distance;
       vector<int> neighbors;
   private:
};

#endif

Vertex.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <limits>
#include "Vertex.H"

#define MaxN 50
#define MaxM 200

using namespace std;

Vertex::Vertex() {

   label = "";
   distance = numeric_limits<int>::max();

}

Vertex::Vertex( string l ) {

   label = l;
   distance = numeric_limits<int>::max();

}

Vertex::~Vertex() {}

input.txt

8
20
Nile
Mondavi
Lodi
Rivoli
Pyramids
Zurich
Marengo
Friedland
Nile Rivoli
Marengo Rivoli
Pyramids Mondavi
Pyramids Lodi
Friedland Mondavi
Mondavi Lodi
Lodi Mondavi
Nile Marengo
Mondavi Nile
Lodi Rivoli
Zurich Nile
Rivoli Nile
Mondavi Zurich
Lodi Pyramids
Pyramids Marengo
Zurich Pyramids
Zurich Lodi
Friedland Nile
Mondavi Friedland
Friedland Marengo

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.