Question

Introduction In this lab, you are supposed to implement a graph class with the data structure implemented before like linked list and queue.

graph

The class graph contains three member variables:

• linkedList *adjacentVertices; //an array of linked list. For a vertice i, adjacentVertices[i] stores the linked list that contains all other vertices connected to vertice i.
• int numVertices; //The number of vertices in the graph.
• int maxNumVertices; //The maximum number of vertices the graph can hold.

Following public methods are needed:

graph(int n = 100); //Constructor, initializes the parameters with maximum vertices given, default to be 100
bool isEmpty() const;
//Function to determine whether the graph is empty. Returns true if it is, otherwise, returns false;
void createGraph(string file_name);
//Function to create a graph based on a file, whose name is file_name.
void clearGraph();
//Function to clear graph. Allocate all memories occupied by vertices
string printGraph() const;
//Function to return the graph as a string in adjacent list format.
string depthFirstTraversal();
//Function to perform the depth first traversal of the entire graph. Return a string with vertice id in the order of visit.

string breadthFirstTraversal();
//Function to perform the breadth first traversal of the entire graph. Return a string with vertice id in the order of visit.


~graph();
//Destructor. The storage occupied by the vertices is deallocated.

Adjacent List Format

Both the file given and the output you return in printGraph() are formatted by the adjacent list format. The format contains one single number n in the first line, which indicates the number of vertices. Each vertice has a corresponding id ranging from 0 to n-1. There are n lines following the first line. The ith line contains vertices that is adjacent (has an edge connected to) the ith vertice. For instance, the file below indicates a graph with 5 vertices. Vertice 0, 1, 2 and 3 are connected to each other, while vertice 4 is connected to vertice 0 only.

5

1 2 3 4

0 2 3

0 1 3

0 1 2

0

linkedList.h code

#include <iostream>
using namespace std;
template <class Type>
struct nodeType{
   Type info;
   nodeType<Type> *link;
};
template <class Type>
class linkedList {
private:
   int count;
   nodeType<Type> *first;
   nodeType<Type> *last;
public:
   linkedList();
   int length();
   void insertLast(const Type& newItem);
   void insertFirst(const Type& newItem);
   void deleteNode(const Type& deleteItem);
   void destroyList();
   string print() const;
   ~linkedList();
   nodeType<Type> *begin(){return first;}
   nodeType<Type> *end(){return NULL;}
};
template <class Type>
linkedList<Type>::linkedList(){
   first = NULL;
   last = NULL;
   count = 0;
}

template <class Type>
int linkedList<Type>::length(){
   return count;
}

template <class Type>
void linkedList<Type>::insertLast(const Type& newItem){
   nodeType<Type> *newNode; //pointer to create the new node
   newNode = new nodeType<Type>; //create the new node
   newNode->info = newItem; //store the new item in the node
   newNode->link = NULL; //set the link field of newNode to NULL

   if (first == NULL) //if the list is empty, newNode is both the first and last node{
      first = newNode;
      last = newNode;
      count++; //increment count
   }
   else //the list is not empty, insert newNode after last {
      last->link = newNode; //insert newNode after last
      last = newNode; //make last point to the actual last node in the list
      count++; //increment count
   }
}

template <class Type>
void linkedList<Type>::insertFirst(const Type& newItem){
   nodeType<Type> *newNode; //pointer to create the new node
   newNode = new nodeType<Type>; //create the new node
   newNode->info = newItem; //store the new item in the node
   newNode->link = first; //insert newNode before first
   first = newNode; //make first point to the actual first node
   count++; //increment count

   if (last == NULL) //if the list was empty, newNode is also the last node in the list
      last = newNode;
}//end insertFirst
template <class Type>
string linkedList<Type>::print() const{
   string result;
   nodeType<Type> *current; //pointer to traverse the list
   current = first; //set current point to the first node
   while (current != NULL) //while more data to print {
      result += to_string(current->info) + " ";
      current = current->link;
   }
   result.pop_back();
   return result;
}

template <class Type>
void linkedList<Type>::destroyList(){
   nodeType<Type> *temp; //pointer to deallocate the memory occupied by the node
   while (first != NULL) //while there are nodes in the list{
      temp = first; //set temp to the current node
      first = first->link; //advance first to the next node
      delete temp; //deallocate the memory occupied by temp
   }
   last = NULL; //initialize last to NULL; first has already been set to NULL by the while loop
   count = 0;
}

template <class Type>
linkedList<Type>::~linkedList(){
   destroyList();
}

template <class Type>
void linkedList<Type>::deleteNode(const Type& deleteItem){
   nodeType<Type> *current; //pointer to traverse the list
   nodeType<Type> *trailCurrent; //pointer just before current
   bool found;
   if (first == NULL) //Case 1: the list is empty.
      cout << "Cannot delete from an empty list." << endl;
   else{
      if (first->info == deleteItem) //Case 2: delete first node{
         current = first;
         first = first->link;
         count--;
         if (first == NULL) //the list has only one node
            last = NULL;
         delete current;
      }
      else //search the list for the node with the given info{
         found = false;
         trailCurrent = first; //set trailCurrent to point to the first node
         current = first->link; //set current to point to the second node
         while (current != NULL && !found){
            if (current->info != deleteItem)
            {
               trailCurrent = current;
               current = current-> link;
            }
            else
               found = true;
         }//end while
         if (found) //Case 3; if found, delete the node{
            trailCurrent->link = current->link;
            count--;
            if (last == current) //node to be deleted was the last node
               last = trailCurrent; //update the value of last
            delete current; //delete the node from the list
         }
         else
         cout << "The item to be deleted is not in the list." << endl;
      }//end else
   }//end else
}//end deleteNode

link to queue.h code ->  

#ifndef QUEUE_TYPE_H
#define QUEUE_TYPE_H
#include <iostream>
#include <cassert>
using namespace std;

template <class Type>
class queue{
public:
   queue(int queueSize = 100);

   bool is_empty() const;
   bool is_full() const;

   void initialize();
   Type front() const;
   Type back() const;

   void enqueue(const Type& element);
   void dequeue();
   ~queue();
private:
   int maxQueueSize; //variable to store the maximum queue size
   int count; //variable to store the number of
   int queueFront; //variable to point to the first
   int queueRear; //variable to point to the last
   Type* list; //pointer to the array that holds
};
#endif // !QUEUE_TYPE_H
template <class Type>
queue<Type>::queue(int queueSize) {
   if (queueSize <= 0){
       maxQueueSize = 100;
   }
   else{
       maxQueueSize = queueSize; //set maxQueueSize to
   }
   queueFront = 0; //initialize queueFront
   queueRear = maxQueueSize - 1; //initialize queueRear
   count = 0;
   list = new Type[maxQueueSize];
}
template <class Type>
bool queue<Type>::is_empty() const {
   return (count == 0);
}
template <class Type>
bool queue<Type>::is_full() const {
   return (count == maxQueueSize);
}
template <class Type>
void queue<Type>::initialize() {
   queueFront = 0;
   queueRear = maxQueueSize - 1;
   count = 0;
}
template <class Type>
Type queue<Type>::front() const {
   assert(!is_empty());
   return list[queueFront];
}
template <class Type>
Type queue<Type>::back() const {
   assert(!is_empty());
   return list[queueRear];
}
template <class Type>
void queue<Type>::enqueue(const Type& queueElement) {
   if (!is_full()){
       queueRear = (queueRear + 1) % maxQueueSize; //use the
       count++;
       list[queueRear] = queueElement;
   }
   else
       cout << "Cannot add to a full queue." << endl;
}
template <class Type>
void queue<Type>::dequeue() {
   if (!is_empty()){
       count--;
       queueFront = (queueFront + 1) % maxQueueSize; //use the
   }
   else
       cout << "Cannot remove from an empty queue" << endl;
}
template <class Type>
queue<Type>::~queue() {
   delete[] list;
}

//graph.h

#include "linkedList.h"
#include "queue.h"
#include
#include
#include
#include
using namespace std;
#ifndef GRAPH_H
#define GRAPH_H

class graph
{
protected:
   linkedList *adjacentVertices;
   int numVertices;
   int maxNumVertices;

public:
   graph(int n = 100); //Constructor, initializes the parameters with maximum vertices given, default to be 100
   bool isEmpty() const;
   //Function to determine whether the graph is empty. Returns true if it is, otherwise, returns false;
   void createGraph(string file_name);
   //Function to create a graph based on a file, whose name is file_name.
   void clearGraph();
   //Function to clear graph. Allocate all memories occupied by vertices
   string printGraph() const;
   //Function to return the graph as a string in adjacent list format.
   string depthFirstTraversal();
   //Function to perform the depth first traversal of the entire graph. Return a string with vertice id in the order of visit.

   string breadthFirstTraversal();
   //Function to perform the breadth first traversal of the entire graph. Return a string with vertice id in the order of visit.
   ~graph();
   //Destructor. The storage occupied by the vertices is deallocated.
};
#endif

Answer 1

#include <iostream>
using namespace std;
template <class Type>
struct nodeType{
Type info;
nodeType<Type> *link;
};
template <class Type>
class linkedList {
private:
int count;
nodeType<Type> *first;
nodeType<Type> *last;
public:
linkedList();
int length();
void insertLast(const Type& newItem);
void insertFirst(const Type& newItem);
void deleteNode(const Type& deleteItem);
void destroyList();
string print() const;
~linkedList();
nodeType<Type> *begin(){return first;}
nodeType<Type> *end(){return NULL;}
};
template <class Type>
linkedList<Type>::linkedList(){
first = NULL;
last = NULL;
count = 0;
}

template <class Type>
int linkedList<Type>::length(){
return count;
}

template <class Type>
void linkedList<Type>::insertLast(const Type& newItem){
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode to NULL

if (first == NULL){ //if the list is empty, newNode is both the first and last node{
first = newNode;
last = newNode;
count++; //increment count
}
else{//the list is not empty, insert newNode after last {
last->link = newNode; //insert newNode after last
last = newNode; //make last point to the actual last node in the list
count++; //increment count
}
}

template <class Type>
void linkedList<Type>::insertFirst(const Type& newItem){
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = first; //insert newNode before first
first = newNode; //make first point to the actual first node
count++; //increment count

if (last == NULL) //if the list was empty, newNode is also the last node in the list
last = newNode;
}//end insertFirst
template <class Type>
string linkedList<Type>::print() const{
string result="";
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current point to the first node
while (current != NULL){ //while more data to print {
result += to_string(current->info) + " ";
current = current->link;
}
return result;
}
//---------------------------------
template <class Type>
void linkedList<Type>::destroyList(){
nodeType<Type> *temp; //pointer to deallocate the memory occupied by the node
while (first != NULL){ //while there are nodes in the list{
temp = first; //set temp to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate the memory occupied by temp
}
last = NULL; //initialize last to NULL; first has already been set to NULL by the while loop
count = 0;
}

template <class Type>
linkedList<Type>::~linkedList(){
destroyList();
}

template <class Type>
void linkedList<Type>::deleteNode(const Type& deleteItem){
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1: the list is empty.
cout << "Cannot delete from an empty list." << endl;
else{
if (first->info == deleteItem){ //Case 2: delete first node{
current = first;
first = first->link;
count--;
if (first == NULL) //the list has only one node
last = NULL;
delete current;
}
else{ //search the list for the node with the given info{
found = false;
trailCurrent = first; //set trailCurrent to point to the first node
current = first->link; //set current to point to the second node
while (current != NULL && !found){
if (current->info != deleteItem)
{
trailCurrent = current;
current = current-> link;
}
else
found = true;
}//end while
if (found){ //Case 3; if found, delete the node{
trailCurrent->link = current->link;
count--;
if (last == current) //node to be deleted was the last node
last = trailCurrent; //update the value of last
delete current; //delete the node from the list
}
else
cout << "The item to be deleted is not in the list." << endl;
}//end else
}//end else
}//end deleteNode

//-----------graph.h-----------------------

#include "linkedList.h"
#include <queue>
#include <stack>
using namespace std;
#ifndef GRAPH_H
#define GRAPH_H

class graph
{
protected:
linkedList<int> *adjacentVertices;
int numVertices;
int maxNumVertices;

public:
graph(int n = 100){ //Constructor, initializes the parameters with maximum vertices given, default to be 100
adjacentVertices=new linkedList<int>[n];
maxNumVertices=100;
}
bool isEmpty() const;
//Function to determine whether the graph is empty. Returns true if it is, otherwise, returns false;
void createGraph(string file_name){//Function to create a graph based on a file, whose name is file_name.
ifstream file;
file.open(file_name);
if(!file){
cout << endl << "Failed to open file ";
return;
}
string str;
getline(file, str);
int V=stoi(str);
numVertices=V;

int starting,ending;
bool flag=false;
int k=0;
int value;

for(int j=0;j<V;j++) {
getline(file, str);
string word = "";
int vertex;
int i=0;
for (auto x : str)
{
if (x == ' ')
{
vertex=stoi(word);
adjacentVertices[k].insertLast(vertex);
//cout<<vertex<<"-";
word = "";

}
else if(i == str.length()-1){
word = word + x;
vertex=stoi(word);
adjacentVertices[k].insertLast(vertex);
//cout<<vertex<<"-";

}
else
{
word = word + x;
}
i++;
}
k++;
}

}
//-----------------------------------------------
void clearGraph(){}
//Function to clear graph. Allocate all memories occupied by vertices
//Function to return the graph as a string in adjacent list format.
string printGraph() {
//cout<<numVertices<<endl;
string outputGraph="";
for(int i=0;i<numVertices;i++){
outputGraph=outputGraph+to_string(i)+"->"+adjacentVertices[i].print()+"\n";
}
return outputGraph;
}

//Function to perform the depth first traversal of the entire graph. Return a string with vertice id in the order of visit.
string depthFirstTraversal(){

bool *visited=new bool[numVertices];
for(int i=0;i<numVertices;i++)
visited[i]=false;
stack<int> S;
string str="";
string adjacent;

for(int i=0;i<numVertices;i++){
if(visited[i]==false){
S.push(i);
while(S.size()!=0){
int v=S.top();
//cout<<v<<endl;
S.pop();

//cout<<v<<endl;
visited[v]=true;
str=str+to_string(v)+"->";
adjacent=adjacentVertices[v].print();
//cout<<adjacent<<endl;

int adjVertex;
int len=0;
string word ="";
for (auto x : adjacent)
{
if (x == ' ')
{
adjVertex=stoi(word);

if(visited[adjVertex]==false){
S.push(adjVertex);
visited[adjVertex]=true;
//break;
}
word = "";

}
else if(len == str.length()-1){
word = word + x;
adjVertex=stoi(word);

if(visited[adjVertex]==false){
S.push(adjVertex);
visited[adjVertex]=true;
//break;
}
}
else
{
word = word + x;
}
len++;
}

}
}
}
return str;
}
//Function to perform the breadth first traversal of the entire graph. Return a string with vertice id in the order of visit.
string breadthFirstTraversal(){

bool *visited=new bool[numVertices];
for(int i=0;i<numVertices;i++)
visited[i]=false;
queue<int> Q;
//Q.initialize();
string str="";
string adjacent;

for(int i=0;i<numVertices;i++){
if(visited[i]==false){
Q.push(i);
while(Q.size()!=0){
int v=Q.front();
//cout<<v<<endl;
Q.pop();

//cout<<v<<endl;
visited[v]=true;
str=str+to_string(v)+"->";
adjacent=adjacentVertices[v].print();
//cout<<adjacent<<endl;

int adjVertex;
int len=0;
string word ="";
for (auto x : adjacent)
{
if (x == ' ')
{
adjVertex=stoi(word);

if(visited[adjVertex]==false){
Q.push(adjVertex);
visited[adjVertex]=true;
}
word = "";

}
else if(len == str.length()-1){
word = word + x;
adjVertex=stoi(word);

if(visited[adjVertex]==false){
Q.push(adjVertex);
visited[adjVertex]=true;
}
}
else
{
word = word + x;
}
len++;
}

}
}
}
return str;
}

~graph(){}
//Destructor. The storage occupied by the vertices is deallocated.
};
#endif

//-------------main.cpp---------------------

#include<iostream>
#include<fstream>
#include<string>
#include "graph.h"

using namespace std;

int main(){
graph G;
G.createGraph("input.txt");
cout<<"Adjacency list representation of Graph"<<endl;
cout<<G.printGraph()<<endl;
cout<<"Breath first Search"<<endl;
cout<<G.breadthFirstTraversal()<<endl<<endl;
cout<<"Depth first Search"<<endl;
cout<<G.depthFirstTraversal()<<endl;
return 0;
}

//----------------------------------

input.txt

7
1 2
0 3 4 5
0
1
1
1 6
5

output:

"C\Users\CSA 2\Dropbox\C Adjacency 1list representation of Graph 01 2 1-0 3 4 5 2->0 3-1 4-1 5-1 6 6-5 Breath first Search В->1->2->3->4->5->6-> Depth first Search В-32-1->5->6->4->3->

NOTE: Inbuilt queue and stack is used for BFS and DFS traversal respectively.