Performs a depth-first search and sort on the directed acyclic graph.
The given $graph with more secondary keys filled in:
public function searchAndSort() {
$state = array(
// The order of last visit of the depth first search. This is the reverse
// of the topological order if the graph is acyclic.
'last_visit_order' => array(),
// The components of the graph.
'components' => array(),
);
// Perform the actual search.
foreach ($this->graph as $start => $data) {
$this
->depthFirstSearch($state, $start);
}
// We do such a numbering that every component starts with 0. This is useful
// for module installs as we can install every 0 weighted module in one
// request, and then every 1 weighted etc.
$component_weights = array();
foreach ($state['last_visit_order'] as $vertex) {
$component = $this->graph[$vertex]['component'];
if (!isset($component_weights[$component])) {
$component_weights[$component] = 0;
}
$this->graph[$vertex]['weight'] = $component_weights[$component]--;
}
return $this->graph;
}