Problem A: Input: Number n of vertices (i.e. vertex set is {1,2, …,n}), and a li

Question

Problem A:

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 ivia a directed path in G; “not reachable”, otherwise. Note that a directed path lengthcan 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 MATRIX 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

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

class directGraph
{
    int noOfVertex;
  
    list<int> *listAdjacencyArray;
  
public:
    directGraph(int noOfVertex); // Constructor method
  
    void graphEdgeAdd(int i, int j); //here adding edge to a graph
  
    bool checkVertexsReach(int a, int b); //check if path exist between vertexs
};

directGraph::directGraph(int noOfVertex)
{
    this->noOfVertex = noOfVertex;
  
    listAdjacencyArray = new list<int>[noOfVertex];
}

void directGraph::graphEdgeAdd(int i, int j)
{
    listAdjacencyArray[i].push_back(j);
}

bool directGraph::checkVertexsReach(int a, int b)
{

    if (a == b)
    {
          return true;
   }

    bool *traversed = new bool[noOfVertex];
  
    for (int k = 0; k < noOfVertex; k++)
    {
        traversed[k] = false;
    }

    list<int> tmpList;

    traversed[a] = true;
  
    tmpList.push_back(a);

    list<int>::iterator l;

    while (!tmpList.empty())
    {
        a = tmpList.front();
        tmpList.pop_front();

        for (l = listAdjacencyArray[a].begin(); l != listAdjacencyArray[a].end(); ++l)
        {
            if (*l == b)
            {
                return true;
            }

            if (!traversed[*l])
            {
                traversed[*l] = true;
                tmpList.push_back(*l);
            }
        }
    }
   
    return false;
}

int main() // main class, program will start from here
{

    directGraph directG(5);
    directG.graphEdgeAdd(1, 2);
    directG.graphEdgeAdd(2, 5);
    directG.graphEdgeAdd(3, 4);
    directG.graphEdgeAdd(1, 3);
  
    int firstVertex, secondVertex;
  
    cout<<"Graph G is constructed";
  
    int wantToContinue =0;

    do
    {
       cin>>firstVertex;
  
       cin>>secondVertex;

       if(directG.checkVertexsReach(firstVertex, secondVertex))
       {
           cout<<"reachable"<<endl;
       }
       else
       {
           cout<<"not reachable"<<endl;
       }
      
       cout<<"For continue press 1 or for exit press 0"<<endl;
       cin>>wantToContinue;
      
   }while(wantToContinue != 0);
      
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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