# Topological Sort

Ordering the nodes of a directed acyclic graph so every edge points forward, which is exactly what dependency resolution requires.

**Leads to:** Decision Jungles, Graph Traversal BFS and DFS

**Rests on nothing.** A place to start.

*Mathematical Foundations · Graph Theory*


## Why learn this

Topological sort is the engine behind dependency resolution — the mechanism that decides in what order to complete a list of tasks when some tasks must happen before others. Master this and you unlock the ability to reason about any system where things depend on other things: package managers (installing package A before package B), build tools (compiling code file X before linking it), spreadsheet formula recalculation, scheduling complex workflows, and pipelines in data processing where steps must run in the right order. It also gives you your first real taste of graph algorithms, the same family that later powers Dijkstra's shortest path, social network analysis, and neural network architectures.


## The intuition

Imagine you have a set of chores to do, and some chores can't start until others are done. You can't wash the car until the car is parked, and you can't park the car until the driveway is clear. Topological sort answers: 'What's a valid order to do all the chores, respecting these rules?' More formally, you have a bunch of items (called 'nodes'), and some pairs of items have a rule 'item A must come before item B' (these rules are called 'edges', and the whole collection is a 'directed graph'). A topological sort is an ordering of all the items such that for every rule 'A before B', A actually comes before B in the ordering. The catch: if there is a cycle (like 'A before B, B before C, C before A'), then no such order exists — it's an impossible requirement, and that's exactly how circular dependencies are detected. Topological sort is the algorithm that either produces a valid order or tells you it's impossible because there's a cycle.


## An analogy

Think of building a house. You have a list of tasks: lay the foundation, build the walls, roof, plumbing, electrical, paint. Some tasks require others to be done first — you can't build the walls before the foundation, you can't put on the roof before the walls. Topological sort is the algorithm that finds a working sequence, like: foundation -> walls -> roof -> plumbing -> electrical -> paint. But what if the architect accidentally specified 'paint before walls'? That would create a cycle (walls need paint, paint needs walls), and the algorithm would say 'No possible order — you have a circular dependency; fix your rules.' The same idea works in software: when you install a package, it may depend on other packages; topological sort tells the installer what to fetch first. And here is where the analogy breaks: a topological sort is not necessarily unique — there can be many valid orders. For our house, you could do plumbing before electrical, or electrical before plumbing, as long as both after walls. The algorithm just gives you one valid order, not 'the' order. Also, topological sort only works on directed graphs (where the rules have a direction, unlike undirected friendships in social networks), and it requires that there be no cycles — it literally cannot produce an answer if there is one.


## Definition

Topological sort is an ordering of the nodes of a directed acyclic graph (a collection of items where connections have a specific direction and no item eventually leads back to itself) such that for every directed edge from node A to node B, A appears before B in the ordering; if no such ordering exists, the graph contains a cycle, and the algorithm detects that failure.


## How it connects

You have not yet studied graph theory in detail, but this concept sits right alongside two neighbours you will soon meet: Depth-First Search (DFS) and cycle detection. Topological sort is often implemented using a DFS traversal — a method of exploring a network by going as deep into one path as possible before backtracking, and the order in which you finish exploring each node gives the topological order (in reverse). Also, the failure condition for topological sort (finding a cycle) is exactly the key idea behind detecting circular dependencies in build systems and package installations. Later, when you learn about Dijkstra's shortest path, you will see this same idea of 'ordering steps' in a different context.


## The mathematics

Topological sort is a way to line up items so that every item comes after the things it depends on. Imagine you are planning a sequence of tasks. Some tasks cannot start until others are finished. We can draw this situation as a directed graph. A directed graph is a collection of points, which we call nodes or vertices, and arrows connecting them, which we call edges. An arrow from node u to node v means 'u must happen before v'.

To find a valid order, we look at how many prerequisites each task has. In graph terms, this is called the in-degree. The in-degree of a node is simply the number of arrows pointing into it. If a task has no prerequisites, its in-degree is zero. Such a task can be done immediately.

The algorithm works by repeatedly picking a task with zero in-degree, placing it next in your list, and then removing it from the graph. When you remove a task, you also remove all the arrows starting from it. This removal might reduce the in-degree of other tasks. If a task's in-degree drops to zero because its last prerequisite is finished, that task becomes available to be picked.

Here is the step-by-step procedure:

1. Count the in-degree for every node. The in-degree of a node v is the number of edges (u, v) where u is any node and v is the current node. In plain words: count how many arrows point at v.

2. Find all nodes with an in-degree of zero. Put these nodes into a list or queue. These are your starting tasks.

3. While there are still nodes left to place:
   a. Take one node from the list of zero-in-degree nodes. Call this node 'current'.
   b. Add 'current' to your final ordered list.
   c. Look at every arrow that starts at 'current' and points to another node, say 'next_node'.
   d. For each such 'next_node', reduce its in-degree by one. This is because the prerequisite 'current' has now been completed.
   e. If the in-degree of 'next_node' becomes zero, add 'next_node' to your list of available nodes.

4. After the loop ends, check if your final ordered list contains every node in the graph. If it does, you have found a valid topological order. If the list is shorter than the total number of nodes, then there is a cycle in the dependencies (for example, A depends on B, and B depends on A). In this case, no valid order exists.

The condition for a valid topological sort to exist is that the directed graph must contain no cycles. A cycle is a path that starts and ends at the same node, following the direction of the arrows.


## A worked example

Suppose you have three tasks: Task A, Task B, and Task C.
The rules are:
- Task A must be completed before Task B can start.
- Task A must be completed before Task C can start.
There is no rule about the order between B and C. They can happen in any order relative to each other, as long as they both come after A.

We represent this with a directed graph:
- Nodes: A, B, C
- Edges (arrows): One arrow from A to B, one arrow from A to C.

Step 1: Calculate the in-degree for each node.
The in-degree is the number of arrows pointing into a node.
- For Node A: Are there any arrows pointing to A? No. So, in-degree(A) = 0.
- For Node B: Is there an arrow pointing to B? Yes, from A. So, in-degree(B) = 1.
- For Node C: Is there an arrow pointing to C? Yes, from A. So, in-degree(C) = 1.

Step 2: Identify nodes with in-degree zero.
The only node with an in-degree of zero is A. We place A in our 'available' list. Our final ordered list is currently empty.

Step 3: Process the available node.
Take A from the available list. Add A to the final ordered list. Final order so far: [A].
Now, remove A and its outgoing arrows from the graph. The arrow from A to B is removed. The arrow from A to C is removed.

Step 4: Update in-degrees.
Because we removed the arrow pointing to B, we reduce B's in-degree by one. Old in-degree(B) was 1. New in-degree(B) = 1 - 1 = 0.
Because we removed the arrow pointing to C, we reduce C's in-degree by one. Old in-degree(C) was 1. New in-degree(C) = 1 - 1 = 0.

Step 5: Check for new available nodes.
Node B now has an in-degree of zero. Add B to the 'available' list.
Node C now has an in-degree of zero. Add C to the 'available' list.
The 'available' list now contains [B, C].

Step 6: Continue processing.
Take B from the available list. Add B to the final ordered list. Final order so far: [A, B].
Remove B and its outgoing arrows. There are no arrows starting at B, so nothing changes for other nodes.
Check in-degrees: No changes needed as no arrows were removed.

Take C from the available list. Add C to the final ordered list. Final order so far: [A, B, C].
Remove C and its outgoing arrows. There are no arrows starting at C.

Step 7: Check completion.
The final ordered list is [A, B, C]. The total number of nodes in the graph is 3. The list has length 3. Since the lengths match, the sort is successful.

Result: A valid topological order is A, B, C.
Note: In Step 5, the available list was [B, C]. If we had chosen C before B, the final order would be [A, C, B]. Both orders are valid because there is no dependency between B and C.


## From scratch, in Python

```python
# We'll represent the graph as a dictionary: each node maps to a list of
# its outgoing neighbours (nodes it must come before).

# Example: A -> B, A -> C
graph = {
    'A': ['B', 'C'],
    'B': [],
    'C': []
}

# Step 1: Compute in-degrees.
# First, get all nodes (keys in the dictionary) and also any node that
# appears as a neighbour (in case a node has no outgoing edges).
nodes = set(graph.keys())
for neighbours in graph.values():
    nodes.update(neighbours)

# Initialise in-degree of every node to 0.
in_degree = {node: 0 for node in nodes}

# For each edge from u to v, increment in_degree[v].
for u in graph:
    for v in graph[u]:
        in_degree[v] = in_degree[v] + 1

# Step 2: Find all nodes with in-degree 0 to start.
queue = [node for node in nodes if in_degree[node] == 0]

# Step 3: Process the queue.
topological_order = []

# We use an index to simulate a queue (we process in order).
index = 0
while index < len(queue):
    u = queue[index]
    index += 1
    topological_order.append(u)
    # For each neighbour v of u, remove the edge u->v:
    # decrement v's in-degree, and if it reaches 0, add to queue.
    for v in graph[u]:
        in_degree[v] = in_degree[v] - 1
        if in_degree[v] == 0:
            queue.append(v)

# Step 4: Check if we have all nodes.
if len(topological_order) == len(nodes):
    print("Topological order:", topological_order)
else:
    print("Graph has a cycle; no topological order exists.")

# For this example, output: ['A', 'B', 'C'] (or ['A', 'C', 'B'] depending on order)
```


## What the code does

First, we define the graph as a Python dictionary. A dictionary is like a phone book: it stores pairs of a name (called a 'key') and a value. Here each node is a key, and its value is a list of the nodes it points to. For example, graph = {'A': ['B', 'C']} means A has edges to B and C. We also make sure we have all nodes: we use a 'set', which is like a bag that holds each item only once, to collect all keys and also any node that appears as a neighbour (but not as a key, in case a node has no outgoing edges). Then we initialise an in_degree dictionary, giving each node a count of zero. We loop over every node u and its neighbour v, and increase v's in-degree by one each time we see an edge. Then we make a list called queue that holds all nodes whose in-degree is zero — these have no prerequisites and can go first. We process the queue using an index (a number telling us where we are in the list). While there are more nodes to process, we take the next node u, add it to the topological_order list, and then for each neighbour v, we decrement v's in-degree by one (because we have removed the edge from u to v). If v's in-degree becomes zero, we add v to the end of the queue. After the loop, if we have placed all nodes, we print the order; otherwise, some nodes are left and there must be a cycle. This is the same as the hand algorithm we did: find zero in-degree, remove, update, repeat.


## Common misconceptions

**Topological sort only works on trees** — I thought topological sort only works on tree structures, because most examples are like dependencies in a chain.

A tree is a special type of graph, but topological sort works on any directed acyclic graph, even if nodes have multiple parents or many interconnections. In fact: Topological sort works on any directed graph as long as it has no cycles. The graph can have any shape—it can have many edges and multiple paths.

**The topological order is unique** — I would think there's only one possible sequence that satisfies all dependencies.

In many graphs, there are multiple valid orders because some nodes are independent of each other. In fact: Topological sort can have many valid outputs. For example, if A depends on nothing and B after A, but C is independent, you can do A, B, C or A, C, B. The algorithm typically returns just one of them.

**If there's a cycle, topological sort just picks a starting point** — When I heard of topological sort, I thought it would handle circular dependencies by just starting somewhere and breaking the cycle arbitrarily.

By definition, a topological order requires every edge to point forward. With a cycle, that's impossible: the cycle has no forward direction that satisfies all edges. In fact: Topological sort fails when there's a cycle. It does not try to break it—it simply reports that no valid order exists. This is the feature that lets you detect circular dependencies.

**Topological sort is about sorting numbers** — I thought topological sort is like sorting a list of numbers in ascending order.

It has nothing to do with numeric value. It's about ordering based on dependencies, not by comparing values. In fact: Topological sort orders items based on 'must come before' relationships, not by their numeric or alphabetical value. It's an ordering of a graph, not a list.


## In short

Topological sort orders the nodes of a directed acyclic graph so every edge points forward. It works by repeatedly removing a node that has no incoming edges (no prerequisites), updating the in-degrees of its neighbours, and repeating. If you run out of removable nodes before placing all nodes, the graph has a cycle and no order exists—this is how circular dependencies are detected. This is foundational for dependency resolution in build systems, package managers, and AI pipelines, and it's your first proper graph algorithm.


## Where this is used

Where is topological sort used in building AI systems? Let me be specific. In large language model training, the pipeline is huge: collect data, clean it, tokenize, build batches, define the model architecture, initialise weights, forward pass, compute loss, backward pass, update with optimizer. Each step depends on earlier ones. Data cleaning must happen before tokenization; model definition must happen before forward pass. Actually, in practice, ML engineers use workflow tools like Airflow, Prefect, or Luigi, which internally use topological sort to schedule the DAG (Directed Acyclic Graph) of tasks. If you define a task that cleans data and a task that trains a model that depends on the cleaned data, Airflow's scheduler topological-sorts your tasks to decide what runs when. In small models running on devices (like a keyword spotter on a phone), the pipeline is likewise: capture audio, preprocess, extract features, run the model, postprocess output. Each stage is a node; topological sort orders them so the model doesn't run before features are extracted. In retrieval-augmented generation (RAG), you have a pipeline: ingest documents, split them, embed them, store in a vector DB, then at query time embed the query, retrieve top-k, then feed them to the LLM with the prompt. Each step depends on the last; topological sort ensures the embedding happens before retrieval, and retrieval before generation. In agentic systems that plan and call tools, the agent may break a task into subtasks, some of which depend on others. The agent's planning module builds a graph of subgoals and uses topological sort to decide the order of tool calls. For example, 'get user input' must happen before 'call API' which must happen before 'write response'. In everyday applied ML, think of fraud detection: features about a transaction, like amount, merchant, previous behavior, are computed in a certain order, then passed to a model. The feature engineering steps are a DAG — compute average transaction amount from history before it can be used as input to the model — and topological sorting the feature pipeline ensures correctness. A developer building a recommendation system may write a DAG in Python using a library like `networkx` or `dask`, and the library's topological sort function orders the computation. For example, using NetworkX: `list(nx.topological_sort(G))` returns the order. Underneath, it runs the same in-degree zero queue algorithm we implemented by hand. If you do it badly — ignore dependencies or have a cycle — your pipeline fails with an error that tells you 'circular dependency detected', which is the topological sort raising the flag. So the concept is not just academic; it is baked into the tools that run AI systems.


---

Read this on the web: https://basavapurushottam.com/learn-ai/topological-sort
