OKlibrary  0.2.1.6
EliminationSequences_Tests.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 10.1.2006 (Swansea)
00002 /* Copyright 2006 - 2007 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00015 #ifndef ELIMINATIONSEQUENCESTESTS_8uyTre
00016 #define ELIMINATIONSEQUENCESTESTS_8uyTre
00017 
00018 #include <vector>
00019 #include <cassert>
00020 
00021 #include <OKlib/TestSystem/TestBaseClass.hpp>
00022 #include <OKlib/TestSystem/TestExceptions.hpp>
00023 
00024 namespace OKlib {
00025   namespace GraphDecomposition {
00026 
00027     template <template <class EliminationSequence, class Graph> class Width_elimination_sequence, class Graph>
00028     class Test_Width_elimination_sequence : public ::OKlib::TestSystem::TestBase {
00029     public :
00030       typedef Test_Width_elimination_sequence test_type;
00031       Test_Width_elimination_sequence() {
00032         insert(this);
00033       }
00034     private :
00035       typedef Graph graph_type;
00036       void perform_test_trivial() {
00037         {
00038           typedef boost::graph_traits<graph_type> graph_traits_type;
00039           typedef typename graph_traits_type::vertex_descriptor vertex_descriptor_type;
00040           typedef std::vector<vertex_descriptor_type> vector_type;
00041           typedef Width_elimination_sequence<vector_type, graph_type> width_elimination_sequence_type;
00042 
00043           {
00044             graph_type g;
00045             vector_type vec;
00046             width_elimination_sequence_type width;
00047             const vertex_descriptor_type v1 = add_vertex(g);
00048             vec.push_back(v1);
00049             OKLIB_TEST_EQUAL(width(vec, g), 0U);
00050           }
00051           {
00052             graph_type g;
00053             vector_type vec;
00054             width_elimination_sequence_type width;
00055             const vertex_descriptor_type v1 = add_vertex(g);
00056             const vertex_descriptor_type v2 = add_vertex(g);
00057             add_edge(v1, v2, g);
00058             vec.push_back(v1); vec.push_back(v2);
00059             OKLIB_TEST_EQUAL(width(vec, g), 1U);
00060           }
00061           {
00062             graph_type g;
00063             vector_type vec;
00064             width_elimination_sequence_type width;
00065             const unsigned int path_size = 20;
00066             vec.reserve(path_size);
00067             assert(path_size >= 1);
00068             for (unsigned int i = 0; i < path_size; ++i)
00069               vec.push_back(add_vertex(g));
00070             for (unsigned int i = 0; i < path_size-1; ++i)
00071               add_edge(vec[i], vec[i+1], g);
00072             OKLIB_TEST_EQUAL(width(vec, g), 1U);
00073           }
00074           {
00075             graph_type g;
00076             vector_type vec;
00077             width_elimination_sequence_type width;
00078             const unsigned int cycle_length = 20;
00079             vec.reserve(cycle_length);
00080             assert(cycle_length >= 1);
00081             for (unsigned int i = 0; i < cycle_length; ++i)
00082               vec.push_back(add_vertex(g));
00083             for (unsigned int i = 0; i < cycle_length-1; ++i)
00084               add_edge(vec[i], vec[i+1], g);
00085             add_edge(vec[cycle_length-1], vec[0], g);
00086             OKLIB_TEST_EQUAL(width(vec, g), 2U);
00087           }
00088           {
00089             graph_type g;
00090             vector_type vec;
00091             width_elimination_sequence_type width;
00092             const unsigned int clique_size = 20;
00093             vec.reserve(clique_size);
00094             assert(clique_size >= 1);
00095             for (unsigned int i = 0; i < clique_size; ++i)
00096               vec.push_back(add_vertex(g));
00097             for (unsigned int i = 0; i < clique_size; ++i)
00098               for (unsigned int j = i+1; j < clique_size; ++j)
00099                 add_edge(vec[i], vec[j], g);
00100             OKLIB_TEST_EQUAL(width(vec, g), clique_size - 1);
00101           }
00102         }
00103       }
00104 
00105     };
00106   
00107   }
00108 
00109 }
00110 
00111 #endif