Performs a depth-first search and sort on a directed acyclic graph.
$graph: A three dimensional associated array, with the first keys being the names of the vertices, these can be strings or numbers. The second key is 'edges' and the third one are again vertices, each such key representing an edge. Values of array elements are copied over.
Example:
$graph[1]['edges'][2] = 1;
$graph[2]['edges'][3] = 1;
$graph[2]['edges'][4] = 1;
$graph[3]['edges'][4] = 1;
On return you will also have:
$graph[1]['paths'][2] = 1;
$graph[1]['paths'][3] = 1;
$graph[2]['reverse_paths'][1] = 1;
$graph[3]['reverse_paths'][1] = 1;
The passed-in $graph with more secondary keys filled in:
function drupal_depth_first_search(&$graph) {
$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 ($graph as $start => $data) {
_drupal_depth_first_search($graph, $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 = $graph[$vertex]['component'];
if (!isset($component_weights[$component])) {
$component_weights[$component] = 0;
}
$graph[$vertex]['weight'] = $component_weights[$component]--;
}
}