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

Order directed prerequisites, choose the smallest legal next vertex, and detect any cycle. Repeated edges denote one dependency rather than several independent prerequisites.

Testing permutations gives a small baseline but factorial work. A plain FIFO zero-indegree frontier may produce a valid order without producing the lexicographically smallest one. Deduplicate before counting indegrees.

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.

Indegree counts unfinished prerequisites. The legal frontier contains only zero-indegree vertices; a min-heap chooses the smallest available vertex to obtain the lexicographically smallest full order. Deduplicate edges before counting. Fewer emitted vertices than n means a cycle. Final O((V+E) log V) time and O(V+E) space.

The legal frontier needs a minimum-first policy, independent of the order vertices became available:

import java.util.*;

class Example {
    public static void main(String[] args) {
        PriorityQueue<Integer> legal = new PriorityQueue<>();
        legal.add(4);
        legal.add(1);
        legal.add(3);
        assert legal.remove() == 1;
        assert legal.remove() == 3;
    }
}

The smallest available vertex is emitted first. The complete algorithm still has to decrement neighbors exactly once per distinct edge, add newly legal vertices, and require a full n-vertex result rather than returning a partial prefix through a cycle.

Detecting a blocked build

Topological order supports build plans, prerequisite scheduling, and dependency validation. A cycle is a domain failure to order, rather than a reason to arbitrarily omit the remaining vertices.

Directed (u,v) means u before v. Return the lexicographically smallest valid vertex order or null for any cycle. Duplicate edges count once. n=0 returns empty. Negative n or invalid endpoints raise IllegalArgumentException. Prototype may test permutations.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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