OKlibrary  0.2.1.6
VanderWaerden.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 15.5.2005 (Swansea)
00002 /* Copyright 2005 - 2007, 2009, 2010 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 
00013 #ifndef VANDERWAERDENHYPERGRAPH_77bQMQM_5993KKl
00014 #define VANDERWAERDENHYPERGRAPH_77bQMQM_5993KKl
00015 
00016 #include <iterator>
00017 #include <cassert>
00018 #include <cstdlib>
00019 #include <vector>
00020 #include <algorithm>
00021 #include <functional>
00022 #include <list>
00023 
00024 #include <OKlib/Concepts/Iterators.hpp>
00025 #include <OKlib/Programming/Utilities/OrderRelations/OrderConstructions.hpp>
00026 #include <OKlib/Structures/Sets/SetAlgorithms/Subsumption.hpp>
00027 
00028 namespace OKlib {
00029  namespace Combinatorics {
00030   namespace Hypergraphs {
00031    namespace Generators {
00032   
00039      template <typename Integer>
00040      class Iterator_arithmetic_progression : public std::iterator<std::input_iterator_tag, Integer> {
00041        Integer current_value;
00042       Integer slope;
00043     public :
00044       typedef ::OKlib::Concepts::MultiPassInputIterator_tag concept_tag;
00045       Iterator_arithmetic_progression(const Integer start_value, const Integer slope) : current_value(start_value), slope(slope) {}
00046       Integer operator* () const { return current_value; }
00047       Iterator_arithmetic_progression& operator ++() {
00048         current_value += slope;
00049         return *this;
00050       }
00051       Iterator_arithmetic_progression operator ++(int) {
00052         Iterator_arithmetic_progression i(*this);
00053         operator ++();
00054         return i;
00055       }
00056     };
00057     
00058     template <typename Integer>
00059     inline bool operator ==(const Iterator_arithmetic_progression<Integer>& lhs, const Iterator_arithmetic_progression<Integer>& rhs) {
00060       return *lhs == *rhs;
00061     }
00062     template <typename Integer>
00063     inline bool operator !=(const Iterator_arithmetic_progression<Integer>& lhs, const Iterator_arithmetic_progression<Integer>& rhs) {
00064       return not (lhs == rhs);
00065     }
00066     
00067     // -----------------------------------------------------------
00068     
00080     template <typename Integer>
00081     class Arithmetic_progression {
00082       Integer start_, length, slope_;
00083       Integer finish;
00084     public :
00085       Arithmetic_progression(const Integer start, const Integer length, const Integer slope) : start_(start), length(length), slope_(slope), finish(start_ + length * slope_) {
00086         assert(length >= 0);
00087       }
00088       typedef Integer value_type;
00089       typedef Integer size_type;
00090       size_type size() const { return length; }
00091       typedef Iterator_arithmetic_progression<Integer> iterator;
00092       typedef iterator const_iterator;
00093       iterator begin() const { return iterator(start_, slope_); }
00094       iterator end() const { return iterator(finish, 0); }
00095         friend bool operator ==(const Arithmetic_progression& lhs, const Arithmetic_progression& rhs) {
00096         return lhs.start == rhs.start and lhs.length == rhs.length and lhs.slope == rhs.slope;
00097       }
00098       value_type start() const { return start_; }
00099       value_type slope() const { return slope_; }
00100     };
00101     
00102     // -----------------------------------------------------------
00103   
00140     template <class Hyperedges, class SetSystem, typename Int = unsigned int>
00141     struct Arithprog_finish {
00142   
00143       typedef Int int_type;
00144       typedef Arithmetic_progression<int_type> progression_type;
00145       typedef Hyperedges hyperedge_type;
00146       typedef SetSystem set_system_type;
00147       typedef typename hyperedge_type::value_type vertex_type;
00148   
00149       int_type k; // length of arithmetic progression
00150   
00151       Arithprog_finish() : k(0) {}
00152       Arithprog_finish(const int_type k) : k(k) {
00153         assert(k >= 1);
00154       }
00155       void set(const int_type k_new) {
00156         assert(k_new >= 1);
00157         k = k_new;
00158       }
00159   
00160       set_system_type operator()(const int_type n) const {
00161         assert(k >= 1);
00162         assert(n >= 1);
00163         typedef std::vector<vertex_type> vector_t;
00164         vector_t H;
00165         H.reserve(k);
00166         typedef std::vector<hyperedge_type> vector2_t;
00167         vector2_t S;
00168         if (k == 1) {
00169           H.push_back(n);
00170           S.push_back(hyperedge_type(H.begin(), H.end()));
00171           return set_system_type(S.begin(),S.end());
00172         }
00173         typedef long int lib_int_type;
00174         const int_type q = std::ldiv(lib_int_type(n-1), lib_int_type(k-1)).quot;
00175         S.reserve(q);
00176         for (int_type d = 1; d <= q; ++d) {
00177           const progression_type P(n - (k-1) * d, k, d);
00178           H.assign(P.begin(), P.end());
00179           assert(P.size() == k);
00180           S.push_back(hyperedge_type(H.begin(), H.end()));
00181         }
00182         assert(S.size() == q);
00183         return set_system_type(S.begin(),S.end());
00184       }
00185     };
00186   
00187     // -----------------------------------------------------------
00188 
00196    template <typename UInt>
00197    inline UInt nhyp_arithprog_hg(const UInt k, const UInt n) {
00198      if (k == 0) return 1;
00199      if (k == 1) return n;
00200      if (n < k) return 0;
00201      const UInt q = (n-1) / (k-1);
00202      return q*n - (q*(k - 1)*(q + 1)) / 2;
00203    }
00204 
00231     template <typename Int>
00232     class Arithmetical_progressions {
00233     public :
00234       typedef Int Index;
00235       const Index n;
00237       const Index k;
00239       const Index count;
00240 
00241     private :
00243       Index current_element;
00245       Index current_distance;
00246 
00247     public :
00248 
00249       Arithmetical_progressions(const Index k, const Index n) :
00250           n(n), k(k),
00251           count(nhyp_arithprog_hg(k,n)),
00252           current_element(1),
00253           current_distance(1) {
00254         assert(k >= 1);
00255         assert(n >= 2);
00256         assert(n >= k);
00257       }
00258       std::string static message() {
00259         return "Iterating through the arithmetic progressions in lexicographical order.";
00260       }
00261 
00262       typedef std::vector<Index> Arithmetical_progression;
00263 
00264       Arithmetical_progression next() {
00265         Arithmetical_progression ap;
00266         ap.reserve(k);
00267         for (Index i = 0; i < k; ++i)
00268     ap.push_back(current_element + i * current_distance);
00269         if (current_element + (k-1) * (current_distance + 1) <= n and k >= 2)
00270     ++current_distance;
00271         else {
00272     ++current_element; current_distance = 1;
00273         }
00274         return ap;
00275       }
00276     };
00277 
00278 
00307     template <typename Int>
00308     class Arithmetical_progressions_colex {
00309     public :
00310       typedef Int Index;
00311       const Index n;
00313       const Index k;
00315       const Index count;
00316 
00317     private :
00319       Index current_element;
00321       Index current_distance;
00322 
00323     public :
00324 
00325       Arithmetical_progressions_colex(const Index k, const Index n) :
00326           n(n), k(k),
00327           count(nhyp_arithprog_hg(k,n)),
00328           current_element(k),
00329           current_distance(1) {
00330         assert(k >= 2);
00331         assert(n >= 2);
00332         assert(n >= k);
00333       }
00334       std::string static message() {
00335         return "Iterating through the arithmetic progressions in colexicographical order.";
00336       }
00337 
00338       typedef std::vector<Index> Arithmetical_progression;
00339 
00340       Arithmetical_progression next() {
00341         Arithmetical_progression ap;
00342         ap.reserve(k);
00343         const Index first_element = current_element - (k-1) * current_distance;
00344         for (Index i = 0; i < k; ++i)
00345     ap.push_back(first_element + i * current_distance);
00346         if (current_distance > 1) --current_distance;
00347         else
00348           current_distance = current_element++ / (k-1);
00349         return ap;
00350       }
00351     };
00352 
00353     // -----------------------------------------------------------
00354 
00395     template <typename Int>
00396     class Pd_arithmetical_progressions {
00397     public :
00398       typedef Int Index;
00399       const Index n;
00401       const Index k;
00403       const Index mp;
00404 
00405     private :
00406       typedef Arithmetical_progressions<Index> AP;
00408       AP ap_;
00409 
00410     public :
00412       const Index count;
00413 
00414     public :
00415 
00416       Pd_arithmetical_progressions(const Index k, const Index n) :
00417           n(n), k(k), mp((n+1)/2),
00418           ap_(k,n),
00419           count(ap_.count - nhyp_arithprog_hg(k,n-mp)) {
00420         assert(k >= 1);
00421         assert(n >= 2);
00422         assert(n >= k);
00423       }
00424       static std::string message() {
00425         return "Iterating through the palindromised arithmetic progressions in lexicographical order.";
00426       }
00427 
00428       Index mirror_image(const Index v) {
00429         assert(1 <= v);
00430         assert(v <= n);
00431         return n-v+1;
00432       }
00433       typedef typename AP::Arithmetical_progression sequence_type;
00434       sequence_type next() {
00435         sequence_type ap(ap_.next());
00436         {typedef typename sequence_type::iterator iterator;
00437          const iterator begin(ap.begin()), end(ap.end());
00438          for (iterator i = begin; i != end; ++i)
00439            if (*i > mp) *i = mirror_image(*i);
00440          std::sort(begin, end);
00441          ap.resize(std::unique(begin, end) - begin);
00442         }
00443         return ap;
00444       }
00445 
00446     };
00447 
00464     template <typename Int = unsigned int>
00465     class Pd_arithprog_ohg {
00466     public :
00467       typedef Int vertex_type;
00468     private :
00469       typedef Pd_arithmetical_progressions<vertex_type> Pd_ap;
00470     public :
00471       typedef typename Pd_ap::sequence_type hyperedge_type;
00472       typedef std::vector<hyperedge_type> set_system_type;
00473       typedef typename set_system_type::size_type size_type;
00474 
00475       set_system_type operator()(const vertex_type k, const vertex_type n) const {
00476         Pd_ap ap(k,n);
00477         set_system_type g;
00478         g.reserve(ap.count);
00479         for (vertex_type i = 0; i < ap.count; ++i) g.push_back(ap.next());
00480         std::sort(g.begin(),g.end(),OKlib::Programming::Utilities::OrderRelations::SizeLessThan<std::less<hyperedge_type> >());
00481         g.resize(std::unique(g.begin(),g.end()) - g.begin());
00482         {
00483          typedef std::list<hyperedge_type> list_type;
00484          list_type gl(g.begin(),g.end());
00485          OKlib::SetAlgorithms::Subsumption_elimination<list_type, OKlib::SetAlgorithms::SubsumptionsTags::hyperedges_are_unique, OKlib::SetAlgorithms::SubsumptionsTags::hyperedges_sorted_by_size>()(gl);
00486          g.assign(gl.begin(),gl.end());
00487         }
00488         std::sort(g.begin(),g.end(),OKlib::Programming::Utilities::OrderRelations::Colexicographical_comparison<hyperedge_type>());
00489         return g;
00490       }
00491     
00492     };
00493     
00494    }
00495   }
00496  }
00497 }
00498 
00499 #endif