2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thanks. +1. Can you please elaborate on last point. Evert node is unique, isn't it? \$\endgroup\$ – Pranit Kothari Sep 12 '17 at 7:12
  • \$\begingroup\$ 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 \$\endgroup\$ – miscco Sep 12 '17 at 7:38
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I do remember your comment regarding test function. But here I am more focusing on Algorithm than design. Your review was helpful though. \$\endgroup\$ – Pranit Kothari Sep 12 '17 at 7:33
  • \$\begingroup\$ 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. \$\endgroup\$ – Roland Illig Sep 12 '17 at 7:36
  • \$\begingroup\$ Agreed. Will take care next time. \$\endgroup\$ – Pranit Kothari Sep 12 '17 at 7:38
  • 2
    \$\begingroup\$ Please add a link when you reference other anwsers/questions \$\endgroup\$ – miscco Sep 12 '17 at 7:41
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.