C++ COde Input: Number n of vertices (i.e. vertex set is {1,2, …,n}), and a list

Question

C++ COde

Input: Number n of vertices (i.e. vertex set is {1,2, …,n}), and a list of edges (i,j) for 1 i,j n for a directed graph G. After this part, read a list of pair of vertices, one pair at a time.

Output: For each given pair of vertices i, j, output “reachable” if vertex j is reachable from vertex i via a directed path in G; “not reachable”, otherwise. Note that a directed path length can be larger than one.

Goal: Create the directed graph G from the given input, and decide for every given pair of vertices if the second vertex is reachable from the first vertex via a directed path in G. Assume that every vertex is reachable from itself in zero steps.

Hint: You can maintain an array of vertices in which you mark reachable vertices.

Example input file:

5

1 2

2 5

3 4

1 3

Example dialog (still during the same execution of the program):

Graph G is constructed

1 2

reachable

1 5

reachable

1 4

not reachable

2 4

not reachable

5 5 0

reachable

In this assignment, you write a C++ program for Problem A. Both correctness and efficiency of your programs are important. You are required to use ADJACENCY LIST to represent arcs of graph G.

Explanation / Answer

Comments added

#include<iostream>
#include <list>
#include <fstream>
#include <sstream>
using namespace std;

class Directed_Graph
{
int VerticesCount; // vertices count
list<int> *adjacenylist; // adjacency list to store links
public:
Directed_Graph(int vertex); // Constructor
void addNodeEdge(int source, int destination); //adding edge to graph
bool isPathExist(int source, int destination); //check path exists
};

//constructor
Directed_Graph::Directed_Graph(int vertex)
{
this->VerticesCount = vertex;
adjacenylist = new list<int>[vertex];
}

//adding edge between nodes
void Directed_Graph::addNodeEdge(int source, int destination)
{
adjacenylist[source].push_back(destination);
}

// check path exists or not .. BFS search
bool Directed_Graph::isPathExist(int source, int destination)
{
// checking for self
if (source == destination)
return true;

// first marking all vertices are unvisited
bool *verticesVisited = new bool[VerticesCount];
for (int k = 0; k < VerticesCount; k++)
verticesVisited[k] = false;

// declaring BFSqueue for BFS search
list<int> BFSqueue;

// keep vertex marked and push into BFSBFSqueue
verticesVisited[source] = true;
BFSqueue.push_back(source);

// declare iterator
list<int>::iterator iter;

while (!BFSqueue.empty())
{
// checking front back vertices
source = BFSqueue.front();
BFSqueue.pop_front();

// check vertices and marked them, which are visited
for (iter = adjacenylist[source].begin(); iter != adjacenylist[source].end(); ++iter)
{
// if ditrectly path is present. return one
if (*iter == destination)
return true;

//otherwise repeat process
if (!verticesVisited[*iter])
{
verticesVisited[*iter] = true;
BFSqueue.push_back(*iter);
}
}
}
  
return false;
}

int main()
{
// creating graph with vertices and edges
std::ifstream readfile("file.txt");//reding numbers from text file
std::string eachline;
int count=0;
int data[10][10];

//reading file
while (std::getline(readfile, eachline))
{
std::istringstream iss(eachline);
int n1,n2;

while (iss >> n1,int n2)//reading each value from file
{
if(count == 0){
data[count][0] = n1;
count++;
}
else{
data[count][0] = n1;
data[count][1] = n2;
count++;
}
}
}

Directed_Graph graph(data[0][0]);
//creating remaining edges
for(int i=1;i<count;i++){
graph.addNodeEdge(data[i][0], data[i][1]);
}

//calling methods
cout<<" Graph G is constructed";
if(graph.isPathExist(1, 2))
cout<< " Reachable";
else
cout<< " Not Reachable";

if(graph.isPathExist(1, 5))
cout<< " Reachable";
else
cout<< " Not Reachable";

if(graph.isPathExist(1, 4))
cout<< " Reachable";
else
cout<< " Not Reachable";

if(graph.isPathExist(2, 4))
cout<< " Reachable";
else
cout<< " Not Reachable";
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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