Topological Sort: Python, C++ Algorithm Example
Alyssa Walker
What is Topological Sort Algorithm?
Topological Sorting is also known as Kahn’s algorithm and is a popular Sorting Algorithm. Using a directed graph as input, Topological Sort sorts the nodes so that each appears before the one it points to.
This algorithm is applied on a DAG (Directed Acyclic Graph) so that each node appears in the ordered array before all other nodes are pointed to it. This algorithm follows some rules repeatedly until the sort is completed.
To simplify, look at the following example:
Here, we can see that “A” has no indegree. It means the edge that points to a node. “B” and “C” have a pre-requisite of “A”, then “E” has a pre-requisite of “D” and “F” nodes. Some of the nodes are dependent on other nodes.
Here’s another representation of the above Graph:
So, when we pass the DAG (Directed Acyclic Graph) to the topological sort, it will give us an array with linear ordering, where the first element has no dependency.
This example shows a graph with a cycle:
Here’re the steps to do this:
Step 1) Find the node with zero incoming edges, a node with zero degrees.
Step 2) Store that zeroes in-degree node in a Queue or Stack and removes the node from the Graph.
Step 3) Then delete the outgoing edge from that node.
This will decrement the in-degree count for the next node.
Topological ordering requires that the graph data structure will not have any cycle.
A graph will be considered a DAG if it follows these requirements:
- One or more nodes with an indegree value of zero.
- Graph doesn’t contain any cycle
As long as there’re nodes in the Graph and the Graph is still DAG, we will run the above three steps. Otherwise, the algorithm will fall into the cyclic dependency, and Kahn’s Algorithm won’t be able to find a node with zero in-degree.
How Topological Sort Works
Here, we will use “Kahn’s Algorithm” for the topological sort. Let’s say we have the following Graph:
Here’re the steps for Kahn’s Algorithm:
Step 1) Calculate the indegree or incoming edge of all nodes in the Graph.
Note:
- Indegree means the directed edges pointing to the node.
- Outdegree means the directed edges that come from a node.
Here’s the indegree and outdegree of the above Graph:
Step 2) Find the node with zero indegrees or zero incoming edges.
The node with zero indegree means no edges are coming toward that node. Node “A” has zero indegrees, meaning there’s no edge pointing to node “A”.
So, we will do the following actions:
- Remove this node and its outdegree edges (outgoing edges)
- Place the node in the Queue for ordering.
- Update the in-degree count of the neighbor node of “A.”
Step 3) We need to find a node with an indegree value of zero. In this example, “B” and “C” have zero indegree.
Here, we can take either of these two. Let’s take “B” and delete it from the Graph.
Then update the indegree values of other nodes.
After performing these operations, our Graph and Queue will look like the following:
Step 4) Node “C” has no incoming edge. So, we will remove node “C” from the Graph and push it into the Queue.
We can also delete the edge that is outgoing from “C”.
Now, our Graph will look like this:
Step 5) We can see that nodes “D” and “F” have the indegree of zero. We will take a node and put it in the Queue.
Let’s take out “D” first. Then the indegree count for node “E” will be 1. Now, there’ll be no node from D to E.
We need to do the same for node “F”, our result will be like the following:
Step 6) The indegree (ingoing edges) and outdegree (outgoing edges) of node “E” became zero. So, we have met all the pre-requisite for node “E”.
Here, we l put “E” at the end of the Queue. So, we don’t have any nodes left, so the algorithm ends here.
Pseudo Code for Topological Sorting
Here’s the pseudo-code for the topological sort while using Kahn’s Algorithm.
function TopologicalSort( Graph G ):
for each node in G:
calculate the indegree
start = Node with 0 indegree
G.remove(start)
topological_list = [start]
While node with O indegree present:
topological_list.append(node)
G.remove(node)
Update Indegree of present nodes
Return topological_list
Topological sort can also be implemented using the DFS (Depth First Search) method. However, that approach is the recursive method. Kahn’s algorithm is more efficient than the DFS approach.
C++ Implementation of Topological Sorting
#include<bits/stdc++.h>
using namespace std;
class graph{
int vertices;
list<int> *adjecentList;
public:
graph(int vertices){
this->vertices = vertices;
adjecentList = new list<int>[vertices];
}
void createEdge(int u, int v){
adjecentList[u].push_back(v);
}
void TopologicalSort(){
// filling the vector with zero initially
vector<int> indegree_count(vertices,0);
for(int i=0;i<vertices;i++){
list<int>::iterator itr;
for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
indegree_count[*itr]++;
}
}
queue<int> Q;
for(int i=0; i<vertices;i++){
if(indegree_count[i]==0){
Q.push(i);
}
}
int visited_node = 0;
vector<int> order;
while(!Q.empty()){
int u = Q.front();
Q.pop();
order.push_back(u);
list<int>::iterator itr;
for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
if(--indegree_count[*itr]==0){
Q.push(*itr);
}
}
visited_node++;
}
if(visited_node!=vertices){
cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
return;
}
for(int i=0; i<order.size();i++){
cout<<order[i]<<"\t";
}
}
};
int main(){
graph G(6);
G.createEdge(0,1);
G.createEdge(0,2);
G.createEdge(1,3);
G.createEdge(1,5);
G.createEdge(2,3);
G.createEdge(2,5);
G.createEdge(3,4);
G.createEdge(5,4);
G.TopologicalSort();
}
Output
0 1 2 3 5 4
Python Implementation of Topological Sorting
from collections import defaultdict
class graph:
def __init__(self, vertices):
self.adjacencyList = defaultdict(list)
self.Vertices = vertices # No. of vertices
# function to add an edge to adjacencyList
def createEdge(self, u, v):
self.adjacencyList[u].append(v)
# The function to do Topological Sort.
def topologicalSort(self):
total_indegree = [0]*(self.Vertices)
for i in self.adjacencyList:
for j in self.adjacencyList[i]:
total_indegree[j] += 1
queue = []
for i in range(self.Vertices):
if total_indegree[i] == 0:
queue.append(i)
visited_node = 0
order = []
while queue:
u = queue.pop(0)
order.append(u)
for i in self.adjacencyList[u]:
total_indegree[i] -= 1
if total_indegree[i] == 0:
queue.append(i)
visited_node += 1
if visited_node != self.Vertices:
print("There's a cycle present in the Graph.\nGiven graph is not DAG")
else:
print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()
Output
[0, 1, 2, 3, 5, 4]
Cyclic Graphs of Topological Sort Algorithm
A graph containing a cycle can’t be topologically ordered. As the cyclic Graph has the dependency in a cyclic manner.
For example, check this Graph:
This Graph is not DAG (Directed Acyclic Graph) because A, B, and C create a cycle. If you notice, there’s no node with zero in-degree value.
According to Kahn’s Algorithm, if we analyze the above Graph:
- Find a node with zero indegrees (no incoming edges).
- Remove that node from the Graph and push it to the Queue.
However, in the above Graph, there’s no node with zero in degrees. Every node has an in-degree value greater than 0. - Return an empty queue, as it could not find any node with zero in degrees.
We can detect cycles using the topological ordering with the following steps:
Step 1) Perform topological Sorting.
Step 2) Calculate the total number of elements in the topologically sorted list.
Step 3) If the number of elements equals the total number of vertex, then there’s no cycle.
Step 4) If it’s not equal to the number of vertices, then there’s at least one cycle in the given graph data structure.
Complexity Analysis of Topological Sort
There are two types of complexity in algorithms. They’re
- Time Complexity
- Space Complexity
These complexities are represented with a function that provides a general complexity.
Time Complexity: All time complexity is the same for Topological Sorting. There are worst, average, and best-case scenarios for time complexity.
The time complexity for topological Sorting is O(E + V), here, E means the number of Edges in the Graph, and V means the number of vertices in the Graph.
Let’s break through this complexity:
Step 1) At the beginning, we will calculate all the indegrees. To do that, we need to go through all the edges, and initially, we will assign all V vertex indegrees to zero. So, the incremental steps we complete will be O(V+E).
Step 2) We will find the node with zero indegree value. We need to search from the V number of the vertex. So, the steps completed will be O(V).
Step 3) For each node with zero indegrees, we will remove that node and decrement the indegree. Performing this operation for all the nodes will take O(E).
Step 4) Finally, we will check if there is any cycle or not. We will check whether the total number of elements in the sorted array is equal to the total number of nodes. It will take O(1).
So, these were the individual time complexity for each step of the topological Sorting or topological ordering. We can say that the time complexity from the above calculation will be O( V + E ); here, O means the complexity function.
Space Complexity: We needed O(V) spaces for running the topological sorting algorithm.
Here are the steps where we needed the space for the program:
- We had to calculate all the indegrees of nodes present in the Graph. As the Graph has a total of V nodes, we need to create an array of size V. So, the space required was O(V).
- A Queue data structure was used to store the node with zero indegree. We removed the nodes with zero indegree from the original Graph and placed them in the Queue. For this, the required space was O(V).
- The array is named “order.” That stored the nodes in topological order. That also required O(V) spaces.
These were the individual space complexity. So, we need to maximize these spaces in the run time.
Space complexity stands for O(V), where V means the number of the vertex in the Graph.
Application of Topological Sort
There’s a huge use for Topological Sorting. Here are some of them:
- It is used when Operating system needs to perform the resource allocation.
- Finding a cycle in the Graph. We can validate if the Graph is DAG or not with topological sort.
- Sentence ordering in the auto-completion apps.
- It is use for detecting deadlocks.
- Different type of Scheduling or course scheduling uses the topological sort.
- Resolving dependencies. For example, if you try to install a package, that package might also need other packages. Topological ordering finds out all the necessary packages to install the current package.
- Linux uses the topological sort in the “apt” to check the dependency of the packages.