annotate core/tests/Drupal/Tests/Component/Graph/GraphTest.php @ 19:fa3358dc1485 tip

Add ndrum files
author Chris Cannam
date Wed, 28 Aug 2019 13:14:47 +0100
parents 4c8ae668cc8c
children
rev   line source
Chris@0 1 <?php
Chris@0 2
Chris@0 3 namespace Drupal\Tests\Component\Graph;
Chris@0 4
Chris@0 5 use Drupal\Component\Graph\Graph;
Chris@0 6 use PHPUnit\Framework\TestCase;
Chris@0 7
Chris@0 8 /**
Chris@0 9 * @coversDefaultClass \Drupal\Component\Graph\Graph
Chris@0 10 * @group Graph
Chris@0 11 */
Chris@0 12 class GraphTest extends TestCase {
Chris@0 13
Chris@0 14 /**
Chris@0 15 * Test depth-first-search features.
Chris@0 16 */
Chris@0 17 public function testDepthFirstSearch() {
Chris@0 18 // The sample graph used is:
Chris@0 19 // 1 --> 2 --> 3 5 ---> 6
Chris@0 20 // | ^ ^
Chris@0 21 // | | |
Chris@0 22 // | | |
Chris@0 23 // +---> 4 <-- 7 8 ---> 9
Chris@0 24 $graph = $this->normalizeGraph([
Chris@0 25 1 => [2],
Chris@0 26 2 => [3, 4],
Chris@0 27 3 => [],
Chris@0 28 4 => [3],
Chris@0 29 5 => [6],
Chris@0 30 7 => [4, 5],
Chris@0 31 8 => [9],
Chris@0 32 9 => [],
Chris@0 33 ]);
Chris@0 34 $graph_object = new Graph($graph);
Chris@0 35 $graph = $graph_object->searchAndSort();
Chris@0 36
Chris@0 37 $expected_paths = [
Chris@0 38 1 => [2, 3, 4],
Chris@0 39 2 => [3, 4],
Chris@0 40 3 => [],
Chris@0 41 4 => [3],
Chris@0 42 5 => [6],
Chris@0 43 7 => [4, 3, 5, 6],
Chris@0 44 8 => [9],
Chris@0 45 9 => [],
Chris@0 46 ];
Chris@0 47 $this->assertPaths($graph, $expected_paths);
Chris@0 48
Chris@0 49 $expected_reverse_paths = [
Chris@0 50 1 => [],
Chris@0 51 2 => [1],
Chris@0 52 3 => [2, 1, 4, 7],
Chris@0 53 4 => [2, 1, 7],
Chris@0 54 5 => [7],
Chris@0 55 7 => [],
Chris@0 56 8 => [],
Chris@0 57 9 => [8],
Chris@0 58 ];
Chris@0 59 $this->assertReversePaths($graph, $expected_reverse_paths);
Chris@0 60
Chris@0 61 // Assert that DFS didn't created "missing" vertexes automatically.
Chris@0 62 $this->assertFalse(isset($graph[6]), 'Vertex 6 has not been created');
Chris@0 63
Chris@0 64 $expected_components = [
Chris@0 65 [1, 2, 3, 4, 5, 7],
Chris@0 66 [8, 9],
Chris@0 67 ];
Chris@0 68 $this->assertComponents($graph, $expected_components);
Chris@0 69
Chris@0 70 $expected_weights = [
Chris@0 71 [1, 2, 3],
Chris@0 72 [2, 4, 3],
Chris@0 73 [7, 4, 3],
Chris@0 74 [7, 5],
Chris@0 75 [8, 9],
Chris@0 76 ];
Chris@0 77 $this->assertWeights($graph, $expected_weights);
Chris@0 78 }
Chris@0 79
Chris@0 80 /**
Chris@0 81 * Normalizes a graph.
Chris@0 82 *
Chris@0 83 * @param $graph
Chris@0 84 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0 85 *
Chris@0 86 * @return array
Chris@0 87 * The normalized version of a graph.
Chris@0 88 */
Chris@0 89 protected function normalizeGraph($graph) {
Chris@0 90 $normalized_graph = [];
Chris@0 91 foreach ($graph as $vertex => $edges) {
Chris@0 92 // Create vertex even if it hasn't any edges.
Chris@0 93 $normalized_graph[$vertex] = [];
Chris@0 94 foreach ($edges as $edge) {
Chris@0 95 $normalized_graph[$vertex]['edges'][$edge] = TRUE;
Chris@0 96 }
Chris@0 97 }
Chris@0 98 return $normalized_graph;
Chris@0 99 }
Chris@0 100
Chris@0 101 /**
Chris@0 102 * Verify expected paths in a graph.
Chris@0 103 *
Chris@0 104 * @param $graph
Chris@0 105 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0 106 * @param $expected_paths
Chris@0 107 * An associative array containing vertices with their expected paths.
Chris@0 108 */
Chris@0 109 protected function assertPaths($graph, $expected_paths) {
Chris@0 110 foreach ($expected_paths as $vertex => $paths) {
Chris@0 111 // Build an array with keys = $paths and values = TRUE.
Chris@0 112 $expected = array_fill_keys($paths, TRUE);
Chris@0 113 $result = isset($graph[$vertex]['paths']) ? $graph[$vertex]['paths'] : [];
Chris@0 114 $this->assertEquals($expected, $result, sprintf('Expected paths for vertex %s: %s, got %s', $vertex, $this->displayArray($expected, TRUE), $this->displayArray($result, TRUE)));
Chris@0 115 }
Chris@0 116 }
Chris@0 117
Chris@0 118 /**
Chris@0 119 * Verify expected reverse paths in a graph.
Chris@0 120 *
Chris@0 121 * @param $graph
Chris@0 122 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0 123 * @param $expected_reverse_paths
Chris@0 124 * An associative array containing vertices with their expected reverse
Chris@0 125 * paths.
Chris@0 126 */
Chris@0 127 protected function assertReversePaths($graph, $expected_reverse_paths) {
Chris@0 128 foreach ($expected_reverse_paths as $vertex => $paths) {
Chris@0 129 // Build an array with keys = $paths and values = TRUE.
Chris@0 130 $expected = array_fill_keys($paths, TRUE);
Chris@0 131 $result = isset($graph[$vertex]['reverse_paths']) ? $graph[$vertex]['reverse_paths'] : [];
Chris@0 132 $this->assertEquals($expected, $result, sprintf('Expected reverse paths for vertex %s: %s, got %s', $vertex, $this->displayArray($expected, TRUE), $this->displayArray($result, TRUE)));
Chris@0 133 }
Chris@0 134 }
Chris@0 135
Chris@0 136 /**
Chris@0 137 * Verify expected components in a graph.
Chris@0 138 *
Chris@0 139 * @param $graph
Chris@0 140 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort().
Chris@0 141 * @param $expected_components
Chris@0 142 * An array containing of components defined as a list of their vertices.
Chris@0 143 */
Chris@0 144 protected function assertComponents($graph, $expected_components) {
Chris@0 145 $unassigned_vertices = array_fill_keys(array_keys($graph), TRUE);
Chris@0 146 foreach ($expected_components as $component) {
Chris@0 147 $result_components = [];
Chris@0 148 foreach ($component as $vertex) {
Chris@0 149 $result_components[] = $graph[$vertex]['component'];
Chris@0 150 unset($unassigned_vertices[$vertex]);
Chris@0 151 }
Chris@0 152 $this->assertEquals(1, count(array_unique($result_components)), sprintf('Expected one unique component for vertices %s, got %s', $this->displayArray($component), $this->displayArray($result_components)));
Chris@0 153 }
Chris@0 154 $this->assertEquals([], $unassigned_vertices, sprintf('Vertices not assigned to a component: %s', $this->displayArray($unassigned_vertices, TRUE)));
Chris@0 155 }
Chris@0 156
Chris@0 157 /**
Chris@0 158 * Verify expected order in a graph.
Chris@0 159 *
Chris@0 160 * @param $graph
Chris@0 161 * A graph array processed by \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0 162 * @param $expected_orders
Chris@0 163 * An array containing lists of vertices in their expected order.
Chris@0 164 */
Chris@0 165 protected function assertWeights($graph, $expected_orders) {
Chris@0 166 foreach ($expected_orders as $order) {
Chris@0 167 $previous_vertex = array_shift($order);
Chris@0 168 foreach ($order as $vertex) {
Chris@0 169 $this->assertTrue($graph[$previous_vertex]['weight'] < $graph[$vertex]['weight'], sprintf('Weights of %s and %s are correct relative to each other', $previous_vertex, $vertex));
Chris@0 170 }
Chris@0 171 }
Chris@0 172 }
Chris@0 173
Chris@0 174 /**
Chris@0 175 * Helper function to output vertices as comma-separated list.
Chris@0 176 *
Chris@0 177 * @param $paths
Chris@0 178 * An array containing a list of vertices.
Chris@0 179 * @param $keys
Chris@0 180 * (optional) Whether to output the keys of $paths instead of the values.
Chris@0 181 */
Chris@0 182 protected function displayArray($paths, $keys = FALSE) {
Chris@0 183 if (!empty($paths)) {
Chris@0 184 return implode(', ', $keys ? array_keys($paths) : $paths);
Chris@0 185 }
Chris@0 186 else {
Chris@0 187 return '(empty)';
Chris@0 188 }
Chris@0 189 }
Chris@0 190
Chris@0 191 }