Class to perform a Topological Sort based on the nodes of a Directed Acyclic Graph representing dependencies.

DependencyResolver.php

<?php

/**
 * Directed acyclic graph based dependency resolver.
 *
 * Class DependencyResolver
 */
class DependencyResolver {
    /**
     * Internal map of outgoing edges for each node.
     *
     * @var array
     */
    private $forwardMap = [];

    /**
     * Add a node to the graph, along with its outgoing edges.
     *
     * @param string $sourceNode
     * @param array $destinationNodes
     * @throws \RuntimeException
     * @throws \InvalidArgumentException
     */
    public function addNode($sourceNode, array $destinationNodes)
    {
        if (!is_string($sourceNode) || is_numeric($sourceNode)) {
            throw new \InvalidArgumentException('Source node name must be a non-numeric string.');
        }

        if (isset($this->forwardMap[$sourceNode])) {
            throw new \RuntimeException('Cannot add the same source node more than once.');
        }

        $this->forwardMap[$sourceNode] = $destinationNodes;
    }

    /**
     * Reset the internal state (delete all connections).
     */
    public function reset()
    {
        $this->forwardMap = [];
    }

    /**
     * Resolve the dependency order. Returns an ordered array or false on failure.
     *
     * @return array|bool
     */
    public function resolve()
    {
        $forwardMap = $this->forwardMap;
        // Precompute a map of incoming connections for each node.
        $reverseMap = [];
        foreach ($forwardMap as $n => $e) {
            $m = array_fill_keys($e, [$n]);
            $reverseMap = array_merge_recursive($reverseMap, $m);
        }

        // $L is used for the sorted list.
        $L = [];

        // $S holds nodes with no incoming connections. The reverse map contains incoming connections.
        $S = array_diff_key($forwardMap, $reverseMap);

        // While we have nodes to process...
        while (!empty($S)) {
            // Pick a node n from S and add it to L.
            $L[] = $n = key($S);

            // Remove n from S and for each node m where an edge e connects n to m.
            foreach (array_shift($S) as $m) {
                $e = array_search($n, $reverseMap[$m], true);

                // Remove edge from the graph.
                unset($reverseMap[$m][$e]);

                // If m has no more incoming connections...
                if (empty($reverseMap[$m])) {
                    // But has outgoing connections...
                    if (isset($forwardMap[$m])) {
                        // Add it to S.
                        $S[$m] = $forwardMap[$m];
                    }
                    else {
                        // Otherwise add it to L.
                        $L[] = $m;
                    }

                    // Remove resolved node from the graph.
                    unset($reverseMap[$m]);
                }
            }
        }

        // If the reverse node map is not empty, the graph was cyclic and cannot be resolved.
        return empty($reverseMap) ? $L : false;
    }
}

Add nodes to the resolver like:

$resolver->addNode('sourceNode', ['destNode1', 'destNode2', ...]);