Topological Sort C++

Question

Comments on optimizing the code or improving the code are requested. The input parameters to the class constructor are a one dimensional array of job ID's and the second argument is a list of vectors each vector containing two elements which specifies a constraint that the first job should be scheduled before the second job

#include <vector>
#include <stack>

// 1. Build Graph structure from the edges. (Create an adjacency list)
// 2. At each node, perform a DFS search
// 3. Push elements onto a stack as we recurse
// 4. Maintain graph color to detect cycles and terminate recursion if already visited node
// 5. Once we finished with all child nodes -> pop off the stack onto the solution vector

// W -> Node has not been visited
// G -> Node is part of current recursive search
// B -> Node has been visited and NOT part of current recursive search
enum color
{
    W, G, B
};

class Graph
{
    private:
    std::unordered_map<int, color> visited;
    std::unordered_map<int, vector < int>> adj;
    std::vector<int> sortedOrder;
    std::stack<int> nodeStack;
    std::vector<int> jobsVector;
    bool cycleDetected;

    public:
        Graph(const std::vector<int> &jobs, const std::vector<vector < int>> &deps)
        {
            jobsVector = jobs;
            for (auto dep: deps)
            {
                addDepedency(dep[0], dep[1]);
            }

            for (auto job: jobs)
            {
                visited[job] = W;
            }

            cycleDetected = false;
        }

    void addDepedency(int a, int b)
    {
        adj[a].push_back(b);
    }

    void topoSort()
    {
        for (auto job: jobsVector)
        {
            DFS(job);
        }
    }

    void DFS(int job)
    {
        auto children = adj[job];
        for (auto node: children)
        {
            if (visited[node] == G)
            {
                cycleDetected = true;
                return;
            }

            if (!(visited[node] == B))
            {
                visited[node] = G;
                DFS(node);
            }
        }

        if (!(visited[job] == B))
        {
            visited[job] = B;
            nodeStack.push(job);
        }

        return;
    }

    vector<int> getSortedOrder()
    {
        if (!cycleDetected)
        {
            while (!nodeStack.empty())
            {
                auto top = nodeStack.top();
                sortedOrder.push_back(top);
                nodeStack.pop();
            }

            return sortedOrder;
        }

        // If there is a cycle in the graph return an empty vector
        return {};
    }
};   

Answer 1

We use std::unordered_map but haven't included the corresponding header. Perhaps that works on your implementation, but it's not portable to depend on that.

addDepedency would be easier to find in a search if "dependency" were spelt correctly. And does it need to be public:? What about topoSort() and DFS() - are they part of the public interface too?

I really don't see why we have an object for this - it seems it does all its work in the constructor, and provides a "get" member to access the result - that seems equivalent to (but more complicated than) an ordinary function that accepts inputs and returns the result.

The deps argument is a vector of vectors, but we only ever use the first two elements of the inner vectors - should it be a vector of pairs instead?

There are absolutely no unit tests included with this code. This algorithm is highly amenable to unit testing, since there are no external dependencies, and there are many useful test cases we could (should) write. I wouldn't accept this code in a pull request without a comprehensive set of tests.