Introduction

Topological sorting produces a valid order of tasks when each task may depend on earlier tasks. It works only on directed acyclic graphs, which means no dependency cycle is allowed. In PHP, Kahn's algorithm is a practical and readable approach for scheduling jobs, build steps, or module initialization.

Model Dependencies as a Directed Graph

Represent each dependency A -> B as "A must run before B". You need two structures: adjacency lists and indegree counts. Indegree tracks how many prerequisites each node still has.

1<?php
2$nodes = ['clean', 'compile', 'test', 'package', 'deploy'];
3$edges = [
4    ['clean', 'compile'],
5    ['compile', 'test'],
6    ['test', 'package'],
7    ['package', 'deploy'],
8];

You can build graph state in linear time with respect to nodes plus edges.

Implement Kahn's Algorithm in PHP

Start with all nodes that have indegree zero. Remove one node at a time, append it to output, and decrement indegree of outgoing neighbors. If a neighbor reaches zero, enqueue it.

1<?php
2function topoSort(array $nodes, array $edges): array {
3    $adj = [];
4    $indegree = [];
5
6    foreach ($nodes as $node) {
7        $adj[$node] = [];
8        $indegree[$node] = 0;
9    }
10
11    foreach ($edges as [$from, $to]) {
12        $adj[$from][] = $to;
13        $indegree[$to]++;
14    }
15
16    $queue = new SplQueue();
17    foreach ($indegree as $node => $deg) {
18        if ($deg === 0) {
19            $queue->enqueue($node);
20        }
21    }
22
23    $order = [];
24    while (!$queue->isEmpty()) {
25        $node = $queue->dequeue();
26        $order[] = $node;
27
28        foreach ($adj[$node] as $next) {
29            $indegree[$next]--;
30            if ($indegree[$next] === 0) {
31                $queue->enqueue($next);
32            }
33        }
34    }
35
36    if (count($order) !== count($nodes)) {
37        throw new RuntimeException('Cycle detected. Topological sort not possible.');
38    }
39
40    return $order;
41}
42
43$nodes = ['clean', 'compile', 'test', 'package', 'deploy'];
44$edges = [
45    ['clean', 'compile'],
46    ['compile', 'test'],
47    ['test', 'package'],
48    ['package', 'deploy'],
49];
50
51print_r(topoSort($nodes, $edges));

This script runs directly and returns one valid dependency order.

Detect Cycles Early

If processed node count is smaller than total nodes, your graph contains a cycle. That is not a sorting bug. It means dependency definitions conflict and must be fixed at source.

For debugging large graphs, print remaining nodes with non-zero indegree after the queue empties. These nodes participate in or depend on a cycle. That insight helps teams fix pipeline configuration faster.

For deterministic outputs, use a priority queue or sort zero-indegree candidates before dequeueing. Determinism is useful in tests and build systems where stable order improves reproducibility.

Real-world Use in Build and Deploy Pipelines

Topological sort is most useful when tasks are dynamic and provided by configuration files instead of hardcoded arrays. In that setup, parse input into node and edge collections, validate unknown task references, and only then run sorting. Reject invalid definitions early with descriptive messages so pipeline users can fix configuration quickly.

1<?php
2$tasks = ['lint', 'unit', 'integration', 'package', 'release'];
3$deps = [
4    ['lint', 'unit'],
5    ['unit', 'integration'],
6    ['integration', 'package'],
7    ['package', 'release'],
8];
9
10$order = topoSort($tasks, $deps);
11echo 'execution order: ' . implode(' -> ', $order) . PHP_EOL;

For large dependency graphs, cache parsed configuration and run validation in pre-commit hooks. This shifts failures earlier and keeps deployment jobs predictable.

For troubleshooting, log indegree snapshots for a few selected nodes at each iteration. This makes it easy to see whether an edge was loaded in the wrong direction. In many incidents, teams accidentally invert dependencies and then misinterpret cycle errors. A short diagnostic mode in your sorter can save significant debugging time during release windows.

Common Pitfalls

• Forgetting to initialize indegree for isolated nodes with no edges.
• Adding duplicate edges and inflating indegree counts.
• Assuming there is exactly one valid topological ordering.
• Treating cycle detection as optional when consuming untrusted dependency input.
• Using recursive DFS in very large graphs and hitting stack limits unexpectedly.

Summary

• Topological sort works for dependency ordering in directed acyclic graphs.
• Kahn's algorithm is iterative, simple, and efficient in PHP.
• Maintain adjacency and indegree maps to process nodes in valid order.
• If output size is smaller than node count, you have a cycle.
• Add deterministic queue policies when stable ordering matters.