Topological sort is an important algorithm in DAG – directed acyclic graphs.
It orders each vertex in line from left to right such that left most vertex could be considered as the highest level or root or entrance of the graph and rightmost as the lowest of the graph.
In the end, topological sort tells you the order of vertices you need to go through from one node to the other without missing any middle vertices.
There could be multiple topological sorts in the same graph.
Let’s take a look at an example for a better understanding
Course Prerequisite Example
The course prerequisite is a great example of this kind of problem.
Let’s say there are 4 courses A, B, C, D and here are some prerequisites for each course.
- Course C requires A, B, D
- Course B requires A
- CourseD requires A, B
- A is a fundamental course you need to complete before any courses
With that in mind, in order to reach from A to C, we need to follow these steps.
- We see a path to node C directly from A but we also see B and D
- Visit B
- From B we see a path to C and D
- Visit D
- Now the order of node visit is A, B, D, C which is the correct order for course completion
However, the above steps are not complete yet for topological sort algorithm since some intuition plays a role there.
Here is the correct algorithm.
Topological Sort Algorithm
- Visit a node and mark it visited (but not processed yet)
- Search any nodes connected to the node from #1 and visit only if it’s not visited yet
- If you see any visited but not processed node then there is a cycle and you cannot find topological sort. (It will be an infinite loop!)
- Mark the node processed and push it into stack
- After all the nodes are processed pop each value from stack and pop order is the correct order for topological sort
Code Example
enum Status
{
UNDISCOVERED,
DISCOVERED,
PROCESSED
};
struct Node
{
Status status;
vector<int> destNodeIds;
};
// return false if there is a cycle
bool findOrderHelper(int currNodeId, unordered_map<int, Node> &nodes, vector<int> &order)
{
auto it = nodes.find(currNodeId);
it->second.status = DISCOVERED;
bool canPublish = true;
for_each(
it->second.destNodeIds.begin(),
it->second.destNodeIds.end(),
[&nodes, &canPublish, &order](int destNodeId)
{
auto it = nodes.find(destNodeId);
if (it->second.status == UNDISCOVERED)
{
canPublish &= findOrderHelper(destNodeId, nodes, order);
}
else if (it->second.status == DISCOVERED)
{
canPublish = false;
}
});
it->second.status = PROCESSED;
order.push_back(currNodeId);
return canPublish;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
{
vector<int> order;
// nodes is a graph constructed from prerequisites vector
unordered_map<int, Node> nodes;
for_each(
prerequisites.begin(),
prerequisites.end(),
[&nodes](const vector<int> &prerequisite)
{
auto it = nodes.insert(make_pair(prerequisite.back(), Node()));
it.first->second.destNodeIds.push_back(prerequisite.front());
nodes.insert(make_pair(prerequisite.front(), Node()));
});
// now iterate nodes (graph) to find topological sort
bool canPublish = true;
for_each(
nodes.begin(),
nodes.end(),
[&nodes, &order, &canPublish](const pair<int, Node> &nodeInfo)
{
if (nodeInfo.second.status == UNDISCOVERED)
{
canPublish &= findOrderHelper(nodeInfo.first, nodes, order);
}
});
if (!canPublish)
{
order.clear();
}
else if (order.size() != numCourses)
{
// courses don't have many prerequisites
for (int i = 0; i < numCourses; ++i)
{
auto it = find(order.begin(), order.end(), i);
if (it == order.end())
{
order.push_back(i);
}
}
}
reverse(order.begin(), order.end());
return order;
}