// Copyright (C) 2007 Davis E. King (davisking@users.sourceforge.net) // License: Boost Software License See LICENSE.txt for the full license. #include <sstream> #include <string> #include <cstdlib> #include <ctime> #include <dlib/directed_graph.h> #include <dlib/graph.h> #include <dlib/graph_utils.h> #include <dlib/set.h> #include "tester.h" // This is called an unnamed-namespace and it has the effect of making everything inside this file "private" // so that everything you declare will have static linkage. Thus we won't have any multiply // defined symbol errors coming out of the linker when we try to compile the test suite. namespace { using namespace test; using namespace dlib; using namespace std; // Declare the logger we will use in this test. The name of the tester // should start with "test." logger dlog("test.directed_graph"); template < typename directed_graph > void directed_graph_test ( ) /*! requires - directed_graph is an implementation of directed_graph/directed_graph_kernel_abstract.h is instantiated with int ensures - runs tests on directed_graph for compliance with the specs !*/ { print_spinner(); COMPILE_TIME_ASSERT(is_directed_graph<directed_graph>::value == true); directed_graph a, b; set<unsigned long>::compare_1b_c s; DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); DLIB_CASSERT(graph_contains_undirected_cycle(a) == false,""); DLIB_CASSERT(a.number_of_nodes() == 0,""); DLIB_CASSERT(graph_contains_length_one_cycle(a) == false,""); a.set_number_of_nodes(5); DLIB_CASSERT(graph_contains_length_one_cycle(a) == false,""); DLIB_CASSERT(graph_is_connected(a) == false,""); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); DLIB_CASSERT(graph_contains_undirected_cycle(a) == false,""); DLIB_CASSERT(a.number_of_nodes() == 5,""); for (int i = 0; i < 5; ++i) { a.node(i).data = i; DLIB_CASSERT(a.node(i).index() == (unsigned int)i,""); } a.remove_node(1); DLIB_CASSERT(a.number_of_nodes() == 4,""); // make sure that only the number with data == 1 was remove int count = 0; for (int i = 0; i < 4; ++i) { count += a.node(i).data; DLIB_CASSERT(a.node(i).number_of_children() == 0,""); DLIB_CASSERT(a.node(i).number_of_parents() == 0,""); DLIB_CASSERT(a.node(i).index() == (unsigned int)i,""); } DLIB_CASSERT(count == 9,""); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); a.add_edge(1,1); DLIB_CASSERT(graph_contains_length_one_cycle(a) == true,""); DLIB_CASSERT(graph_contains_undirected_cycle(a) == true,""); DLIB_CASSERT(graph_contains_directed_cycle(a) == true,""); a.add_edge(1,2); DLIB_CASSERT(graph_contains_directed_cycle(a) == true,""); DLIB_CASSERT(a.node(1).number_of_children() == 2,""); DLIB_CASSERT(a.node(1).number_of_parents() == 1,""); DLIB_CASSERT(a.node(1).parent(0).index() == 1,"") DLIB_CASSERT(a.node(1).child(0).index() + a.node(1).child(1).index() == 3,"") DLIB_CASSERT(a.node(2).number_of_children() == 0,""); DLIB_CASSERT(a.node(2).number_of_parents() == 1,""); DLIB_CASSERT(a.node(2).index() == 2,""); int val = a.node(1).data; a.remove_node(1); DLIB_CASSERT(graph_contains_length_one_cycle(a) == false,""); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); DLIB_CASSERT(graph_contains_undirected_cycle(a) == false,""); DLIB_CASSERT(a.number_of_nodes() == 3,""); count = 0; for (int i = 0; i < 3; ++i) { count += a.node(i).data; DLIB_CASSERT(a.node(i).number_of_children() == 0,""); DLIB_CASSERT(a.node(i).number_of_parents() == 0,""); DLIB_CASSERT(a.node(i).index() == (unsigned int)i,""); } DLIB_CASSERT(count == 9-val,""); val = a.add_node(); DLIB_CASSERT(val == 3,""); DLIB_CASSERT(a.number_of_nodes() == 4,""); for (int i = 0; i < 4; ++i) { a.node(i).data = i; DLIB_CASSERT(a.node(i).index() == (unsigned int)i,""); } for (int i = 0; i < 4; ++i) { DLIB_CASSERT(a.node(i).data == i,""); DLIB_CASSERT(a.node(i).index() == (unsigned int)i,""); } a.add_edge(0, 1); a.add_edge(0, 2); DLIB_CASSERT(graph_is_connected(a) == false,""); a.add_edge(1, 3); DLIB_CASSERT(graph_is_connected(a) == true,""); a.add_edge(2, 3); DLIB_CASSERT(graph_is_connected(a) == true,""); DLIB_CASSERT(graph_contains_length_one_cycle(a) == false,""); DLIB_CASSERT(a.has_edge(0, 1),""); DLIB_CASSERT(a.has_edge(0, 2),""); DLIB_CASSERT(a.has_edge(1, 3),""); DLIB_CASSERT(a.has_edge(2, 3),""); DLIB_CASSERT(!a.has_edge(1, 0),""); DLIB_CASSERT(!a.has_edge(2, 0),""); DLIB_CASSERT(!a.has_edge(3, 1),""); DLIB_CASSERT(!a.has_edge(3, 2),""); DLIB_CASSERT(a.node(0).number_of_parents() == 0,""); DLIB_CASSERT(a.node(0).number_of_children() == 2,""); DLIB_CASSERT(a.node(1).number_of_parents() == 1,""); DLIB_CASSERT(a.node(1).number_of_children() == 1,""); DLIB_CASSERT(a.node(1).child(0).index() == 3,""); DLIB_CASSERT(a.node(1).parent(0).index() == 0,""); DLIB_CASSERT(a.node(2).number_of_parents() == 1,""); DLIB_CASSERT(a.node(2).number_of_children() == 1,""); DLIB_CASSERT(a.node(2).child(0).index() == 3,""); DLIB_CASSERT(a.node(2).parent(0).index() == 0,""); DLIB_CASSERT(a.node(3).number_of_parents() == 2,""); DLIB_CASSERT(a.node(3).number_of_children() == 0,""); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); DLIB_CASSERT(graph_contains_undirected_cycle(a) == true,""); a.remove_edge(0,1); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); DLIB_CASSERT(!a.has_edge(0, 1),""); DLIB_CASSERT(a.has_edge(0, 2),""); DLIB_CASSERT(a.has_edge(1, 3),""); DLIB_CASSERT(a.has_edge(2, 3),""); DLIB_CASSERT(!a.has_edge(1, 0),""); DLIB_CASSERT(!a.has_edge(2, 0),""); DLIB_CASSERT(!a.has_edge(3, 1),""); DLIB_CASSERT(!a.has_edge(3, 2),""); DLIB_CASSERT(a.node(0).number_of_parents() == 0,""); DLIB_CASSERT(a.node(0).number_of_children() == 1,""); DLIB_CASSERT(a.node(1).number_of_parents() == 0,""); DLIB_CASSERT(a.node(1).number_of_children() == 1,""); DLIB_CASSERT(a.node(1).child(0).index() == 3,""); DLIB_CASSERT(a.node(2).number_of_parents() == 1,""); DLIB_CASSERT(a.node(2).number_of_children() == 1,""); DLIB_CASSERT(a.node(2).child(0).index() == 3,""); DLIB_CASSERT(a.node(2).parent(0).index() == 0,""); DLIB_CASSERT(a.node(3).number_of_parents() == 2,""); DLIB_CASSERT(a.node(3).number_of_children() == 0,""); for (int i = 0; i < 4; ++i) { DLIB_CASSERT(a.node(i).data == i,""); DLIB_CASSERT(a.node(i).index() == (unsigned int)i,""); } swap(a,b); DLIB_CASSERT(a.number_of_nodes() == 0, ""); DLIB_CASSERT(b.number_of_nodes() == 4, ""); DLIB_CASSERT(b.node(0).number_of_parents() == 0,""); DLIB_CASSERT(b.node(0).number_of_children() == 1,""); DLIB_CASSERT(b.node(1).number_of_parents() == 0,""); DLIB_CASSERT(b.node(1).number_of_children() == 1,""); DLIB_CASSERT(b.node(1).child(0).index() == 3,""); DLIB_CASSERT(b.node(2).number_of_parents() == 1,""); DLIB_CASSERT(b.node(2).number_of_children() == 1,""); DLIB_CASSERT(b.node(2).child(0).index() == 3,""); DLIB_CASSERT(b.node(2).parent(0).index() == 0,""); DLIB_CASSERT(b.node(3).number_of_parents() == 2,""); DLIB_CASSERT(b.node(3).number_of_children() == 0,""); b.node(0).child_edge(0) = static_cast<unsigned short>(b.node(0).child(0).index()+1); b.node(1).child_edge(0) = static_cast<unsigned short>(b.node(1).child(0).index()+1); b.node(2).child_edge(0) = static_cast<unsigned short>(b.node(2).child(0).index()+1); DLIB_CASSERT(b.node(0).child_edge(0) == b.node(0).child(0).index()+1, b.node(0).child_edge(0) << " " << b.node(0).child(0).index()+1); DLIB_CASSERT(b.node(1).child_edge(0) == b.node(1).child(0).index()+1, b.node(1).child_edge(0) << " " << b.node(1).child(0).index()+1); DLIB_CASSERT(b.node(2).child_edge(0) == b.node(2).child(0).index()+1, b.node(2).child_edge(0) << " " << b.node(2).child(0).index()+1); DLIB_CASSERT(b.node(2).parent_edge(0) == 2+1, b.node(2).parent_edge(0) << " " << 2+1); DLIB_CASSERT(b.node(3).parent_edge(0) == 3+1, b.node(3).parent_edge(0) << " " << 3+1); DLIB_CASSERT(b.node(3).parent_edge(1) == 3+1, b.node(3).parent_edge(1) << " " << 3+1); ostringstream sout; serialize(b, sout); istringstream sin(sout.str()); a.set_number_of_nodes(20); DLIB_CASSERT(a.number_of_nodes() == 20,""); deserialize(a, sin); DLIB_CASSERT(a.number_of_nodes() == 4,""); DLIB_CASSERT(!a.has_edge(0, 1),""); DLIB_CASSERT(a.has_edge(0, 2),""); DLIB_CASSERT(a.has_edge(1, 3),""); DLIB_CASSERT(a.has_edge(2, 3),""); DLIB_CASSERT(!a.has_edge(1, 0),""); DLIB_CASSERT(!a.has_edge(2, 0),""); DLIB_CASSERT(!a.has_edge(3, 1),""); DLIB_CASSERT(!a.has_edge(3, 2),""); DLIB_CASSERT(a.node(0).child_edge(0) == a.node(0).child(0).index()+1, a.node(0).child_edge(0) << " " << a.node(0).child(0).index()+1); DLIB_CASSERT(a.node(1).child_edge(0) == a.node(1).child(0).index()+1, a.node(1).child_edge(0) << " " << a.node(1).child(0).index()+1); DLIB_CASSERT(a.node(2).child_edge(0) == a.node(2).child(0).index()+1, a.node(2).child_edge(0) << " " << a.node(2).child(0).index()+1); DLIB_CASSERT(a.node(2).parent_edge(0) == 2+1, a.node(2).parent_edge(0) << " " << 2+1); DLIB_CASSERT(a.node(3).parent_edge(0) == 3+1, a.node(3).parent_edge(0) << " " << 3+1); DLIB_CASSERT(a.node(3).parent_edge(1) == 3+1, a.node(3).parent_edge(1) << " " << 3+1); for (int i = 0; i < 4; ++i) { DLIB_CASSERT(a.node(i).data == i,""); DLIB_CASSERT(a.node(i).index() == (unsigned int)i,""); } DLIB_CASSERT(graph_contains_undirected_cycle(a) == false,""); DLIB_CASSERT(b.number_of_nodes() == 4, ""); DLIB_CASSERT(b.node(0).number_of_parents() == 0,""); DLIB_CASSERT(b.node(0).number_of_children() == 1,""); DLIB_CASSERT(b.node(1).number_of_parents() == 0,""); DLIB_CASSERT(b.node(1).number_of_children() == 1,""); DLIB_CASSERT(b.node(1).child(0).index() == 3,""); DLIB_CASSERT(b.node(2).number_of_parents() == 1,""); DLIB_CASSERT(b.node(2).number_of_children() == 1,""); DLIB_CASSERT(b.node(2).child(0).index() == 3,""); DLIB_CASSERT(b.node(2).parent(0).index() == 0,""); DLIB_CASSERT(b.node(3).number_of_parents() == 2,""); DLIB_CASSERT(b.node(3).number_of_children() == 0,""); DLIB_CASSERT(a.number_of_nodes() == 4, ""); DLIB_CASSERT(a.node(0).number_of_parents() == 0,""); DLIB_CASSERT(a.node(0).number_of_children() == 1,""); DLIB_CASSERT(a.node(1).number_of_parents() == 0,""); DLIB_CASSERT(a.node(1).number_of_children() == 1,""); DLIB_CASSERT(a.node(1).child(0).index() == 3,""); DLIB_CASSERT(a.node(2).number_of_parents() == 1,""); DLIB_CASSERT(a.node(2).number_of_children() == 1,""); DLIB_CASSERT(a.node(2).child(0).index() == 3,""); DLIB_CASSERT(a.node(2).parent(0).index() == 0,""); DLIB_CASSERT(a.node(3).number_of_parents() == 2,""); DLIB_CASSERT(a.node(3).number_of_children() == 0,""); DLIB_CASSERT(a.number_of_nodes() == 4, ""); a.clear(); DLIB_CASSERT(a.number_of_nodes() == 0, ""); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); a.set_number_of_nodes(10); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); a.add_edge(0,1); a.add_edge(1,2); a.add_edge(1,3); a.add_edge(2,4); a.add_edge(3,4); a.add_edge(4,5); a.add_edge(5,1); DLIB_CASSERT(graph_contains_directed_cycle(a) == true,""); DLIB_CASSERT(graph_contains_undirected_cycle(a) == true,""); a.remove_edge(5,1); DLIB_CASSERT(graph_contains_undirected_cycle(a) == true,""); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); a.add_edge(7,8); DLIB_CASSERT(graph_contains_directed_cycle(a) == false,""); a.add_edge(8,7); DLIB_CASSERT(graph_contains_directed_cycle(a) == true,""); DLIB_CASSERT(graph_contains_undirected_cycle(a) == true,""); a.clear(); /* Make a graph that looks like: 0 1 \ / 2 | 3 */ a.set_number_of_nodes(4); a.add_edge(0,2); a.add_edge(1,2); a.add_edge(2,3); for (unsigned long i = 0; i < 4; ++i) a.node(i).data = i; graph<int>::kernel_1a_c g; create_moral_graph(a,g); graph<set<unsigned long>::compare_1b_c, set<unsigned long>::compare_1a_c>::kernel_1a_c join_tree; set<set<unsigned long>::compare_1b_c>::kernel_1b_c sos; create_join_tree(g, join_tree); DLIB_CASSERT(is_join_tree(g, join_tree),""); DLIB_CASSERT(join_tree.number_of_nodes() == 2,""); DLIB_CASSERT(graph_contains_undirected_cycle(join_tree) == false,""); DLIB_CASSERT(graph_is_connected(join_tree) == true,""); unsigned long temp; triangulate_graph_and_find_cliques(g,sos); temp = 2; s.add(temp); temp = 3; s.add(temp); DLIB_CASSERT(sos.is_member(s),""); s.clear(); temp = 0; s.add(temp); temp = 1; s.add(temp); temp = 2; s.add(temp); DLIB_CASSERT(sos.is_member(s),""); DLIB_CASSERT(sos.size() == 2,""); DLIB_CASSERT(sos.is_member(join_tree.node(0).data), ""); DLIB_CASSERT(sos.is_member(join_tree.node(1).data), ""); s.clear(); temp = 0; s.add(temp); DLIB_CASSERT(is_clique(g,s) == true,""); DLIB_CASSERT(is_maximal_clique(g,s) == false,""); temp = 3; s.add(temp); DLIB_CASSERT(is_clique(g,s) == false,""); s.destroy(3); DLIB_CASSERT(is_clique(g,s) == true,""); temp = 2; s.add(temp); DLIB_CASSERT(is_clique(g,s) == true,""); DLIB_CASSERT(is_maximal_clique(g,s) == false,""); temp = 1; s.add(temp); DLIB_CASSERT(is_clique(g,s) == true,""); DLIB_CASSERT(is_maximal_clique(g,s) == true,""); s.clear(); DLIB_CASSERT(is_clique(g,s) == true,""); temp = 3; s.add(temp); DLIB_CASSERT(is_clique(g,s) == true,""); temp = 2; s.add(temp); DLIB_CASSERT(is_clique(g,s) == true,""); DLIB_CASSERT(is_maximal_clique(g,s) == true,""); DLIB_CASSERT(a.number_of_nodes() == 4,""); DLIB_CASSERT(g.number_of_nodes() == 4,""); for (unsigned long i = 0; i < 4; ++i) DLIB_CASSERT( a.node(i).data == (int)i,""); DLIB_CASSERT(g.has_edge(0,1),""); DLIB_CASSERT(g.has_edge(0,2),""); DLIB_CASSERT(g.has_edge(1,2),""); DLIB_CASSERT(g.has_edge(3,2),""); DLIB_CASSERT(g.has_edge(0,3) == false,""); DLIB_CASSERT(g.has_edge(1,3) == false,""); } class directed_graph_tester : public tester { /*! WHAT THIS OBJECT REPRESENTS This object represents a test for the directed_graph object. When it is constructed it adds itself into the testing framework. The command line switch is specified as test_directed_graph by passing that string to the tester constructor. !*/ public: directed_graph_tester ( ) : tester ("test_directed_graph", "Runs tests on the directed_graph component.") {} void perform_test ( ) { dlog << LINFO << "testing kernel_1a_c"; directed_graph_test<directed_graph<int,unsigned short>::kernel_1a_c>(); dlog << LINFO << "testing kernel_1a"; directed_graph_test<directed_graph<int,unsigned short>::kernel_1a>(); } } a; }