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