Question

In this assignment you will implement the BFS and DFS graph traversal algorithms as a part of the code below (graph.cpp). graph.cpp sample edges.txt Here's the test - graph test.cpp The code reads in a graph from the sample_edges.txt file (to be put in the same directory as your code), and returns an adjacency list. The adjacency list is a vector, where each element is in turn a vector of (adjacent vertex, edge weight) pairs. Typedef is used to enhance readability. You are to use the adjacency list returned to implement the BFS and DFS algorithms. A header for the helper function is also included to implement DFS recursively. A utility function that prints the queue is provided to help you with the BFS implementation. Please do not modify any code provided including the test. Upload your implementation of DFS and BFS in graph.cpp

/* Graph read from file, and represnted as adjacency list.
To implement DFS and BFS on the graph
*/
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <set>
#include <queue>

using namespace std;

// Each vertex has an integer id.

typedef vector<vector<pair<int,int>>> adjlist; // Pair: (head vertex, edge weight)

adjlist makeGraph(ifstream& ifs);
void printGraph(const adjlist& alist);
vector<int> BFS(const adjlist& alist, int source); // Return vertices in BFS order
vector<int> DFS(const adjlist& alist, int source); // Return vertices in DFS order
void DFSHelper(const adjlist& alist, vector<int>& dfslist, vector<bool>& visited, int source);
void printQ(queue<int> qcopy);


// DFS - returns list of nodes in DFS order starting from source vertex
vector<int> DFS(const adjlist& alist, int source) {
// Your code here

}

void DFSHelper(const adjlist& alist, vector<int>& dfslist, vector<bool>& visited, int source) {
// Your code here

}

// BFS - returns list of nodes in BFS order starting from source vertex
vector<int> BFS(const adjlist& alist, int source) {
// Your code here

}




// Reads a csv graph from file and returns an adjacency list
adjlist makeGraph(ifstream& ifs) {
int vh, vt, wt;
string line;
unordered_multimap<int, pair<int, int>> elist;
set<int> vlist;

while (getline(ifs, line)) {
stringstream ss(line);
ss >> vt;
if (ss.peek() == ',')
ss.ignore();
ss >> vh;
if (ss.peek() == ',')
ss.ignore();
ss >> wt;

elist.emplace(vt, make_pair(vh, wt));
vlist.insert(vt);
vlist.insert(vh);
}

adjlist res(vlist.size()); // Preallocate vector

for (auto& ele : elist) {
  res.at(ele.first).push_back(make_pair(ele.second.first, ele.second.second));
}
return res;
}

// Prints the adjacency list (only vertices, not edge weights)
void printGraph(const adjlist& alist) {
int i = 0;
for (auto& v : alist) {
cout << i++ << ": ";
for (auto& av : v) {
cout << av.first << " ";
}
cout << endl;
}
}

// Prints queue for debugging
void printQ(queue<int> qcopy) {
while (!qcopy.empty()) {
cout << qcopy.front();
qcopy.pop();
}
cout << endl;
}

int main() {
ifstream ifs("sample_edges.txt");
adjlist alist = makeGraph(ifs);
printGraph(alist);
vector<int> dfslist = DFS(alist, 0);
for (auto& ele : dfslist) // Prints 0 2 4 5 1 3
cout << ele << " ";
cout << endl;

vector<int> bfslist = BFS(alist, 0);
for (auto& ele : bfslist) // Prints 0 2 1 4 3 5
cout << ele << " ";
cout << endl;

}

// sampletxt
//0, 1, 1
//0, 2, 1
//1, 3, 1
//2, 4, 1
//3, 4, 1
//3, 5, 1
//4, 5, 1
//0, 1, 1
//0, 2, 1
//1, 3, 1
//2, 4, 1
//3, 4, 1

Answer 1

Working code implemented in C++ and appropriate comments provided for better understanding:

Here I am attaching code for these files:

• graph_test.cpp
• graph.cpp

Source code for graph_test.cpp:

/* Test for BFS and DFS */
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <set>
#include <queue>

using namespace std;

// Each vertex has an integer id.

typedef vector<vector<pair<int,int>>> adjlist; // Pair: (head vertex, edge weight)
adjlist makeGraph(ifstream& ifs);
void printGraph(const adjlist& alist);
vector<int> BFS(const adjlist& alist, int source); // Return vertices in BFS order
vector<int> DFS(const adjlist& alist, int source); // Return vertices in DFS order

int main() {
ifstream ifs("sample_edges.txt");
adjlist alist = makeGraph(ifs);
printGraph(alist);
vector<int> dfslist = DFS(alist, 0);
for (auto& ele : dfslist) // Prints 0 2 4 5 1 3
cout << ele << " ";
cout << endl;
  
vector<int> bfslist = BFS(alist, 0);
for (auto& ele : bfslist) // Prints 0 2 1 4 3 5
cout << ele << " ";
cout << endl;
}

Source code for graph.cpp:

/* Graph read from file, and represnted as adjacency list.
To implement DFS and BFS on the graph
*/
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <set>
#include <queue>

using namespace std;

// Each vertex has an integer id.

typedef vector<vector<pair<int,int>>> adjlist; // Pair: (head vertex, edge weight)

adjlist makeGraph(ifstream& ifs);
void printGraph(const adjlist& alist);
vector<int> BFS(const adjlist& alist, int source); // Return vertices in BFS order
vector<int> DFS(const adjlist& alist, int source); // Return vertices in DFS order
void DFSHelper(const adjlist& alist, vector<int>& dfslist, vector<bool>& visited, int source);
void printQ(queue<int> qcopy);

// DFS - returns list of nodes in DFS order starting from source vertex
vector<int> DFS(const adjlist& alist, int source) {
   vector<bool> visited;
   vector<int> dfslist;
   for(auto& x : alist){
       visited.push_back(false);
   }
   DFSHelper(alist, dfslist, visited, source);  
   return dfslist;
}

void DFSHelper(const adjlist& alist, vector<int>& dfslist, vector<bool>& visited, int source) {
   visited[source] = true;
   dfslist.push_back(source);  
int i = 0;
for (auto& v : alist) {
if(i == source){
           for(auto& av : v) {
               if(!visited[av.first]){
                   DFSHelper(alist, dfslist, visited, av.first);
               }
           }
       }
       else{
           i++;
       }   
}
}

// BFS - returns list of nodes in BFS order starting from source vertex
vector<int> BFS(const adjlist& alist, int source) {
   vector<bool> visited;
   vector<int> bfslist;
   queue<int> q;
   int add;
   for(auto& x : alist){
       visited.push_back(false);
   }
  
   visited[source] = true;
   q.push(source);  
  
   while(!q.empty()){
       add = q.front();
       bfslist.push_back(add);
       q.pop();
       int i = 0;
       for (auto& v : alist) {
           if(i == add){
               for(auto& av : v) {
                   if(!visited[av.first]){
                       q.push(av.first);
                       visited[av.first] = true;
                   }
               }
           }
           i++;
       }
   }
   return bfslist;
}

// Reads a csv graph from file and returns an adjacency list
adjlist makeGraph(ifstream& ifs) {
int vh, vt, wt;
string line;
unordered_multimap<int, pair<int, int>> elist;
set<int> vlist;
  
while (getline(ifs, line)) {
stringstream ss(line);
ss >> vt;
if (ss.peek() == ',')
ss.ignore();
ss >> vh;
if (ss.peek() == ',')
ss.ignore();
ss >> wt;

elist.emplace(vt, make_pair(vh, wt));   
vlist.insert(vt);
vlist.insert(vh);
}
  
adjlist res(vlist.size()); // Preallocate vector
  
for (auto& ele : elist) {
res.at(ele.first).push_back(make_pair(ele.second.first, ele.second.second));
}
return res;
}

// Prints the adjacency list (only vertices, not edge weights)
void printGraph(const adjlist& alist) {
int i = 0;
for (auto& v : alist) {
cout << i++ << ": ";
for (auto& av : v) {
cout << av.first << " ";
}
cout << endl;
}
}

// Prints queue for debugging
void printQ(queue<int> qcopy) {
while (!qcopy.empty()) {
cout << qcopy.front();
qcopy.pop();
}
cout << endl;
}

Sample Output Screenshots:

sample_edges.txt 1 0,1,1 2 0,2,1 3 1,3,1 4 2,4,1 5 3,4,1 6 3,5,1 7 4,5,1 8 0,1,1 0,2,1 10 1,3,1 11 2,4,1 12 3,4,1 > clang++-7 -pthread -std=c++17 -o main Graph.cop main.cpp } ./main 0: 2 1 2 1 1: 3 3 2: 4 4 3: 4 5 4 4: 5 5: 0 2 4 5 1 3 0 2 1 4 3 5 9

Hope it helps, if you like the answer give it a thumbs up. Thank you.