Graphs Order work so each step runs after what it needs

Topological sort

Place each step after what it needs.

Put a total above the numbers it adds up, and a spreadsheet still gets it right: Excel builds a calculation chain, every formula cell in the order it should be calculated. Go initializes package variables only after the variables they read, and Turborepo builds your shared packages before the apps that import them. You rely on this ordering every day. Let’s watch an invoice put its cells in order, recalculate only what an edit reaches, and catch a circular reference instead of spinning forever.

TypeScriptGoOne invoice sheet, two implementations.

01 / The idea

Calculate what it reads first.

An invoice for a repair job is typed the way it reads: Total at the top, then Tax, Subtotal, and Labour, with the numbers Hours, Rate, and Parts at the bottom. Total adds Subtotal and Tax. Tax is 20% of Subtotal. Calculate the rows in the order they were typed, and Total runs first, adding up cells that have not been calculated yet.

A topological sort finds an order that works. Think of each cell as a node, and each reference as an arrow from the cell being read to the cell reading it. A topological order lists every node after all the nodes with arrows into it. For the invoice: Hours, Rate, Parts, Labour, Subtotal, Tax, Total.

That is Excel’s calculation chain, which “lists all the cells that contain formulas in the order in which they should be calculated.” It is how Go initializes package-level variables, each step selecting the variable “earliest in declaration order which has no dependencies on uninitialized variables.” And it is what Turborepo does with "dependsOn": ["^build"]: a package’s build waits for the builds of the packages it depends on.

02 / Name the rule

Ready means nothing it reads is still waiting.

Kahn’s algorithm, first described in 1962, builds the order one node at a time. Count how many distinct cells each cell reads. A cell with a count of zero is ready: put it in a line. Then repeat: take the cell at the front of the line and place it next in the order. Every cell that reads it now has one fewer input to wait for, so lower their counts. A count that reaches zero joins the back of the line.

When the line is empty, either every cell is placed or some are left over. A left-over cell is still waiting on a cell that was never placed. That is a circular reference: a loop of cells that each wait on the next, plus any cell downstream of the loop. The sort does not spin. It stops, and reports them.

Often more than one order is correct: Hours, Rate, and Parts could be taken in any order. This sheet takes ready cells first in, first out, starting in the order they were typed, so the same sheet always gives the same order in both languages.

Why does a left-over cell always lead to a loop?Follow what it waits on

Take any left-over cell. Its count never reached zero, so at least one cell it reads was never placed, and that cell is left over too. Follow that link, then again from there. There are only so many cells, so the walk must reach one it has already visited. The stretch from that cell back to itself is a loop. The example does exactly this to name one: Total waits on Subtotal, Subtotal on Parts, and Parts on Total.

The other direction holds too. No cell in a loop can be placed first, because each one waits on another in the loop. So the sort places every cell exactly when there is no loop.

A depth-first search also finds a topological order: finish everything a node reads before finishing the node. That is how JavaScript evaluates modules. The specification’s InnerModuleEvaluation evaluates each module a module imports before the module itself. A module already being evaluated is skipped rather than reported, which is why a circular import is allowed, and one module can run before a module it imports has finished.

03 / Follow one operation

An invoice, sorted, edited, and broken.

The repair invoice has seven cells, typed top-down: 12 Hours at a Rate of 85, 180 of Parts, and Tax at 20%.

Before you watch, predict which cell is placed fourth, and which cells must be calculated again when Hours changes to 15. Then Parts becomes 10% of Total, which makes a loop. The animation replays what the TypeScript example recorded. Try it lets you rewrite any cell.

Playback controls

Topological sort

Place a cell only after everything it reads.

Sheet · as typed

Total	= Subtotal + Tax	waits on 2
Tax	= 20% of Subtotal	waits on 1
Subtotal	= Labour + Parts	waits on 2
Labour	= Hours × Rate	waits on 2
Hours	12
Rate	85
Parts	180

Ready —

Order —

01/ 05

Calculate the invoice

Typed top-down, the way an invoice reads.

Total is the first row, but it adds up Subtotal and Tax, which are below it. The order cells were typed in is not an order they can be calculated in.

Reduced motion: choose a scene to see its completed state.

Read this scene

Total is the first row, but it adds up Subtotal and Tax, which are below it. The order cells were typed in is not an order they can be calculated in.

Order so far: none.

Try the example by reading

An invoice sheet is typed top-down: Total adds Subtotal and Tax, Tax is 20% of Subtotal, Subtotal adds Labour and Parts, Labour is Hours times Rate, and Hours 12, Rate 85, and Parts 180 are numbers. Hours, Rate, and Parts read nothing, so they are ready first. Taking Hours and Rate leaves Labour with nothing to wait on; taking Parts and Labour frees Subtotal; Subtotal frees Tax; and Tax frees Total. The order is Hours, Rate, Parts, Labour, Subtotal, Tax, Total, and Total is 1,440. Changing Hours to 15 recalculates only Labour, Subtotal, Tax, and Total, to a Total of 1,746. Making Parts 10% of Total creates a loop, Total, Subtotal, Parts, Total: after Hours, Rate, and Labour, nothing is ready, and the sort reports the loop. Setting Parts back to 200 restores the order, and Total is 1,770.

Edit the invoice

Change any cell to a number or a formula. The sheet sorts itself again, recalculates what the change can reach, and names any loop it finds.

The invoice is calculated. Apply Parts = 10% of Total to make a loop, then set Parts back to a number.

Total: 1440
Recalculated: 7
Stuck cells: 0
Sort steps: 21

Inspect the last change step by step

The sheet above is already updated. Stepping replays what the sort and the calculation recorded; it does not run them again.

After step 28 of 28. Calculate Total = Subtotal + Tax: 1440.

Hours waits on no other cell, so it joins the ready line.
Rate waits on no other cell, so it joins the ready line.
Parts waits on no other cell, so it joins the ready line.
Take Hours from the front of the line: it is next in the calculation order.
Labour reads Hours. It still waits on 1 more cell.
Take Rate from the front of the line: it is next in the calculation order.
Labour reads Rate, its last missing input. Nothing it needs is still waiting.
Labour waits on no other cell, so it joins the ready line.
Take Parts from the front of the line: it is next in the calculation order.
Subtotal reads Parts. It still waits on 1 more cell.
Take Labour from the front of the line: it is next in the calculation order.
Subtotal reads Labour, its last missing input. Nothing it needs is still waiting.
Subtotal waits on no other cell, so it joins the ready line.
Take Subtotal from the front of the line: it is next in the calculation order.
Total reads Subtotal. It still waits on 1 more cell.
Tax reads Subtotal, its last missing input. Nothing it needs is still waiting.
Tax waits on no other cell, so it joins the ready line.
Take Tax from the front of the line: it is next in the calculation order.
Total reads Tax, its last missing input. Nothing it needs is still waiting.
Total waits on no other cell, so it joins the ready line.
Take Total from the front of the line: it is next in the calculation order.
Calculate Hours 12: 12.
Calculate Rate 85: 85.
Calculate Parts 180: 180.
Calculate Labour = Hours × Rate: 1020.
Calculate Subtotal = Labour + Parts: 1200.
Calculate Tax = 20% of Subtotal: 240.
Calculate Total = Subtotal + Tax: 1440.

Sheet · as typed

Total	= Subtotal + Tax	1440	#7
Tax	= 20% of Subtotal	240	#6
Subtotal	= Labour + Parts	1200	#5
Labour	= Hours × Rate	1020	#4
Hours	12	12	#1
Rate	85	85	#2
Parts	180	180	#3

Ready —

Order Hours → Rate → Parts → Labour → Subtotal → Tax → Total

Seven named cells; formulas add, multiply, or take a percentage of other cells, rounded to whole numbers. A formula is written as = 20% of Subtotal.

Watch restarts when you return. Step through keeps your selected step. Try it starts from the invoice each time you open it.

04 / Read the shape

One sort, one sheet.

Basic form is Kahn’s algorithm over nodes that list what they come after: topologicalOrder returns the order, the blocked nodes, and one cycle. In the wild wraps it in Sheet, which validates cell definitions, calculates in sorted order, follows readers to find every cell an edit reaches, and marks stuck cells.

A value that cannot be calculated is not a crash. A cell on or after a loop holds CYCLE. A result beyond one trillion holds TOO-LARGE, and a formula that reads an error holds NEEDS: and the name of the cell it read. Values are whole numbers, and percentages round half away from zero, so TypeScript and Go agree exactly.

Read in

Compare with

Kahn’s algorithm over nodes that list what they depend on. Count each node’s distinct dependencies, take ready nodes first in first out, lower the counts of what depends on each one, and report the blocked nodes and one cycle among them. Pass an array to record every step.

TypeScriptReading

invoice.ts

export type GraphNode = { id: string; after: readonly string[] };
export type Step = {
	kind: 'ready' | 'take' | 'decrement';
	node: string;
	/** For decrement: how many of the node's dependencies are still waiting. */
	remaining: number;
};
export type Ordering = {
	/** Every node that could be placed, each after all of its dependencies. */
	order: string[];
	/** Nodes that never became ready, in input order: a cycle, or downstream of one. */
	blocked: string[];
	/** One cycle among the blocked nodes, starting and ending on the same node, or empty. */
	cycle: string[];
};

// Kahn's algorithm. Count each node's distinct dependencies. A node with none is ready.
// Take ready nodes first in, first out; taking one lowers the count of everything that
// depends on it, and a count that reaches zero makes that node ready. Whatever is never
// taken is waiting on a cycle.
export function topologicalOrder(nodes: readonly GraphNode[], steps?: Step[]): Ordering {
	const index = new Map<string, number>();
	nodes.forEach((node, i) => {
		if (index.has(node.id)) throw new RangeError(`node ${i} repeats the id ${node.id}`);
		index.set(node.id, i);
	});
	const dependencies = nodes.map((node) => {
		const distinct = new Set<string>();
		for (const dependency of node.after) {
			if (!index.has(dependency))
				throw new RangeError(`${node.id} depends on unknown node ${dependency}`);
			distinct.add(dependency);
		}
		return [...distinct];
	});
	const waiting = dependencies.map((list) => list.length);
	const dependents: number[][] = nodes.map(() => []);
	dependencies.forEach((list, i) => {
		for (const dependency of list) dependents[index.get(dependency)!].push(i);
	});

	const queue: number[] = [];
	let head = 0;
	const ready = (i: number) => {
		queue.push(i);
		steps?.push({ kind: 'ready', node: nodes[i].id, remaining: 0 });
	};
	waiting.forEach((count, i) => {
		if (count === 0) ready(i);
	});
	const order: string[] = [];
	while (head < queue.length) {
		const taken = queue[head++];
		order.push(nodes[taken].id);
		steps?.push({ kind: 'take', node: nodes[taken].id, remaining: 0 });
		for (const dependent of dependents[taken]) {
			waiting[dependent]--;
			steps?.push({ kind: 'decrement', node: nodes[dependent].id, remaining: waiting[dependent] });
			if (waiting[dependent] === 0) ready(dependent);
		}
	}

	const placed = new Set(order);
	const blocked = nodes.map((node) => node.id).filter((id) => !placed.has(id));
	const cycle: string[] = [];
	if (blocked.length > 0) {
		// Every blocked node waits on another blocked node, so following those links from any
		// blocked node must eventually repeat one. The repeated stretch is a cycle.
		const seen = new Map<string, number>();
		let current = blocked[0];
		while (!seen.has(current)) {
			seen.set(current, cycle.length);
			cycle.push(current);
			current = dependencies[index.get(current)!].find((d) => !placed.has(d))!;
		}
		cycle.splice(0, seen.get(current)!);
		cycle.push(current);
	}
	return { order, blocked, cycle };
}

GoAlongside

invoice.go

type GraphNode struct {
	ID    string   `json:"id"`
	After []string `json:"after"`
}

// Step is one move of the sort: "ready", "take", or "decrement". Remaining is, for a
// decrement, how many of the node's dependencies are still waiting.
type Step struct {
	Kind      string `json:"kind"`
	Node      string `json:"node"`
	Remaining int    `json:"remaining"`
}

// Ordering is every node that could be placed, each after all of its dependencies;
// the nodes that never became ready, in input order; and one cycle among them,
// starting and ending on the same node, or empty.
type Ordering struct {
	Order, Blocked, Cycle []string
}

// TopologicalOrder is Kahn's algorithm. Count each node's distinct dependencies. A
// node with none is ready. Take ready nodes first in, first out; taking one lowers
// the count of everything that depends on it, and a count that reaches zero makes
// that node ready. Whatever is never taken is waiting on a cycle.
func TopologicalOrder(nodes []GraphNode, steps *[]Step) (Ordering, error) {
	index := map[string]int{}
	for i, node := range nodes {
		if _, taken := index[node.ID]; taken {
			return Ordering{}, fmt.Errorf("node %d repeats the id %s", i, node.ID)
		}
		index[node.ID] = i
	}
	dependencies := make([][]string, len(nodes))
	for i, node := range nodes {
		seen := map[string]bool{}
		for _, dependency := range node.After {
			if _, known := index[dependency]; !known {
				return Ordering{}, fmt.Errorf("%s depends on unknown node %s", node.ID, dependency)
			}
			if !seen[dependency] {
				seen[dependency] = true
				dependencies[i] = append(dependencies[i], dependency)
			}
		}
	}
	waiting := make([]int, len(nodes))
	dependents := make([][]int, len(nodes))
	for i, list := range dependencies {
		waiting[i] = len(list)
		for _, dependency := range list {
			dependents[index[dependency]] = append(dependents[index[dependency]], i)
		}
	}

	var queue []int
	ready := func(i int) {
		queue = append(queue, i)
		record(steps, "ready", nodes[i].ID, 0)
	}
	for i, count := range waiting {
		if count == 0 {
			ready(i)
		}
	}
	order := []string{}
	for head := 0; head < len(queue); head++ {
		taken := queue[head]
		order = append(order, nodes[taken].ID)
		record(steps, "take", nodes[taken].ID, 0)
		for _, dependent := range dependents[taken] {
			waiting[dependent]--
			record(steps, "decrement", nodes[dependent].ID, waiting[dependent])
			if waiting[dependent] == 0 {
				ready(dependent)
			}
		}
	}

	placed := map[string]bool{}
	for _, id := range order {
		placed[id] = true
	}
	blocked, cycle := []string{}, []string{}
	for _, node := range nodes {
		if !placed[node.ID] {
			blocked = append(blocked, node.ID)
		}
	}
	if len(blocked) > 0 {
		// Every blocked node waits on another blocked node, so following those links from
		// any blocked node must eventually repeat one. The repeated stretch is a cycle.
		seen := map[string]int{}
		current := blocked[0]
		for {
			if at, repeated := seen[current]; repeated {
				cycle = append(cycle[at:], current)
				break
			}
			seen[current] = len(cycle)
			cycle = append(cycle, current)
			for _, dependency := range dependencies[index[current]] {
				if !placed[dependency] {
					current = dependency
					break
				}
			}
		}
	}
	return Ordering{order, blocked, cycle}, nil
}

func record(steps *[]Step, kind, node string, remaining int) {
	if steps != nil {
		*steps = append(*steps, Step{kind, node, remaining})
	}
}

Reading the TypeScriptAn index, a line, and counts

index maps each id to its position, so counts and dependents live in plain arrays. The ready line is an array with a head position: shift() would move every remaining item, and head++ does not.

Passing a steps array records every move, and leaving it out records nothing, through steps?.push. The animation and the lab read those records. A Set keeps each cell’s distinct references in the order they were written.

Reading the GoAn error, and a pointer to steps

TopologicalOrder returns (Ordering, error), with an error for an unknown or repeated id. The ready line is a slice read by a head loop variable, so taking from the front never copies.

steps *[]Step is nil when you want no trace, and record checks for that in one place. CellValue keeps the number and the problem in separate fields, and its String method prints whichever is set.

What would I normally use in application code?Usually the tool that already owns the graph

Neither TypeScript nor Go ships a topological sort, and the function above is short enough to own. Python has one in its standard library: graphlib’s TopologicalSorter. Its prepare() raises CycleError, but get_ready() “can still be used to obtain as many nodes as possible until cycles block more progress,” the same split between ordered and blocked nodes as here.

More often the graph already belongs to a tool. For builds, declare dependsOn in Turborepo and let it order the tasks. For spreadsheets inside a product, embed one with a calculation engine rather than growing your own formula language.

05 / Try a decision

Why not calculate top to bottom?

Row order is the order a person reads the invoice. Decide what it gets wrong before the feedback tells you.

06 / Follow the cost

Five cells, not 3,003.

Here is every operation at a glance, with V cells, E distinct references, and D cells an edit reaches. The rest of this section is about where V + E comes from.

Invoice sheet: time and extra space per operation
Operation	Time	Extra space	What it assumes
Sort the cells	`O(V + E) average`	`O(V + E)`	Each cell joins the ready line once and is taken once. Each distinct reference is counted down once. Names are looked up in a hash map.
Calculate every cell	`O(V + E)`	`O(V)`	Each formula runs once, in sorted order, reading each of its references once.
Recalculate after an edit	`O(V + E), then D formulas`	`O(V)`	Following readers from the edited cell finds the D cells it reaches. This sheet sorts again on every edit to keep the code short; a spreadsheet keeps its order and revises it.
Name one loop	`O(V)`	`O(V)`	The walk visits each left-over cell at most once before one repeats.
Recalculate in row order until nothing changes	`O(V × passes)`	`O(V)`	A chain typed backwards settles one cell per pass: V + 1 passes, O(V²) evaluations. A circular reference may never settle.

The invoice took 21 sort steps. Each of its 7 cells joined the ready line once and was taken once, and each of its 7 references was counted down once. That accounting holds for any sheet.

Scale the invoice to 1,000 line items, each a quantity times a price: 3,003 cells, 3,003 references, and 9,009 sort steps. Changing one quantity recalculates 5 cells: that quantity, its line, Subtotal, Tax, and Total. Calculating the same sheet from scratch in row order took 5 full passes, 15,015 cell evaluations, before the values stopped changing. Type a chain of 1,000 cells backwards, each reading the one below it, and row order needs 1,001 passes and 1,001,000 evaluations. The sorted order evaluates each cell once.

This sheet sorts all 3,003 cells again on every edit, to keep the code short. Excel keeps its chain between edits, and “revises this chain if it comes across a formula that depends on a cell that has not yet been calculated.” These are counts from this lesson’s TypeScript example, not timings.

07 / Give it a real job

Refuse the loop before it spreads.

A real sheet gets its definitions from people. Sheet validates every definition before it sorts, and an edit it rejects leaves the sheet as it was.

A circular reference can still be applied, because a sheet someone is typing into passes through loops on the way to being fixed. The loop’s cells, and every cell downstream of it, show CYCLE instead of a wrong number. Excel “detects the circular reference and warns the user.” Some tools also offer iterative calculation, where a loop runs a set number of times; Google Sheets has it as a setting. That is a different contract, and this sheet does not offer it.

Build UIs?See the ordering behind your builds and imports, and the day your form fields depend on each other.

Where it already is in your components

Run a build in a monorepo whose turbo.json says "dependsOn": ["^build"], and you ran a topological sort of your packages. Turborepo “starts at the ‘bottom’ of the package graph” and works its way back to the top, so the design system builds before the app that imports it.

The browser does it with your modules. A module’s imports are evaluated before the module, depth first. Two modules that import each other are not an error: one runs before the other has finished. That is why a circular import shows up as a binding used before it was initialized, not as a message naming the loop.

When you have to own it

You are building a form builder. An author adds “Bringing a guest?” and gives it a rule: show it when “Are you coming?” is Yes. Then “Guest’s name”, shown when “Bringing a guest?” is Yes. A field appears only if the field controlling it is showing and holds that answer, so you cannot judge “Guest’s name” until you have judged “Bringing a guest?”. Authors point rules at fields above and below, so the order on screen is no help. Sort the rules, judge each field in that order, and every field’s controller is settled before you reach it.

Then an author sets “Are you coming?” to show only when “Bringing a guest?” is Yes. Neither field can now appear before the other, and the sort leaves both over. Try the new rule on a copy of the form, refuse to save it, and name the loop with the labels the author typed. Keep their draft on screen so they fix the rule instead of rebuilding it. And decide on purpose what happens to answers in fields a rule hides; the editor below keeps them, and says why.

An event sign-up form whose fields show on conditions. Each field is judged after the field that controls it, in topological order, and the visible fields render in the order the author laid out.

ReactAlready in your code

ConditionalForm.tsx

import { useMemo, useState } from 'react';

type Rule = { field: string; equals: string };
type Field = { id: string; label: string; options?: string[]; showWhen?: Rule };

// Authors can point a rule at any field, above or below, so the order on screen says
// nothing about which field to judge first.
const fields: Field[] = [
	{ id: 'guestName', label: 'Guest’s name', showWhen: { field: 'guest', equals: 'Yes' } },
	{ id: 'attending', label: 'Are you coming?', options: ['Yes', 'No'] },
	{
		id: 'guest',
		label: 'Bringing a guest?',
		options: ['Yes', 'No'],
		showWhen: { field: 'attending', equals: 'Yes' }
	},
	{ id: 'diet', label: 'Anything you can’t eat?', showWhen: { field: 'attending', equals: 'Yes' } }
];

// Kahn's algorithm. A field with no rule is ready at once. A field waits on exactly one
// other field, so it becomes ready the moment that field is taken. A field in a loop, or
// pointing at a field that isn't on the form, is never taken, so it stays hidden.
function evaluationOrder(form: readonly Field[]): Field[] {
	const controls = new Map<string, Field[]>();
	for (const field of form) {
		if (!field.showWhen) continue;
		const list = controls.get(field.showWhen.field) ?? [];
		list.push(field);
		controls.set(field.showWhen.field, list);
	}
	const order = form.filter((field) => !field.showWhen);
	for (let head = 0; head < order.length; head++) {
		order.push(...(controls.get(order[head].id) ?? []));
	}
	return order;
}

// In this order, a field's controlling field has always been judged already.
function visibleIds(form: readonly Field[], answers: Record<string, string>): Set<string> {
	const visible = new Set<string>();
	for (const field of evaluationOrder(form)) {
		const rule = field.showWhen;
		if (!rule || (visible.has(rule.field) && answers[rule.field] === rule.equals)) {
			visible.add(field.id);
		}
	}
	return visible;
}

export function ConditionalForm() {
	const [answers, setAnswers] = useState<Record<string, string>>({});
	const visible = useMemo(() => visibleIds(fields, answers), [answers]);
	const answer = (id: string, value: string) => setAnswers((prev) => ({ ...prev, [id]: value }));

	// Judge in dependency order, render in the author's order.
	return (
		<form onSubmit={(e) => e.preventDefault()}>
			{fields
				.filter((field) => visible.has(field.id))
				.map((field) => (
					<label key={field.id}>
						{field.label}
						{field.options ? (
							<select
								value={answers[field.id] ?? ''}
								onChange={(e) => answer(field.id, e.target.value)}
							>
								<option value="">Choose…</option>
								{field.options.map((option) => (
									<option key={option}>{option}</option>
								))}
							</select>
						) : (
							<input
								value={answers[field.id] ?? ''}
								onChange={(e) => answer(field.id, e.target.value)}
							/>
						)}
					</label>
				))}
		</form>
	);
}

08 / Make the call

Ask whether the order comes from pairs.

Reach for a topological sort when things must happen after other things and the constraints come in pairs: this cell reads that one, this package builds after that one, this migration needs that one first. It gives one valid order in O(V + E) time, and tells you when no order exists.

Look elsewhere when the question changes. If a key decides the order, such as a date or a price, sort by the key. If some ready work is more urgent than other ready work, keep the ready line in a binary heap instead of a queue; Go’s initialization rule is like that, always taking the ready variable earliest in declaration order. If you need the shortest route through a graph, you want a shortest-path algorithm, not an order. And if loops are expected and should run until values settle, you want iterative calculation, not a sort that refuses them.

09 / Take the idea with you

Explain it without saying “topological sort.”

“I count how many things each item is waiting for. Anything waiting for nothing goes in a line. I take from the front of the line, and everything that was waiting for it now waits for one fewer thing; when that reaches zero, it joins the line. If the line empties with items left over, those items are stuck on a loop.” That describes the mechanism. The name is what you call it in a review.

Before moving on, explain three things without the name: why row order left a stale total, why a left-over cell always leads to a loop, and why changing Hours did not recalculate Parts. Then find a chain of effects in your own code where one value updates another, and draw the arrows.

Connections to follow nextRelated lessons

Graph overview names nodes, edges, direction, and weight, and sends each question to the lesson that answers it.
Queue and deque is the ready line, first in and first out.
Hash map finds a cell’s position by name, so every count is one lookup away.
Sorting is the tool when a key, not a set of pairs, decides the order.
Adjacency list is the list of readers the sort walks for each cell.