X-Git-Url: https://git.sthu.org/?a=blobdiff_plain;f=include%2Flibstick-0.1%2Fsimplicialcomplex.h;h=707fd4f3240ae7fe71c4c90e7a4d1ab25926689e;hb=46e2e26363bfa07dc79d912ebe6df772942536bd;hp=d829721c02da3515a354ec89f034933ecb90e46a;hpb=267194caeb2fe56530b11c440fefd01c344e5482;p=libstick.git diff --git a/include/libstick-0.1/simplicialcomplex.h b/include/libstick-0.1/simplicialcomplex.h index d829721..707fd4f 100644 --- a/include/libstick-0.1/simplicialcomplex.h +++ b/include/libstick-0.1/simplicialcomplex.h @@ -6,6 +6,7 @@ #include #include #include +#include #include @@ -17,13 +18,17 @@ namespace libstick { /** A simplicial complex is a std::vector of simplices such that each face is * also part of the complex. Every simplex has dimension at most MAXDIM. The * indices of simplices resp. their faces are of type IT. To each simplex a - * value is assigend, which is of type VT. */ -template -class SimplicialComplex { + * value is assigend, which is of type VT. When a simplicial_complex is + * instantiated, a single (-1) dimensional simplex is automatically created. + * Each 0-dimensional simplex automatically has this simplex as its face. + * Consequently, the innner class simplex_order gives the extended boundary + * matrix. */ +template +class simplicial_complex { public: /** The type of this class. */ - typedef SimplicialComplex simplcompltype; + typedef simplicial_complex simplcompltype; /** Type of indices of simplices. */ typedef IT index_type; /** To every simplex a function value is assigned according to which a @@ -33,21 +38,39 @@ class SimplicialComplex { /** A simplex of the complex. */ struct Simplex { /** Dimension of the simplex. */ - size_t dim; + int dim; /** The indices of the faces of the simplex. */ index_type faces[MAXDIM+1]; /** The value of the simplex. */ value_type value; /** Create a new simplex with dimension 'dim', (dim+1)-faces and - * its value. */ - static Simplex create(size_t dim, index_type* faces, value_type value) { - assert(dim <= MAXDIM); + * its value. If simpley is 0-dimensional, its face is + * automatically set to one (-1)-dimensional simplex. */ + static Simplex create(int dim, index_type* faces, value_type value) { + assert(0 <= dim && dim <= MAXDIM); Simplex s; s.dim = dim; s.value = value; - memcpy(s.faces, faces, face_count_bydim(dim)*sizeof(index_type)); + + if (dim > 0) + memcpy(s.faces, faces, face_count_bydim(dim)*sizeof(index_type)); + else + s.faces[0] = 0; + + return s; + } + + /** Create a (-1)-dimensional simplex. It has the lowest possible value. */ + static Simplex create_minusonedim_simplex() { + Simplex s; + + s.dim = -1; + s.faces[0] = 0; + s.value = std::numeric_limits::has_infinity + ? -std::numeric_limits::infinity() + : std::numeric_limits::min(); return s; } @@ -58,22 +81,21 @@ class SimplicialComplex { } /** Get number of faces of a dim-dimensional simplex. */ - static size_t face_count_bydim(size_t dim) { - if (dim == 0) - return 0; + static size_t face_count_bydim(int dim) { + assert(-1 <= dim && dim <= MAXDIM); return dim + 1; } }; /** An order of the simplices of complex c. An order can be interpreted * as a permuation of the complex's std::vector of simplices. */ - class SimplexOrder { + class simplex_order { public: - typedef BooleanColRowMatrix BoundaryMatrix; + typedef boolean_colrowmatrix boundary_matrix; /** Create a standard order of the complex c, i.e., the identity permutation. */ - SimplexOrder(const simplcompltype &c) : + simplex_order(const simplcompltype &c) : c(c) { reset(); @@ -94,63 +116,63 @@ class SimplicialComplex { } /** Get i-th simplex in the simplex order. */ - const Simplex& getSimplex(size_t i) const { + const Simplex& get_simplex(size_t i) const { assert(i < size()); return c.simplices[order.at(i)]; } /** Returns true iff the faces of simplex i are before i in this order. */ - bool isFiltration() const { + bool is_filtration() const { assert(size() == c.size()); for (unsigned i=0; i < size(); ++i) - for (unsigned f=0; f < getSimplex(i).face_count(); ++f) - if (revorder[getSimplex(i).faces[f]] >= i) + for (unsigned f=0; f < get_simplex(i).face_count(); ++f) + if (revorder[get_simplex(i).faces[f]] >= i) return false; return true; } - /** Returns true iff isFiltration() gives true and values of simplices + /** Returns true iff is_filtration() gives true and values of simplices * are monotone w.r.t. this order of simplices. */ - bool isMonotone() const { + bool is_monotone() const { assert(size() == c.size()); for (unsigned i=1; i < size(); ++i) - if (getSimplex(i-1).value > getSimplex(i).value) + if (get_simplex(i-1).value > get_simplex(i).value) return false; - return isFiltration(); + return is_filtration(); } - /** Sort simplices such that isMonotone() gives true. This - * requires that the complex's isMonotone() gave true + /** Sort simplices such that is_monotone() gives true. This + * requires that the complex's is_monotone() gave true * beforehand.*/ - void makeMonotoneFiltration() { - assert(c.isMonotone()); + void make_monotone_filtration() { + assert(c.is_monotone()); - sort(order.begin(), order.end(), cmpMonotoneFiltration(c)); - restoreRevorderFromOrder(); + sort(order.begin(), order.end(), cmp_monotone_filtration(c)); + restore_revorder_from_order(); - assert(c.isMonotone()); - assert(isFiltration()); - assert(isMonotone()); + assert(c.is_monotone()); + assert(is_filtration()); + assert(is_monotone()); } /** Get the boundary matrix of the complex according to this order. */ - BoundaryMatrix getBoundaryMatrix() const { - BoundaryMatrix mat(size()); + boundary_matrix get_boundary_matrix() const { + boundary_matrix mat(size()); for (unsigned c=0; c < size(); ++c) - for(unsigned r=0; r < getSimplex(c).face_count(); ++r) - mat.set(revorder[getSimplex(c).faces[r]], c, true); + for(unsigned r=0; r < get_simplex(c).face_count(); ++r) + mat.set(revorder[get_simplex(c).faces[r]], c, true); return mat; } private: /** Reconstruct 'revorder' by inverting the permutation given by 'order'. */ - void restoreRevorderFromOrder() { + void restore_revorder_from_order() { // Make revorder * order the identity permutation for (unsigned i=0; i < size(); ++i) revorder[order[i]] = i; @@ -171,6 +193,11 @@ class SimplicialComplex { }; public: + simplicial_complex() { + // Add the one minus-one dimensional simplex + add_simplex(Simplex::create_minusonedim_simplex()); + } + /** Return number of simplices. */ size_t size() const { return simplices.size(); @@ -178,13 +205,13 @@ class SimplicialComplex { /** Add a simplex to the complex. The dimension of the faces must be * dim-1, and they must already be part of the complex. */ - void addSimplex(size_t dim, index_type* faces, value_type value) { - addSimplex(Simplex::create(dim, faces, value)); + void add_simplex(int dim, index_type* faces, value_type value) { + add_simplex(Simplex::create(dim, faces, value)); } /** Add a simplex to the complex. The dimension of the faces must be * dim-1, and they must already be part of the complex. */ - void addSimplex(Simplex s) { + void add_simplex(Simplex s) { // Check requirements for faces for (unsigned i=0; i < s.face_count(); ++i) { // Faces are already in complex. @@ -196,10 +223,15 @@ class SimplicialComplex { simplices.push_back(s); } + /** Add an array of simplices */ + void add_simplices(Simplex* sarray, size_t count) { + for (unsigned i=0; i < count; ++i) + add_simplex(sarray[i]); + } + /** Return true iff for each simplex i with dimension dim it holds that * the faces of i are contained in the complex and have dimension dim-1. */ - bool isComplex() const { - typename std::vector::const_iterator it = ++simplices.begin(); + bool is_complex() const { for (unsigned i=0; i < size(); ++i) { const Simplex &s = simplices[i]; @@ -218,9 +250,9 @@ class SimplicialComplex { /** 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 isComplex() gives true. */ - bool isMonotone() const { - assert(isComplex()); + * the values of its faces. Requires that is_complex() gives true. */ + bool is_monotone() const { + assert(is_complex()); typename std::vector::const_iterator it = ++simplices.begin(); for (; it != simplices.end(); ++it) @@ -233,12 +265,12 @@ class SimplicialComplex { private: /** Compares (operator<) two simplices (i.e. indices) in a - * SimplexOrder w.r.t. lexicographical order on (value, + * simplex_order w.r.t. lexicographical order on (value, * dimension)-tuples. */ - struct cmpMonotoneFiltration { - const SimplicialComplex &c; + struct cmp_monotone_filtration { + const simplicial_complex &c; - cmpMonotoneFiltration(const SimplicialComplex &c) : + cmp_monotone_filtration(const simplicial_complex &c) : c(c){ }