include/libstick/simplicialfunction.h

   1 #ifndef simplicialfunction_h_thee5Oonae6eig5k
   2 #define simplicialfunction_h_thee5Oonae6eig5k
   3
   4 #include <algorithm>
   5 #include <vector>
   6 #include <limits>
   7
   8 #include "simplicialcomplex.h"
   9
  10
  11 namespace libstick {
  12
  13 /** A simplicial function assigns to each simplex in a
  14  * simplicial_complex<MAXDIM, IT> a function value of type VT. A natural way to
  15  * obtain a simplex_order is to sort the simplicies of a complex according to
  16  * their function values while preserving the filtration property. */
  17 template<int MAXDIM, class IT, class VT>
  18 class simplicial_function {
  19
  20     public:
  21         /** The type of the underlying simplicial complex. */
  22         typedef simplicial_complex<MAXDIM, IT> simplcompltype;
  23         /** Type of indices of simplices. */
  24         typedef IT index_type;
  25         /** Type of the simplices of the underlying simplicial complex */
  26         typedef typename simplcompltype::simplex simplex;
  27         /** Type of the order on the underlying simplicial complex */
  28         typedef typename simplcompltype::simplex_order simplex_order;
  29         /** To every simplex a function value is assigned according to which a
  30          * filtration is considered. This is the value type of the function. */
  31         typedef VT value_type;
  32         /** The container that holds the values. */
  33         typedef std::vector<value_type> values_type;
  34
  35         /** This struct adds a function value to a simplex and is designed to
  36          * be an aggregate. */
  37         struct valuedsimplex {
  38             simplex simpl;
  39             value_type value;
  40
  41             /** Create a valuedsimplex. */
  42             static valuedsimplex create_valuedsimplex(int dim, index_type* faces, value_type value) {
  43                 valuedsimplex vs;
  44                 vs.simpl = simplex::create_simplex(dim, faces);
  45                 vs.value = value;
  46                 return vs;
  47             }
  48         };
  49
  50
  51         /**Create a simplicial function on a given simplicial complex c. Only
  52          * define for the (-1)-dim dummy vertex a value, namely
  53          * get_minusonedim_value().*/
  54         simplicial_function(simplcompltype &c) :
  55             c(c) {
  56                 values.push_back(get_minusonedim_value());
  57             }
  58
  59         /** Get the value of the (-1)-dimensional dummy simplex. */
  60         static value_type get_minusonedim_value() {
  61             return std::numeric_limits<value_type>::has_infinity
  62                 ? -std::numeric_limits<value_type>::infinity()
  63                 : std::numeric_limits<value_type>::min();
  64         }
  65
  66         /** Return number of function values. */
  67         size_t size() const {
  68             return values.size();
  69         }
  70
  71         /** Returns true if we have a function value for exactly every
  72          * simplex. */
  73         bool is_complete() const {
  74             return (size() == c.size());
  75         }
  76
  77         /** Make the simplicial function complete, i.e. s.t.  is_complete()
  78          * returns true, by truncating or filling up the list of function
  79          * values by the given value. */
  80         void make_complete(value_type fill = value_type()) {
  81             // We never would like to get rid of the dummy vertex's value
  82             assert(c.size() >= 1);
  83             values.resize(c.size(), fill);
  84         }
  85
  86         /** Return the underlying complex. */
  87         const simplcompltype& get_complex() const {
  88             return c;
  89         }
  90
  91         /** Get value of idx-th simplex */
  92         const value_type& get_value(index_type idx) const {
  93             assert(0 <= idx && idx < size());
  94             return values.at(idx);
  95         }
  96
  97         /** Set value of idx-th simplex */
  98         void set_value(index_type idx, const value_type& value) {
  99             assert(0 <= idx && idx < size());
 100             values.at(idx) = value;
 101         }
 102
 103         /** Get all the values. */
 104         const values_type& get_values() const {
 105             return values;
 106         }
 107
 108         /** Set all the values at once. Requires that is_complete() returns
 109          * true afterwards. */
 110         void set_values(const values_type& values) {
 111             this->values = values;
 112             assert(is_complete());
 113         }
 114
 115         /** Add a simplex to the complex and the function. Requires
 116          * that is_complete() returns true.
 117          *
 118          * See also simplicial_complex::add_simplex(). */
 119         index_type add_simplex(int dim, index_type* faces, value_type value) {
 120             assert(is_complete());
 121
 122             return add_simplex(valuedsimplex::create_valuedsimplex(dim, faces, value));
 123         }
 124
 125         /** Add a simplex of at least dimension 1 to the complex and the
 126          * function. The value of the simplex is set to the maximum value of
 127          * its faces. Returns the index of the added simplex.  Requires that
 128          * is_complete() returns true.
 129          *
 130          * See also simplicial_complex::add_simplex(). */
 131         index_type add_simplex(int dim, index_type* faces) {
 132             assert(dim >= 1);
 133             assert(is_complete());
 134
 135             // Get max value of its faces
 136             VT value = get_value(faces[0]);
 137             for (size_t i=1; i < simplex::face_count_bydim(dim); ++i)
 138                 value = std::max(value, get_value(faces[i]));
 139
 140             return add_simplex(dim, faces, value);
 141         }
 142
 143         /** Add a valued simplex. Requires that is_complete() returns true.
 144          *
 145          * See also simplicial_comple::add_simplex(). */
 146         index_type add_simplex(const valuedsimplex &s) {
 147             assert(is_complete());
 148
 149             values.push_back(s.value);
 150             return c.add_simplex(s.simpl);
 151         }
 152
 153         /** Add an array of valued simplices. Requires that is_complete()
 154          * returns true. */
 155         void add_simplices(valuedsimplex* sarray, size_t count) {
 156             assert(is_complete());
 157
 158             for (unsigned i=0; i < count; ++i)
 159                 add_simplex(sarray[i]);
 160         }
 161
 162         /** Returns true iff simplex's values are monotone w.r.t.
 163          * face-inclusion, i.e., for each simplex its value is not smaller than
 164          * the values of its faces. Requires that is_complex() gives true. */
 165         bool is_monotone() const {
 166             assert(size() == c.size());
 167             assert(c.is_complex());
 168
 169             for (unsigned i=0; i < size(); ++i) {
 170                 const simplex& s = c.get_simplex(i);
 171                 for (unsigned f=0; f < s.face_count(); ++f)
 172                     if (get_value(s.faces[f]) > get_value(i))
 173                         return false;
 174             }
 175
 176             return true;
 177         }
 178
 179         /** Check if the given simplex order is a filtration and monotone
 180          * w.r.t. to this simplicial function. Note is_monotone() &&
 181          * o.is_filtration() can be true, but is_order_monotonefiltration(o)
 182          * may still be false. */
 183         bool is_order_monotonefiltration(const simplex_order &o) const {
 184             assert(size() == c.size());
 185
 186             for (unsigned i=1; i < size(); ++i)
 187                 if (values.at(o.order_to_complex(i-1)) > values.at(o.order_to_complex(i)))
 188                     return false;
 189
 190             return o.is_filtration();
 191         }
 192
 193         /** Make simplex order a monotone filtration of the underlying complex. */
 194         void make_order_monotonefiltration(simplex_order &so) const {
 195             typename simplex_order::order_type order = so.get_order();
 196             std::sort(order.begin(), order.end(), cmp_monotone_filtration(*this));
 197             so.set_order(order);
 198         }
 199
 200     private:
 201         /** Compares (operator<) two valued simplices (i.e. indices) in a
 202          * simplicial complex w.r.t. lexicographical order on (value,
 203          * dimension)-tuples.
 204          * */
 205         struct cmp_monotone_filtration {
 206             const simplicial_function &f;
 207
 208             cmp_monotone_filtration(const simplicial_function &f) :
 209                 f(f) {
 210                     assert(f.is_complete());
 211                 }
 212
 213             bool operator()(index_type i, index_type j) const {
 214                 assert(f.is_complete());
 215
 216                 if (f.get_value(i) != f.get_value(j))
 217                     return (f.get_value(i) < f.get_value(j));
 218                 else
 219                     return f.get_complex().get_simplex(i).dim < f.get_complex().get_simplex(j).dim;
 220             }
 221         };
 222
 223         /** Simplex c[i] get assigned values[i]. */
 224         values_type values;
 225
 226         /** The complex on which we consider a function. */
 227         simplcompltype &c;
 228 };
 229
 230 }
 231
 232
 233 #endif