Topological Sort

Before you can study DSA you need programming, and before Maths II you need Maths I. Before a wedding feast, the vegetables must be bought before they are cut, and cut before they are cooked. Whenever tasks depend on other tasks, you need an order that respects every dependency. That order is called a topological order, and finding it is topological sort.

In this lesson you will learn two algorithms for topological sort (Kahn's algorithm and the DFS method), use Python's built-in graphlib module, detect impossible circular dependencies, and work out the shortest time to finish a project when tasks can run in parallel.

The problem

Model each task as a vertex and each dependency as a directed edge: an edge from u to v means "u must come before v". A topological order lists all vertices so that every edge points forward, from earlier to later in the list.

Two facts matter:

• A topological order exists only if the graph has no cycle. If A needs B and B needs A, nothing can go first. Such a graph is a DAG, a directed acyclic graph (see Graphs & Representations).
• There is usually more than one valid order. Any order that respects all the edges is correct.

Kahn's algorithm

Kahn's algorithm is the most intuitive method. A task with in-degree 0 (no unfinished prerequisites) can be done right now. Do it, remove its outgoing edges, and some other tasks may now have in-degree 0. Keep a queue of ready tasks:

1. Count the in-degree of every vertex.
2. Put every vertex with in-degree 0 in a queue.
3. Take a vertex from the queue, add it to the order, and lower the in-degree of each of its neighbours by 1. Any neighbour that reaches 0 joins the queue.
4. If the order ends up shorter than the number of vertices, the leftover vertices are stuck in a cycle.

from collections import deque

def kahn(graph):
    in_degree = {v: 0 for v in graph}
    for v in graph:
        for nxt in graph[v]:
            in_degree[nxt] += 1
    ready = deque(v for v in graph if in_degree[v] == 0)
    order = []
    while ready:
        v = ready.popleft()
        order.append(v)
        for nxt in graph[v]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                ready.append(nxt)
    if len(order) < len(graph):
        stuck = [v for v in graph if in_degree[v] > 0]
        raise ValueError(f"cycle among {stuck}")
    return order

# subject -> subjects that need it first
course = {
    "Maths I": ["Maths II"],
    "Programming": ["DSA", "OOP"],
    "Maths II": ["DSA"],
    "DSA": ["Algorithms"],
    "OOP": [],
    "Algorithms": [],
}
print(kahn(course))

course["Algorithms"].append("Programming")      # a circular rule sneaks in
try:
    kahn(course)
except ValueError as err:
    print("Error:", err)

['Maths I', 'Programming', 'Maths II', 'OOP', 'DSA', 'Algorithms']
Error: cycle among ['Programming', 'DSA', 'OOP', 'Algorithms']

Every vertex enters the queue once and every edge lowers one in-degree once, so Kahn's algorithm is O(V + E). Note that OOP is reported as stuck too: it is not in the cycle, but it depends on Programming, which is.

The DFS method

The second method uses Depth-First Search (DFS). When a DFS call finishes a vertex, everything that depends on it has already been finished. So if you record vertices in the order they finish (postorder) and then reverse that list, every vertex appears before everything that depends on it.

def topo_dfs(graph):
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {v: WHITE for v in graph}
    finished = []

    def visit(v):
        colour[v] = GREY
        for nxt in graph[v]:
            if colour[nxt] == GREY:
                raise ValueError(f"cycle through {nxt}")
            if colour[nxt] == WHITE:
                visit(nxt)
        colour[v] = BLACK
        finished.append(v)              # v is done after all it leads to

    for v in graph:
        if colour[v] == WHITE:
            visit(v)
    return finished[::-1]

recipe = {
    "buy vegetables": ["wash vegetables"],
    "wash vegetables": ["chop vegetables"],
    "soak dal": ["boil dal"],
    "boil dal": ["make tadka"],
    "chop vegetables": ["make tadka", "make sabzi"],
    "make tadka": ["serve"],
    "make sabzi": ["serve"],
    "serve": [],
}
for step, task in enumerate(topo_dfs(recipe), 1):
    print(step, task)

1 soak dal
2 boil dal
3 buy vegetables
4 wash vegetables
5 chop vegetables
6 make sabzi
7 make tadka
8 serve

This order is different from what Kahn's algorithm would give, and both are correct. The grey colour check is the same cycle detection you learned in the DFS lesson. The DFS method is also O(V + E), but remember that deep recursion can hit Python's limit on very long chains; Kahn's algorithm has no such issue.

Python's graphlib module

Python 3.9 added the graphlib module with a TopologicalSorter class. You give it each vertex with its predecessors (the things that must come before it, the reverse of the edges above).

from graphlib import TopologicalSorter, CycleError

# subject -> subjects needed BEFORE it
needs = {
    "DSA": ["Maths II", "Programming"],
    "Maths II": ["Maths I"],
    "Algorithms": ["DSA"],
    "OOP": ["Programming"],
}
print(list(TopologicalSorter(needs).static_order()))

try:
    list(TopologicalSorter({"tax": ["rates"], "rates": ["billing"],
                            "billing": ["tax"]}).static_order())
except CycleError as err:
    print("CycleError:", err.args[1])

['Programming', 'Maths I', 'OOP', 'Maths II', 'DSA', 'Algorithms']
CycleError: ['tax', 'billing', 'rates', 'tax']

When a cycle exists, CycleError carries the list of vertices in the cycle, which is exactly what you want in an error message for a build tool or a course planner.

Doing tasks in rounds

TopologicalSorter can also hand out tasks in rounds: get_ready() returns everything that can be done now, and done() reports finished tasks so that their dependants become ready. Each round could be one semester, or one batch of jobs running in parallel.

from graphlib import TopologicalSorter

needs = {
    "DSA": ["Maths II", "Programming"],
    "Maths II": ["Maths I"],
    "Algorithms": ["DSA"],
    "OOP": ["Programming"],
    "Databases": ["Programming"],
    "Web Apps": ["Databases", "OOP"],
}
planner = TopologicalSorter(needs)
planner.prepare()
semester = 1
while planner.is_active():
    ready = sorted(planner.get_ready())
    print(f"Semester {semester}: {', '.join(ready)}")
    planner.done(*ready)
    semester += 1

Semester 1: Maths I, Programming
Semester 2: Databases, Maths II, OOP
Semester 3: DSA, Web Apps
Semester 4: Algorithms

The number of rounds is the length of the longest chain of dependencies: Maths I, Maths II, DSA, Algorithms needs four semesters however many subjects you take at once.

Advanced: the critical path

If each task also has a duration and independent tasks can run at the same time, how soon can the whole project finish? Process the tasks in topological order. A task can start only when all its prerequisites have finished, so its earliest finish time is its own duration plus the latest finish among its prerequisites. The project's finish time is the largest of these, and the chain of tasks that produces it is the critical path: any delay on it delays everything.

from graphlib import TopologicalSorter

# Preparing for a family function: task -> (days, prerequisites)
tasks = {
    "book hall": (2, []),
    "print cards": (3, ["book hall"]),
    "send cards": (4, ["print cards"]),
    "order sweets": (1, ["book hall"]),
    "decorate": (2, ["book hall", "order sweets"]),
    "function day": (1, ["send cards", "decorate"]),
}
order = TopologicalSorter({t: deps for t, (_, deps) in tasks.items()}).static_order()

finish, came_from = {}, {}
for t in order:
    days, deps = tasks[t]
    start = max((finish[d] for d in deps), default=0)
    finish[t] = start + days
    came_from[t] = max(deps, key=finish.get) if deps else None

end = max(finish, key=finish.get)
path = []
while end:
    path.append(end)
    end = came_from[end]
print("Total days:", max(finish.values()))
print("Critical path:", " -> ".join(reversed(path)))

Total days: 10
Critical path: book hall -> print cards -> send cards -> function day

Ordering sweets and decorating can happen while the cards are being printed and posted, so they do not affect the total. To finish sooner, you must speed up a task on the critical path, such as sending the cards. This is the core of project planning methods used in construction and software teams.

Common mistakes

• Reversing the edge direction. Decide clearly whether an edge means "u comes before v" or "u needs v", and stay consistent. graphlib expects predecessors.
• Not checking for cycles. Kahn's algorithm silently returns a short list if you forget to compare its length with V.
• Expecting one unique answer. Several orders can be correct; test that every edge points forward instead of comparing with one fixed list.
• Forgetting vertices that only appear as targets. Make sure every vertex is in the graph dictionary, even with no outgoing edges.

Key points

• A topological order lists the vertices of a directed graph so that every edge points forward.
• It exists only for DAGs; a cycle makes it impossible.
• Kahn's algorithm repeatedly takes vertices with in-degree 0; if some vertices are left, there is a cycle.
• The DFS method reverses the order in which vertices finish.
• Python's graphlib.TopologicalSorter provides static_order(), rounds with get_ready() and done(), and raises CycleError.
• With durations, processing tasks in topological order finds the earliest finish time and the critical path.

from graphlib import TopologicalSorter

needs = {"app": ["ui", "api"], "ui": ["design"], "api": ["db", "auth"],
         "auth": ["db"], "db": [], "design": []}

print(list(TopologicalSorter(needs).static_order()))

ts = TopologicalSorter(needs)
ts.prepare()
rounds = []
while ts.is_active():
    ready = sorted(ts.get_ready())
    rounds.append(ready)
    ts.done(*ready)
print(rounds)

['design', 'db', 'ui', 'auth', 'api', 'app']
[['db', 'design'], ['auth', 'ui'], ['api'], ['app']]