Think like a butterfly

Topological sort is a fundamental algorithm in computer science, particularly useful in dependency resolution, task scheduling, and build systems. In this post, we’ll explore what topological sort is, how it works, and how to implement it in Python using both a custom approach and built-in libraries.

What is Topological Sort?

Topological sort is an algorithm for ordering the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. In simpler terms, it’s a way to arrange the nodes of a graph in a linear order that respects all the dependencies.

Implementing Topological Sort in Python

Let’s implement topological sort using depth-first search (DFS) in Python:

from collections import defaultdict

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

    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] * self.V
        stack = []

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

        return stack

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

print("Topological Sort:")
print(g.topological_sort())

This implementation uses a depth-first search approach to perform the topological sort. It maintains a stack to store the sorted vertices.

Using Python’s Built-in Libraries

Python’s graphlib module, introduced in Python 3.9, provides a convenient way to perform topological sorting:

from graphlib import TopologicalSorter

# Create a graph
graph = {
    5: {2, 0},
    4: {0, 1},
    2: {3},
    3: {1},
    0: set(),
    1: set()
}

# Create a TopologicalSorter object
ts = TopologicalSorter(graph)

# Perform topological sort
sorted_items = list(ts.static_order())

print("Topological Sort using graphlib:")
print(sorted_items)

The graphlib.TopologicalSorter class provides a more Pythonic and efficient way to perform topological sorting, especially for larger graphs.

Applications of Topological Sort

1. Build Systems: Determining the order of compilation tasks.
2. Data Processing Pipelines: Ordering data transformation steps.
3. Dependency Resolution: In package managers or project dependencies.
4. Task Scheduling: In job scheduling systems.

Identifying Topological Sort Problems

Recognizing when a problem can be solved using topological sort is a valuable skill. Here are some key indicators:

1. Dependency Relationships: The problem involves elements that depend on or precede other elements.
2. Directed Relationships: The dependencies are one-way (directed).
3. No Cycles: The relationships don’t form any loops or circular dependencies.
4. Ordering Required: You need to find a valid sequence or ordering of elements.

Common Problem Patterns

• Task scheduling with prerequisites
• Course scheduling in academic settings
• Software build systems
• Pipeline processing stages
• Hierarchical data processing

some popular Topological Sort in Problems

Topological sort is a popular algorithm that appears in various algorithm problems, especially those involving dependencies, scheduling, or ordering. Recognizing when to apply topological sort can be crucial in solving these problems efficiently. Here are some common types of (i.e.LeetCode) problems where topological sort is applicable:

1. Course Schedule Problems

• Course Schedule
  • Given a number of courses and their prerequisites, determine if it’s possible to finish all courses.
• Course Schedule II
  • Similar to above, but also requires returning the order of courses to take.

These problems directly map to topological sort, where courses are nodes and prerequisites are edges.

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    visited = [0] * numCourses

    def dfs(course):
        if visited[course] == 1: return True
        if visited[course] == -1: return False

        visited[course] = -1
        for prereq in graph[course]:
            if not dfs(prereq):
                return False
        visited[course] = 1
        return True

    for course in range(numCourses):
        if not dfs(course):
            return False
    return True

2. Dependency Resolution Problems

• Alien Dictionary
  • Given a sorted dictionary of an alien language, find the order of characters in the alphabet.

This problem requires inferring character order from word order and using topological sort to determine the alphabet order.

3. Build Order Problems

• Parallel Courses
  • Given N courses and their dependencies, find the minimum number of semesters needed to complete all courses.

This problem combines topological sort with level-order traversal to determine the minimum time to complete all tasks.

4. Graph Validity Problems

• LeetCode 802: Find Eventual Safe States
• In a directed graph, find all safe nodes (nodes that eventually lead to a terminal node).

While not a direct application of topological sort, this problem can be solved using a similar approach to detect cycles and safe paths.

5. Task Scheduling Problems

• Sort Items by Groups Respecting Dependencies
  • Sort items while respecting both item-level and group-level dependencies.

This problem requires applying topological sort at two levels: within groups and between groups.

Implementation Tips for Problems

1. Graph Representation: Often, you’ll need to convert the input into an adjacency list or matrix.
2. Cycle Detection: Many problems require detecting cycles, which can be done during the topological sort.
3. Kahn’s Algorithm vs DFS: Both approaches work, but Kahn’s algorithm (using in-degree counts) can be more intuitive for some problems.
4. Handling Invalid Inputs: Always consider cases where a valid topological order doesn’t exist.

from collections import deque

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == len(graph) else []  # Check if valid order exists