Java topological sorting: prerequisites and cycle rejection

Java 8+. The program uses only JDK classes and runs without a framework.

Make edge direction explicit

A build pipeline has compile and schema-generation tasks that must finish before packaging; packaging must finish before publication. In this representation, an edge points from prerequisite to dependent. Reversing that meaning would produce an order that looks structured but starts tasks before their inputs exist.

The method counts incoming prerequisite edges, places zero-incoming tasks in a queue, and removes one ready task at a time. Processing it reduces the counts of its dependents. A dependent becomes ready only after its final prerequisite edge has been accounted for.

The sample reports indexes for a four-task fixture. An application would map those indexes to stable task IDs. A valid order is not necessarily unique. Queue insertion order controls which independent ready task appears first, so tests should check edge constraints rather than assume every valid implementation produces the same ordering.

Detect an incomplete result

If the graph contains a cycle, some tasks never reach zero incoming count. Producing fewer than v tasks therefore means the method has not found a complete topological order. The sample throws instead of returning a partial prefix that a caller might mistake for a complete build plan.

A prerequisite cycle is not fixed by retrying the blocked tasks. The graph definition must change, or the application must use another model for mutually dependent state. Parallel edges are counted and decremented consistently here; a builder that deduplicates only one side of that accounting can introduce false readiness or false cycle reports.

Working program

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
public class BuildPrerequisites {
    static int[] order(int[][] dependents) {
        int[] incoming = new int[dependents.length];
        for (int[] nextTasks : dependents) {
            for (int task : nextTasks) {
                if (task < 0 || task >= incoming.length) throw new IllegalArgumentException("Unknown task");
                incoming[task]++;
            }
        }
        Queue<Integer> ready = new ArrayDeque<>();
        for (int task = 0; task < incoming.length; task++) if (incoming[task] == 0) ready.add(task);
        int[] ordered = new int[incoming.length];
        int completed = 0;
        while (!ready.isEmpty()) {
            int task = ready.remove();
            ordered[completed++] = task;
            for (int dependent : dependents[task]) {
                if (--incoming[dependent] == 0) ready.add(dependent);
            }
        }
        if (completed != incoming.length) throw new IllegalArgumentException("Prerequisite cycle");
        return ordered;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(order(new int[][]{{2}, {2}, {3}, {}})));
        try { order(new int[][]{{1}, {0}}); }
        catch (IllegalArgumentException rejected) { System.out.println("Cycle rejected"); }
    }
}

Output

[0, 1, 2, 3]
Cycle rejected

Cost and failure boundaries

Each task enters the queue once and each directed edge is counted and later visited once. Time is O(v+e), with O(v) extra counters, queue and result storage beyond the input adjacency representation. An empty graph returns an empty complete order.

This method produces a plan; it does not run tasks, observe task failures or coordinate workers. A concurrent build scheduler must mark a prerequisite complete only after successful execution, and decide whether dependent tasks are cancelled after failure. See completion stages for dependency composition.

Common Mistakes

• Do not reverse prerequisite/dependent edge meaning halfway through the pipeline.
• Do not report a partial order as a complete acyclic plan.
• Do not assume independent tasks have one mandatory order.

Connect the contracts

Compare the boundary explained in Directed graph traversal with the assumptions made by this program.

Compare the boundary explained in Ready-task queues with the assumptions made by this program.