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 }
|