Write C++ program on graphs Input: Number n of vertices (i.e. vertex set is {1 ,

Question

Write C++ program on graphs

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 <ENTER>

reachable

1 5 <ENTER>

reachable

1 4 <ENTER>

not reachable

2 4 <ENTER>

not reachable

5 5 0 <ENTER>

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. See a large input file for creating G on Page 5 (the last page). Test it with your list of pairs of vertices for reachable/not reachable queries.

Explanation / Answer

//Assuming the directed graph is one way direction

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>

using namespace std;

int main() {
   string line;
   ifstream myfile("D:/ravi/Cheg/directedgraph.txt");

   int adjMax[50][50]; //change max size as per your need
   if (myfile.is_open()) {
       //read file data
       string line;
       int n = 0; //cur size of adjacency matrix - nodes of the grpah
       int count = 0;
       int index = 0;
       int val[2];
       int i,j;
       for(i = 0; i < 50; i++)
       for(j = 0; j < 50; j++)
           adjMax[i][j] = 0;
       while (getline(myfile, line)) {

           string word;

           istringstream iss(line, istringstream::in);
           index = 0;

           if (iss) {
               val[0] = 0;
               val[1] = 0;
               //cout << word << endl;
               if (count == 0) {//line 1
                   iss >> word;
                   istringstream(word) >> n;
                }
                else {
                   //other lines- elements of edges
                   iss >> word;
                   istringstream(word) >> val[index++];
                   iss >> word;
                   istringstream(word) >> val[index++];
               }
           }
           if(count > 0 && val[0] > 0 && val[1] > 0) {
               //2nd line onwards are edges
               adjMax[val[0]][val[1]] = 1;
           }

            count++;

       }
       myfile.close();

       int k = 0;
       //derive indirect reachability
       for(i = 1; i <= n; i++) {
           for(j = 1; j <= n; j++) {
//           cout << " i = " << i << " j == " << val[0] << " -- "<<adjMax[i][val[0]] << endl;
               if(adjMax[i][j] == 1) {
                   //check new node is reachable from other nodes or not
                   for(k = 1; k <= n; k++) {
                       if(adjMax[j][k] == 1)
                           adjMax[i][k] = 1;
                   }
               }
           }
       }

       cout << " Adjancy matrix for graph with n = " << n << endl;
       for(i = 1; i <= n; i++) {
               for(j = 1; j <= n; j++)
               cout << adjMax[i][j] << " ";
               cout <<endl;
       }
       cout <<" Graph G is constructed" <<endl;

       int node1 = 0, node2 = 0;
       while(node1 >= 0) {
           cout << "Enter two nodes of edge:" <<endl;
           cin >> node1;
           cin >> node2;
           if(node1 > 0 && node1 <= n)
               cout <<(adjMax[node1][node2] == 1 ? " Reachable" : " Not reachable") <<endl;
       }
   }

   else
       cout << "Unable to open file";

}

--output----

Adjancy matrix for graph with n = 5
0 1 1 1 1
0 0 0 0 1
0 0 0 1 0
0 0 0 0 0
0 0 0 0 0
Graph G is constructed
Enter two nodes of edge:
1 2
Reachable
Enter two nodes of edge:
1 5
Reachable
Enter two nodes of edge:
2 4
Not reachable
Enter two nodes of edge:
2 3
Not reachable
Enter two nodes of edge:
-1
1

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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