|
1 <?php |
|
2 |
|
3 /** |
|
4 * @file |
|
5 * Provides unit tests for graph.inc. |
|
6 */ |
|
7 |
|
8 /** |
|
9 * Unit tests for the graph handling features. |
|
10 */ |
|
11 class GraphUnitTest extends DrupalUnitTestCase { |
|
12 public static function getInfo() { |
|
13 return array( |
|
14 'name' => 'Graph', |
|
15 'description' => 'Graph handling unit tests.', |
|
16 'group' => 'System', |
|
17 ); |
|
18 } |
|
19 |
|
20 function setUp() { |
|
21 require_once DRUPAL_ROOT . '/includes/graph.inc'; |
|
22 parent::setUp(); |
|
23 } |
|
24 |
|
25 /** |
|
26 * Test depth-first-search features. |
|
27 */ |
|
28 function testDepthFirstSearch() { |
|
29 // The sample graph used is: |
|
30 // 1 --> 2 --> 3 5 ---> 6 |
|
31 // | ^ ^ |
|
32 // | | | |
|
33 // | | | |
|
34 // +---> 4 <-- 7 8 ---> 9 |
|
35 $graph = $this->normalizeGraph(array( |
|
36 1 => array(2), |
|
37 2 => array(3, 4), |
|
38 3 => array(), |
|
39 4 => array(3), |
|
40 5 => array(6), |
|
41 7 => array(4, 5), |
|
42 8 => array(9), |
|
43 9 => array(), |
|
44 )); |
|
45 drupal_depth_first_search($graph); |
|
46 |
|
47 $expected_paths = array( |
|
48 1 => array(2, 3, 4), |
|
49 2 => array(3, 4), |
|
50 3 => array(), |
|
51 4 => array(3), |
|
52 5 => array(6), |
|
53 7 => array(4, 3, 5, 6), |
|
54 8 => array(9), |
|
55 9 => array(), |
|
56 ); |
|
57 $this->assertPaths($graph, $expected_paths); |
|
58 |
|
59 $expected_reverse_paths = array( |
|
60 1 => array(), |
|
61 2 => array(1), |
|
62 3 => array(2, 1, 4, 7), |
|
63 4 => array(2, 1, 7), |
|
64 5 => array(7), |
|
65 7 => array(), |
|
66 8 => array(), |
|
67 9 => array(8), |
|
68 ); |
|
69 $this->assertReversePaths($graph, $expected_reverse_paths); |
|
70 |
|
71 // Assert that DFS didn't created "missing" vertexes automatically. |
|
72 $this->assertFALSE(isset($graph[6]), 'Vertex 6 has not been created'); |
|
73 |
|
74 $expected_components = array( |
|
75 array(1, 2, 3, 4, 5, 7), |
|
76 array(8, 9), |
|
77 ); |
|
78 $this->assertComponents($graph, $expected_components); |
|
79 |
|
80 $expected_weights = array( |
|
81 array(1, 2, 3), |
|
82 array(2, 4, 3), |
|
83 array(7, 4, 3), |
|
84 array(7, 5), |
|
85 array(8, 9), |
|
86 ); |
|
87 $this->assertWeights($graph, $expected_weights); |
|
88 } |
|
89 |
|
90 /** |
|
91 * Return a normalized version of a graph. |
|
92 */ |
|
93 function normalizeGraph($graph) { |
|
94 $normalized_graph = array(); |
|
95 foreach ($graph as $vertex => $edges) { |
|
96 // Create vertex even if it hasn't any edges. |
|
97 $normalized_graph[$vertex] = array(); |
|
98 foreach ($edges as $edge) { |
|
99 $normalized_graph[$vertex]['edges'][$edge] = TRUE; |
|
100 } |
|
101 } |
|
102 return $normalized_graph; |
|
103 } |
|
104 |
|
105 /** |
|
106 * Verify expected paths in a graph. |
|
107 * |
|
108 * @param $graph |
|
109 * A graph array processed by drupal_depth_first_search(). |
|
110 * @param $expected_paths |
|
111 * An associative array containing vertices with their expected paths. |
|
112 */ |
|
113 function assertPaths($graph, $expected_paths) { |
|
114 foreach ($expected_paths as $vertex => $paths) { |
|
115 // Build an array with keys = $paths and values = TRUE. |
|
116 $expected = array_fill_keys($paths, TRUE); |
|
117 $result = isset($graph[$vertex]['paths']) ? $graph[$vertex]['paths'] : array(); |
|
118 $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)))); |
|
119 } |
|
120 } |
|
121 |
|
122 /** |
|
123 * Verify expected reverse paths in a graph. |
|
124 * |
|
125 * @param $graph |
|
126 * A graph array processed by drupal_depth_first_search(). |
|
127 * @param $expected_reverse_paths |
|
128 * An associative array containing vertices with their expected reverse |
|
129 * paths. |
|
130 */ |
|
131 function assertReversePaths($graph, $expected_reverse_paths) { |
|
132 foreach ($expected_reverse_paths as $vertex => $paths) { |
|
133 // Build an array with keys = $paths and values = TRUE. |
|
134 $expected = array_fill_keys($paths, TRUE); |
|
135 $result = isset($graph[$vertex]['reverse_paths']) ? $graph[$vertex]['reverse_paths'] : array(); |
|
136 $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)))); |
|
137 } |
|
138 } |
|
139 |
|
140 /** |
|
141 * Verify expected components in a graph. |
|
142 * |
|
143 * @param $graph |
|
144 * A graph array processed by drupal_depth_first_search(). |
|
145 * @param $expected_components |
|
146 * An array containing of components defined as a list of their vertices. |
|
147 */ |
|
148 function assertComponents($graph, $expected_components) { |
|
149 $unassigned_vertices = array_fill_keys(array_keys($graph), TRUE); |
|
150 foreach ($expected_components as $component) { |
|
151 $result_components = array(); |
|
152 foreach ($component as $vertex) { |
|
153 $result_components[] = $graph[$vertex]['component']; |
|
154 unset($unassigned_vertices[$vertex]); |
|
155 } |
|
156 $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)))); |
|
157 } |
|
158 $this->assertEqual(array(), $unassigned_vertices, format_string('Vertices not assigned to a component: @vertices', array('@vertices' => $this->displayArray($unassigned_vertices, TRUE)))); |
|
159 } |
|
160 |
|
161 /** |
|
162 * Verify expected order in a graph. |
|
163 * |
|
164 * @param $graph |
|
165 * A graph array processed by drupal_depth_first_search(). |
|
166 * @param $expected_orders |
|
167 * An array containing lists of vertices in their expected order. |
|
168 */ |
|
169 function assertWeights($graph, $expected_orders) { |
|
170 foreach ($expected_orders as $order) { |
|
171 $previous_vertex = array_shift($order); |
|
172 foreach ($order as $vertex) { |
|
173 $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))); |
|
174 } |
|
175 } |
|
176 } |
|
177 |
|
178 /** |
|
179 * Helper function to output vertices as comma-separated list. |
|
180 * |
|
181 * @param $paths |
|
182 * An array containing a list of vertices. |
|
183 * @param $keys |
|
184 * (optional) Whether to output the keys of $paths instead of the values. |
|
185 */ |
|
186 function displayArray($paths, $keys = FALSE) { |
|
187 if (!empty($paths)) { |
|
188 return implode(', ', $keys ? array_keys($paths) : $paths); |
|
189 } |
|
190 else { |
|
191 return '(empty)'; |
|
192 } |
|
193 } |
|
194 } |
|
195 |