Gecko [ ifk.uw.edu.pl ]

Name	Size	Permission
database	[ DIR ]	drwxr-xr-x
filetransfer	[ DIR ]	drwxr-xr-x
actions.inc	13.49 KB	-rw-r--r--
ajax.inc	49.28 KB	-rw-r--r--
archiver.inc	1.66 KB	-rw-r--r--
authorize.inc	13.34 KB	-rw-r--r--
batch.inc	17.09 KB	-rw-r--r--
batch.queue.inc	2.26 KB	-rw-r--r--
bootstrap.inc	118.59 KB	-rw-r--r--
cache-install.inc	2.43 KB	-rw-r--r--
cache.inc	19.95 KB	-rw-r--r--
common.inc	303.4 KB	-rw-r--r--
date.inc	4.4 KB	-rw-r--r--
entity.inc	47.12 KB	-rw-r--r--
errors.inc	10.08 KB	-rw-r--r--
file.inc	88.53 KB	-rw-r--r--
file.mimetypes.inc	23.8 KB	-rw-r--r--
form.inc	194.91 KB	-rw-r--r--
graph.inc	4.71 KB	-rw-r--r--
image.inc	13.1 KB	-rw-r--r--
install.core.inc	77.61 KB	-rw-r--r--
install.inc	43.28 KB	-rw-r--r--
iso.inc	15.21 KB	-rw-r--r--
json-encode.inc	3.11 KB	-rw-r--r--
language.inc	19.02 KB	-rw-r--r--
locale.inc	82.36 KB	-rw-r--r--
lock.inc	9.2 KB	-rw-r--r--
mail.inc	22.69 KB	-rw-r--r--
menu.inc	137.14 KB	-rw-r--r--
module.inc	40.02 KB	-rw-r--r--
pager.inc	22.03 KB	-rw-r--r--
password.inc	9.3 KB	-rw-r--r--
path.inc	20.25 KB	-rw-r--r--
registry.inc	6.35 KB	-rw-r--r--
session.inc	17.93 KB	-rw-r--r--
stream_wrappers.inc	22.63 KB	-rw-r--r--
tablesort.inc	7.27 KB	-rw-r--r--
theme.inc	110.91 KB	-rw-r--r--
theme.maintenance.inc	6.9 KB	-rw-r--r--
token.inc	9.63 KB	-rw-r--r--
unicode.entities.inc	5.36 KB	-rw-r--r--
unicode.inc	22.22 KB	-rw-r--r--
update.inc	57.66 KB	-rw-r--r--
updater.inc	13.35 KB	-rw-r--r--
utility.inc	1.94 KB	-rw-r--r--
xmlrpc.inc	18.39 KB	-rw-r--r--
xmlrpcs.inc	11.02 KB	-rw-r--r--

Code Editor : graph.inc

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

${this.title}

Code Editor : graph.inc