home | career | drupal | java | mac | mysql | perl | php | scala | uml | unix

Drupal example source code file (graph.test)

This example Drupal source code file (graph.test) is included in the DevDaily.com "Drupal Source Code Warehouse" project. The intent of this project is to help you "Learn Drupal by Example".

PHP - Drupal tags/keywords

array, as, component, expected, expected_components, foreach, function, graph, paths, php, result, return, true, vertex

The graph.test Drupal example source code

<?php
// $Id: graph.test,v 1.10 2010/09/04 13:33:53 dries Exp $

/**
 * @file
 * Provides unit tests for graph.inc.
 */

/**
 * Unit tests for the graph handling features.
 */
class GraphUnitTest extends DrupalUnitTestCase {
  public static function getInfo() {
    return array(
      'name' => 'Graph',
      'description' => 'Graph handling unit tests.',
      'group' => 'System',
    );
  }

  function setUp() {
    require_once DRUPAL_ROOT . '/includes/graph.inc';
    parent::setUp();
  }

  /**
   * Test depth-first-search features.
   */
  function testDepthFirstSearch() {
    // The sample graph used is:
    // 1 --> 2 --> 3     5 ---> 6
    //       |     ^     ^
    //       |     |     |
    //       |     |     |
    //       +---> 4 <-- 7      8 ---> 9
    $graph = $this->normalizeGraph(array(
      1 => array(2),
      2 => array(3, 4),
      3 => array(),
      4 => array(3),
      5 => array(6),
      7 => array(4, 5),
      8 => array(9),
      9 => array(),
    ));
    drupal_depth_first_search($graph);

    $expected_paths = array(
      1 => array(2, 3, 4),
      2 => array(3, 4),
      3 => array(),
      4 => array(3),
      5 => array(6),
      7 => array(4, 3, 5, 6),
      8 => array(9),
      9 => array(),
    );
    $this->assertPaths($graph, $expected_paths);

    $expected_reverse_paths = array(
      1 => array(),
      2 => array(1),
      3 => array(2, 1, 4, 7),
      4 => array(2, 1, 7),
      5 => array(7),
      7 => array(),
      8 => array(),
      9 => array(8),
    );
    $this->assertReversePaths($graph, $expected_reverse_paths);

    // Assert that DFS didn't created "missing" vertexes automatically.
    $this->assertFALSE(isset($graph[6]), t('Vertex 6 has not been created'));

    $expected_components = array(
      array(1, 2, 3, 4, 5, 7),
      array(8, 9),
    );
    $this->assertComponents($graph, $expected_components);

    $expected_weights = array(
      array(1, 2, 3),
      array(2, 4, 3),
      array(7, 4, 3),
      array(7, 5),
      array(8, 9),
    );
    $this->assertWeights($graph, $expected_weights);
  }

  /**
   * Return a normalized version of a graph.
   */
  function normalizeGraph($graph) {
    $normalized_graph = array();
    foreach ($graph as $vertex => $edges) {
      // Create vertex even if it hasn't any edges.
      $normalized_graph[$vertex] = array();
      foreach ($edges as $edge) {
        $normalized_graph[$vertex]['edges'][$edge] = TRUE;
      }
    }
    return $normalized_graph;
  }

  /**
   * Verify expected paths in a graph.
   *
   * @param $graph
   *   A graph array processed by drupal_depth_first_search().
   * @param $expected_paths
   *   An associative array containing vertices with their expected paths.
   */
  function assertPaths($graph, $expected_paths) {
    foreach ($expected_paths as $vertex => $paths) {
      // Build an array with keys = $paths and values = TRUE.
      $expected = array_fill_keys($paths, TRUE);
      $result = isset($graph[$vertex]['paths']) ? $graph[$vertex]['paths'] : array();
      $this->assertEqual($expected, $result, t('Expected paths for vertex @vertex: @expected-paths, got @paths', array('@vertex' => $vertex, '@expected-paths' => $this->displayArray($expected, TRUE), '@paths' => $this->displayArray($result, TRUE))));
    }
  }

  /**
   * Verify expected reverse paths in a graph.
   *
   * @param $graph
   *   A graph array processed by drupal_depth_first_search().
   * @param $expected_reverse_paths
   *   An associative array containing vertices with their expected reverse
   *   paths.
   */
  function assertReversePaths($graph, $expected_reverse_paths) {
    foreach ($expected_reverse_paths as $vertex => $paths) {
      // Build an array with keys = $paths and values = TRUE.
      $expected = array_fill_keys($paths, TRUE);
      $result = isset($graph[$vertex]['reverse_paths']) ? $graph[$vertex]['reverse_paths'] : array();
      $this->assertEqual($expected, $result, t('Expected reverse paths for vertex @vertex: @expected-paths, got @paths', array('@vertex' => $vertex, '@expected-paths' => $this->displayArray($expected, TRUE), '@paths' => $this->displayArray($result, TRUE))));
    }
  }

  /**
   * Verify expected components in a graph.
   *
   * @param $graph
   *   A graph array processed by drupal_depth_first_search().
   * @param $expected_components
   *   An array containing of components defined as a list of their vertices.
   */
  function assertComponents($graph, $expected_components) {
    $unassigned_vertices = array_fill_keys(array_keys($graph), TRUE);
    foreach ($expected_components as $component) {
      $result_components = array();
      foreach ($component as $vertex) {
        $result_components[] = $graph[$vertex]['component'];
        unset($unassigned_vertices[$vertex]);
      }
      $this->assertEqual(1, count(array_unique($result_components)), t('Expected one unique component for vertices @vertices, got @components', array('@vertices' => $this->displayArray($component), '@components' => $this->displayArray($result_components))));
    }
    $this->assertEqual(array(), $unassigned_vertices, t('Vertices not assigned to a component: @vertices', array('@vertices' => $this->displayArray($unassigned_vertices, TRUE))));
  }

  /**
   * Verify expected order in a graph.
   *
   * @param $graph
   *   A graph array processed by drupal_depth_first_search().
   * @param $expected_orders
   *   An array containing lists of vertices in their expected order.
   */
  function assertWeights($graph, $expected_orders) {
    foreach ($expected_orders as $order) {
      $previous_vertex = array_shift($order);
      foreach ($order as $vertex) {
        $this->assertTrue($graph[$previous_vertex]['weight'] < $graph[$vertex]['weight'], t('Weights of @previous-vertex and @vertex are correct relative to each other', array('@previous-vertex' => $previous_vertex, '@vertex' => $vertex)));
      }
    }
  }

  /**
   * Helper function to output vertices as comma-separated list.
   *
   * @param $paths
   *   An array containing a list of vertices.
   * @param $keys
   *   (optional) Whether to output the keys of $paths instead of the values.
   */
  function displayArray($paths, $keys = FALSE) {
    if (!empty($paths)) {
      return implode(', ', $keys ? array_keys($paths) : $paths);
    }
    else {
      return '(empty)';
    }
  }
}

Other Drupal examples (source code examples)

Here is a short list of links related to this Drupal graph.test source code file:

new blog posts

"Drupal" is a registered trademark of Dries Buytaert.

my drupal tutorials and examples  

Copyright 1998-2016 Alvin Alexander, alvinalexander.com
All Rights Reserved.

Beginning in 2016, a portion of the proceeds from pages under the '/drupal-code-examples/' URI will be donated to charity.