<?php

/**

 * @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]), '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, format_string('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, format_string('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)), format_string('Expected one unique component for vertices @vertices, got @components', array('@vertices' => $this->displayArray($component), '@components' => $this->displayArray($result_components))));

    }

    $this->assertEqual(array(), $unassigned_vertices, format_string('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'], format_string('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)';

    }

  }

}