OKlibrary  0.2.1.6
EliminationSequences.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 ELIMINATIONSEQUENCES_hhgrrEw34
00016 #define ELIMINATIONSEQUENCES_hhgrrEw34
00017 
00018 #include <cassert>
00019 #include <utility>
00020 #include <functional>
00021 #include <vector>
00022 #include <algorithm>
00023 
00024 #include <boost/range/value_type.hpp>
00025 #include <boost/range/const_iterator.hpp>
00026 #include <boost/range/empty.hpp>
00027 #include <boost/range/begin.hpp>
00028 #include <boost/range/end.hpp>
00029 #include <boost/utility.hpp>
00030 #include <boost/static_assert.hpp>
00031 #include <boost/graph/graph_traits.hpp>
00032 #include <boost/graph/graph_concepts.hpp>
00033 #include <boost/iterator/counting_iterator.hpp>
00034 #include <boost/iterator/transform_iterator.hpp>
00035 #include <boost/range/iterator_range.hpp>
00036 
00037 namespace OKlib {
00038   namespace GraphDecomposition {
00039 
00064     template <class EliminationSequence, class Graph>
00065     class Width_elimination_sequence : public std::binary_function<const EliminationSequence&, Graph&, typename boost::graph_traits<Graph>::degree_size_type> {
00066 
00067       typedef boost::graph_traits<Graph> graph_traits_type;
00068 
00069       BOOST_CLASS_REQUIRE(Graph, boost, AdjacencyGraphConcept);
00070       BOOST_CLASS_REQUIRE(Graph, boost, MutableGraphConcept);
00071 
00072       BOOST_STATIC_ASSERT((boost::is_convertible<typename graph_traits_type::directed_category, boost::undirected_tag>::value));
00073       BOOST_STATIC_ASSERT((boost::is_convertible<typename graph_traits_type::edge_parallel_category, boost::disallow_parallel_edge_tag>::value));
00074       BOOST_STATIC_ASSERT((boost::is_convertible<typename boost::range_value<EliminationSequence>::type, typename graph_traits_type::vertex_descriptor>::value));
00075 
00076     public :
00077 
00078       typedef EliminationSequence elimination_sequence_type;
00079       typedef Graph graph_type;
00080 
00081     private :
00082 
00083       typedef typename graph_traits_type::vertex_descriptor vertex_descriptor_type;
00084       typedef typename graph_traits_type::adjacency_iterator adjacency_iterator_type;
00085       typedef typename graph_traits_type::degree_size_type degree_size_type;
00086 
00087     public :
00088 
00089       degree_size_type operator() (const elimination_sequence_type& elim, graph_type& g) const {
00090         assert(not boost::empty(elim));
00091         degree_size_type width = 0;
00092         typedef typename boost::range_const_iterator<elimination_sequence_type>::type container_iterator_t;
00093         const container_iterator_t& end_elim(boost::end(elim));
00094         for (container_iterator_t v_it(boost::begin(elim)); v_it != end_elim; ++v_it) {
00095           const vertex_descriptor_type& v(*v_it);
00096           const std::pair<adjacency_iterator_type, adjacency_iterator_type>& neighbours(adjacent_vertices(v, g));
00097           degree_size_type deg = 0;
00098           for (adjacency_iterator_type i(boost::begin(neighbours)); i != boost::end(neighbours); ++i, ++deg) {
00099             assert(*i != v);
00100             for (adjacency_iterator_type j(boost::next(i)); j != boost::end(neighbours); ++j)
00101               add_edge(*i, *j, g);
00102           }
00103           assert(deg == degree(v, g));
00104           if (deg > width)
00105             width = deg;
00106           clear_vertex(v, g);
00107           remove_vertex(v, g);
00108         }
00109         return width;
00110       }
00111     };
00112 
00113     // ##################################################
00114 
00115     template <class Graph>
00116     struct Treewidth_by_enumerating_elimination_sequences : public std::unary_function<const Graph&, typename boost::graph_traits<Graph>::vertices_size_type> {
00117 
00118       typedef boost::graph_traits<Graph> graph_traits_type;
00119 
00120       BOOST_CLASS_REQUIRE(Graph, boost, AdjacencyGraphConcept);
00121       BOOST_CLASS_REQUIRE(Graph, boost, VertexListGraphConcept);
00122       BOOST_CLASS_REQUIRE(Graph, boost, MutableGraphConcept);
00123 
00124       BOOST_STATIC_ASSERT((boost::is_convertible<typename graph_traits_type::directed_category, boost::undirected_tag>::value));
00125       BOOST_STATIC_ASSERT((boost::is_convertible<typename graph_traits_type::edge_parallel_category, boost::disallow_parallel_edge_tag>::value));
00126 
00127     public :
00128 
00129       typedef Graph graph_type;
00130 
00131     private :
00132 
00133       typedef typename graph_traits_type::vertex_descriptor vertex_descriptor_type;
00134       typedef typename graph_traits_type::vertex_iterator vertex_iterator_type;
00135       typedef typename graph_traits_type::vertices_size_type vertices_size_type;
00136 
00137       template <class Container, typename Index>
00138       class DeIndex : public std::unary_function<typename Container::value_type, Index> {
00139         const Container& container;
00140       public :
00141         DeIndex(const Container& container) : container(container) {}
00142         Index operator() (Index i) const {
00143           return container[i];
00144         }
00145       };
00146 
00147     public :
00148 
00149       vertices_size_type operator() (const graph_type& g) const {
00150         const std::pair<vertex_iterator_type, vertex_iterator_type>& vertex_range(vertices(g));
00151         assert(not boost::empty(vertex_range));
00152         typedef std::vector<vertex_descriptor_type> vertex_vector_type;
00153         vertex_vector_type vertex_vector(boost::begin(vertex_range), boost::end(vertex_range)); // inefficient, but unavoidable, since no index concept(!)
00154         typedef typename vertex_vector_type::size_type index_type;
00155         typedef std::vector<index_type> index_vector_type;
00156         const index_type& num_vertices(vertex_vector.size());
00157         assert(num_vertices >= 1);
00158         index_vector_type index_vector(boost::counting_iterator<index_type>(0), boost::counting_iterator<index_type>(num_vertices));
00159         typedef typename index_vector_type::const_iterator index_iterator_type;
00160         const index_iterator_type& begin_index_vector(index_vector.begin());
00161         const index_iterator_type& end_index_vector(index_vector.end());
00162 
00163         vertices_size_type treewidth = num_vertices - 1;
00164         do {
00165           typedef DeIndex<vertex_vector_type,  index_type> de_index_type;
00166           typedef boost::transform_iterator<de_index_type, index_iterator_type> transform_iterator_type;
00167           typedef boost::iterator_range<transform_iterator_type> elimination_sequence_type;
00168           graph_type g_copy(g);
00169           const vertices_size_type& new_width(Width_elimination_sequence<elimination_sequence_type, graph_type>()(elimination_sequence_type(transform_iterator_type(begin_index_vector, de_index_type(vertex_vector)), transform_iterator_type(end_index_vector, de_index_type(vertex_vector))), g_copy));
00170           if (new_width < treewidth)
00171             treewidth = new_width;
00172         } while (std::next_permutation(index_vector.begin(), index_vector.end()));
00173         return treewidth;
00174       }
00175     };
00176 
00177   }
00178 }
00179 
00180 #endif