Your Tasks Advance Part Task 1 Write a function that determi

Your Tasks: Advance Part

Task 1. Write a function that determines whether the graph is strongly connected or not. A graph is strongly connected if and only if every node can reach any other nodes.

Task 2. Write a function that determines whether the graph contains a cycle. You should notice that the graphs we consider here are directed graphs. The idea of DFS can be helpful in this task.

Task 3. Write some test cases for your code

Here is what I have so far:

   // include the required header files

   #include <iostream>

   #include <cstdlib>

   using namespace std;

   #define MAX 20

   //GraphAM

   class GraphAM

   {

       //Access specifier

   private:

       int n;

       int **adj;

       bool *visited;

       //Access specifier

   public:

       //Constructor

       GraphAM(int n)

       {

           this->n = n;

           visited = new bool[n];

           adj = new int*[n];

           for (int i = 1; i <= n; i++)

           {

               adj[i] = new int[n];

               for (int j = 1; j <= n; j++)

               {

                   adj[i][j] = 0;

               }

           }

       }

       //Add edge to graph

       void add_edge(int o, int d)

       {

           if (o > n || d > n || o < 0 || d < 0)

           {

               cout << \"Invalid edge!\ \";

           }

           else

           {

               adj[o][d] = 1;

           }

       }

       //initialize the visited

       void initializeVisited()

       {

           for (int i = 1; i <= n; i++)

               visited[i] = false;

       }

       //\"DFS\" traversal

       void depthFirstSrch(int vt)

       {

           //Set visited to true

           visited[vt] = true;

           //print visited vt

           printf(\"%d \", vt);

           //for all nodes in the graph

           for (int kk = 1; kk <= n; kk++)

               //check adjecent vertex is not visited

               if (adj[vt][kk] == 1 && visited[kk] == false)

                   //call depthFirstSrch

                   depthFirstSrch(kk);

       }

       //\"BFS\" traversal

       void breadthFirstSrch(int vt)

       {

           //Declare the required variables

           int kk, frt, rar;

           int q[20];

           frt = rar = -1;

           //print vt

           printf(\"%d \", vt);

           visited[vt] = true;

           rar++;

           frt++;

           q[rar] = vt;

           //until vertex in the graph

           while (frt <= rar)

           {

               //delete from queue

               vt = q[frt];

               frt++;

               //for all vertex in graph

               for (kk = 1; kk <= n; kk++)

               {

                   //checking adjecent unvisited nodes

                   if (adj[vt][kk] == 1 && visited[kk] == false)

                   {

                       //print visited kk

                       printf(\"%d \", kk);

                       visited[kk] = true;

                       rar++;

                       q[rar] = kk;

                   }

               }

           }

       }

       void display()

       {

           int i, j;

           for (i = 1; i <= n; i++)

           {

               for (j = 1; j <= n; j++)

                   cout << adj[i][j] << \" \";

               cout << endl;

           }

       }

   };

   int main()

   {

       int nodes, max_edges, o, d;

       cout << \"Enter number of nodes: \";

       cin >> nodes;

       GraphAM adjmatrix(nodes);

       int vt;

       max_edges = nodes * (nodes - 1);

       for (int i = 0; i < max_edges; i++)

       {

           cout << \"Enter edge (-1 -1 to exit): \";

           cin >> o >> d;

           if ((o == -1) && (d == -1))

               break;

           adjmatrix.add_edge(o, d);

       }

       cout << \"Adjacent matrix is: \ \";

       adjmatrix.display();

       cout << \"Enter start vertex:\";

       cin >> vt;

       //DFS traversal

       cout << \"DFS Traversal:\" << endl;

       adjmatrix.initializeVisited();

       adjmatrix.depthFirstSrch(vt);

       //BFS traversal

       cout << \"\ BFS Traversal:\" << endl;

       adjmatrix.initializeVisited();

       adjmatrix.breadthFirstSrch(vt);

       cin.get();

       cin.get();

       return 0;

   }

Solution

program #include <iostream>
#include <list>
#include <stack>
using namespace std;
class SGraph
{
int V;
list<int> *adj;
void fillOrder(int v, bool visited[], stack<int> &Stack);
void DFSUtil(int v, bool visited[]);
public:
SGraph(int V);
void addEdge(int v, int w);
int printSCCs();
Graph getTranspose();
};
SGraph::SGraph(int V)
{
this->V = V;
adj = new list<int> [V];
}
void SGraph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
cout << v << \" \";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
Graph SGraph::getTranspose()
{
SGraph g(V);
for (int v = 0; v < V; v++)
{
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
void SGraph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void SGraph::fillOrder(int v, bool visited[], stack<int> &Stack)
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
fillOrder(*i, visited, Stack);
Stack.push(v);
}
int SGraph::printSCCs()
{
stack<int> Stack;
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
fillOrder(i, visited, Stack);
SGraph gr = getTranspose();
for (int i = 0; i < V; i++)
visited[i] = false;
int count = 0;
while (Stack.empty() == false)
{
int v = Stack.top();
Stack.pop();
if (visited[v] == false)
{
gr.DFSUtil(v, visited);
cout << endl;
}
count++;
}
return count;
}
int main()
{
SGraph g(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
cout << \"Following are strongly connected components in given graph \ \";
g.printSCCs();
return 0;
}