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 order respects directed precedence constraints. Several vertices can be legal next choices, so obtaining any valid order is weaker than obtaining the lexicographically smallest one. An exhaustive prototype tests permutations in sorted order and stops at the first valid full ordering.

The final algorithm maintains indegrees after already selected vertices have been removed. Exactly the zero-indegree vertices are currently legal next choices.

Choosing from the currently ready tasks

Choose the smallest legal vertex, emit it, and remove its outgoing edges by decrementing neighbors' indegrees. Choosing the minimum yields the smallest possible first differing position; any valid alternative must also choose a currently legal vertex, so it cannot improve on the chosen minimum.

Deduplicate edges before counting indegrees. Incrementing for duplicates but decrementing only once can manufacture a false cycle. A self-loop is a real directed cycle. If fewer than n vertices can be emitted, the remaining graph contains a cycle, and an incomplete prefix is not an acceptable result.

A FIFO queue can produce a valid order but does not enforce the minimum available choice. Use a numeric min-heap; JavaScript has no standard built-in priority queue. Repeatedly sorting or scanning the frontier may be a useful prototype, but has a different cost. Empty n=0 has a valid empty ordering, distinct from null for a cyclic graph.

const outgoing = new Set([2, 2]);
console.log(outgoing.size); // 1: duplicate constraints count once
const ready = [10, 2, 1].sort((a, b) => a - b);
console.log(ready[0]); // 1: frontier choices use numeric order

Detecting a blocked build

Deduplicated adjacency plus a min-heap gives O(V+E+V log(V+1)) time and O(V+E) storage under standard hash/set assumptions. Use topological sorting for dependency ordering and cycle detection. It does not choose task durations or schedule parallel resources; those decisions require additional state after dependencies are known.

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