Introduction To Topological Sort Using Python

Introduction To Topological Sort

 

Topological sort in data structure is an important topic and works for DAG(Directed Acyclic Graph). Topological sort is a method where we order the nodes of a directed in a way that for each directed edge from node 1 to node 2, node 1 must appear before node 2. 

 

The most interesting thing about this sorting algorithm is that here the solution is not unique. The topological sort for every directed graph is not guaranteed, which means a topological order for a directed graph may or may not exist . 

 

Also, the topological sort for undirected graphs does not exist. Consider a topological sort example-:

---

---

The topological ordering of the directed graph shown above is-:

 

Node 1-> Node 2-> Node 3-> Node 4 -> Node 5, this is one of the solutions of the topological sort, as Node 2 and Node 3 appear in the same level both of them can come before either. Therefore, the next possible topological order is-:

 

Node 1-> Node 3-> Node 2-> Node 4 -> Node 5

 

Above example proves that topological sort is not always unique, and the graph where there are more than one nodes in the same level, there could be multiple solutions.

 

Consider another topological sort example-:

---

---

The directed graph shown above is one of the examples where we cannot find topological ordering as if one chooses to start from A, C shall come before A, and if one chooses C then B shall come before it, and the same way we cannot choose B either. The graph is clearly a cyclic graph and forms a deadlock as the cycle is formed in the nodes.

 

Therefore, whenever we spot a cycle in a directed graph, we can assume that topological ordering will not work here or topological ordering does not work for directed cyclic graph, it works for the directed acyclic graph.

 

One thing is clear, in order to start we have to choose a node that doesn’t have any incoming edge towards it. In the perspective of the graph, we can say that every vertex with zero in-degree can be added to the topological sort or every vertex that doesn’t have any incoming edges can be added.

 

(Also read: Introduction To Knapsack Problem)

 

Topological Sort Algorithm

 

To frame the whole idea of topological sort into an algorithm we will simply run the loop till all the nodes are visited and will check the in-degree of each node, if the indegree is zero then only we can add it to the topological order otherwise we cannot. 

 

Another thing to keep in mind is that if we are considering a node, we have to subtract the in-degree of its adjacent node by 1 as the node we selected will not be needed in the next step. 

 

Now, we shall implement the topological sort using python programming language to see its working and necessary steps to perform it.

 

 

Topological Sort Python Code

---

from collections import defaultdict

 

class Graph:

 

    def __init__(self,n):

 

        self.graph = defaultdict(list)

 

        self.N = n

 

    def addEdge(self,u,v):

 

        self.graph[u].append(v)

 

    def sort(self,n,visited,stack):

 

        visited[n] = True

 

        for element in self.graph[n]:

 

            if visited[element] == False:

 

                self.sort(element,visited,stack)

 

        stack.insert(0,n)

 

    def topologicalSort(self):

 

        visited = [False]*self.N

 

        stack =[]

 

        for element in range(self.N):

 

            if visited[element] == False:

 

                self.sort(element,visited,stack)

 

        print(stack)

 

graph = Graph(6)

graph.addEdge(0,1);

graph.addEdge(0,2);

graph.addEdge(1,2);

graph.addEdge(2,3);

graph.addEdge(2,4);

graph.addEdge(3,4);

 

print("Topological Sort:  ")

 

graph.topologicalSort()

---

Our first and important step in the above code is to import the ‘defaultdict’ from collections module. Collections are used to store the data into a container like dictionary, list, set, and more. 

 

Now, we have created a class ‘graph’ and initialized a function under which we have declared two variables, one is ‘self.graph’ which is a dictionary containing the adjacency list and the other variable is ‘self.N’ which shows the number of vertices. 

 

Furthermore, there is a function to add an edge to the graph. The function ‘sort’ marks the current node as visited and sorts the nodes recursively; this function later adds the current vertex to the stack. The last function marks all the non visited nodes and calls a function to sort the nodes in the topological order. 

 

(Must read: Bubble sort and merge sort)

 

 

Time And Space Complexity of Topological Sort

 

We are calculating the in-degree of each node and if we consider ‘E’ as the number of edges in the graph, then the time taken to calculate the in-degree of each node is O(E). 

 

We also have to run a loop to check if the in-degree of nodes is zero or not, if ‘V’ is the number of nodes then this loop will take O(V). The total time complexity of the topological sort becomes O(V+E). The space complexity of the topological sort will be O(V) as it has to consider all the nodes in a graph.

 

The time complexity of the topological sort tells us that the larger the graph, the more time it will take to execute as it depends upon the number of nodes and edges in the graph. Similarly, the more the values in a graph, the more space it will consume. 

 

Now, we have learned about the time and space complexity of the topological sort algorithm, let's move to the application of topological sort algorithms.

 

Application of Topological Sort

 

1. The topological sort is only possible for the directed graph that doesn’t have any cycle, therefore, topological sort is used to find the cycle in the graph.

 

2. Topological sort is also used in the detection of deadlocks. Deadlock is a state where a process is holding a resource and another state is waiting for that resource to be free. 

 

3. Scheduling problems like course schedule problems can be sorted with the help of topological ordering. Topological sort is capable of providing more than one solution to complete the course.

 

4. Project management techniques like critical path analysis use topological sort to predict or measure the time that a project can take. A project is generally solved in steps, therefore topological ordering is the best method to find the order that takes minimum time as it considers all the previous steps. 

 

The topological answer could answer the questions like how much time each activity is going to take, how many dependencies are there for an activity, and more.

 

5. The topological ordering is also used for data serialization. Data serialization is a method by which structured data is converted in a format where the data could be saved and reused whenever needed.

 

 

Conclusion

 

In this blog, we learned the working of topological sort using some examples and calculated the topological ordering. The cycle in a directed graph makes it impossible for a topological sort to work as discussed using an example of a cyclic graph.

 

In the later section of the blog, we have discussed the implementation of topological sort using python. The final section includes some of the major applications of topological sort like detection of deadlocks, solving scheduling problems, and more. 

 

(Also check: How to Use Selection Sort Using Python?)