topological_sort.py

from collections import defaultdict

def ordering(graph:dict):
    in_counts = defaultdict(int)
    for k, v in graph.items():
        if not k in in_counts:
            in_counts[k] = 0
        for in_node in v:
            in_counts[in_node] += 1

    queue = []
    for in_node in in_counts.keys():
        if in_counts[in_node] == 0:
            queue.append(in_node)

    topological_order = []

    while queue:
        current_node = queue.pop(0)
        topological_order.append(current_node)
        if not current_node in graph:
            continue
        for in_node in graph[current_node]:
            in_counts[in_node] -= 1
            if in_counts[in_node] == 0:
                queue.append(in_node)

    return topological_order