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 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. In the program, your program has to follow our convention (= ascending order). So, your program starts from the node 0 between the two possible starting nodes 0 and 1. And also, you should follow our convention in the DFS algorithm.

Input file format:

This is another sample input file called t2.txt. 00 1 0 0 00 1 0 0 000 1 1 000 0 1 This is a sample run: $ g+t -o ts ts.cpp /ts Enter a filename: C:\tmp\t2.txt Start node (s): 0 1 Popping-off order: 4 3 20 1 Topological sort: 1 ->0 2 -> 3 - 4

Explanation / Answer

Code:

//Include libraries

#include <iostream>

#include <fstream>

#include <vector>

#include <cassert>

//Use namespace std

namespace std {   };

//Use std namespace

using namespace std;

//Define a method operator>>()

istream& operator>>(istream& is, vector<vector<size_t> >& graph)

{

     //Declare variables

     size_t li = 0, lj = 0;

     //Read li

     is >> li;

     //Resize graph

     graph.resize(li);

     //Loop until length

     while (is >> li >> lj)

     {

          //Decrement li

          --li;

    

          //Decrement lj

          --lj;

          //If li not equals lj

          if (li != lj)

          {

              //Push element

              graph[li].push_back(lj);

          }

     }

     //Return

     return is;

}

//Define a method lts()

void lts(vector<vector<size_t> >& graph, vector<bool>& explored, size_t li, vector<size_t>& sorted, size_t& lt)

{

     //Set value

     explored[li] = true;

     //Loop until length

     for (size_t lj = 0; lj < graph[li].size(); ++lj)

     {

          //If value is false

          if (explored[graph[li][lj]] == false)

          {

              //Call method

              lts(graph, explored, graph[li][lj], sorted, lt);

          }

     }

     //Decrement lt

     --lt;

     //Assign value

     sorted[lt] = li;

     //Return

     return;

}

//Define a method ltsloop

void ltsloop(vector<vector<size_t> >& graph, vector<size_t>& sorted)

{

     //Define a vector

     vector<bool> explored(graph.size(), false);

  

     //Define size

     size_t lt = graph.size();

     //Loop until length

     for (size_t li = 0; li < graph.size(); ++li)

     {

          //If value is false

          if (explored[li] == false)

          {

              //Call method

              lts(graph, explored, li, sorted, lt);

          }

     }

     //Assert

     assert(lt == 0);

     //Return

     return;

}

//Define a main method

int main(int argc, char* argv[])

{

     //Define a vector

     vector<vector<size_t> > graph;

     //If argument present

     if (argc > 1)

     {

          //Define file reader

          ifstream ifs;

          //Open file reader

          ifs.open(argv[1]);

          //Take graph

          ifs >> graph;

          //Close

          ifs.close();

     }

     //Assert

     assert(graph.size() == 7);

     //Define vector

     vector<size_t> sorted(graph.size(), 0);

  

  

     //Call method

     ltsloop(graph, sorted);

     //Display message

     cout << "Input Graph Size: " << graph.size() << endl

     << "Possible Topological sorted order: ";

     //Loop until length

     for (size_t li = 0; li < sorted.size(); ++li)

     {

          //Display value

          cout << (sorted[li] + 1) << ", ";

     }

     //Display new line

     cout << endl;

   

     //Pause console window

     system("pause");

     //Return 0

     return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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