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

}