PrivacyScanData/visualize/Visualization-of-popular-algorithms-in-Python/Topological Sort

Visualisation of Topological sort algorithm using networkx library

Topological sort

Topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. PS: Topological sorting is possible only if the graph is a directed acyclic graph.

Two commom approaches for topological sort:

1. Kahn's algorithm
2. Depth - first search

The code here is an implementation of Kahn's algorithm.

#### Kahn's algorithm ####

This is computationally simpler compared to DFS approach.

Step 1: Find all the nodes in the graph with in-degree as 0 and add them into a queue Step 2: Remove the nodes from the queue one by one, append it to the sorted_list and simulatneously update the graph(remove the node from the graph, resulting which, in-degree of nodes which had edges directed from the reomved node decreases by one). Step 3: If there are anymore nodes left in the graph, go back to step 1

This method is optimal but modifies the graph. For the algorithm to not modify the original graph, you'll need to maintain a boolean array visited[] - to keep track to the visited nodes and indegree[] to store the in-degree of the graph nodes.

Working

Consider the sample input below:

6
1 2
1 3
2 3
2 4
3 4
3 5

Visualization of the input graph:

Node 1 is the only node with in-degree as 0. Remove it from the graph, and append it to the sorted_list. sorted_list = [1]

Now, Node 2 has an in-degree of 0. Remove it from the graph, and append it to the sorted list. sorted_list = [1,2]

Next, Node 3 has an in-degree of 0. sorted_list = [1,2 3]

Next, Node 4 and Node 5, both have an in-degree of 0. sorted_list = [1,2,3,4,5] Note that: [1,2,3,5,4] is also the right order.

Visualization of the topologically sorted order.
Green node - denotes the starting node.
Red node - denotes the final node.