Topological Sort

topological_sort.py

from collections import deque
from typing import Dict, List


def topological_sort_dfs(nodes: List[int], edges: Dict[int, List[int]]):
    visited = set()
    stack = []
    on_path = set()  # To detect cycles
    
    def dfs(node):
        if node in on_path:  # Cycle detected
            raise ValueError("Cycle detected in the graph")
        if node in visited:
            return
        
        on_path.add(node)
        for neighbor in edges[node]:
            dfs(neighbor)
        on_path.remove(node)
        visited.add(node)
        stack.append(node)
    
    for node in nodes:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]  # Return in topological order


def kahns_algorithm(nodes: List[int], edges: Dict[int, List[int]]):
    in_degree = {node: 0 for node in nodes}
    for u, v in edges.items():
        in_degree[v] += 1
  
    queue = deque([node for node in nodes if in_degree[node] == 0])
  
    res = []
    while queue:
        node = queue.popleft()
        res.append(node)
    
        for neighbor in edges.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
        
    if len(res) == len(nodes):
        return res
    else:
        raise ValueError("Error: cyclic graph")