From a10731cedf6acb9acabaed2ad3c8fe6ce4816ae9 Mon Sep 17 00:00:00 2001 From: Dries Buytaert Date: Wed, 14 Jan 2009 12:18:37 +0000 Subject: - Patch #320451 by chx, Damien Tournoud: improved Drupal's module dependency system. This helps with fields in core. Comes with tests\! --- modules/simpletest/tests/graph.test | 190 ++++++++++++++++++++++++++++++++++++ 1 file changed, 190 insertions(+) create mode 100644 modules/simpletest/tests/graph.test (limited to 'modules/simpletest/tests/graph.test') 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 @@ + 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)'; + } + } +} + -- cgit v1.2.3