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 legal next vertex has indegree zero after previously selected vertices have been removed. Choosing the smallest legal vertex at every step yields the lexicographically smallest topological ordering, because every alternative first difference would choose a larger currently legal value.

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.

std::priority_queue<Int,std::vector<Int>,std::greater<>> ready;
// A FIFO queue gives a valid order, but need not give the smallest one.

Detecting a blocked build

Deduplicate edges before incrementing indegrees. Counting a duplicate twice but decrementing once can manufacture a false cycle. Self-loops are real cycles. If fewer than n vertices are emitted, a cycle remains; return nullopt rather than an incomplete order. An empty graph has an engaged empty ordering. The min-heap adds O(V log V) work on top of O(V+E) adjacency processing. Exhaustive permutation testing is only a small-input prototype.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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