Question

Write a C++ program called ts.cpp that implements the topological sorting algorithm based on the DFS algorithm. Your program should read an input file name and determine if the input graph is a DAG (= directed acyclic graph) or not. If the graph is not a DAG, your program has to stop without further processing. However, if it’s a DAG, your program should display the starting node(s), popping-off order, and topologically sorted list. In the problem, you can assume that the number of nodes in the input file is less than 100.

When we grade your programming assignment, we will use the g++ compiler on the cloud9. So, you must use the cloud9 for the homework. Additionally, you must include five items such as “Title”, “Abstract”, “Class ID”, “Name”, and “Date” at the beginning of the program as head comments.

Input file format: This is a sample input file called t1.txt.

3

2

0 1

1 2

The first line (= 3 in the example) indicates that there are three vertices in the graph. The second line (= 2 in the example) presents the number of edges in the graph. The remaining two lines are the edge information in the graph. For the homework, you should assume that the first vertex starts from the number 0. Thus, t1.txt describes a directed graph like below:

One blank space is used to delimiter the data. Note that there’s no blank space at the end of each line. If your program does not read the file properly, your program will get no credit. And also, note that you used this format at the homework 2.

This is a sample run of the program on the cloud9. Your program should be compiled and executed exactly like this.

$ g++ -o ts ts.cpp

$ ./ts

Enter a filename: C:\\tmp\\t1.txt

This is a DAG.

Start node(s): 0

Popping-off order: 2 1 0

Topological sort: 0 -> 1 -> 2

In the program, your program has to follow our convention (= ascending order) as you learned in the class.

This is another sample input file called t2.txt.

4

4

0 1

1 2

2 3

3 1

t2.txt describes a directed graph like below:

This is a sample run on the cloud9:

$ g++ -o ts ts.cpp

$ ./ts

Enter a filename: C:\\tmp\\t2.txt

This is not a DAG.

This is the last sample input file called t3.txt.

5

5

2 3

3 4

1 2

0 2

2 4

t3.txt describes a directed graph like below:

This is a sample run on the cloud9:

$ g++ -o ts ts.cpp

$ ./ts

Enter a filename: C:\\tmp\\t3.txt

This is a DAG.

Start node(s): 0 1

Popping-off order: 4 3 2 0 1

Topological sort: 1 -> 0 -> 2 -> 3 -> 4

Again, your program must follow our convention (= ascending order). Thus, your program starts from the node 0 between the two possible starting nodes 0 and 1.

Answer 1

Implemented c++ source code:-
======================
#include<iostream>
#include <fstream>
#include <list>
#include <stack>
using namespace std;
class DAG_Graph
{
public:
int Vertices;
list<int> *adj;
public:
DAG_Graph(int Vertices)
{
this->Vertices=Vertices;
adj = new list<int>[Vertices];
}   
void addEdge(int Vertices, int width)
{
adj[Vertices].push_back(width);
}
void Topo_Sort()
{
stack<int> Stack;
bool *visited = new bool[Vertices]; // Mark all the vertices as not visited
for(int i=0;i<Vertices;i++)
visited[i] = false;
for(int i=0;i<Vertices;i++)
if(visited[i]==false)
SortUtil(i, visited, Stack);
while(Stack.empty() == false)
{
cout<< Stack.top()<<"-> ";
Stack.pop();
}
}
void SortUtil(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])
SortUtil(*i, visited, Stack);
Stack.push(v);
}
};
int main()
{
char filename[]="Topo.txt";
cout<<"\n-----------------------------------------";
cout<<"\n**** Implementation of Topological sort ***";
cout<<"\n-----------------------------------------";
cout<<"\nPlease enter the Filename ";
cin>>filename;
ifstream infile;
infile.open(filename);
int length,width,vertices;
infile>>length;
infile>>length;
DAG_Graph graph(length);
for(int i=2;i<length;i++)
{
infile>>vertices;
infile>>width;
graph.addEdge(vertices,width);
}
cout<<"\nThe Order is: "<<endl;
graph.Topo_Sort();
infile.close();
return 0;
}

input file(Topo.txt):-
===============
5
5
2 3
3 4
1 2
0 2
2 4

Sample Output:-
============
-----------------------------------------
**** Implementation of Topological sort ***
-----------------------------------------
Please enter the Filename Topo.txt
The Order is:
1-> 2-> 3-> 4-> 0->
--------------------------------
Process exited after 4.888 seconds with return value 0
Press any key to continue . . .





$C:\UsersiVENKEWDesktop\Chegg-TasksTopo-Sort.exe Implementation of Topological sort C3 Please enter the Filename Topo.txt The Order is: Process exited after 4.888 seconds with return value e Press any key to continue .. .$