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