Topology Sorting in Python

Topology sorting, also known as topological sorting or topological ordering, is a linear ordering of the vertices of a directed acyclic graph (DAG) in such a way that for every directed edge (u, v), vertex u comes before vertex v in the ordering. Topological sorting is primarily used for scheduling tasks with dependencies, such as in project management or compiling.

To perform topological sorting in Python, you can use depth-first search (DFS) on the DAG. Here’s a Python program to do topological sorting using DFS:

from collections import defaultdict

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

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True

        for i in self.graph[v]:
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)

        stack.insert(0, v)

    def topological_sort(self):
        visited = [False] * len(self.graph)
        stack = []

        for i in range(len(self.graph)):
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)

        return stack

# Example usage:
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)

result = g.topological_sort()
print("Topological Sorting:", result)

In this program:

• We define a Graph class to represent a directed graph. It has methods for adding edges and performing topological sorting.
• The add_edge method adds directed edges to the graph.
• The topological_sort_util method is a recursive function used for DFS traversal. It marks vertices as visited and pushes them onto a stack when all their adjacent vertices have been visited.
• The topological_sort method initializes an array to track visited vertices, and it iterates through the graph’s vertices, calling topological_sort_util on unvisited vertices.
• The topological order is stored in the stack, and it is returned as the final result.

When you run the code with the example usage, it will perform topological sorting on the provided directed graph and print the topological order. In the example, the topological sorting is [0, 1, 2, 3, 4].