Topological sorting

A monorepo build has packages that depend on generated clients and shared libraries. Alphabetical order is reproducible, but can start a package before its prerequisites exist. Repeatedly trying every possible order is unnecessary too.

Topological sorting tracks which tasks are ready now. When several are ready, this build planner chooses the smallest task ID so the same dependency graph produces the same plan.

Building packages after their prerequisites

A topological ordering respects every directed dependency. Zero-indegree vertices are currently legal; removing one releases its outgoing dependencies. A smallest-first frontier gives the lexicographically smallest ordering.

Choosing from the currently ready tasks

For dependencies 0 → 2, 1 → 2, and 2 → 3, tasks 0 and 1 are initially ready. Completing only 0 doesn't release 2; its count still includes 1. Once both finish, 2 becomes ready, followed by 3. Count a repeated dependency once, and use the same rule in both indegrees and adjacency.

adjacency := [][]int{{2}, {2}, {3}, {}}
indegree := []int{0, 0, 2, 1}
ready := []int{0, 1} // The initial smallest-ready choices.
u := ready[0]        // Process just task 0 for this transition.
ready = ready[1:]
for _, v := range adjacency[u] {
	indegree[v]--
	if indegree[v] == 0 {
		ready = append(ready, v)
	}
}
fmt.Println(indegree[2], ready) // 1 [1]: task 2 still waits for task 1.

Detecting a blocked build

Deduplicate edges before counting indegrees or decrements must track the same multiplicity. If fewer than n vertices can be removed, a cycle remains, even in a disconnected component. This models build ordering and dependency execution; BFS layers alone do not encode directed prerequisites. Keep dependency records unchanged. A nil result means a cycle, while a nonnil empty slice is a valid empty build.

With edge deduplication and a smallest-ID heap, time is expected O(V+E+V log(V+1)) and storage is O(V+E). A plain ready queue can reach O(V+E) when the canonical tie rule is unnecessary. A topological order represents prerequisites, not elapsed build time.

The build planner must report a cycle instead of publishing an incomplete order that merely looks plausible.