How to Implement Topological Sort Algorithm in Python

1. Topological Sort Algorithm in Python
2. Implement the Topological Sort Algorithm in Python

This tutorial will show the implementation of the topological sort algorithm in Python.

Topological Sort Algorithm in Python

The topological sort algorithm sorts Directed Acyclic Graphs (DAGs). A directed acyclic graph (DAG) is a graph with directed edges from one node to another but with no cycles.

Topological sort is an algorithm that accepts a DAG as input and returns an array where each node appears before the nodes it points to.

It cannot be applied to any graphs other than DAGs because, in topological sort, the ordering completely depends upon the direction of edges between the nodes, and if there are cycles inside a graph, there can be multiple arrangements for it.

As a result, we can state that a topological sort of the nodes of a directed acyclic graph is the action of arranging the nodes in the order such that if an edge (i,j) exists, i comes before j in the lists.

A topological sort essentially provides a sequence in which we should conduct the task and assists us in determining if the graph has a cycle or not.

Every graph may support more than 1 topological ordering. The node’s in-degree in the graph determines it.

In addition, the topological ordering of the network begins with the node with in-degree 0, i.e., a node with no incoming edges.

Let us look at an example to better understand what is happening in topological sorting.

Input DAG:

First Iteration: []

Second Iteration: [B]

Third Iteration: [B, E]

Fourth Iteration: [B, E, A]

Fifth Iteration: [B, E, A, F]

Final Output: [B, E, A, F, C, D]

In the above example, we are iteratively removing the node with no input edges from our graph and putting it into our array. We repeat this process until there is only one node left in our graph.

In the end, we append this final node at the end of our array.

Implement the Topological Sort Algorithm in Python

We can implement the same logic discussed above to create a topological sort program in Python. The steps to implement this algorithm in our code are given below.

1. Identify the node that has no incoming edges.
2. Delete this node and its corresponding edges from the graph.
3. Update the in-degree of the adjacent nodes.
4. Repeat steps 1 to 3 until the graph is empty.

It is clear from these 4 steps that we have to create a graph for topological sort. This can be done in multiple ways, but the most convenient method is to create a graph class that contains methods for inserting nodes and edges into our graph.

The following code snippet shows a graph class with a constructor and a method to add more edges to our graph.

from collections import defaultdict


class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def addEdge(self, frm, to):
        self.graph[frm].append(to)
        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

Now, we have a class named graph that can initialize a directed or undirected graph and a method addEdge() that can be used to add more edges to our graph.

All we need now is a mechanism to implement the topological sort algorithm. We need to create a function that visits a node, checks if there are no incoming edges and deletes that node if there aren’t any incoming edges.

This type of function is shown in the following code snippet.

def visitNode(self, s, visited, sortlist):
    visited[s] = True
    for i in self.graph[s]:
        if not visited[i]:
            self.visitNode(i, visited, sortlist)
    sortlist.insert(0, s)

The above function takes the index of the current node s; a Boolean list visited that contains information about whether a node has already been visited or not, and a sortlist that we will use to store the nodes deleted from the graph.

We need to create another helper function that incrementally calls this visitNode() for all the nodes in our graph and prints the values of the sorted list at the end. The following code snippet shows a similar function implemented in Python.

def topologicalSort(self):
    visited = {i: False for i in self.graph}
    sortlist = []

    for v in self.graph:
        if not visited[v]:
            self.visitNode(v, visited, sortlist)
    print(sortlist)

Now, our implementation of the graph class is complete. We now need to create a graph and call the topologicalSort() function to sort our list.

This process has been implemented in the following code.

if __name__ == "__main__":

    graph = Graph(directed=True)
    graph.addEdge(1, 6)
    graph.addEdge(1, 3)
    graph.addEdge(2, 1)
    graph.addEdge(2, 5)
    graph.addEdge(3, 4)
    graph.addEdge(5, 1)
    graph.addEdge(5, 6)
    graph.addEdge(5, 6)
    graph.addEdge(6, 3)
    graph.addEdge(6, 4)

    print("Topological Sort Algorithm:")
    graph.topologicalSort()

Output:

Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example

The graph that we created in this code corresponds to the diagram in the diagrams given above. Here, indices 1 to 6 refer to nodes A to F.

As we have seen, the final sorted list was [B, E, A, F, C, D], which is the same as our output in the code.

Now, let’s look at our above code combined in one code block.

from collections import defaultdict


class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def addEdge(self, frm, to):
        self.graph[frm].append(to)
        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

    def visitNode(self, s, visited, sortlist):
        visited[s] = True
        for i in self.graph[s]:
            if not visited[i]:
                self.visitNode(i, visited, sortlist)
        sortlist.insert(0, s)

    def topologicalSort(self):
        visited = {i: False for i in self.graph}
        sortlist = []

        for v in self.graph:
            if not visited[v]:
                self.visitNode(v, visited, sortlist)
        print(sortlist)


if __name__ == "__main__":

    graph = Graph(directed=True)
    graph.addEdge(1, 6)
    graph.addEdge(1, 3)
    graph.addEdge(2, 1)
    graph.addEdge(2, 5)
    graph.addEdge(3, 4)
    graph.addEdge(5, 1)
    graph.addEdge(5, 6)
    graph.addEdge(5, 6)
    graph.addEdge(6, 3)
    graph.addEdge(6, 4)

    print("Topological Sort Algorithm:")
    graph.topologicalSort()

Output:

Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example

This concludes our tutorial. Now, you can implement topological sort with a complete understanding of how it works.