Submit your solution in a header file named Graph.h Write a class named Graph th
ID: 2247049 • Letter: S
Question
Submit your solution in a header file named Graph.h Write a class named Graph that implements an unweighted, directional graph. The book is correct in that there are many different ways to implement a Graph, and you are free to choose the implementation that is easiest to you. As such, the following UML diagram only specifies the methods you must have in your public interface. Any private attributes will depend on your implementation and so are left undefined in the diagram Graph +addVertex(name: string): void +addEdge(from: string, to: string): void +removeVertex(name: string): void +removeEdge(from: string, to: string): void +printPath(from: string, to: string) void Attribute Descriptions: . addVertex): takes the name of the Vertex as it's only argument. The vertex is added to the graph addEdge0: takes the name of the source Vertex as it's first argument, an the destination Vertex as it's second argument. Adds the edge to the graph. So, if the edge is supposed to be (A, D), then the first argument would be "A" and the second would be removeVertex0: takes the name of a Vertex as it's only argument. The matching Vertex is removed from the graph, along with all edges pointing to it. removeEdge0: takes the names of adjacent Vertices as it's only arguments. Removes the matching edge from the graph. printPath0: Accepts a starting Vertex and an ending Vertex as it's arguments. Uses either Breadth-first or Depth-first search (your choice) to print all the nodes from the starting Vertex to the ending Vertex to the screen. If the ending Vertex is not found, should print "NO PATH FOUND" to the screen.Explanation / Answer
Given below is the implementation of graph using c++ STL vector and queue classes. It prints the path in BFS order.
Graph.h
#ifndef Graph_h
#define Graph_h
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
//class representing an unweighted directional graph
class Graph
{
private:
vector<string> vertices; //vertices in the graph
vector<vector<string>> edges; //for each vertex in the vertices list, its correspoding list of adjacen t vertices
int indexOf(vector<string> list, string vertex);
public:
Graph();
void addVertex(string v);
void removeVertex(string v);
void addEdge(string from, string to);
void removeEdge(string from, string to);
void printPath(string from, string to); //BFS traversal of graph to find the path
};
Graph::Graph()
{}
void Graph::addVertex(string v)
{
if(indexOf(vertices, v) == -1) //check that this vertex is not already added
{
vertices.push_back(v);
edges.push_back(vector<string>());//an empty edge list
}
}
void Graph::removeVertex(string v)
{
int idx = indexOf(vertices, v);
if(idx != -1)
{
vertices.erase(vertices.begin() + idx); //remove from vertex list
edges.erase(edges.begin() + idx); // delete the adjacent list of the vertex being deleted
}
}
void Graph::addEdge(string from, string to)
{
int idx1 = indexOf(vertices, from), idx2 = indexOf(vertices, to);
if(idx1 != -1 && idx2 != -1) //make sure both the vertices are in the vertex list
{
if(indexOf(edges[idx1], to) == -1) //only if the vertex is not already present in the adjancent list
edges[idx1].push_back(to);
}
}
void Graph::removeEdge(string from, string to)
{
int idx1 = indexOf(vertices, from), idx2 = indexOf(vertices, to);
if(idx1 != -1 && idx2 != -1) //make sure both the vertices are in the vertex list
{
idx2 = indexOf(edges[idx1], to);
if(idx2 != -1)//only if the vertex present in the adjancent list
edges[idx1].erase(edges[idx1].begin() + idx2);
}
}
void Graph::printPath(string from, string to)
{
if(indexOf(vertices, from) == -1 || indexOf(vertices, to) == -1)
{
cout << "One or both vertices not in the graph" << endl;
return;
}
vector<bool> visited(vertices.size(), false);
vector<string> path;
queue<string> que;
int idx1, idx2;
que.push(from);
visited[indexOf(vertices, from)] = true;
string curr;
while(!que.empty())
{
curr = que.front();
que.pop();
path.push_back(curr);
if(curr == to)
break;
idx1 = indexOf(vertices,curr);
for(int i = 0; i < edges[idx1].size(); i++)
{
string neigh = edges[idx1][i];
idx2 = indexOf(vertices, neigh);
if(!visited[idx2])
{
que.push(neigh);
visited[idx2] = true;
}
}
}
if(path.back() != to)
cout << "NO PATH FOUND" << endl;
else
{
cout << "BFS traversal from " << from << " to " << to << " is [" << path[0];
for(int i = 1; i < path.size(); i++)
cout << "-" << path[i];
cout <<"]" << endl;
}
cout << endl;
}
//finds the index of the given vertex in the given list, returns -1 if not found
int Graph::indexOf(vector<string> list, string vertex)
{
for(int i = 0 ;i < list.size(); i++)
if(list[i] == vertex)
return i;
return -1;
}
#endif /* Graph_h */
output of main
BFS traversal from A to D is [A-B-C-E-D]
BFS traversal from B to D is [B-A-C-E-D]
NO PATH FOUND