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