1 graph.inc backdrop_depth_first_search(&$graph)

Performs a depth-first search and sort on a directed acyclic graph.

Parameters

$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;

Return value

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 also

_backdrop_depth_first_search()

File

core/includes/graph.inc, line 46
Directed acyclic graph manipulation.

Code

function backdrop_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) {
    _backdrop_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]--;
  }
}