Write a C++ program called ts.cpp that implements the topological sorting algori

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 Input file format: This is a sample input file called tl.txt. 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, tl.txt describes a directed graph like below: This is a sample run of the program on the cloud9. Y our program should be compiled and executed exactly like this $ gtt -o ts ts.cpp Enter a filename: C:\tmp\tl.txt This is a DAG Start node (s): 0 Popping-off order: 2 1 0 Topological sort: 0 ->1 -> 2

Explanation / Answer

#include<iostream>
#include<fstream>
#include <list>
#include <stack>
#include <stdlib.h>
using namespace std;

// Class Graph definition
class Graph
{
// Data member to store number of vertices
int Vertices;

// Pointer to an array containing adjacency list
list<int> *adjacent;

// prototype of member function for topologicalSort
void topologicalSortHelper(int, bool [], stack<int> &);
public:
// Prototype of member functions
void setVertices(int);
// Function to add an edge to graph
void addEdge(int, int);

// Function to print Topological Sort of the complete graph
void printTopologicalSort();
};// End of class

// Parameterized constructor definition
void Graph::setVertices(int Vertices)
{
this->Vertices = Vertices;
adjacent = new list<int>[Vertices];
}// End of constructor

// Function to add an edge to graph
void Graph::addEdge(int ver, int wait)
{
// Add wait to vertices
adjacent[ver].push_back(wait);
}// End of function

// Recursive function used by topologicalSort
void Graph::topologicalSortHelper(int ver, bool visitedNode[], stack<int> &MyStack)
{
// Mark the current node as visited.
visitedNode[ver] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator c;
// Loops till end of the list using iterator
for (c = adjacent[ver].begin(); c != adjacent[ver].end(); ++c)
if (!visitedNode[*c])
topologicalSortHelper(*c, visitedNode, MyStack);

// Push current vertex to stack which stores result
MyStack.push(ver);
}// End of function

// Function to do Topological Sort. Takes the help of recursive function topologicalSortHelper()
void Graph::printTopologicalSort()
{

// Creates a stack of type integer
stack<int> MyStack;

// Mark all the vertices as not visited
bool *visitedNode = new bool[Vertices];
// Loops all the vertices
for (int c = 0; c < Vertices; c++)
visitedNode[c] = false;

// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int c = 0; c < Vertices; c++)
if (visitedNode[c] == false)
topologicalSortHelper(c, visitedNode, MyStack);

// Print contents of stack till stack is empty
while (MyStack.empty() == false)
{
cout << MyStack.top() << " ";
MyStack.pop();
}// End of while loop
}// End of function

// Function to read file and create a Graph
void readFile(Graph &g, string fileName)
{
// ifstream class object declared
ifstream rFile;
// To store number of vertices and edges
int ver;
int edge;
// To store the adjacency value
int one, two;
// Opens the file for reading
rFile.open(fileName.c_str());
// Check that file can be opened or not
// is_open() function returns true if a file is open and associated with this stream object.
// Otherwise returns false.
if(!rFile.is_open())
{
// Displays error message
cout<<" Error: Unable to open the file! "<<fileName;
return;
}// End of if condition
// Reads the vertices from file
rFile>>ver;
// Set the vertices to graph
g.setVertices(ver);
// Reads edges from file
rFile>>edge;
// Loops till number of edges
for(int c = 0; c < edge; c++)
{
// Reads the adjacency values
rFile>>one>>two;
// Calls the method to add the edges
g.addEdge(one, two);
}// End of ouster for loop
// Close the file
rFile.close();
}// End of function

// main function definition
int main()
{
// To store file name
string fileName;
// Create a graph given in the above diagram
Graph g;
do
{
// Accept file name
cout<<" Enter the file name (END to stop) : ";
cin>>fileName;
if(fileName.compare("END") == 0)
exit(0);
// Calls the function to read file
readFile(g, fileName);

cout << "Following is a Topological Sort of the given graph: ";
// Calls the function to display
g.printTopologicalSort();
}while(1);

return 0;
}// End of main function

Sample Output:

Enter the file name (END to stop) : Graph1.txt
Following is a Topological Sort of the given graph: 0 1 2
Enter the file name (END to stop) : Graph2.txt
Following is a Topological Sort of the given graph: 0 1 2 3
Enter the file name (END to stop) : Graph3.txt
Following is a Topological Sort of the given graph: 1 0 2 3 4
Enter the file name (END to stop) : Graph4.txt

Error: Unable to open the file! Graph4.txt

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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