class GraphUnitTest in SimpleTest 7

Unit tests for the graph handling features.

Hierarchy

class \DrupalTestCase
- class \DrupalUnitTestCase
  - class \GraphUnitTest

Expanded class hierarchy of GraphUnitTest

File

tests/graph.test, line 11: Provides unit tests for graph.inc.

View source

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

  /**
   * Test depth-first-search features.
   */
  function testDepthFirstSearch() {

    // Provoke the inclusion of graph.inc.
    require_once 'includes/graph.inc';

    // 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)';
    }
  }

}

Members

Name	Modifiers	Type	Description	Overrides
DrupalTestCase::$assertions	protected	property	Assertions thrown in that test case.
DrupalTestCase::$originalFileDirectory	protected	property	The original file directory, before it was changed for testing purposes.
DrupalTestCase::$originalPrefix	protected	property	The original database prefix, before it was changed for testing purposes.
DrupalTestCase::$results	public	property	Current results of this test case.
DrupalTestCase::$skipClasses	protected	property	This class is skipped when looking for the source of an assertion.
DrupalTestCase::$testId	protected	property	The test run ID.
DrupalTestCase::$timeLimit	protected	property	Time limit for the test.
DrupalTestCase::assert	protected	function	Internal helper: stores the assert.
DrupalTestCase::assertEqual	protected	function	Check to see if two values are equal.
DrupalTestCase::assertFalse	protected	function	Check to see if a value is false (an empty string, 0, NULL, or FALSE).
DrupalTestCase::assertIdentical	protected	function	Check to see if two values are identical.
DrupalTestCase::assertNotEqual	protected	function	Check to see if two values are not equal.
DrupalTestCase::assertNotIdentical	protected	function	Check to see if two values are not identical.
DrupalTestCase::assertNotNull	protected	function	Check to see if a value is not NULL.
DrupalTestCase::assertNull	protected	function	Check to see if a value is NULL.
DrupalTestCase::assertTrue	protected	function	Check to see if a value is not false (not an empty string, 0, NULL, or FALSE).
DrupalTestCase::error	protected	function	Fire an error assertion.	1
DrupalTestCase::errorHandler	public	function	Handle errors.
DrupalTestCase::exceptionHandler	protected	function	Handle exceptions.
DrupalTestCase::fail	protected	function	Fire an assertion that is always negative.
DrupalTestCase::getAssertionCall	protected	function	Cycles through backtrace until the first non-assertion method is found.
DrupalTestCase::insertAssert	public static	function	Store an assertion from outside the testing context.
DrupalTestCase::pass	protected	function	Fire an assertion that is always positive.
DrupalTestCase::randomName	public static	function	Generates a random string containing letters and numbers.
DrupalTestCase::randomString	public static	function	Generates a random string of ASCII characters of codes 32 to 126.
DrupalTestCase::run	public	function	Run all tests in this class.
DrupalUnitTestCase::setUp		function		1
DrupalUnitTestCase::tearDown		function
DrupalUnitTestCase::__construct		function	Constructor for DrupalUnitTestCase. Overrides DrupalTestCase::__construct
GraphUnitTest::assertComponents		function	Verify expected components in a graph.
GraphUnitTest::assertPaths		function	Verify expected paths in a graph.
GraphUnitTest::assertReversePaths		function	Verify expected reverse paths in a graph.
GraphUnitTest::assertWeights		function	Verify expected order in a graph.
GraphUnitTest::displayArray		function	Helper function to output vertices as comma-separated list.
GraphUnitTest::getInfo	public static	function
GraphUnitTest::normalizeGraph		function	Return a normalized version of a graph.
GraphUnitTest::testDepthFirstSearch		function	Test depth-first-search features.

You are here

class GraphUnitTest in SimpleTest 7

Hierarchy

File

Members

API Navigation