Topological Sort in Python: Kahn's Algorithm and DFS

By Engr. Henry Akpan

Doing Things in the Right Order

You cannot register for MTH 201 before passing MTH 101. A house's walls go up before its roof, and a program's libraries must be built before the program that uses them. Whenever tasks have prerequisites, we need an order that respects every "this before that" rule. Finding such an order is called topological sorting. It is how build tools, package managers (pip and npm), spreadsheet recalculation, course planners and project schedulers decide what to do first.

This tutorial covers topological sort in Python: directed acyclic graphs, Kahn's algorithm with in-degrees, the depth-first search method, detecting impossible (cyclic) dependencies, grouping tasks into semesters or parallel stages, finding the critical path of a project, and Python's built-in graphlib module. It builds on the tutorials on graphs, BFS and DFS.

Directed Acyclic Graphs

Model each task as a vertex and each rule "A must come before B" as a directed edge A → B. A topological order is a list of all the vertices in which every edge points forwards.

  • A topological order exists exactly when the graph has no directed cycle. Such a graph is a directed acyclic graph (DAG).
  • If A needs B, B needs C and C needs A, no valid order exists. Detecting this is an important part of the job.
  • A DAG usually has many valid topological orders.

Our example is a set of courses and their prerequisites:

prereqs = {
    "MTH101": [],
    "PHY101": [],
    "CSC101": [],
    "MTH102": ["MTH101"],
    "PHY102": ["PHY101", "MTH101"],
    "CSC201": ["CSC101", "MTH102"],
    "MTH201": ["MTH102"],
    "CSC202": ["CSC201"],
    "PHY201": ["PHY102", "MTH201"],
}

# Build the graph: an edge from each prerequisite to the course that needs it
from collections import defaultdict
graph = defaultdict(list)
for course, needs in prereqs.items():
    for p in needs:
        graph[p].append(course)
print(graph["MTH101"], graph["MTH102"])

Output:

['MTH102', 'PHY102'] ['CSC201', 'MTH201']

Kahn's Algorithm

The in-degree of a vertex is the number of edges coming into it: here, the number of prerequisites a course has. A course with in-degree 0 can be taken straight away. Kahn's algorithm repeatedly takes such a course and "removes" it, which lowers the in-degree of the courses that depended on it:

  1. Compute every vertex's in-degree.
  2. Put all vertices with in-degree 0 into a queue.
  3. Repeatedly take a vertex from the queue, add it to the order, and decrease the in-degree of each of its neighbours. Whenever a neighbour's in-degree reaches 0, add it to the queue.
  4. If the order contains every vertex, it is valid. If some vertices are left over, they are part of a cycle.
from collections import deque

def kahn(prereqs):
    graph = defaultdict(list)
    indegree = {c: 0 for c in prereqs}
    for course, needs in prereqs.items():
        for p in needs:
            graph[p].append(course)
            indegree[course] += 1

    queue = deque(c for c in prereqs if indegree[c] == 0)
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    if len(order) != len(prereqs):
        stuck = sorted(c for c in prereqs if indegree[c] > 0)
        raise ValueError(f"cycle among: {stuck}")
    return order

print(kahn(prereqs))

Output:

['MTH101', 'PHY101', 'CSC101', 'MTH102', 'PHY102', 'CSC201', 'MTH201', 'CSC202', 'PHY201']

Check a few rules: MTH101 comes before MTH102, both CSC101 and MTH102 come before CSC201, and PHY102 and MTH201 both come before PHY201. Every vertex and every edge is handled once, so Kahn's algorithm runs in O(V + E) time.

Detecting Impossible Requirements

bad = {
    "A": ["C"],
    "B": ["A"],
    "C": ["B"],
    "D": [],
}
try:
    kahn(bad)
except ValueError as e:
    print("Impossible:", e)

Output:

Impossible: cycle among: ['A', 'B', 'C']

D can be scheduled, but A, B and C each wait for another one, so their in-degrees never reach 0.

Grouping into Semesters (Levels)

If a student can take any number of courses per semester, what is the fewest number of semesters? Process Kahn's queue one level at a time: everything with in-degree 0 now goes in semester 1, everything freed by those goes in semester 2, and so on. The same idea groups build steps that can run in parallel.

def semesters(prereqs):
    graph = defaultdict(list)
    indegree = {c: len(n) for c, n in prereqs.items()}
    for course, needs in prereqs.items():
        for p in needs:
            graph[p].append(course)
    level = sorted(c for c in prereqs if indegree[c] == 0)
    plan = []
    while level:
        plan.append(level)
        nxt = []
        for c in level:
            for d in graph[c]:
                indegree[d] -= 1
                if indegree[d] == 0:
                    nxt.append(d)
        level = sorted(nxt)
    return plan

for i, group in enumerate(semesters(prereqs), start=1):
    print(f"Semester {i}: {', '.join(group)}")

Output:

Semester 1: CSC101, MTH101, PHY101
Semester 2: MTH102, PHY102
Semester 3: CSC201, MTH201
Semester 4: CSC202, PHY201

The number of levels equals the length of the longest chain of prerequisites: here MTH101 → MTH102 → MTH201 → PHY201, which is four courses.

The DFS Method

Depth-first search gives another O(V + E) algorithm. Visit each vertex's dependants fully before finishing the vertex itself, and record each vertex when it finishes. Reversing the finishing order gives a topological order. Colouring the vertices detects cycles: a vertex is "in progress" while its descendants are being explored, and reaching an in-progress vertex again means there is a cycle.

def dfs_topo(prereqs):
    graph = defaultdict(list)
    for course, needs in prereqs.items():
        for p in needs:
            graph[p].append(course)
    WHITE, GREY, BLACK = 0, 1, 2          # unvisited, in progress, finished
    colour = {c: WHITE for c in prereqs}
    finished = []

    def visit(c):
        colour[c] = GREY
        for nxt in graph[c]:
            if colour[nxt] == GREY:
                raise ValueError(f"cycle through {c} -> {nxt}")
            if colour[nxt] == WHITE:
                visit(nxt)
        colour[c] = BLACK
        finished.append(c)

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

order = dfs_topo(prereqs)
print(order)
position = {c: i for i, c in enumerate(order)}
print(all(position[p] < position[c] for c, needs in prereqs.items() for p in needs))
try:
    dfs_topo(bad)
except ValueError as e:
    print(e)

Output:

['CSC101', 'PHY101', 'MTH101', 'PHY102', 'MTH102', 'MTH201', 'PHY201', 'CSC201', 'CSC202']
True
cycle through C -> A

This order differs from Kahn's, but the check on the second line confirms that every prerequisite still comes first. Both are valid. For very deep graphs, the recursive version can hit Python's recursion limit, and Kahn's algorithm avoids this.

Application: the Critical Path of a Project

When each task has a duration and independent tasks can run at the same time, the earliest finish time of the whole project is the length of the longest path through the DAG, called the critical path. Processing the tasks in topological order makes this easy: each task can start only when its last prerequisite has finished.

tasks = {                     # task: (days, prerequisites)
    "foundation": (5, []),
    "walls": (7, ["foundation"]),
    "plumbing": (4, ["foundation"]),
    "roof": (6, ["walls"]),
    "wiring": (3, ["walls"]),
    "plaster": (4, ["plumbing", "wiring"]),
    "paint": (2, ["roof", "plaster"]),
}
order = kahn({t: needs for t, (_, needs) in tasks.items()})
finish, came_from = {}, {}
for t in order:
    days, needs = tasks[t]
    start = max((finish[p] for p in needs), default=0)
    came_from[t] = max(needs, key=lambda p: finish[p], default=None)
    finish[t] = start + days

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

Output:

project takes 21 days
critical path: foundation -> walls -> wiring -> plaster -> paint

Walls finish on day 12, wiring on day 15 and plaster on day 19, so painting ends on day 21. Any delay to a task on the critical path delays the whole project. Other tasks have some slack. Plumbing finishes on day 9, but plastering cannot start until the wiring is done on day 15, so plumbing could slip by 6 days. The roof, finishing on day 18, could slip by 1 day.

Python's Built-In graphlib

Since Python 3.9, the standard library includes graphlib.TopologicalSorter. It takes a dictionary mapping each node to its prerequisites, exactly the shape of our prereqs dictionary, and raises CycleError for cycles.

from graphlib import TopologicalSorter, CycleError

order = list(TopologicalSorter(prereqs).static_order())
position = {c: i for i, c in enumerate(order)}
print(len(order), all(position[p] < position[c] for c, needs in prereqs.items() for p in needs))

try:
    list(TopologicalSorter(bad).static_order())
except CycleError as e:
    print("CycleError found a cycle:", sorted(set(e.args[1])))

Output:

9 True
CycleError found a cycle: ['A', 'B', 'C']

Its prepare(), get_ready() and done() methods also support running ready tasks in parallel, much like the semester grouping above.

Common Mistakes with Topological Sort

  • Pointing the edges the wrong way. Decide clearly whether an edge means "must come before" or "depends on", and be consistent. Reversed edges give a reversed order.
  • Forgetting to check for cycles. Without the final length check, Kahn's algorithm silently returns a partial order.
  • Using the finishing order of DFS without reversing it.
  • Leaving out vertices that have no edges. Include every task in the in-degree table, even those with no prerequisites and no dependants.
  • Expecting one unique answer. Many valid orders usually exist, so tests should check the rules rather than one exact list.

Topological Sort: Practice Exercises

  1. Write can_finish(n, pairs) that returns True if n courses (numbered 0 to n − 1) with the given (course, prerequisite) pairs can all be completed.
  2. Recipes need ingredients that are themselves recipes. Given a dictionary of recipe dependencies, list the order in which to cook them.
  3. Write is_valid_order(order, prereqs) that checks whether a proposed order obeys every prerequisite.

Sample solutions:

def can_finish(n, pairs):
    needs = {i: [] for i in range(n)}
    for course, pre in pairs:
        needs[course].append(pre)
    try:
        kahn(needs)
        return True
    except ValueError:
        return False

def is_valid_order(order, prereqs):
    if sorted(order) != sorted(prereqs):
        return False
    pos = {c: i for i, c in enumerate(order)}
    return all(pos[p] < pos[c] for c, needs in prereqs.items() for p in needs)

print(can_finish(3, [(1, 0), (2, 1)]), can_finish(2, [(0, 1), (1, 0)]))

recipes = {"fried rice": ["stock", "boiled rice"], "stock": [], "boiled rice": [], "party pack": ["fried rice", "chicken"], "chicken": ["stock"]}
print(kahn(recipes))

print(is_valid_order(["MTH101", "MTH102"], {"MTH101": [], "MTH102": ["MTH101"]}),
      is_valid_order(["MTH102", "MTH101"], {"MTH101": [], "MTH102": ["MTH101"]}))

Output:

True False
['stock', 'boiled rice', 'chicken', 'fried rice', 'party pack']
True False

Conclusion

Topological sorting orders the vertices of a directed acyclic graph so that every edge points forwards, putting prerequisites before the tasks that need them. Kahn's algorithm repeatedly removes vertices with in-degree 0, and processing it level by level groups tasks into semesters or parallel stages. The DFS method reverses the finishing order. Both run in O(V + E) and detect cycles, which make the task impossible. In topological order, the longest path gives a project's critical path, and graphlib.TopologicalSorter provides a ready-made implementation in the standard library.

Related Tutorials