1 #!/usr/bin/env python3 2 # Copyright 2016 Google Inc. All Rights Reserved. 3 # 4 # Licensed under the Apache License, Version 2.0 (the "License"); 5 # you may not use this file except in compliance with the License. 6 # You may obtain a copy of the License at 7 # 8 # http://www.apache.org/licenses/LICENSE-2.0 9 # 10 # Unless required by applicable law or agreed to in writing, software 11 # distributed under the License is distributed on an "AS-IS" BASIS, 12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 # See the License for the specific language governing permissions and 14 # limitations under the License. 15 16 from fruit_test_common import * 17 18 COMMON_DEFINITIONS = ''' 19 #include "test_common.h" 20 21 #define IN_FRUIT_CPP_FILE 1 22 #include <fruit/impl/data_structures/semistatic_graph.templates.h> 23 24 using namespace std; 25 using namespace fruit::impl; 26 27 using Graph = SemistaticGraph<int, const char*>; 28 using node_iterator = Graph::node_iterator; 29 using edge_iterator = Graph::edge_iterator; 30 31 vector<int> no_neighbors{}; 32 33 struct SimpleNode { 34 int id; 35 const char* value; 36 const vector<int>* neighbors; 37 bool is_terminal; 38 39 int getId() { return id; } 40 const char* getValue() { return value; } 41 bool isTerminal() { return is_terminal; } 42 vector<int>::const_iterator getEdgesBegin() { return neighbors->begin(); } 43 vector<int>::const_iterator getEdgesEnd() { return neighbors->end(); } 44 }; 45 ''' 46 47 def test_empty(): 48 source = ''' 49 int main() { 50 MemoryPool memory_pool; 51 vector<SimpleNode> values{}; 52 53 Graph graph(values.begin(), values.end(), memory_pool); 54 Assert(graph.find(0) == graph.end()); 55 Assert(graph.find(2) == graph.end()); 56 Assert(graph.find(5) == graph.end()); 57 const Graph& cgraph = graph; 58 Assert(cgraph.find(0) == cgraph.end()); 59 Assert(cgraph.find(2) == cgraph.end()); 60 Assert(cgraph.find(5) == cgraph.end()); 61 } 62 ''' 63 expect_success( 64 COMMON_DEFINITIONS, 65 source, 66 locals()) 67 68 def test_1_node_no_edges(): 69 source = ''' 70 int main() { 71 MemoryPool memory_pool; 72 vector<SimpleNode> values{{2, "foo", &no_neighbors, false}}; 73 74 Graph graph(values.begin(), values.end(), memory_pool); 75 Assert(graph.find(0) == graph.end()); 76 Assert(!(graph.find(2) == graph.end())); 77 Assert(graph.at(2).getNode() == string("foo")); 78 Assert(graph.at(2).isTerminal() == false); 79 Assert(graph.find(5) == graph.end()); 80 const Graph& cgraph = graph; 81 Assert(cgraph.find(0) == cgraph.end()); 82 Assert(!(cgraph.find(2) == cgraph.end())); 83 Assert(cgraph.find(2).getNode() == string("foo")); 84 Assert(cgraph.find(2).isTerminal() == false); 85 Assert(cgraph.find(5) == cgraph.end()); 86 } 87 ''' 88 expect_success( 89 COMMON_DEFINITIONS, 90 source, 91 locals()) 92 93 def test_1_node_no_edges_terminal(): 94 source = ''' 95 int main() { 96 MemoryPool memory_pool; 97 vector<SimpleNode> values{{2, "foo", &no_neighbors, true}}; 98 99 Graph graph(values.begin(), values.end(), memory_pool); 100 Assert(graph.find(0) == graph.end()); 101 Assert(!(graph.find(2) == graph.end())); 102 Assert(graph.at(2).getNode() == string("foo")); 103 Assert(graph.at(2).isTerminal() == true); 104 Assert(graph.find(5) == graph.end()); 105 const Graph& cgraph = graph; 106 Assert(cgraph.find(0) == cgraph.end()); 107 Assert(!(cgraph.find(2) == cgraph.end())); 108 Assert(cgraph.find(2).getNode() == string("foo")); 109 Assert(cgraph.find(2).isTerminal() == true); 110 Assert(cgraph.find(5) == cgraph.end()); 111 } 112 ''' 113 expect_success( 114 COMMON_DEFINITIONS, 115 source, 116 locals()) 117 118 def test_1_node_self_edge(): 119 source = ''' 120 int main() { 121 MemoryPool memory_pool; 122 vector<int> neighbors = {2}; 123 vector<SimpleNode> values{{2, "foo", &neighbors, false}}; 124 125 Graph graph(values.begin(), values.end(), memory_pool); 126 Assert(graph.find(0) == graph.end()); 127 Assert(!(graph.find(2) == graph.end())); 128 Assert(graph.at(2).getNode() == string("foo")); 129 Assert(graph.at(2).isTerminal() == false); 130 edge_iterator itr = graph.at(2).neighborsBegin(); 131 (void)itr; 132 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo")); 133 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false); 134 Assert(graph.find(5) == graph.end()); 135 const Graph& cgraph = graph; 136 Assert(cgraph.find(0) == cgraph.end()); 137 Assert(!(cgraph.find(2) == cgraph.end())); 138 Assert(cgraph.find(2).getNode() == string("foo")); 139 Assert(cgraph.find(2).isTerminal() == false); 140 } 141 ''' 142 expect_success( 143 COMMON_DEFINITIONS, 144 source, 145 locals()) 146 147 def test_2_nodes_one_edge(): 148 source = ''' 149 int main() { 150 MemoryPool memory_pool; 151 vector<int> neighbors = {2}; 152 vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}}; 153 154 Graph graph(values.begin(), values.end(), memory_pool); 155 Assert(graph.find(0) == graph.end()); 156 Assert(!(graph.find(2) == graph.end())); 157 Assert(graph.at(2).getNode() == string("foo")); 158 Assert(graph.at(2).isTerminal() == false); 159 Assert(graph.at(3).getNode() == string("bar")); 160 Assert(graph.at(3).isTerminal() == false); 161 edge_iterator itr = graph.at(3).neighborsBegin(); 162 (void)itr; 163 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo")); 164 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false); 165 Assert(graph.find(5) == graph.end()); 166 const Graph& cgraph = graph; 167 Assert(cgraph.find(0) == cgraph.end()); 168 Assert(!(cgraph.find(2) == cgraph.end())); 169 Assert(cgraph.find(2).getNode() == string("foo")); 170 Assert(cgraph.find(2).isTerminal() == false); 171 Assert(cgraph.find(3).getNode() == string("bar")); 172 Assert(cgraph.find(3).isTerminal() == false); 173 } 174 ''' 175 expect_success( 176 COMMON_DEFINITIONS, 177 source, 178 locals()) 179 180 def test_3_nodes_two_edges(): 181 source = ''' 182 int main() { 183 MemoryPool memory_pool; 184 vector<int> neighbors = {2, 4}; 185 vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}, {4, "baz", &no_neighbors, true}}; 186 187 Graph graph(values.begin(), values.end(), memory_pool); 188 Assert(graph.find(0) == graph.end()); 189 Assert(!(graph.find(2) == graph.end())); 190 Assert(graph.at(2).getNode() == string("foo")); 191 Assert(graph.at(2).isTerminal() == false); 192 Assert(graph.at(3).getNode() == string("bar")); 193 Assert(graph.at(3).isTerminal() == false); 194 edge_iterator itr = graph.at(3).neighborsBegin(); 195 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo")); 196 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false); 197 ++itr; 198 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("baz")); 199 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == true); 200 Assert(graph.at(4).getNode() == string("baz")); 201 Assert(graph.at(4).isTerminal() == true); 202 Assert(graph.find(5) == graph.end()); 203 const Graph& cgraph = graph; 204 Assert(cgraph.find(0) == cgraph.end()); 205 Assert(!(cgraph.find(2) == cgraph.end())); 206 Assert(cgraph.find(2).getNode() == string("foo")); 207 Assert(cgraph.find(2).isTerminal() == false); 208 Assert(cgraph.find(3).getNode() == string("bar")); 209 Assert(cgraph.find(3).isTerminal() == false); 210 Assert(cgraph.find(4).getNode() == string("baz")); 211 Assert(cgraph.find(4).isTerminal() == true); 212 Assert(cgraph.find(5) == cgraph.end()); 213 } 214 ''' 215 expect_success( 216 COMMON_DEFINITIONS, 217 source, 218 locals()) 219 220 def test_add_node(): 221 source = ''' 222 int main() { 223 MemoryPool memory_pool; 224 vector<SimpleNode> old_values{{2, "foo", &no_neighbors, false}, {4, "baz", &no_neighbors, true}}; 225 226 Graph old_graph(old_values.begin(), old_values.end(), memory_pool); 227 vector<int> neighbors = {2, 4}; 228 vector<SimpleNode> new_values{{3, "bar", &neighbors, false}}; 229 230 Graph graph(old_graph, new_values.begin(), new_values.end(), memory_pool); 231 Assert(graph.find(0) == graph.end()); 232 Assert(!(graph.find(2) == graph.end())); 233 Assert(graph.at(2).getNode() == string("foo")); 234 Assert(graph.at(2).isTerminal() == false); 235 Assert(graph.at(3).getNode() == string("bar")); 236 Assert(graph.at(3).isTerminal() == false); 237 edge_iterator itr = graph.at(3).neighborsBegin(); 238 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo")); 239 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false); 240 ++itr; 241 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("baz")); 242 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == true); 243 Assert(graph.at(4).getNode() == string("baz")); 244 Assert(graph.at(4).isTerminal() == true); 245 Assert(graph.find(5) == graph.end()); 246 const Graph& cgraph = graph; 247 Assert(cgraph.find(0) == cgraph.end()); 248 Assert(!(cgraph.find(2) == cgraph.end())); 249 Assert(cgraph.find(2).getNode() == string("foo")); 250 Assert(cgraph.find(2).isTerminal() == false); 251 Assert(cgraph.find(3).getNode() == string("bar")); 252 Assert(cgraph.find(3).isTerminal() == false); 253 Assert(cgraph.find(4).getNode() == string("baz")); 254 Assert(cgraph.find(4).isTerminal() == true); 255 Assert(cgraph.find(5) == cgraph.end()); 256 } 257 ''' 258 expect_success( 259 COMMON_DEFINITIONS, 260 source, 261 locals()) 262 263 def test_set_terminal(): 264 source = ''' 265 int main() { 266 MemoryPool memory_pool; 267 vector<int> neighbors = {2, 4}; 268 vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}, {4, "baz", &no_neighbors, true}}; 269 270 Graph graph(values.begin(), values.end(), memory_pool); 271 graph.find(3).setTerminal(); 272 Assert(graph.find(0) == graph.end()); 273 Assert(!(graph.find(2) == graph.end())); 274 Assert(graph.at(2).getNode() == string("foo")); 275 Assert(graph.at(2).isTerminal() == false); 276 Assert(graph.at(3).getNode() == string("bar")); 277 Assert(graph.at(3).isTerminal() == true); 278 Assert(graph.at(4).getNode() == string("baz")); 279 Assert(graph.at(4).isTerminal() == true); 280 Assert(graph.find(5) == graph.end()); 281 const Graph& cgraph = graph; 282 Assert(cgraph.find(0) == cgraph.end()); 283 Assert(!(cgraph.find(2) == cgraph.end())); 284 Assert(cgraph.find(2).getNode() == string("foo")); 285 Assert(cgraph.find(3).getNode() == string("bar")); 286 Assert(cgraph.find(4).getNode() == string("baz")); 287 Assert(cgraph.find(5) == cgraph.end()); 288 } 289 ''' 290 expect_success( 291 COMMON_DEFINITIONS, 292 source, 293 locals()) 294 295 def test_move_constructor(): 296 source = ''' 297 int main() { 298 MemoryPool memory_pool; 299 vector<int> neighbors = {2}; 300 vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}}; 301 302 Graph graph1(values.begin(), values.end(), memory_pool); 303 Graph graph = std::move(graph1); 304 Assert(graph.find(0) == graph.end()); 305 Assert(!(graph.find(2) == graph.end())); 306 Assert(graph.at(2).getNode() == string("foo")); 307 Assert(graph.at(2).isTerminal() == false); 308 Assert(graph.at(3).getNode() == string("bar")); 309 Assert(graph.at(3).isTerminal() == false); 310 edge_iterator itr = graph.at(3).neighborsBegin(); 311 (void)itr; 312 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo")); 313 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false); 314 Assert(graph.find(5) == graph.end()); 315 } 316 ''' 317 expect_success( 318 COMMON_DEFINITIONS, 319 source, 320 locals()) 321 322 def test_move_assignment(): 323 source = ''' 324 int main() { 325 MemoryPool memory_pool; 326 vector<int> neighbors = {2}; 327 vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}}; 328 329 Graph graph1(values.begin(), values.end(), memory_pool); 330 Graph graph; 331 graph = std::move(graph1); 332 Assert(graph.find(0) == graph.end()); 333 Assert(!(graph.find(2) == graph.end())); 334 Assert(graph.at(2).getNode() == string("foo")); 335 Assert(graph.at(2).isTerminal() == false); 336 Assert(graph.at(3).getNode() == string("bar")); 337 Assert(graph.at(3).isTerminal() == false); 338 edge_iterator itr = graph.at(3).neighborsBegin(); 339 (void)itr; 340 Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo")); 341 Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false); 342 Assert(graph.find(5) == graph.end()); 343 } 344 ''' 345 expect_success( 346 COMMON_DEFINITIONS, 347 source, 348 locals()) 349 350 def test_incomplete_graph(): 351 source = ''' 352 int main() { 353 MemoryPool memory_pool; 354 vector<int> neighbors = {2}; 355 vector<SimpleNode> values{{1, "foo", &neighbors, false}}; 356 357 Graph graph(values.begin(), values.end(), memory_pool); 358 Assert(!(graph.find(1) == graph.end())); 359 Assert(graph.at(1).getNode() == string("foo")); 360 Assert(graph.at(1).isTerminal() == false); 361 Assert(graph.find(2) == graph.end()); 362 const Graph& cgraph = graph; 363 Assert(!(cgraph.find(1) == cgraph.end())); 364 Assert(cgraph.find(1).getNode() == string("foo")); 365 Assert(cgraph.find(1).isTerminal() == false); 366 Assert(cgraph.find(2) == cgraph.end()); 367 } 368 ''' 369 expect_success( 370 COMMON_DEFINITIONS, 371 source, 372 locals()) 373 374 if __name__== '__main__': 375 main(__file__) 376
