Topological sort of a graph

Question

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

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

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.

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.