- Patch #320451 by chx, Damien Tournoud: improved Drupal's module dependency system. This helps with fields in core. Comes with tests\!

1 files changed, 190 insertions, 0 deletions

diff --git a/modules/simpletest/tests/graph.test b/modules/simpletest/tests/graph.test
new file mode 100644
index 000000000..ce95ac46b
--- /dev/null
+++ b/modules/simpletest/tests/graph.test
@@ -0,0 +1,190 @@
+<?php
+// $Id$
+
+/**
+ * @file
+ * Provides unit tests for graph.inc.
+ */
+
+/**
+ * Unit tests for the graph handling features.
+ */
+class GraphUnitTest extends DrupalWebTestCase {
+  function getInfo() {
+    return array(
+      'name' => t('Graph'),
+      'description' => t('Graph handling unit tests.'),
+      'group' => t('System'),
+    );
+  }
+
+  /**
+   * Test depth-first-search features.
+   */
+  function testDepthFirstSearch() {
+    // Provoke the inclusion of graph.inc.
+    drupal_function_exists('drupal_depth_first_search');
+
+    // 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),
+    ));
+    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),
+      6 => array(),
+      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),
+      6 => array(5, 7),
+      7 => array(),
+      8 => array(),
+      9 => array(8),
+    );
+    $this->assertReversePaths($graph, $expected_reverse_paths);
+
+    $expected_components = array(
+      array(1, 2, 3, 4, 5, 6, 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, 6),
+      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) {
+      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)';
+    }
+  }
+}
+