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