Topological sort of a graph

Question

Please refer following graph.

enter image description here

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);
 }
}

Answer 1

Small nits from my side.

1. You are always using for (auto foo : bar). This involves a copy of foo. If you do not alter foo then you should use for (const auto& foo : bar)

2. As far as i know it is more idiomatic to check for existense of an element in a set via count. So rather than Visited.find(n) != Visited.end() you can check Visited.count(n) or the in my opinion way better Visited.count(n) != 1

3. Your code assumes every node is unique. You might want to adopt to a more robust approach utilizing a struct node that holds the data and then wr on pointers to that node

• Pranit Kothari: Thanks. +1. Can you please elaborate on last point. Evert node is unique, isn't it?
• miscco: In your problem yes, but as @Roland Illig pointed out your approach fails for graphs that have repeated characters. This is the reason for encapsulating the data into a helper structure so your algorithm works with multiple nodes ofidentical data

Answer 2

Too bad that you didn't learn anything from the last review I gave you.

Your class cannot be used for arbitrary graphs, but it should. If you wrote all this code for your simple example graph, it would be easier to just sort it using pen and paper.

The public API of your sorter must have functions for adding nodes and edges to the graph, and to inspect the result.

For the other stylistic remarks, see my answer to your code from some days ago.

• Pranit Kothari: I do remember your comment regarding test function. But here I am more focusing on Algorithm than design. Your review was helpful though.
• Roland Illig: By the way, if you only want to test your code on a single graph and not on arbitrary graphs, you don't even need to split your code into header and body files.
• Pranit Kothari: Agreed. Will take care next time.
• miscco: Please add a link when you reference other anwsers/questions

Answer 3

TopolocialSort is not a class. That doesn't change by just adding the token class in front of it.

You could argue a TopolocialSorter might be a class, but why would you make it one? The sorter has no state! Only the sort itself has state.

You might mistake

set<char> Visited;
stack<char> Sorted;
unordered_map<char, vector<char>> G;

for state, though. This is a very bad idea. G is an input argument, whereas Visited and Sorted are locals. Pass them around as function arguments, because that's how they're meant to be passed around. Faux-pas globals are much, much worse.

Just make functions, doing function-y things. It'll be cleaner and better express the intent.