Please refer following graph.
Please review following code for topological sort.
I can sense one odd thing in my code, TS()
is calling TSUtil()
, still I had to write Visited.emplace(n.first);
and Sorted.emplace(n.first);
in TS()
.
Please suggest if I could handle it better.
test()
method is called from main to test the code.
I tried to follow C++ 11 standard.
.h file
#pragma once
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
using std::set;
using std::stack;
using std::unordered_map;
using std::vector;
class TopolocialSort
{
private:
set<char> Visited;
stack<char> Sorted;
unordered_map<char, vector<char>> G;
void createGraph();
void TS();
void TSUtil(vector<char> childNode);
void PrintTS();
public:
void test();
};
.cpp
#include "TopolocialSort.h"
#include <iostream>
using std::cout;
using std::endl;
void TopolocialSort::createGraph()
{
G['A'].push_back('E');
G['A'].push_back('C');
G['B'].push_back('D');
G['B'].push_back('C');
G['C'].push_back('\0');
G['D'].push_back('F');
G['E'].push_back('F');
G['E'].push_back('H');
G['F'].push_back('G');
G['G'].push_back('\0');
G['H'].push_back('\0');
}
void TopolocialSort::test()
{
createGraph();
TS();
PrintTS();
}
void TopolocialSort::PrintTS()
{
while (!Sorted.empty())
{
cout << Sorted.top() <<" ";
Sorted.pop();
}
}
void TopolocialSort::TSUtil(vector<char> childNode)
{
for (auto n : childNode)
{
//will visit node only once
if (Visited.find(n) != Visited.end())
{
continue;
}
Visited.emplace(n);
TSUtil(G[n]);
Sorted.emplace(n);
}
}
void TopolocialSort::TS()
{
for (auto n : G)
{
//will visit node only once
if (Visited.find(n.first) != Visited.end())
{
continue;
}
Visited.emplace(n.first);
TSUtil(n.second);
Sorted.emplace(n.first);
}
}