Topological Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

from typing import Dict, Set, List, Any


def toposort(graph: Dict[Any, Set[Any]]) -> List[Any]:
    """
    Topological sort using DFS (reverse post-order).

    Args:
        graph: Adjacency list for directed graph {node: {successors}}

    Returns:
        List of nodes in topological order

    Raises:
        ValueError: If graph contains a cycle
    """
    visited = set()
    in_stack = set()  # For cycle detection
    result = []

    def _dfs(node: Any) -> None:
        if node in in_stack:
            raise ValueError(f"Graph contains a cycle involving node '{node}'")
        if node in visited:
            return

        in_stack.add(node)

        for neighbor in graph.get(node, set()):
            _dfs(neighbor)

        in_stack.remove(node)
        visited.add(node)
        result.append(node)  # Add after all descendants processed

    for node in graph:
        if node not in visited:
            _dfs(node)

    return result[::-1]  # Reverse for correct order


# Example usage and demonstration
if __name__ == "__main__":
    # Example DAG (course prerequisites)
    #
    #   A ──→ B ──→ D
    #   │     │
    #   ↓     ↓
    #   C ──→ E
    #
    example_dag = {
        "A": {"B", "C"},
        "B": {"D", "E"},
        "C": {"E"},
        "D": set(),
        "E": set(),
    }

    print("Topological Sort (DFS):", toposort(example_dag))

    # Example with cycle
    cyclic_graph = {
        "A": {"B"},
        "B": {"C"},
        "C": {"A"},
    }

    try:
        toposort(cyclic_graph)
    except ValueError as e:
        print(f"Cycle detected: {e}")