X-Git-Url: https://git.sthu.org/?p=libstick.git;a=blobdiff_plain;f=include%2Flibstick%2Fsimplicialfunction.h;fp=include%2Flibstick%2Fsimplicialfunction.h;h=6371d66e0fd72cb88d852477f659b0573cb53b8e;hp=0000000000000000000000000000000000000000;hb=7186ae9cc97393496d7f0e0cb281524276f1e47c;hpb=d6673c66ae1cb2b421b6e0c4b6a2f6ea6f0fad98 diff --git a/include/libstick/simplicialfunction.h b/include/libstick/simplicialfunction.h new file mode 100644 index 0000000..6371d66 --- /dev/null +++ b/include/libstick/simplicialfunction.h @@ -0,0 +1,233 @@ +#ifndef simplicialfunction_h_thee5Oonae6eig5k +#define simplicialfunction_h_thee5Oonae6eig5k + +#include +#include +#include + +#include "simplicialcomplex.h" + + +namespace libstick { + +/** A simplicial function assigns to each simplex in a + * simplicial_complex a function value of type VT. A natural way to + * obtain a simplex_order is to sort the simplicies of a complex according to + * their function values while preserving the filtration property. */ +template +class simplicial_function { + + public: + /** The type of the underlying simplicial complex. */ + typedef simplicial_complex simplcompltype; + /** Type of indices of simplices. */ + typedef IT index_type; + /** Type of the simplices of the underlying simplicial complex */ + typedef typename simplcompltype::simplex simplex; + /** Type of the order on the underlying simplicial complex */ + typedef typename simplcompltype::simplex_order simplex_order; + /** To every simplex a function value is assigned according to which a + * filtration is considered. This is the value type of the function. */ + typedef VT value_type; + /** The container that holds the values. */ + typedef std::vector values_type; + + /** This struct adds a function value to a simplex and is designed to + * be an aggregate. */ + struct valuedsimplex { + simplex simpl; + value_type value; + + /** Create a valuedsimplex. */ + static valuedsimplex create_valuedsimplex(int dim, index_type* faces, value_type value) { + valuedsimplex vs; + vs.simpl = simplex::create_simplex(dim, faces); + vs.value = value; + return vs; + } + }; + + + /**Create a simplicial function on a given simplicial complex c. Only + * define for the (-1)-dim dummy vertex a value, namely + * get_minusonedim_value().*/ + simplicial_function(simplcompltype &c) : + c(c) { + values.push_back(get_minusonedim_value()); + } + + /** Get the value of the (-1)-dimensional dummy simplex. */ + static value_type get_minusonedim_value() { + return std::numeric_limits::has_infinity + ? -std::numeric_limits::infinity() + : std::numeric_limits::min(); + } + + /** Return number of function values. */ + size_t size() const { + return values.size(); + } + + /** Returns true if we have a function value for exactly every + * simplex. */ + bool is_complete() const { + return (size() == c.size()); + } + + /** Make the simplicial function complete, i.e. s.t. is_complete() + * returns true, by truncating or filling up the list of function + * values by the given value. */ + void make_complete(value_type fill = value_type()) { + // We never would like to get rid of the dummy vertex's value + assert(c.size() >= 1); + values.resize(c.size(), fill); + } + + /** Return the underlying complex. */ + const simplcompltype& get_complex() const { + return c; + } + + /** Get value of idx-th simplex */ + const value_type& get_value(index_type idx) const { + assert(0 <= idx && idx < size()); + return values.at(idx); + } + + /** Set value of idx-th simplex */ + void set_value(index_type idx, const value_type& value) { + assert(0 <= idx && idx < size()); + values.at(idx) = value; + } + + /** Get all the values. */ + const values_type& get_values() const { + return values; + } + + /** Set all the values at once. Requires that is_complete() returns + * true afterwards. */ + void set_values(const values_type& values) { + this->values = values; + assert(is_complete()); + } + + /** Add a simplex to the complex and the function. Requires + * that is_complete() returns true. + * + * See also simplicial_complex::add_simplex(). */ + index_type add_simplex(int dim, index_type* faces, value_type value) { + assert(is_complete()); + + return add_simplex(valuedsimplex::create_valuedsimplex(dim, faces, value)); + } + + /** Add a simplex of at least dimension 1 to the complex and the + * function. The value of the simplex is set to the maximum value of + * its faces. Returns the index of the added simplex. Requires that + * is_complete() returns true. + * + * See also simplicial_complex::add_simplex(). */ + index_type add_simplex(int dim, index_type* faces) { + assert(dim >= 1); + assert(is_complete()); + + // Get max value of its faces + VT value = get_value(faces[0]); + for (size_t i=1; i < simplex::face_count_bydim(dim); ++i) + value = std::max(value, get_value(faces[i])); + + return add_simplex(dim, faces, value); + } + + /** Add a valued simplex. Requires that is_complete() returns true. + * + * See also simplicial_comple::add_simplex(). */ + index_type add_simplex(const valuedsimplex &s) { + assert(is_complete()); + + values.push_back(s.value); + return c.add_simplex(s.simpl); + } + + /** Add an array of valued simplices. Requires that is_complete() + * returns true. */ + void add_simplices(valuedsimplex* sarray, size_t count) { + assert(is_complete()); + + for (unsigned i=0; i < count; ++i) + add_simplex(sarray[i]); + } + + /** Returns true iff simplex's values are monotone w.r.t. + * face-inclusion, i.e., for each simplex its value is not smaller than + * the values of its faces. Requires that is_complex() gives true. */ + bool is_monotone() const { + assert(size() == c.size()); + assert(c.is_complex()); + + for (unsigned i=0; i < size(); ++i) { + const simplex& s = c.get_simplex(i); + for (unsigned f=0; f < s.face_count(); ++f) + if (get_value(s.faces[f]) > get_value(i)) + return false; + } + + return true; + } + + /** Check if the given simplex order is a filtration and monotone + * w.r.t. to this simplicial function. Note is_monotone() && + * o.is_filtration() can be true, but is_order_monotonefiltration(o) + * may still be false. */ + bool is_order_monotonefiltration(const simplex_order &o) const { + assert(size() == c.size()); + + for (unsigned i=1; i < size(); ++i) + if (values.at(o.order_to_complex(i-1)) > values.at(o.order_to_complex(i))) + return false; + + return o.is_filtration(); + } + + /** Make simplex order a monotone filtration of the underlying complex. */ + void make_order_monotonefiltration(simplex_order &so) const { + typename simplex_order::order_type order = so.get_order(); + std::sort(order.begin(), order.end(), cmp_monotone_filtration(*this)); + so.set_order(order); + } + + private: + /** Compares (operator<) two valued simplices (i.e. indices) in a + * simplicial complex w.r.t. lexicographical order on (value, + * dimension)-tuples. + * */ + struct cmp_monotone_filtration { + const simplicial_function &f; + + cmp_monotone_filtration(const simplicial_function &f) : + f(f) { + assert(f.is_complete()); + } + + bool operator()(index_type i, index_type j) const { + assert(f.is_complete()); + + if (f.get_value(i) != f.get_value(j)) + return (f.get_value(i) < f.get_value(j)); + else + return f.get_complex().get_simplex(i).dim < f.get_complex().get_simplex(j).dim; + } + }; + + /** Simplex c[i] get assigned values[i]. */ + values_type values; + + /** The complex on which we consider a function. */ + simplcompltype &c; +}; + +} + + +#endif