1 // Copyright (C) 2007 Davis E. King (davis@dlib.net) 2 // License: Boost Software License See LICENSE.txt for the full license. 3 4 5 #include <sstream> 6 #include <string> 7 #include <cstdlib> 8 #include <ctime> 9 #include <dlib/directed_graph.h> 10 #include <dlib/graph.h> 11 #include <dlib/graph_utils.h> 12 #include <dlib/set.h> 13 14 #include "tester.h" 15 16 // This is called an unnamed-namespace and it has the effect of making everything inside this file "private" 17 // so that everything you declare will have static linkage. Thus we won't have any multiply 18 // defined symbol errors coming out of the linker when we try to compile the test suite. 19 namespace 20 { 21 22 using namespace test; 23 using namespace dlib; 24 using namespace std; 25 26 // Declare the logger we will use in this test. The name of the tester 27 // should start with "test." 28 logger dlog("test.directed_graph"); 29 30 template < 31 typename directed_graph 32 > directed_graph_test()33 void directed_graph_test ( 34 ) 35 /*! 36 requires 37 - directed_graph is an implementation of directed_graph/directed_graph_kernel_abstract.h 38 is instantiated with int 39 ensures 40 - runs tests on directed_graph for compliance with the specs 41 !*/ 42 { 43 print_spinner(); 44 45 COMPILE_TIME_ASSERT(is_directed_graph<directed_graph>::value == true); 46 directed_graph a, b; 47 dlib::set<unsigned long>::compare_1b_c s; 48 49 DLIB_TEST(graph_contains_directed_cycle(a) == false); 50 DLIB_TEST(graph_contains_undirected_cycle(a) == false); 51 52 DLIB_TEST(a.number_of_nodes() == 0); 53 54 DLIB_TEST(graph_contains_length_one_cycle(a) == false); 55 56 a.set_number_of_nodes(5); 57 DLIB_TEST(graph_contains_length_one_cycle(a) == false); 58 DLIB_TEST(graph_is_connected(a) == false); 59 DLIB_TEST(graph_contains_directed_cycle(a) == false); 60 DLIB_TEST(graph_contains_undirected_cycle(a) == false); 61 DLIB_TEST(a.number_of_nodes() == 5); 62 63 for (int i = 0; i < 5; ++i) 64 { 65 a.node(i).data = i; 66 DLIB_TEST(a.node(i).index() == (unsigned int)i); 67 } 68 69 a.remove_node(1); 70 71 DLIB_TEST(a.number_of_nodes() == 4); 72 73 74 // make sure that only the number with data == 1 was remove 75 int count = 0; 76 for (int i = 0; i < 4; ++i) 77 { 78 count += a.node(i).data; 79 DLIB_TEST(a.node(i).number_of_children() == 0); 80 DLIB_TEST(a.node(i).number_of_parents() == 0); 81 DLIB_TEST(a.node(i).index() == (unsigned int)i); 82 } 83 84 DLIB_TEST(count == 9); 85 86 DLIB_TEST(graph_contains_directed_cycle(a) == false); 87 88 a.add_edge(1,1); 89 DLIB_TEST(graph_contains_length_one_cycle(a) == true); 90 DLIB_TEST(graph_contains_undirected_cycle(a) == true); 91 92 DLIB_TEST(graph_contains_directed_cycle(a) == true); 93 94 a.add_edge(1,2); 95 96 DLIB_TEST(graph_contains_directed_cycle(a) == true); 97 98 DLIB_TEST(a.node(1).number_of_children() == 2); 99 DLIB_TEST(a.node(1).number_of_parents() == 1); 100 DLIB_TEST_MSG(a.node(1).parent(0).index() == 1,""); 101 102 DLIB_TEST_MSG(a.node(1).child(0).index() + a.node(1).child(1).index() == 3,""); 103 DLIB_TEST(a.node(2).number_of_children() == 0); 104 DLIB_TEST(a.node(2).number_of_parents() == 1); 105 DLIB_TEST(a.node(2).index() == 2); 106 107 int val = a.node(1).data; 108 a.remove_node(1); 109 DLIB_TEST(graph_contains_length_one_cycle(a) == false); 110 111 DLIB_TEST(graph_contains_directed_cycle(a) == false); 112 DLIB_TEST(graph_contains_undirected_cycle(a) == false); 113 114 115 DLIB_TEST(a.number_of_nodes() == 3); 116 117 count = 0; 118 for (int i = 0; i < 3; ++i) 119 { 120 count += a.node(i).data; 121 DLIB_TEST(a.node(i).number_of_children() == 0); 122 DLIB_TEST(a.node(i).number_of_parents() == 0); 123 DLIB_TEST(a.node(i).index() == (unsigned int)i); 124 } 125 DLIB_TEST(count == 9-val); 126 127 128 val = a.add_node(); 129 DLIB_TEST(val == 3); 130 DLIB_TEST(a.number_of_nodes() == 4); 131 132 for (int i = 0; i < 4; ++i) 133 { 134 a.node(i).data = i; 135 DLIB_TEST(a.node(i).index() == (unsigned int)i); 136 } 137 138 for (int i = 0; i < 4; ++i) 139 { 140 DLIB_TEST(a.node(i).data == i); 141 DLIB_TEST(a.node(i).index() == (unsigned int)i); 142 } 143 144 a.add_edge(0, 1); 145 a.add_edge(0, 2); 146 DLIB_TEST(graph_is_connected(a) == false); 147 a.add_edge(1, 3); 148 DLIB_TEST(graph_is_connected(a) == true); 149 a.add_edge(2, 3); 150 DLIB_TEST(graph_is_connected(a) == true); 151 DLIB_TEST(graph_contains_length_one_cycle(a) == false); 152 153 DLIB_TEST(a.has_edge(0, 1)); 154 DLIB_TEST(a.has_edge(0, 2)); 155 DLIB_TEST(a.has_edge(1, 3)); 156 DLIB_TEST(a.has_edge(2, 3)); 157 158 DLIB_TEST(!a.has_edge(1, 0)); 159 DLIB_TEST(!a.has_edge(2, 0)); 160 DLIB_TEST(!a.has_edge(3, 1)); 161 DLIB_TEST(!a.has_edge(3, 2)); 162 163 DLIB_TEST(a.node(0).number_of_parents() == 0); 164 DLIB_TEST(a.node(0).number_of_children() == 2); 165 166 DLIB_TEST(a.node(1).number_of_parents() == 1); 167 DLIB_TEST(a.node(1).number_of_children() == 1); 168 DLIB_TEST(a.node(1).child(0).index() == 3); 169 DLIB_TEST(a.node(1).parent(0).index() == 0); 170 171 DLIB_TEST(a.node(2).number_of_parents() == 1); 172 DLIB_TEST(a.node(2).number_of_children() == 1); 173 DLIB_TEST(a.node(2).child(0).index() == 3); 174 DLIB_TEST(a.node(2).parent(0).index() == 0); 175 176 DLIB_TEST(a.node(3).number_of_parents() == 2); 177 DLIB_TEST(a.node(3).number_of_children() == 0); 178 179 DLIB_TEST(graph_contains_directed_cycle(a) == false); 180 DLIB_TEST(graph_contains_undirected_cycle(a) == true); 181 182 a.remove_edge(0,1); 183 184 DLIB_TEST(graph_contains_directed_cycle(a) == false); 185 186 DLIB_TEST(!a.has_edge(0, 1)); 187 DLIB_TEST(a.has_edge(0, 2)); 188 DLIB_TEST(a.has_edge(1, 3)); 189 DLIB_TEST(a.has_edge(2, 3)); 190 191 DLIB_TEST(!a.has_edge(1, 0)); 192 DLIB_TEST(!a.has_edge(2, 0)); 193 DLIB_TEST(!a.has_edge(3, 1)); 194 DLIB_TEST(!a.has_edge(3, 2)); 195 196 197 DLIB_TEST(a.node(0).number_of_parents() == 0); 198 DLIB_TEST(a.node(0).number_of_children() == 1); 199 200 DLIB_TEST(a.node(1).number_of_parents() == 0); 201 DLIB_TEST(a.node(1).number_of_children() == 1); 202 DLIB_TEST(a.node(1).child(0).index() == 3); 203 204 DLIB_TEST(a.node(2).number_of_parents() == 1); 205 DLIB_TEST(a.node(2).number_of_children() == 1); 206 DLIB_TEST(a.node(2).child(0).index() == 3); 207 DLIB_TEST(a.node(2).parent(0).index() == 0); 208 209 DLIB_TEST(a.node(3).number_of_parents() == 2); 210 DLIB_TEST(a.node(3).number_of_children() == 0); 211 212 for (int i = 0; i < 4; ++i) 213 { 214 DLIB_TEST(a.node(i).data == i); 215 DLIB_TEST(a.node(i).index() == (unsigned int)i); 216 } 217 218 219 220 swap(a,b); 221 222 DLIB_TEST(a.number_of_nodes() == 0); 223 DLIB_TEST(b.number_of_nodes() == 4); 224 DLIB_TEST(b.node(0).number_of_parents() == 0); 225 DLIB_TEST(b.node(0).number_of_children() == 1); 226 227 DLIB_TEST(b.node(1).number_of_parents() == 0); 228 DLIB_TEST(b.node(1).number_of_children() == 1); 229 DLIB_TEST(b.node(1).child(0).index() == 3); 230 231 DLIB_TEST(b.node(2).number_of_parents() == 1); 232 DLIB_TEST(b.node(2).number_of_children() == 1); 233 DLIB_TEST(b.node(2).child(0).index() == 3); 234 DLIB_TEST(b.node(2).parent(0).index() == 0); 235 236 DLIB_TEST(b.node(3).number_of_parents() == 2); 237 DLIB_TEST(b.node(3).number_of_children() == 0); 238 b.node(0).child_edge(0) = static_cast<unsigned short>(b.node(0).child(0).index()+1); 239 b.node(1).child_edge(0) = static_cast<unsigned short>(b.node(1).child(0).index()+1); 240 b.node(2).child_edge(0) = static_cast<unsigned short>(b.node(2).child(0).index()+1); 241 242 DLIB_TEST_MSG(b.node(0).child_edge(0) == b.node(0).child(0).index()+1, 243 b.node(0).child_edge(0) << " " << b.node(0).child(0).index()+1); 244 DLIB_TEST_MSG(b.node(1).child_edge(0) == b.node(1).child(0).index()+1, 245 b.node(1).child_edge(0) << " " << b.node(1).child(0).index()+1); 246 DLIB_TEST_MSG(b.node(2).child_edge(0) == b.node(2).child(0).index()+1, 247 b.node(2).child_edge(0) << " " << b.node(2).child(0).index()+1); 248 249 DLIB_TEST_MSG(b.node(2).parent_edge(0) == 2+1, 250 b.node(2).parent_edge(0) << " " << 2+1); 251 DLIB_TEST_MSG(b.node(3).parent_edge(0) == 3+1, 252 b.node(3).parent_edge(0) << " " << 3+1); 253 DLIB_TEST_MSG(b.node(3).parent_edge(1) == 3+1, 254 b.node(3).parent_edge(1) << " " << 3+1); 255 256 ostringstream sout; 257 258 serialize(b, sout); 259 260 istringstream sin(sout.str()); 261 262 a.set_number_of_nodes(20); 263 DLIB_TEST(a.number_of_nodes() == 20); 264 deserialize(a, sin); 265 DLIB_TEST(a.number_of_nodes() == 4); 266 267 DLIB_TEST(!a.has_edge(0, 1)); 268 DLIB_TEST(a.has_edge(0, 2)); 269 DLIB_TEST(a.has_edge(1, 3)); 270 DLIB_TEST(a.has_edge(2, 3)); 271 272 DLIB_TEST(!a.has_edge(1, 0)); 273 DLIB_TEST(!a.has_edge(2, 0)); 274 DLIB_TEST(!a.has_edge(3, 1)); 275 DLIB_TEST(!a.has_edge(3, 2)); 276 277 DLIB_TEST_MSG(a.node(0).child_edge(0) == a.node(0).child(0).index()+1, 278 a.node(0).child_edge(0) << " " << a.node(0).child(0).index()+1); 279 DLIB_TEST_MSG(a.node(1).child_edge(0) == a.node(1).child(0).index()+1, 280 a.node(1).child_edge(0) << " " << a.node(1).child(0).index()+1); 281 DLIB_TEST_MSG(a.node(2).child_edge(0) == a.node(2).child(0).index()+1, 282 a.node(2).child_edge(0) << " " << a.node(2).child(0).index()+1); 283 DLIB_TEST_MSG(a.node(2).parent_edge(0) == 2+1, 284 a.node(2).parent_edge(0) << " " << 2+1); 285 DLIB_TEST_MSG(a.node(3).parent_edge(0) == 3+1, 286 a.node(3).parent_edge(0) << " " << 3+1); 287 DLIB_TEST_MSG(a.node(3).parent_edge(1) == 3+1, 288 a.node(3).parent_edge(1) << " " << 3+1); 289 290 291 292 for (int i = 0; i < 4; ++i) 293 { 294 DLIB_TEST(a.node(i).data == i); 295 DLIB_TEST(a.node(i).index() == (unsigned int)i); 296 } 297 298 299 DLIB_TEST(graph_contains_undirected_cycle(a) == false); 300 301 DLIB_TEST(b.number_of_nodes() == 4); 302 DLIB_TEST(b.node(0).number_of_parents() == 0); 303 DLIB_TEST(b.node(0).number_of_children() == 1); 304 305 DLIB_TEST(b.node(1).number_of_parents() == 0); 306 DLIB_TEST(b.node(1).number_of_children() == 1); 307 DLIB_TEST(b.node(1).child(0).index() == 3); 308 309 DLIB_TEST(b.node(2).number_of_parents() == 1); 310 DLIB_TEST(b.node(2).number_of_children() == 1); 311 DLIB_TEST(b.node(2).child(0).index() == 3); 312 DLIB_TEST(b.node(2).parent(0).index() == 0); 313 314 DLIB_TEST(b.node(3).number_of_parents() == 2); 315 DLIB_TEST(b.node(3).number_of_children() == 0); 316 317 318 DLIB_TEST(a.number_of_nodes() == 4); 319 DLIB_TEST(a.node(0).number_of_parents() == 0); 320 DLIB_TEST(a.node(0).number_of_children() == 1); 321 322 DLIB_TEST(a.node(1).number_of_parents() == 0); 323 DLIB_TEST(a.node(1).number_of_children() == 1); 324 DLIB_TEST(a.node(1).child(0).index() == 3); 325 326 DLIB_TEST(a.node(2).number_of_parents() == 1); 327 DLIB_TEST(a.node(2).number_of_children() == 1); 328 DLIB_TEST(a.node(2).child(0).index() == 3); 329 DLIB_TEST(a.node(2).parent(0).index() == 0); 330 331 DLIB_TEST(a.node(3).number_of_parents() == 2); 332 DLIB_TEST(a.node(3).number_of_children() == 0); 333 334 DLIB_TEST(a.number_of_nodes() == 4); 335 a.clear(); 336 DLIB_TEST(a.number_of_nodes() == 0); 337 338 339 DLIB_TEST(graph_contains_directed_cycle(a) == false); 340 341 a.set_number_of_nodes(10); 342 343 DLIB_TEST(graph_contains_directed_cycle(a) == false); 344 345 a.add_edge(0,1); 346 a.add_edge(1,2); 347 a.add_edge(1,3); 348 a.add_edge(2,4); 349 a.add_edge(3,4); 350 a.add_edge(4,5); 351 a.add_edge(5,1); 352 353 DLIB_TEST(graph_contains_directed_cycle(a) == true); 354 DLIB_TEST(graph_contains_undirected_cycle(a) == true); 355 356 a.remove_edge(5,1); 357 358 DLIB_TEST(graph_contains_undirected_cycle(a) == true); 359 DLIB_TEST(graph_contains_directed_cycle(a) == false); 360 a.add_edge(7,8); 361 DLIB_TEST(graph_contains_directed_cycle(a) == false); 362 a.add_edge(8,7); 363 DLIB_TEST(graph_contains_directed_cycle(a) == true); 364 DLIB_TEST(graph_contains_undirected_cycle(a) == true); 365 366 367 a.clear(); 368 /* 369 Make a graph that looks like: 370 0 1 371 \ / 372 2 373 | 374 3 375 */ 376 a.set_number_of_nodes(4); 377 a.add_edge(0,2); 378 a.add_edge(1,2); 379 a.add_edge(2,3); 380 for (unsigned long i = 0; i < 4; ++i) 381 a.node(i).data = i; 382 383 graph<int>::kernel_1a_c g; 384 create_moral_graph(a,g); 385 386 graph<dlib::set<unsigned long>::compare_1b_c, dlib::set<unsigned long>::compare_1a_c>::kernel_1a_c join_tree; 387 dlib::set<dlib::set<unsigned long>::compare_1b_c>::kernel_1b_c sos; 388 389 create_join_tree(g, join_tree); 390 DLIB_TEST(is_join_tree(g, join_tree)); 391 DLIB_TEST(join_tree.number_of_nodes() == 2); 392 DLIB_TEST(graph_contains_undirected_cycle(join_tree) == false); 393 DLIB_TEST(graph_is_connected(join_tree) == true); 394 395 unsigned long temp; 396 triangulate_graph_and_find_cliques(g,sos); 397 398 temp = 2; s.add(temp); 399 temp = 3; s.add(temp); 400 DLIB_TEST(sos.is_member(s)); 401 s.clear(); 402 temp = 0; s.add(temp); 403 temp = 1; s.add(temp); 404 temp = 2; s.add(temp); 405 DLIB_TEST(sos.is_member(s)); 406 DLIB_TEST(sos.size() == 2); 407 DLIB_TEST(sos.is_member(join_tree.node(0).data)); 408 DLIB_TEST(sos.is_member(join_tree.node(1).data)); 409 410 411 s.clear(); 412 temp = 0; s.add(temp); 413 DLIB_TEST(is_clique(g,s) == true); 414 DLIB_TEST(is_maximal_clique(g,s) == false); 415 temp = 3; s.add(temp); 416 DLIB_TEST(is_clique(g,s) == false); 417 s.destroy(3); 418 DLIB_TEST(is_clique(g,s) == true); 419 temp = 2; s.add(temp); 420 DLIB_TEST(is_clique(g,s) == true); 421 DLIB_TEST(is_maximal_clique(g,s) == false); 422 temp = 1; s.add(temp); 423 DLIB_TEST(is_clique(g,s) == true); 424 DLIB_TEST(is_maximal_clique(g,s) == true); 425 s.clear(); 426 DLIB_TEST(is_clique(g,s) == true); 427 temp = 3; s.add(temp); 428 DLIB_TEST(is_clique(g,s) == true); 429 temp = 2; s.add(temp); 430 DLIB_TEST(is_clique(g,s) == true); 431 DLIB_TEST(is_maximal_clique(g,s) == true); 432 433 434 DLIB_TEST(a.number_of_nodes() == 4); 435 DLIB_TEST(g.number_of_nodes() == 4); 436 for (unsigned long i = 0; i < 4; ++i) 437 DLIB_TEST( a.node(i).data == (int)i); 438 DLIB_TEST(g.has_edge(0,1)); 439 DLIB_TEST(g.has_edge(0,2)); 440 DLIB_TEST(g.has_edge(1,2)); 441 DLIB_TEST(g.has_edge(3,2)); 442 DLIB_TEST(g.has_edge(0,3) == false); 443 DLIB_TEST(g.has_edge(1,3) == false); 444 445 } 446 447 test_copy()448 void test_copy() 449 { 450 { 451 directed_graph<int,int>::kernel_1a_c a,b; 452 453 a.set_number_of_nodes(3); 454 a.node(0).data = 1; 455 a.node(1).data = 2; 456 a.node(2).data = 3; 457 a.add_edge(0,1); 458 a.add_edge(1,0); 459 a.add_edge(0,2); 460 edge(a,0,1) = 4; 461 edge(a,1,0) = 3; 462 edge(a,0,2) = 5; 463 464 a.add_edge(0,0); 465 edge(a,0,0) = 9; 466 copy_graph(a, b); 467 468 DLIB_TEST(b.number_of_nodes() == 3); 469 DLIB_TEST(b.node(0).data == 1); 470 DLIB_TEST(b.node(1).data == 2); 471 DLIB_TEST(b.node(2).data == 3); 472 DLIB_TEST(edge(b,0,1) == 4); 473 DLIB_TEST(edge(b,1,0) == 3); 474 DLIB_TEST(edge(b,0,2) == 5); 475 DLIB_TEST(edge(b,0,0) == 9); 476 } 477 { 478 directed_graph<int,int>::kernel_1a_c a,b; 479 480 a.set_number_of_nodes(4); 481 a.node(0).data = 1; 482 a.node(1).data = 2; 483 a.node(2).data = 3; 484 a.node(3).data = 8; 485 a.add_edge(0,1); 486 a.add_edge(0,2); 487 a.add_edge(2,3); 488 a.add_edge(3,2); 489 edge(a,0,1) = 4; 490 edge(a,0,2) = 5; 491 edge(a,2,3) = 6; 492 edge(a,3,2) = 3; 493 494 copy_graph(a, b); 495 496 DLIB_TEST(b.number_of_nodes() == 4); 497 DLIB_TEST(b.node(0).data == 1); 498 DLIB_TEST(b.node(1).data == 2); 499 DLIB_TEST(b.node(2).data == 3); 500 DLIB_TEST(b.node(3).data == 8); 501 DLIB_TEST(edge(b,0,1) == 4); 502 DLIB_TEST(edge(b,0,2) == 5); 503 DLIB_TEST(edge(b,2,3) == 6); 504 DLIB_TEST(edge(b,3,2) == 3); 505 } 506 } 507 508 509 510 class directed_graph_tester : public tester 511 { 512 /*! 513 WHAT THIS OBJECT REPRESENTS 514 This object represents a test for the directed_graph object. When it is constructed 515 it adds itself into the testing framework. The command line switch is 516 specified as test_directed_graph by passing that string to the tester constructor. 517 !*/ 518 public: directed_graph_tester()519 directed_graph_tester ( 520 ) : 521 tester ("test_directed_graph", 522 "Runs tests on the directed_graph component.") 523 {} 524 perform_test()525 void perform_test ( 526 ) 527 { 528 test_copy(); 529 530 dlog << LINFO << "testing kernel_1a_c"; 531 directed_graph_test<directed_graph<int,unsigned short>::kernel_1a_c>(); 532 533 dlog << LINFO << "testing kernel_1a"; 534 directed_graph_test<directed_graph<int,unsigned short>::kernel_1a>(); 535 } 536 } a; 537 538 539 } 540 541 542