Topological Sort with Kahn Algorithm

Whenever you have tasks with dependencies, build steps, database migrations, plugin load order, you need a sequence where everything comes after the things it depends on. Topological sort produces exactly that ordering, or tells you it is impossible because the dependencies form a cycle. Kahn algorithm is the most intuitive way to compute it.

The function takes a map from each node to the list of nodes it depends on, inverts that into an adjacency list plus an indegree count, and seeds a queue with every node that depends on nothing. It then drains the queue, and each time it places a node it decrements the indegree of everything waiting on it, enqueueing any that hit zero. If fewer nodes come out than went in, the leftover ones are tangled in a cycle.

function topologicalSort(array $graph): array {
    $indegree = [];
    $adj = [];
    foreach ($graph as $node => $deps) {
        $indegree[$node] ??= 0;
        foreach ($deps as $dep) {
            $adj[$dep][] = $node;
            $indegree[$dep] ??= 0;
            $indegree[$node]++;
        }
    }
    $queue = [];
    foreach ($indegree as $node => $deg) {
        if ($deg === 0) {
            $queue[] = $node;
        }
    }
    $order = [];
    while ($queue) {
        $node = array_shift($queue);
        $order[] = $node;
        foreach ($adj[$node] ?? [] as $next) {
            if (--$indegree[$next] === 0) {
                $queue[] = $next;
            }
        }
    }
    if (count($order) !== count($indegree)) {
        throw new RuntimeException('Cycle detected in graph');
    }
    return $order;
}

$graph = [
    'app'    => ['db', 'cache'],
    'db'     => ['config'],
    'cache'  => ['config'],
    'config' => [],
];
echo implode(' -> ', topologicalSort($graph)) . "\n";
// config -> db -> cache -> app