OKlibrary  0.2.1.6
Hindman.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 30.7.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 
00013 #ifndef HINDMANHYPERGRAPH_jjdhsTfr435R
00014 #define HINDMANHYPERGRAPH_jjdhsTfr435R
00015 
00016 #include <vector>
00017 #include <cassert>
00018 #include <cmath>
00019 #include <stdexcept>
00020 
00021 namespace OKlib {
00022   namespace Combinatorics {
00023     namespace Hypergraphs {
00024       namespace Generators {
00025 
00062         template <typename UInt = unsigned int>
00063         struct Hindman_k2 {
00064 
00065           typedef UInt vertex_type;
00066           typedef std::vector<vertex_type> hyperedge_type;
00067           typedef std::vector<hyperedge_type> set_system_type;
00068           typedef typename set_system_type::size_type size_type;
00069 
00070           const vertex_type a; // start index
00071           const vertex_type n; // end index
00072           const bool inj; // whether only different vertices are considered
00073 
00074           Hindman_k2(const vertex_type a, const vertex_type n, const bool inj = false)
00075             : a(a), n(n), inj(inj) {
00076             assert(a >= 1);
00077           }
00078           Hindman_k2() : a(1), n(0), inj(false) {}
00079 
00080           size_type nver() const {
00081             if (n < a) return 0; else return n-a+1;
00082           }
00083           size_type nhyp() const {
00084             if (n < a+a+inj or n < a*(a+inj)) return 0;
00085             const size_type s = std::sqrt((double) n);
00086             if (a == 1)
00087               return sum(2,s) - (s+2*inj-1)*s/2 + (n-1);
00088             else
00089               return sum(a,s) - ((s+a+2*inj-2)*(s+1-a))/2;
00090           }
00091 
00092           set_system_type hyperedge_set() const {
00093 
00094           }
00095 
00096         private :
00097 
00098           size_type sum(const vertex_type start, const size_type end) const {
00099             size_type sum = 0;
00100             for (vertex_type x = start; x <= end; ++x) {
00101               const vertex_type q =  n/x;
00102               sum += q;
00103               if (sum < q)
00104                 throw std::overflow_error("ERROR[Hindman]: n too big.");
00105               return sum;
00106             }
00107           }
00108         };
00109 
00110       }
00111     }
00112   }
00113 }
00114 
00115 #endif