OKlibrary  0.2.1.6
VertexBranching.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 6.6.2009 (Swansea)
00002 /* Copyright 2009 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 
00016 #ifndef TRANSVERSALSBV_jsBgf4wY
00017 #define TRANSVERSALSBV_jsBgf4wY
00018 
00019 #include <list>
00020 #include <vector>
00021 #include <iterator>
00022 #include <cassert>
00023 #include <algorithm>
00024 #include <functional>
00025 #include <ostream>
00026 #include <iomanip>
00027 #include <set>
00028 
00029 #include <OKlib/Structures/Sets/SetAlgorithms/BasicSetOperations.hpp>
00030 
00031 namespace OKlib {
00032  namespace Combinatorics {
00033   namespace Hypergraphs {
00034    namespace Transversals {
00035     namespace Bounded {
00036 
00053       template <class SetSystem>
00054       struct Bounded_transversals_bv {
00055         
00056         typedef SetSystem set_system_type;
00057         typedef typename set_system_type::const_iterator const_iterator;
00058         typedef typename set_system_type::iterator iterator;
00059         typedef typename set_system_type::value_type hyperedge_type;
00060         typedef typename hyperedge_type::value_type vertex_type;
00061         typedef typename hyperedge_type::size_type size_type;
00062         
00063         typedef std::list<hyperedge_type> transversal_list_type;
00064         typedef typename transversal_list_type::const_iterator const_result_iterator;
00065         typedef typename transversal_list_type::iterator result_iterator;
00066         
00067         const set_system_type& G_orig;
00068         size_type bound;
00069         
00070         Bounded_transversals_bv(const set_system_type& G, const size_type B)
00071           : G_orig(G), bound(B) {}
00072         
00073         transversal_list_type operator() () const {
00074           return operator()(G_orig, bound);
00075         }
00076         transversal_list_type iterated() {
00077           transversal_list_type result(operator()(G_orig, bound));
00078           while (result.empty())
00079             result = operator()(G_orig, ++bound);
00080           return result;
00081         }
00082         
00083         transversal_list_type operator()
00084           (set_system_type G, const size_type B) const {
00085           transversal_list_type result;
00086           
00087           if (G.empty()) { result.push_back(hyperedge_type()); return result; }
00088           if (B == 0) return result;
00089           const hyperedge_type H(*G.begin());
00090           if (H.empty()) return result;
00091           if (B == 1) {
00092             typedef std::vector<vertex_type> vertex_list_t;
00093             vertex_list_t I;
00094             OKlib::SetAlgorithms::intersection_sets(G.begin(), G.end(), std::back_inserter(I));
00095             typedef typename vertex_list_t::const_iterator iterator_t;
00096             const iterator_t& end(I.end());
00097             for (iterator_t i = I.begin(); i != end; ++i) {
00098               hyperedge_type S; S.insert(*i);
00099               result.push_back(S);
00100             }
00101             return result;
00102           }
00103           
00104           const vertex_type a(*H.begin());
00105           if (H.size() == 1) {
00106             for (const_iterator i = G.begin(); i != G.end(); ) {
00107               const hyperedge_type& K(*i);
00108               const const_iterator j(i); ++i;
00109               if (K.find(a) != K.end()) G.erase(j);
00110             }
00111             result = operator()(G,B-1);
00112             const result_iterator& end(result.end());
00113             for (result_iterator i = result.begin(); i != end; ++i)
00114               i -> insert(a);
00115             return result;
00116           }
00117           else {
00118             set_system_type G_a;
00119             { const_iterator old_insert(G_a.begin());
00120               for (iterator i = G.begin(); i != G.end(); ) {
00121                 hyperedge_type K(*i);
00122                 const const_iterator j(i); ++i;
00123                 if (K.erase(a) != 0) {
00124                   old_insert = G_a.insert(old_insert,K);
00125                   G.erase(j);
00126                 }
00127               }
00128             }
00129             result = operator()(G,B-1);
00130             const result_iterator& end(result.end());
00131             for (result_iterator i = result.begin(); i != end; ++i)
00132               i -> insert(a);
00133             {
00134               const_iterator old_insert(G.begin());
00135               const const_iterator& end(G_a.end());
00136               for (const_iterator i = G_a.begin(); i != end; ++i)
00137                 old_insert = G.insert(old_insert, *i);
00138             }
00139             transversal_list_type temp_res(operator()(G, B));
00140             result.splice(result.end(), temp_res);
00141             return result;
00142           }
00143         }
00144         
00145       };
00146 
00147 
00153       template <class SetSystem>
00154       struct TransversalPredicate : std::unary_function<const typename SetSystem::value_type&, bool> {
00155         typedef SetSystem set_system_type;
00156         typedef typename set_system_type::value_type hyperedge_type;
00157         typedef typename set_system_type::const_iterator iterator;
00158         const set_system_type& G;
00159         const iterator begin;
00160         const iterator end;
00161         TransversalPredicate(const set_system_type& G)
00162           : G(G), begin(G.begin()), end(G.end()) {}
00163         bool operator() (const hyperedge_type& T) const {
00164           return std::find_if(begin, end, OKlib::SetAlgorithms::Disjoint<hyperedge_type>(T)) == end;
00165         }
00166       };
00167 
00168 
00182       template <class SetSystem,
00183                 template <class SetSystem> class Generator,
00184                 template <class SetSystem> class Output>
00185       struct Minimum_transversals_mongen {
00186                   
00187         typedef SetSystem set_system_type;
00188         
00189         typedef Bounded_transversals_bv<set_system_type> transversals_bv_type;
00190         typedef typename transversals_bv_type::const_iterator const_iterator;
00191         typedef typename transversals_bv_type::iterator iterator;
00192         typedef typename transversals_bv_type::hyperedge_type hyperedge_type;
00193         typedef typename transversals_bv_type::vertex_type vertex_type;
00194         typedef typename transversals_bv_type::size_type size_type;
00195         typedef typename transversals_bv_type::transversal_list_type transversal_list_type;
00196         typedef typename transversals_bv_type::const_result_iterator const_result_iterator;
00197         typedef typename transversals_bv_type::result_iterator result_iterator;
00198         
00199         typedef Generator<set_system_type> generator_type;
00200         typedef Output<set_system_type> output_type;
00201 
00202         typedef typename generator_type::hyperedge_list_type hyperedge_list_type;
00203 
00204         void operator() (
00205                          const size_type N0,
00206                          const size_type Nmax,
00207                          set_system_type G,
00208                          transversal_list_type MT0,
00209                          generator_type gen,
00210                          output_type out) const {
00211           if (N0 > Nmax) return;
00212           assert(not MT0.empty());
00213           size_type t = MT0.begin() -> size();
00214           for (size_type n = N0+1; n <= Nmax; ++n) {
00215             const hyperedge_list_type E(gen(n));
00216             const vertex_type a = n;
00217             hyperedge_list_type Er(E);
00218             { // removing vertex a from Er
00219               typedef typename hyperedge_list_type::iterator i_t;
00220               const i_t& end(Er.end());
00221               for (i_t i = Er.begin(); i != end; ++i)
00222                 i -> erase(a);
00223             }
00224             transversal_list_type MT1;
00225             { // MT1 = elements of MT0 which are transversals of E (or Er):
00226               TransversalPredicate<hyperedge_list_type> t_p(Er);
00227               const const_result_iterator end(MT0.end());
00228               for (const_result_iterator i = MT0.begin(); i != end; ++i)
00229                 if (t_p(*i)) MT1.push_back(*i);
00230             }
00231             if (MT1.empty()) {
00232               ++t;
00233               const result_iterator end(MT0.end());
00234               for (result_iterator i = MT0.begin(); i != end; ++i)
00235                 i -> insert(a);
00236               MT1.splice(MT1.end(), MT0);
00237               set_system_type Gr(G);
00238               Gr.insert(Er.begin(), Er.end());
00239               transversal_list_type temp_res(transversals_bv_type(Gr,t)());
00240               MT1.splice(MT1.end(), temp_res);
00241             }
00242             out(n,t,MT1);
00243             G.insert(E.begin(), E.end());
00244             MT0.swap(MT1);
00245           }
00246         }
00247 
00248         void operator() (
00249                          const size_type Nmax,
00250                          generator_type gen,
00251                          output_type out) const {
00252           operator()(0, Nmax, set_system_type(), transversal_list_type(1), gen, out);
00253         }
00254 
00255       };
00256 
00257 
00264       template <class SetSystem> struct TrivialOutput {
00265         typedef SetSystem set_system_type;
00266         typedef Bounded_transversals_bv<set_system_type> transversals_bv_type;
00267         typedef typename transversals_bv_type::size_type size_type;
00268         typedef typename transversals_bv_type::transversal_list_type transversal_list_type;
00269         std::ostream& out;
00270         TrivialOutput(std::ostream& out) : out(out) {}
00271         void operator() (const size_type n, const size_type t, const transversal_list_type& MT) {
00272           out << n << " " << t << " " << MT.size() << std::endl;
00273         }
00274       };
00275 
00276 
00308       template <class SetSystem, typename UInt = unsigned int>
00309       struct DirectStratification {
00310         typedef SetSystem set_system_type;
00311         typedef UInt uint_type;
00312         typedef typename set_system_type::value_type hyperedge_type;
00313         typedef typename hyperedge_type::value_type vertex_type;
00314 
00315         typedef std::set<uint_type> new_hyperedge_type;
00316         typedef std::vector<new_hyperedge_type> new_set_system_type;
00317         typedef std::vector<new_set_system_type> strata_type;
00318 
00319         typedef std::vector<uint_type> vertex_container;
00320         typedef typename vertex_container::const_iterator vertex_iterator;
00321         
00322         const vertex_container V; // the vertices
00323         const uint_type n; // number of vertices
00324         const vertex_iterator begin_V;
00325         const vertex_iterator end_V;
00326 
00327         DirectStratification(
00328             const set_system_type& S,
00329             const hyperedge_type& L)
00330           : V(L.begin(),L.end()), n(V.size()), begin_V(V.begin()), end_V(V.end()), St(n) {
00331           typedef typename set_system_type::const_iterator hyperedge_it;
00332           const hyperedge_it end_S(S.end());
00333           for (hyperedge_it H = S.begin(); H != end_S; ++H) {
00334             // TODO: use iterator-construction for the following transfer
00335             new_hyperedge_type N;
00336             typedef typename hyperedge_type::const_iterator vertex_it;
00337             const vertex_it end_H(H -> end());
00338             for (vertex_it v = H -> begin(); v != end_H; ++v)
00339               N.insert(index(*v));
00340             St[*--N.end()-1].push_back(N);
00341           }
00342         }
00343 
00344         uint_type index(const vertex_type v) const {
00345           assert(std::lower_bound(begin_V, end_V, v) != end_V);
00346           return (std::lower_bound(begin_V, end_V, v) - begin_V) + 1;
00347         }
00348 
00349         const new_set_system_type& operator()(const uint_type i) const {
00350           assert(i > 0);
00351           assert(i <= n);
00352           return St[i-1];
00353         }
00354 
00355         private :
00356 
00357           strata_type St;
00358       };
00359 
00360     }
00361    }
00362   }
00363  }
00364 }
00365 
00366 #endif