Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

146 lines (133 sloc) 4.828 kb
<?php
/**
* @file
* Directed acyclic graph manipulation.
*/
/**
* Performs a depth-first search and sort on a directed acyclic graph.
*
* @param $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:
* @code
* $graph[1]['edges'][2] = 1;
* $graph[2]['edges'][3] = 1;
* $graph[2]['edges'][4] = 1;
* $graph[3]['edges'][4] = 1;
* @endcode
*
* On return you will also have:
* @code
* $graph[1]['paths'][2] = 1;
* $graph[1]['paths'][3] = 1;
* $graph[2]['reverse_paths'][1] = 1;
* $graph[3]['reverse_paths'][1] = 1;
* @endcode
*
* @return
* The passed-in $graph with more secondary keys filled in:
* - 'paths': Contains a list of vertices than can be reached on a path from
* this vertex.
* - 'reverse_paths': Contains a list of vertices that has a path from them
* to this vertex.
* - 'weight': If there is a path from a vertex to another then the weight of
* the latter is higher.
* - 'component': Vertices in the same component have the same component
* identifier.
*
* @see _drupal_depth_first_search()
*/
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]--;
}
}
/**
* Performs a depth-first search on a graph.
*
* @param $graph
* A three dimensional associated graph array.
* @param $state
* An associative array. The key 'last_visit_order' stores a list of the
* vertices visited. The key components stores list of vertices belonging
* to the same the component.
* @param $start
* An arbitrary vertex where we started traversing the graph.
* @param $component
* The component of the last vertex.
*
* @see drupal_depth_first_search()
*/
function _drupal_depth_first_search(&$graph, &$state, $start, &$component = NULL) {
// Assign new component for each new vertex, i.e. when not called recursively.
if (!isset($component)) {
$component = $start;
}
// Nothing to do, if we already visited this vertex.
if (isset($graph[$start]['paths'])) {
return;
}
// Mark $start as visited.
$graph[$start]['paths'] = array();
// Assign $start to the current component.
$graph[$start]['component'] = $component;
$state['components'][$component][] = $start;
// Visit edges of $start.
if (isset($graph[$start]['edges'])) {
foreach ($graph[$start]['edges'] as $end => $v) {
// Mark that $start can reach $end.
$graph[$start]['paths'][$end] = $v;
if (isset($graph[$end]['component']) && $component != $graph[$end]['component']) {
// This vertex already has a component, use that from now on and
// reassign all the previously explored vertices.
$new_component = $graph[$end]['component'];
foreach ($state['components'][$component] as $vertex) {
$graph[$vertex]['component'] = $new_component;
$state['components'][$new_component][] = $vertex;
}
unset($state['components'][$component]);
$component = $new_component;
}
// Only visit existing vertices.
if (isset($graph[$end])) {
// Visit the connected vertex.
_drupal_depth_first_search($graph, $state, $end, $component);
// All vertices reachable by $end are also reachable by $start.
$graph[$start]['paths'] += $graph[$end]['paths'];
}
}
}
// Now that any other subgraph has been explored, add $start to all reverse
// paths.
foreach ($graph[$start]['paths'] as $end => $v) {
if (isset($graph[$end])) {
$graph[$end]['reverse_paths'][$start] = $v;
}
}
// Record the order of the last visit. This is the reverse of the
// topological order if the graph is acyclic.
$state['last_visit_order'][] = $start;
}
Jump to Line
Something went wrong with that request. Please try again.