OKlibrary  0.2.1.6
SubsumptionHypergraph.hpp
Go to the documentation of this file.
00001 // Matthew Gwynne, 29.7.2010 (Swansea)
00002 /* Copyright 2010, 2011 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 
00064 #ifndef SUBSUMPTION_HYPERGRAPH_yhgBBv567
00065 #define SUBSUMPTION_HYPERGRAPH_yhgBBv567
00066 
00067 #include <algorithm>
00068 #include <map>
00069 #include <vector>
00070 
00071 #include <boost/range.hpp>
00072 #include <boost/iterator/counting_iterator.hpp>
00073 
00074 
00075 namespace OKlib {
00076   namespace SetAlgorithms {
00077 
00078     // ############################################
00079 
00098     template <class RangeF,
00099         class RangeG,
00100               typename Int = typename boost::range_difference<RangeF>::type>
00101     class Subsumption_hypergraph {
00102 
00103     public :
00104 
00108       typedef Int vertex_type;
00111       typedef std::vector<vertex_type> hyperedge_type;
00115       typedef std::vector<hyperedge_type> set_system_type;
00116       
00121       const hyperedge_type vertex_set;
00125       const set_system_type hyperedges;
00126 
00127       Subsumption_hypergraph(const RangeF& f_range, 
00128                              const RangeG& g_range):
00129         vertex_set(fill_vertex_set(boost::distance(f_range))), 
00130         hyperedges(subsumption_hypergraph(f_range, g_range)) {}
00131 
00132     private:
00133 
00135       typedef typename boost::range_const_iterator<RangeF>::type f_iterator_type;
00137       typedef typename boost::range_const_iterator<RangeG>::type g_iterator_type;
00139       typedef typename boost::range_value<RangeF>::type f_value_type;
00141       typedef std::map<f_value_type, Int> hyperedge_map_type;
00144       typedef std::vector<f_value_type> hyperedge_nonstd_type;
00146       typedef typename boost::range_size<RangeF>::type f_size_type;
00147 
00150       static const hyperedge_type fill_vertex_set(const f_size_type size_f) {
00151         hyperedge_type vertex_set;
00152         const boost::counting_iterator<Int> v_begin(0);
00153         const boost::counting_iterator<Int> v_end(size_f);
00154         vertex_set.assign(v_begin, v_end);
00155         return(vertex_set);
00156       }
00157 
00161       static hyperedge_map_type fill_hyperedge_map(const RangeF& f_range) {
00162         hyperedge_map_type hyperedge_map;
00163         for(
00164             struct {
00165               f_iterator_type it;
00166               Int count;
00167               const f_iterator_type f_end;
00168             } l = {boost::begin(f_range), 0, boost::end(f_range)};
00169             l.it != l.f_end;
00170             ++l.it)
00171           hyperedge_map[*l.it] = ++l.count;
00172         return(hyperedge_map);
00173       }
00174 
00179       static
00180       hyperedge_type standardise_hyperedge(const hyperedge_nonstd_type& edge, 
00181                                            const hyperedge_map_type& hmap) {
00182         typedef typename boost::range_const_iterator<hyperedge_nonstd_type>::type
00183           hyperedge_nonstd_const_iterator_type;
00184 
00185         hyperedge_type new_edge;
00186         for(
00187             struct {
00188               hyperedge_nonstd_const_iterator_type it;
00189               const hyperedge_nonstd_const_iterator_type end;
00190             } l = {boost::begin(edge),boost::end(edge)};
00191             l.it != l.end; 
00192             ++l.it)
00193           new_edge.push_back(hmap.find(*l.it)->second);
00194         return(new_edge);
00195       }
00196 
00200       template <class RangeC>
00201       static
00202       hyperedge_nonstd_type all_subsuming(const RangeC c_range, 
00203                                           const RangeF& f_range) {
00204         hyperedge_nonstd_type subsumes_set;
00205         for (
00206              struct {
00207                f_iterator_type it;
00208                const f_iterator_type end;
00209              } f = { boost::begin(f_range), boost::end(f_range) };
00210              f.it != f.end; ++f.it) 
00211           if (std::includes(boost::begin(c_range), boost::end(c_range), 
00212                             boost::begin(*f.it),boost::end(*f.it)))
00213             subsumes_set.push_back(*f.it);
00214         return(subsumes_set);
00215       }
00216 
00219       static const set_system_type subsumption_hypergraph(const RangeF& f_range,
00220                                                           const RangeG& g_range) {
00221         set_system_type hyperedges;
00222         for (
00223              struct {
00224                g_iterator_type it;
00225                const g_iterator_type end;
00226                const hyperedge_map_type map;
00227              } g = {boost::begin(g_range), boost::end(g_range), 
00228                     fill_hyperedge_map(f_range)};
00229              g.it != g.end; ++g.it)
00230           hyperedges.push_back(standardise_hyperedge(all_subsuming(*g.it, f_range), g.map));
00231         return hyperedges;
00232       }
00233     };
00234 
00235 
00259     template<class RangeF, class RangeG>
00260     typename Subsumption_hypergraph<RangeF, RangeG>::set_system_type
00261     subsumption_hypergraph(const RangeF& f_range, const RangeG& g_range) {
00262       Subsumption_hypergraph<RangeF, RangeG> sub_hyp(f_range,g_range);
00263       return sub_hyp.hyperedges;
00264     }
00265 
00266   }
00267 }
00268 
00269 #endif