Simplex_tree.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author(s): ClĂ©ment Maria
4  *
5  * Copyright (C) 2014 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef SIMPLEX_TREE_H_
12 #define SIMPLEX_TREE_H_
13 
14 #include <gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h>
15 #include <gudhi/Simplex_tree/Simplex_tree_siblings.h>
16 #include <gudhi/Simplex_tree/Simplex_tree_iterators.h>
17 #include <gudhi/Simplex_tree/indexing_tag.h>
18 
19 #include <gudhi/reader_utils.h>
20 #include <gudhi/graph_simplicial_complex.h>
21 #include <gudhi/Debug_utils.h>
22 
23 #include <boost/container/flat_map.hpp>
24 #include <boost/iterator/transform_iterator.hpp>
25 #include <boost/graph/adjacency_list.hpp>
26 #include <boost/range/adaptor/reversed.hpp>
27 
28 #ifdef GUDHI_USE_TBB
29 #include <tbb/parallel_sort.h>
30 #endif
31 
32 #include <utility>
33 #include <vector>
34 #include <functional> // for greater<>
35 #include <stdexcept>
36 #include <limits> // Inf
37 #include <initializer_list>
38 #include <algorithm> // for std::max
39 #include <cstdint> // for std::uint32_t
40 #include <iterator> // for std::distance
41 
42 namespace Gudhi {
43 
44 struct Simplex_tree_options_full_featured;
45 
59 template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>
60 class Simplex_tree {
61  public:
63  typedef typename Options::Indexing_tag Indexing_tag;
76 
77  /* Type of node in the simplex tree. */
78  typedef Simplex_tree_node_explicit_storage<Simplex_tree> Node;
79  /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */
80  // Note: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a
81  // flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and
82  // Simplex_key next to each other).
83  typedef typename boost::container::flat_map<Vertex_handle, Node> Dictionary;
84 
85  /* \brief Set of nodes sharing a same parent in the simplex tree. */
86  /* \brief Set of nodes sharing a same parent in the simplex tree. */
87  typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings;
88 
89  struct Key_simplex_base_real {
90  Key_simplex_base_real() : key_(-1) {}
91  void assign_key(Simplex_key k) { key_ = k; }
92  Simplex_key key() const { return key_; }
93  private:
94  Simplex_key key_;
95  };
96  struct Key_simplex_base_dummy {
97  Key_simplex_base_dummy() {}
98  // Undefined so it will not link
99  void assign_key(Simplex_key);
100  Simplex_key key() const;
101  };
102  typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type
103  Key_simplex_base;
104 
105  struct Filtration_simplex_base_real {
106  Filtration_simplex_base_real() : filt_(0) {}
107  void assign_filtration(Filtration_value f) { filt_ = f; }
108  Filtration_value filtration() const { return filt_; }
109  private:
110  Filtration_value filt_;
111  };
112  struct Filtration_simplex_base_dummy {
113  Filtration_simplex_base_dummy() {}
114  void assign_filtration(Filtration_value GUDHI_CHECK_code(f)) { GUDHI_CHECK(f == 0, "filtration value specified for a complex that does not store them"); }
115  Filtration_value filtration() const { return 0; }
116  };
117  typedef typename std::conditional<Options::store_filtration, Filtration_simplex_base_real,
118  Filtration_simplex_base_dummy>::type Filtration_simplex_base;
119 
120  public:
123  typedef typename Dictionary::iterator Simplex_handle;
124 
125  private:
126  typedef typename Dictionary::iterator Dictionary_it;
127  typedef typename Dictionary_it::value_type Dit_value_t;
128 
129  struct return_first {
130  Vertex_handle operator()(const Dit_value_t& p_sh) const {
131  return p_sh.first;
132  }
133  };
134 
135  public:
147  typedef boost::transform_iterator<return_first, Dictionary_it> Complex_vertex_iterator;
149  typedef boost::iterator_range<Complex_vertex_iterator> Complex_vertex_range;
153  typedef Simplex_tree_simplex_vertex_iterator<Simplex_tree> Simplex_vertex_iterator;
155  typedef boost::iterator_range<Simplex_vertex_iterator> Simplex_vertex_range;
157  typedef std::vector<Simplex_handle> Cofaces_simplex_range;
161  typedef Simplex_tree_boundary_simplex_iterator<Simplex_tree> Boundary_simplex_iterator;
163  typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
167  typedef Simplex_tree_complex_simplex_iterator<Simplex_tree> Complex_simplex_iterator;
169  typedef boost::iterator_range<Complex_simplex_iterator> Complex_simplex_range;
174  typedef Simplex_tree_skeleton_simplex_iterator<Simplex_tree> Skeleton_simplex_iterator;
177  typedef boost::iterator_range<Skeleton_simplex_iterator> Skeleton_simplex_range;
179  typedef std::vector<Simplex_handle> Filtration_simplex_range;
183  typedef typename Filtration_simplex_range::const_iterator Filtration_simplex_iterator;
184 
185  /* @} */ // end name range and iterator types
191  Complex_vertex_range complex_vertex_range() {
192  return Complex_vertex_range(
193  boost::make_transform_iterator(root_.members_.begin(), return_first()),
194  boost::make_transform_iterator(root_.members_.end(), return_first()));
195  }
196 
202  Complex_simplex_range complex_simplex_range() {
205  }
206 
216  Skeleton_simplex_range skeleton_simplex_range(int dim) {
219  }
220 
236  Filtration_simplex_range const& filtration_simplex_range(Indexing_tag = Indexing_tag()) {
237  if (filtration_vect_.empty()) {
239  }
240  return filtration_vect_;
241  }
242 
249  Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) {
250  assert(sh != null_simplex()); // Empty simplex
253  }
254 
269  template<class SimplexHandle>
270  Boundary_simplex_range boundary_simplex_range(SimplexHandle sh) {
273  }
274  // end range and iterator methods
281  : null_vertex_(-1),
282  root_(nullptr, null_vertex_),
283  filtration_vect_(),
284  dimension_(-1) { }
285 
287  Simplex_tree(const Simplex_tree& complex_source) {
288 #ifdef DEBUG_TRACES
289  std::cout << "Simplex_tree copy constructor" << std::endl;
290 #endif // DEBUG_TRACES
291  copy_from(complex_source);
292  }
293 
297  Simplex_tree(Simplex_tree && complex_source) {
298 #ifdef DEBUG_TRACES
299  std::cout << "Simplex_tree move constructor" << std::endl;
300 #endif // DEBUG_TRACES
301  move_from(complex_source);
302 
303  // just need to set dimension_ on source to make it available again
304  // (filtration_vect_ and members are already set from the move)
305  complex_source.dimension_ = -1;
306  }
307 
310  root_members_recursive_deletion();
311  }
312 
314  Simplex_tree& operator= (const Simplex_tree& complex_source) {
315 #ifdef DEBUG_TRACES
316  std::cout << "Simplex_tree copy assignment" << std::endl;
317 #endif // DEBUG_TRACES
318  // Self-assignment detection
319  if (&complex_source != this) {
320  // We start by deleting root_ if not empty
321  root_members_recursive_deletion();
322 
323  copy_from(complex_source);
324  }
325  return *this;
326  }
327 
331  Simplex_tree& operator=(Simplex_tree&& complex_source) {
332 #ifdef DEBUG_TRACES
333  std::cout << "Simplex_tree move assignment" << std::endl;
334 #endif // DEBUG_TRACES
335  // Self-assignment detection
336  if (&complex_source != this) {
337  // root_ deletion in case it was not empty
338  root_members_recursive_deletion();
339 
340  move_from(complex_source);
341  }
342  return *this;
343  } // end constructor/destructor
345 
346  private:
347  // Copy from complex_source to "this"
348  void copy_from(const Simplex_tree& complex_source) {
349  null_vertex_ = complex_source.null_vertex_;
350  filtration_vect_.clear();
351  dimension_ = complex_source.dimension_;
352  auto root_source = complex_source.root_;
353 
354  // root members copy
355  root_.members() = Dictionary(boost::container::ordered_unique_range, root_source.members().begin(), root_source.members().end());
356  // Needs to reassign children
357  for (auto& map_el : root_.members()) {
358  map_el.second.assign_children(&root_);
359  }
360  rec_copy(&root_, &root_source);
361  }
362 
364  void rec_copy(Siblings *sib, Siblings *sib_source) {
365  for (auto sh = sib->members().begin(), sh_source = sib_source->members().begin();
366  sh != sib->members().end(); ++sh, ++sh_source) {
367  if (has_children(sh_source)) {
368  Siblings * newsib = new Siblings(sib, sh_source->first);
369  newsib->members_.reserve(sh_source->second.children()->members().size());
370  for (auto & child : sh_source->second.children()->members())
371  newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(newsib, child.second.filtration()));
372  rec_copy(newsib, sh_source->second.children());
373  sh->second.assign_children(newsib);
374  }
375  }
376  }
377 
378  // Move from complex_source to "this"
379  void move_from(Simplex_tree& complex_source) {
380  null_vertex_ = std::move(complex_source.null_vertex_);
381  root_ = std::move(complex_source.root_);
382  filtration_vect_ = std::move(complex_source.filtration_vect_);
383  dimension_ = std::move(complex_source.dimension_);
384 
385  // Need to update root members (children->oncles and children need to point on the new root pointer)
386  for (auto& map_el : root_.members()) {
387  if (map_el.second.children() != &(complex_source.root_)) {
388  // reset children->oncles with the moved root_ pointer value
389  map_el.second.children()->oncles_ = &root_;
390  } else {
391  // if simplex is of dimension 0, oncles_ shall be nullptr
392  GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr,
393  std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree"));
394  // and children points on root_ - to be moved
395  map_el.second.assign_children(&root_);
396  }
397  }
398  }
399 
400  // delete all root_.members() recursively
401  void root_members_recursive_deletion() {
402  for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) {
403  if (has_children(sh)) {
404  rec_delete(sh->second.children());
405  }
406  }
407  root_.members().clear();
408  }
409 
410  // Recursive deletion
411  void rec_delete(Siblings * sib) {
412  for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
413  if (has_children(sh)) {
414  rec_delete(sh->second.children());
415  }
416  }
417  delete sib;
418  }
419 
420  public:
423  if ((null_vertex_ != st2.null_vertex_) ||
424  (dimension_ != st2.dimension_))
425  return false;
426  return rec_equal(&root_, &st2.root_);
427  }
428 
431  return (!(*this == st2));
432  }
433 
434  private:
436  bool rec_equal(Siblings* s1, Siblings* s2) {
437  if (s1->members().size() != s2->members().size())
438  return false;
439  for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin();
440  (sh1 != s1->members().end() && sh2 != s2->members().end()); ++sh1, ++sh2) {
441  if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration())
442  return false;
443  if (has_children(sh1) != has_children(sh2))
444  return false;
445  // Recursivity on children only if both have children
446  else if (has_children(sh1))
447  if (!rec_equal(sh1->second.children(), sh2->second.children()))
448  return false;
449  }
450  return true;
451  }
452 
453  public:
459  static Simplex_key key(Simplex_handle sh) {
460  return sh->second.key();
461  }
462 
468  Simplex_handle simplex(Simplex_key idx) const {
469  return filtration_vect_[idx];
470  }
471 
477  static Filtration_value filtration(Simplex_handle sh) {
478  if (sh != null_simplex()) {
479  return sh->second.filtration();
480  } else {
481  return std::numeric_limits<Filtration_value>::infinity();
482  }
483  }
484 
488  void assign_filtration(Simplex_handle sh, Filtration_value fv) {
489  GUDHI_CHECK(sh != null_simplex(),
490  std::invalid_argument("Simplex_tree::assign_filtration - cannot assign filtration on null_simplex"));
491  sh->second.assign_filtration(fv);
492  }
493 
498  static Simplex_handle null_simplex() {
499  return Dictionary_it(nullptr);
500  }
501 
504  static Simplex_key null_key() {
505  return -1;
506  }
507 
510  Vertex_handle null_vertex() const {
511  return null_vertex_;
512  }
513 
515  size_t num_vertices() const {
516  return root_.members_.size();
517  }
518 
519  public:
521  size_t num_simplices() {
522  return num_simplices(&root_);
523  }
524 
525  private:
527  size_t num_simplices(Siblings * sib) {
528  auto sib_begin = sib->members().begin();
529  auto sib_end = sib->members().end();
530  size_t simplices_number = sib_end - sib_begin;
531  for (auto sh = sib_begin; sh != sib_end; ++sh) {
532  if (has_children(sh)) {
533  simplices_number += num_simplices(sh->second.children());
534  }
535  }
536  return simplices_number;
537  }
538 
539  public:
543  int dimension(Simplex_handle sh) {
544  Siblings * curr_sib = self_siblings(sh);
545  int dim = 0;
546  while (curr_sib != nullptr) {
547  ++dim;
548  curr_sib = curr_sib->oncles();
549  }
550  return dim - 1;
551  }
552 
554  int upper_bound_dimension() const {
555  return dimension_;
556  }
557 
562  int dimension() {
563  if (dimension_to_be_lowered_)
564  lower_upper_bound_dimension();
565  return dimension_;
566  }
567 
570  template<class SimplexHandle>
571  bool has_children(SimplexHandle sh) const {
572  // Here we rely on the root using null_vertex(), which cannot match any real vertex.
573  return (sh->second.children()->parent() == sh->first);
574  }
575 
583  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
584  Simplex_handle find(const InputVertexRange & s) {
585  auto first = std::begin(s);
586  auto last = std::end(s);
587 
588  if (first == last)
589  return null_simplex(); // ----->>
590 
591  // Copy before sorting
592  std::vector<Vertex_handle> copy(first, last);
593  std::sort(std::begin(copy), std::end(copy));
594  return find_simplex(copy);
595  }
596 
597  private:
599  Simplex_handle find_simplex(const std::vector<Vertex_handle> & simplex) {
600  Siblings * tmp_sib = &root_;
601  Dictionary_it tmp_dit;
602  auto vi = simplex.begin();
604  // Equivalent to the first iteration of the normal loop
605  GUDHI_CHECK(contiguous_vertices(), "non-contiguous vertices");
606  Vertex_handle v = *vi++;
607  if(v < 0 || v >= static_cast<Vertex_handle>(root_.members_.size()))
608  return null_simplex();
609  tmp_dit = root_.members_.begin() + v;
610  if (vi == simplex.end())
611  return tmp_dit;
612  if (!has_children(tmp_dit))
613  return null_simplex();
614  tmp_sib = tmp_dit->second.children();
615  }
616  for (;;) {
617  tmp_dit = tmp_sib->members_.find(*vi++);
618  if (tmp_dit == tmp_sib->members_.end())
619  return null_simplex();
620  if (vi == simplex.end())
621  return tmp_dit;
622  if (!has_children(tmp_dit))
623  return null_simplex();
624  tmp_sib = tmp_dit->second.children();
625  }
626  }
627 
630  Simplex_handle find_vertex(Vertex_handle v) {
632  assert(contiguous_vertices());
633  return root_.members_.begin() + v;
634  } else {
635  return root_.members_.find(v);
636  }
637  }
638 
639  public:
641  bool contiguous_vertices() const {
642  if (root_.members_.empty()) return true;
643  if (root_.members_.begin()->first != 0) return false;
644  if (std::prev(root_.members_.end())->first != static_cast<Vertex_handle>(root_.members_.size() - 1)) return false;
645  return true;
646  }
647 
648  private:
663  std::pair<Simplex_handle, bool> insert_vertex_vector(const std::vector<Vertex_handle>& simplex,
664  Filtration_value filtration) {
665  Siblings * curr_sib = &root_;
666  std::pair<Simplex_handle, bool> res_insert;
667  auto vi = simplex.begin();
668  for (; vi != simplex.end() - 1; ++vi) {
669  GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
670  res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration));
671  if (!(has_children(res_insert.first))) {
672  res_insert.first->second.assign_children(new Siblings(curr_sib, *vi));
673  }
674  curr_sib = res_insert.first->second.children();
675  }
676  GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
677  res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration));
678  if (!res_insert.second) {
679  // if already in the complex
680  if (res_insert.first->second.filtration() > filtration) {
681  // if filtration value modified
682  res_insert.first->second.assign_filtration(filtration);
683  return res_insert;
684  }
685  // if filtration value unchanged
686  return std::pair<Simplex_handle, bool>(null_simplex(), false);
687  }
688  // otherwise the insertion has succeeded - size is a size_type
689  if (static_cast<int>(simplex.size()) - 1 > dimension_) {
690  // Update dimension if needed
691  dimension_ = static_cast<int>(simplex.size()) - 1;
692  }
693  return res_insert;
694  }
695 
696  public:
720  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
721  std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex,
722  Filtration_value filtration = 0) {
723  auto first = std::begin(simplex);
724  auto last = std::end(simplex);
725 
726  if (first == last)
727  return std::pair<Simplex_handle, bool>(null_simplex(), true); // ----->>
728 
729  // Copy before sorting
730  std::vector<Vertex_handle> copy(first, last);
731  std::sort(std::begin(copy), std::end(copy));
732  return insert_vertex_vector(copy, filtration);
733  }
734 
749  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
750  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex,
751  Filtration_value filtration = 0) {
752  auto first = std::begin(Nsimplex);
753  auto last = std::end(Nsimplex);
754 
755  if (first == last)
756  return { null_simplex(), true }; // FIXME: false would make more sense to me.
757 
758  // Copy before sorting
759  // Thread local is not available on XCode version < V.8 - It will slow down computation
760 #ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL
761  thread_local
762 #endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL
763  std::vector<Vertex_handle> copy;
764  copy.clear();
765  copy.insert(copy.end(), first, last);
766  std::sort(copy.begin(), copy.end());
767  auto last_unique = std::unique(copy.begin(), copy.end());
768  copy.erase(last_unique, copy.end());
769  GUDHI_CHECK_code(
770  for (Vertex_handle v : copy)
771  GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
772  )
773  // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
774  dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(copy.begin(), copy.end())) - 1);
775 
776  return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration);
777  }
778 
779  private:
780  // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
781  template<class ForwardVertexIterator>
782  std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
783  ForwardVertexIterator first,
784  ForwardVertexIterator last,
785  Filtration_value filt) {
786  // An alternative strategy would be:
787  // - try to find the complete simplex, if found (and low filtration) exit
788  // - insert all the vertices at once in sib
789  // - loop over those (new or not) simplices, with a recursive call(++first, last)
790  Vertex_handle vertex_one = *first;
791  auto&& dict = sib->members();
792  auto insertion_result = dict.emplace(vertex_one, Node(sib, filt));
793  Simplex_handle simplex_one = insertion_result.first;
794  bool one_is_new = insertion_result.second;
795  if (!one_is_new) {
796  if (filtration(simplex_one) > filt) {
797  assign_filtration(simplex_one, filt);
798  } else {
799  // FIXME: this interface makes no sense, and it doesn't seem to be tested.
800  insertion_result.first = null_simplex();
801  }
802  }
803  if (++first == last) return insertion_result;
804  if (!has_children(simplex_one))
805  // TODO: have special code here, we know we are building the whole subtree from scratch.
806  simplex_one->second.assign_children(new Siblings(sib, vertex_one));
807  auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt);
808  // No need to continue if the full simplex was already there with a low enough filtration value.
809  if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt);
810  return res;
811  }
812 
813  public:
816  void assign_key(Simplex_handle sh, Simplex_key key) {
817  sh->second.assign_key(key);
818  }
819 
823  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
824  assert(dimension(sh) == 1);
825  return { find_vertex(sh->first), find_vertex(self_siblings(sh)->parent()) };
826  }
827 
829  template<class SimplexHandle>
830  Siblings* self_siblings(SimplexHandle sh) {
831  if (sh->second.children()->parent() == sh->first)
832  return sh->second.children()->oncles();
833  else
834  return sh->second.children();
835  }
836 
837  public:
839  Siblings * root() {
840  return &root_;
841  }
842 
848  dimension_to_be_lowered_ = false;
849  dimension_ = dimension;
850  }
851 
852  public:
863  filtration_vect_.clear();
864  filtration_vect_.reserve(num_simplices());
865  for (Simplex_handle sh : complex_simplex_range())
866  filtration_vect_.push_back(sh);
867 
868  /* We use stable_sort here because with libstdc++ it is faster than sort.
869  * is_before_in_filtration is now a total order, but we used to call
870  * stable_sort for the following heuristic:
871  * The use of a depth-first traversal of the simplex tree, provided by
872  * complex_simplex_range(), combined with a stable sort is meant to
873  * optimize the order of simplices with same filtration value. The
874  * heuristic consists in inserting the cofaces of a simplex as soon as
875  * possible.
876  */
877 #ifdef GUDHI_USE_TBB
878  tbb::parallel_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
879 #else
880  std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
881 #endif
882  }
883 
884  private:
897  void rec_coface(std::vector<Vertex_handle> &vertices, Siblings *curr_sib, int curr_nbVertices,
898  std::vector<Simplex_handle>& cofaces, bool star, int nbVertices) {
899  if (!(star || curr_nbVertices <= nbVertices)) // dimension of actual simplex <= nbVertices
900  return;
901  for (Simplex_handle simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) {
902  if (vertices.empty()) {
903  // If we reached the end of the vertices, and the simplex has more vertices than the given simplex
904  // => we found a coface
905 
906  // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices
907  bool addCoface = (star || curr_nbVertices == nbVertices);
908  if (addCoface)
909  cofaces.push_back(simplex);
910  if ((!addCoface || star) && has_children(simplex)) // Rec call
911  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
912  } else {
913  if (simplex->first == vertices.back()) {
914  // If curr_sib matches with the top vertex
915  bool equalDim = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices
916  bool addCoface = vertices.size() == 1 && equalDim;
917  if (addCoface)
918  cofaces.push_back(simplex);
919  if ((!addCoface || star) && has_children(simplex)) {
920  // Rec call
921  Vertex_handle tmp = vertices.back();
922  vertices.pop_back();
923  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
924  vertices.push_back(tmp);
925  }
926  } else if (simplex->first > vertices.back()) {
927  return;
928  } else {
929  // (simplex->first < vertices.back()
930  if (has_children(simplex))
931  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
932  }
933  }
934  }
935  }
936 
937  public:
943  Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex) {
944  return cofaces_simplex_range(simplex, 0);
945  }
946 
954  Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) {
955  Cofaces_simplex_range cofaces;
956  // codimension must be positive or null integer
957  assert(codimension >= 0);
958  Simplex_vertex_range rg = simplex_vertex_range(simplex);
959  std::vector<Vertex_handle> copy(rg.begin(), rg.end());
960  if (codimension + static_cast<int>(copy.size()) > dimension_ + 1 ||
961  (codimension == 0 && static_cast<int>(copy.size()) > dimension_)) // n+codimension greater than dimension_
962  return cofaces;
963  // must be sorted in decreasing order
964  assert(std::is_sorted(copy.begin(), copy.end(), std::greater<Vertex_handle>()));
965  bool star = codimension == 0;
966  rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast<int>(copy.size()));
967  return cofaces;
968  }
969 
970  private:
978  bool reverse_lexicographic_order(Simplex_handle sh1, Simplex_handle sh2) {
979  Simplex_vertex_range rg1 = simplex_vertex_range(sh1);
980  Simplex_vertex_range rg2 = simplex_vertex_range(sh2);
981  Simplex_vertex_iterator it1 = rg1.begin();
982  Simplex_vertex_iterator it2 = rg2.begin();
983  while (it1 != rg1.end() && it2 != rg2.end()) {
984  if (*it1 == *it2) {
985  ++it1;
986  ++it2;
987  } else {
988  return *it1 < *it2;
989  }
990  }
991  return ((it1 == rg1.end()) && (it2 != rg2.end()));
992  }
993 
1000  struct is_before_in_filtration {
1001  explicit is_before_in_filtration(Simplex_tree * st)
1002  : st_(st) { }
1003 
1004  bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const {
1005  // Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
1006  if (sh1->second.filtration() != sh2->second.filtration()) {
1007  return sh1->second.filtration() < sh2->second.filtration();
1008  }
1009  // is sh1 a proper subface of sh2
1010  return st_->reverse_lexicographic_order(sh1, sh2);
1011  }
1012 
1013  Simplex_tree * st_;
1014  };
1015 
1016  public:
1040  template<class OneSkeletonGraph>
1041  void insert_graph(const OneSkeletonGraph& skel_graph) {
1042  // the simplex tree must be empty
1043  assert(num_simplices() == 0);
1044 
1045  if (boost::num_vertices(skel_graph) == 0) {
1046  return;
1047  }
1048  if (num_edges(skel_graph) == 0) {
1049  dimension_ = 0;
1050  } else {
1051  dimension_ = 1;
1052  }
1053 
1054  root_.members_.reserve(boost::num_vertices(skel_graph));
1055 
1056  typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator v_it,
1057  v_it_end;
1058  for (std::tie(v_it, v_it_end) = boost::vertices(skel_graph); v_it != v_it_end;
1059  ++v_it) {
1060  root_.members_.emplace_hint(
1061  root_.members_.end(), *v_it,
1062  Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it)));
1063  }
1064  std::pair<typename boost::graph_traits<OneSkeletonGraph>::edge_iterator,
1065  typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = boost::edges(skel_graph);
1066  // boost_edges.first is the equivalent to boost_edges.begin()
1067  // boost_edges.second is the equivalent to boost_edges.end()
1068  for (; boost_edges.first != boost_edges.second; boost_edges.first++) {
1069  auto edge = *(boost_edges.first);
1070  auto u = source(edge, skel_graph);
1071  auto v = target(edge, skel_graph);
1072  if (u == v) throw "Self-loops are not simplicial";
1073  // We cannot skip edges with the wrong orientation and expect them to
1074  // come a second time with the right orientation, that does not always
1075  // happen in practice. emplace() should be a NOP when an element with the
1076  // same key is already there, so seeing the same edge multiple times is
1077  // ok.
1078  // Should we actually forbid multiple edges? That would be consistent
1079  // with rejecting self-loops.
1080  if (v < u) std::swap(u, v);
1081  auto sh = find_vertex(u);
1082  if (!has_children(sh)) {
1083  sh->second.assign_children(new Siblings(&root_, sh->first));
1084  }
1085 
1086  sh->second.children()->members().emplace(v,
1087  Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, edge)));
1088  }
1089  }
1090 
1102  void expansion(int max_dim) {
1103  if (max_dim <= 1) return;
1104  dimension_ = max_dim;
1105  for (Dictionary_it root_it = root_.members_.begin();
1106  root_it != root_.members_.end(); ++root_it) {
1107  if (has_children(root_it)) {
1108  siblings_expansion(root_it->second.children(), max_dim - 1);
1109  }
1110  }
1111  dimension_ = max_dim - dimension_;
1112  }
1113 
1114  private:
1116  void siblings_expansion(Siblings * siblings, // must contain elements
1117  int k) {
1118  if (dimension_ > k) {
1119  dimension_ = k;
1120  }
1121  if (k == 0)
1122  return;
1123  Dictionary_it next = siblings->members().begin();
1124  ++next;
1125 
1126 #ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL
1127  thread_local
1128 #endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL
1129  std::vector<std::pair<Vertex_handle, Node> > inter;
1130  for (Dictionary_it s_h = siblings->members().begin();
1131  s_h != siblings->members().end(); ++s_h, ++next) {
1132  Simplex_handle root_sh = find_vertex(s_h->first);
1133  if (has_children(root_sh)) {
1134  intersection(
1135  inter, // output intersection
1136  next, // begin
1137  siblings->members().end(), // end
1138  root_sh->second.children()->members().begin(),
1139  root_sh->second.children()->members().end(),
1140  s_h->second.filtration());
1141  if (inter.size() != 0) {
1142  Siblings * new_sib = new Siblings(siblings, // oncles
1143  s_h->first, // parent
1144  inter); // boost::container::ordered_unique_range_t
1145  inter.clear();
1146  s_h->second.assign_children(new_sib);
1147  siblings_expansion(new_sib, k - 1);
1148  } else {
1149  // ensure the children property
1150  s_h->second.assign_children(siblings);
1151  inter.clear();
1152  }
1153  }
1154  }
1155  }
1156 
1159  static void intersection(std::vector<std::pair<Vertex_handle, Node> >& intersection,
1160  Dictionary_it begin1, Dictionary_it end1,
1161  Dictionary_it begin2, Dictionary_it end2,
1162  Filtration_value filtration_) {
1163  if (begin1 == end1 || begin2 == end2)
1164  return; // ----->>
1165  while (true) {
1166  if (begin1->first == begin2->first) {
1167  Filtration_value filt = (std::max)({begin1->second.filtration(), begin2->second.filtration(), filtration_});
1168  intersection.emplace_back(begin1->first, Node(nullptr, filt));
1169  if (++begin1 == end1 || ++begin2 == end2)
1170  return; // ----->>
1171  } else if (begin1->first < begin2->first) {
1172  if (++begin1 == end1)
1173  return;
1174  } else /* begin1->first > begin2->first */ {
1175  if (++begin2 == end2)
1176  return; // ----->>
1177  }
1178  }
1179  }
1180 
1181  public:
1200  template< typename Blocker >
1201  void expansion_with_blockers(int max_dim, Blocker block_simplex) {
1202  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1203  for (auto& simplex : boost::adaptors::reverse(root_.members())) {
1204  if (has_children(&simplex)) {
1205  siblings_expansion_with_blockers(simplex.second.children(), max_dim, max_dim - 1, block_simplex);
1206  }
1207  }
1208  }
1209 
1210  private:
1212  template< typename Blocker >
1213  void siblings_expansion_with_blockers(Siblings* siblings, int max_dim, int k, Blocker block_simplex) {
1214  if (dimension_ < max_dim - k) {
1215  dimension_ = max_dim - k;
1216  }
1217  if (k == 0)
1218  return;
1219  // No need to go deeper
1220  if (siblings->members().size() < 2)
1221  return;
1222  // Reverse loop starting before the last one for 'next' to be the last one
1223  for (auto simplex = siblings->members().rbegin() + 1; simplex != siblings->members().rend(); simplex++) {
1224  std::vector<std::pair<Vertex_handle, Node> > intersection;
1225  for(auto next = siblings->members().rbegin(); next != simplex; next++) {
1226  bool to_be_inserted = true;
1227  Filtration_value filt = simplex->second.filtration();
1228  // If all the boundaries are present, 'next' needs to be inserted
1229  for (Simplex_handle border : boundary_simplex_range(simplex)) {
1230  Simplex_handle border_child = find_child(border, next->first);
1231  if (border_child == null_simplex()) {
1232  to_be_inserted=false;
1233  break;
1234  }
1235  filt = (std::max)(filt, filtration(border_child));
1236  }
1237  if (to_be_inserted) {
1238  intersection.emplace_back(next->first, Node(nullptr, filt));
1239  }
1240  }
1241  if (intersection.size() != 0) {
1242  // Reverse the order to insert
1243  Siblings * new_sib = new Siblings(siblings, // oncles
1244  simplex->first, // parent
1245  boost::adaptors::reverse(intersection)); // boost::container::ordered_unique_range_t
1246  std::vector<Vertex_handle> blocked_new_sib_vertex_list;
1247  // As all intersections are inserted, we can call the blocker function on all new_sib members
1248  for (auto new_sib_member = new_sib->members().begin();
1249  new_sib_member != new_sib->members().end();
1250  new_sib_member++) {
1251  bool blocker_result = block_simplex(new_sib_member);
1252  // new_sib member has been blocked by the blocker function
1253  // add it to the list to be removed - do not perform it while looping on it
1254  if (blocker_result) {
1255  blocked_new_sib_vertex_list.push_back(new_sib_member->first);
1256  }
1257  }
1258  if (blocked_new_sib_vertex_list.size() == new_sib->members().size()) {
1259  // Specific case where all have to be deleted
1260  delete new_sib;
1261  // ensure the children property
1262  simplex->second.assign_children(siblings);
1263  } else {
1264  for (auto& blocked_new_sib_member : blocked_new_sib_vertex_list) {
1265  new_sib->members().erase(blocked_new_sib_member);
1266  }
1267  // ensure recursive call
1268  simplex->second.assign_children(new_sib);
1269  siblings_expansion_with_blockers(new_sib, max_dim, k - 1, block_simplex);
1270  }
1271  } else {
1272  // ensure the children property
1273  simplex->second.assign_children(siblings);
1274  }
1275  }
1276  }
1277 
1278  /* \private Returns the Simplex_handle composed of the vertex list (from the Simplex_handle), plus the given
1279  * Vertex_handle if the Vertex_handle is found in the Simplex_handle children list.
1280  * Returns null_simplex() if it does not exist
1281  */
1282  Simplex_handle find_child(Simplex_handle sh, Vertex_handle vh) const {
1283  if (!has_children(sh))
1284  return null_simplex();
1285 
1286  Simplex_handle child = sh->second.children()->find(vh);
1287  // Specific case of boost::flat_map does not find, returns boost::flat_map::end()
1288  // in simplex tree we want a null_simplex()
1289  if (child == sh->second.children()->members().end())
1290  return null_simplex();
1291 
1292  return child;
1293  }
1294 
1295  public:
1302  void print_hasse(std::ostream& os) {
1303  os << num_simplices() << " " << std::endl;
1304  for (auto sh : filtration_simplex_range()) {
1305  os << dimension(sh) << " ";
1306  for (auto b_sh : boundary_simplex_range(sh)) {
1307  os << key(b_sh) << " ";
1308  }
1309  os << filtration(sh) << " \n";
1310  }
1311  }
1312 
1313  public:
1322  bool modified = false;
1323  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1324  for (auto& simplex : boost::adaptors::reverse(root_.members())) {
1325  if (has_children(&simplex)) {
1326  modified |= rec_make_filtration_non_decreasing(simplex.second.children());
1327  }
1328  }
1329  return modified;
1330  }
1331 
1332  private:
1337  bool rec_make_filtration_non_decreasing(Siblings * sib) {
1338  bool modified = false;
1339 
1340  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1341  for (auto& simplex : boost::adaptors::reverse(sib->members())) {
1342  // Find the maximum filtration value in the border
1343  Boundary_simplex_range boundary = boundary_simplex_range(&simplex);
1344  Boundary_simplex_iterator max_border = std::max_element(std::begin(boundary), std::end(boundary),
1345  [](Simplex_handle sh1, Simplex_handle sh2) {
1346  return filtration(sh1) < filtration(sh2);
1347  });
1348 
1349  Filtration_value max_filt_border_value = filtration(*max_border);
1350  if (simplex.second.filtration() < max_filt_border_value) {
1351  // Store the filtration modification information
1352  modified = true;
1353  simplex.second.assign_filtration(max_filt_border_value);
1354  }
1355  if (has_children(&simplex)) {
1356  modified |= rec_make_filtration_non_decreasing(simplex.second.children());
1357  }
1358  }
1359  // Make the modified information to be traced by upper call
1360  return modified;
1361  }
1362 
1363  public:
1374  bool prune_above_filtration(Filtration_value filtration) {
1375  return rec_prune_above_filtration(root(), filtration);
1376  }
1377 
1378  private:
1379  bool rec_prune_above_filtration(Siblings* sib, Filtration_value filt) {
1380  auto&& list = sib->members();
1381  auto last = std::remove_if(list.begin(), list.end(), [this,filt](Dit_value_t& simplex) {
1382  if (simplex.second.filtration() <= filt) return false;
1383  if (has_children(&simplex)) rec_delete(simplex.second.children());
1384  // dimension may need to be lowered
1385  dimension_to_be_lowered_ = true;
1386  return true;
1387  });
1388 
1389  bool modified = (last != list.end());
1390  if (last == list.begin() && sib != root()) {
1391  // Removing the whole siblings, parent becomes a leaf.
1392  sib->oncles()->members()[sib->parent()].assign_children(sib->oncles());
1393  delete sib;
1394  // dimension may need to be lowered
1395  dimension_to_be_lowered_ = true;
1396  return true;
1397  } else {
1398  // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones.
1399  list.erase(last, list.end());
1400  for (auto&& simplex : list)
1401  if (has_children(&simplex))
1402  modified |= rec_prune_above_filtration(simplex.second.children(), filt);
1403  }
1404  return modified;
1405  }
1406 
1407  private:
1413  bool lower_upper_bound_dimension() {
1414  // reset automatic detection to recompute
1415  dimension_to_be_lowered_ = false;
1416  int new_dimension = -1;
1417  // Browse the tree from the left to the right as higher dimension cells are more likely on the left part of the tree
1418  for (Simplex_handle sh : complex_simplex_range()) {
1419 #ifdef DEBUG_TRACES
1420  for (auto vertex : simplex_vertex_range(sh)) {
1421  std::cout << " " << vertex;
1422  }
1423  std::cout << std::endl;
1424 #endif // DEBUG_TRACES
1425 
1426  int sh_dimension = dimension(sh);
1427  if (sh_dimension >= dimension_)
1428  // Stop browsing as soon as the dimension is reached, no need to go furter
1429  return false;
1430  new_dimension = (std::max)(new_dimension, sh_dimension);
1431  }
1432  dimension_ = new_dimension;
1433  return true;
1434  }
1435 
1436 
1437  public:
1447  void remove_maximal_simplex(Simplex_handle sh) {
1448  // Guarantee the simplex has no children
1449  GUDHI_CHECK(!has_children(sh),
1450  std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children"));
1451 
1452  // Simplex is a leaf, it means the child is the Siblings owning the leaf
1453  Siblings* child = sh->second.children();
1454 
1455  if ((child->size() > 1) || (child == root())) {
1456  // Not alone, just remove it from members
1457  // Special case when child is the root of the simplex tree, just remove it from members
1458  child->erase(sh);
1459  } else {
1460  // Sibling is emptied : must be deleted, and its parent must point on his own Sibling
1461  child->oncles()->members().at(child->parent()).assign_children(child->oncles());
1462  delete child;
1463  // dimension may need to be lowered
1464  dimension_to_be_lowered_ = true;
1465  }
1466  }
1467 
1468  private:
1469  Vertex_handle null_vertex_;
1472  Siblings root_;
1474  std::vector<Simplex_handle> filtration_vect_;
1476  int dimension_;
1477  bool dimension_to_be_lowered_ = false;
1478 };
1479 
1480 // Print a Simplex_tree in os.
1481 template<typename...T>
1482 std::ostream& operator<<(std::ostream & os, Simplex_tree<T...> & st) {
1483  for (auto sh : st.filtration_simplex_range()) {
1484  os << st.dimension(sh) << " ";
1485  for (auto v : st.simplex_vertex_range(sh)) {
1486  os << v << " ";
1487  }
1488  os << st.filtration(sh) << "\n"; // TODO(VR): why adding the key ?? not read ?? << " " << st.key(sh) << " \n";
1489  }
1490  return os;
1491 }
1492 
1493 template<typename...T>
1494 std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
1495  typedef Simplex_tree<T...> ST;
1496  std::vector<typename ST::Vertex_handle> simplex;
1497  typename ST::Filtration_value fil;
1498  int max_dim = -1;
1499  while (read_simplex(is, simplex, fil)) {
1500  // read all simplices in the file as a list of vertices
1501  // Warning : simplex_size needs to be casted in int - Can be 0
1502  int dim = static_cast<int> (simplex.size() - 1);
1503  if (max_dim < dim) {
1504  max_dim = dim;
1505  }
1506  // insert every simplex in the simplex tree
1507  st.insert_simplex(simplex, fil);
1508  simplex.clear();
1509  }
1510  st.set_dimension(max_dim);
1511 
1512  return is;
1513 }
1514 
1520  typedef linear_indexing_tag Indexing_tag;
1521  typedef int Vertex_handle;
1522  typedef double Filtration_value;
1523  typedef std::uint32_t Simplex_key;
1524  static const bool store_key = true;
1525  static const bool store_filtration = true;
1526  static const bool contiguous_vertices = false;
1527 };
1528 
1536  typedef linear_indexing_tag Indexing_tag;
1537  typedef int Vertex_handle;
1538  typedef float Filtration_value;
1539  typedef std::uint32_t Simplex_key;
1540  static const bool store_key = true;
1541  static const bool store_filtration = true;
1542  static const bool contiguous_vertices = true;
1543 };
1544  // end defgroup simplex_tree
1546 
1547 } // namespace Gudhi
1548 
1549 #endif // SIMPLEX_TREE_H_
Simplex_tree_skeleton_simplex_iterator< Simplex_tree > Skeleton_simplex_iterator
Iterator over the simplices of the skeleton of the simplicial complex, for a given dimension...
Definition: Simplex_tree.h:174
Simplex_tree & operator=(const Simplex_tree &complex_source)
User-defined copy assignment reproduces the whole tree structure.
Definition: Simplex_tree.h:314
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree...
Definition: Simplex_tree.h:123
bool prune_above_filtration(Filtration_value filtration)
Prune above filtration value given as parameter.
Definition: Simplex_tree.h:1374
void expansion(int max_dim)
Expands the Simplex_tree containing only its one skeleton until dimension max_dim.
Definition: Simplex_tree.h:1102
Filtration_simplex_range::const_iterator Filtration_simplex_iterator
Iterator over the simplices of the simplicial complex, ordered by the filtration. ...
Definition: Simplex_tree.h:183
Tag for a linear ordering of simplices.
Definition: indexing_tag.h:20
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:60
Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:830
std::pair< Simplex_handle, bool > insert_simplex_and_subfaces(const InputVertexRange &Nsimplex, Filtration_value filtration=0)
Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of Vertex_handles...
Definition: Simplex_tree.h:750
void assign_key(Simplex_handle sh, Simplex_key key)
Assign a value &#39;key&#39; to the key of the simplex represented by the Simplex_handle &#39;sh&#39;.
Definition: Simplex_tree.h:816
bool read_simplex(std::istream &in_, std::vector< Vertex_handle > &simplex, Filtration_value &fil)
Read a face from a file.
Definition: reader_utils.h:158
bool operator==(Simplex_tree &st2)
Checks if two simplex trees are equal.
Definition: Simplex_tree.h:422
Concept describing an indexing scheme (see FilteredComplex) for applying continuous maps to a cell co...
Definition: IndexingTag.h:18
static Simplex_key key(Simplex_handle sh)
Returns the key associated to a simplex.
Definition: Simplex_tree.h:459
static Simplex_handle null_simplex()
Returns a Simplex_handle different from all Simplex_handles associated to the simplices in the simpli...
Definition: Simplex_tree.h:498
static constexpr bool contiguous_vertices
If true, the list of vertices present in the complex must always be 0, ..., num_vertices-1, without any hole.
Definition: SimplexTreeOptions.h:29
boost::iterator_range< Complex_vertex_iterator > Complex_vertex_range
Range over the vertices of the simplicial complex.
Definition: Simplex_tree.h:149
Vertex_handle null_vertex() const
Returns a Vertex_handle different from all Vertex_handles associated to the vertices of the simplicia...
Definition: Simplex_tree.h:510
Simplex_tree_simplex_vertex_iterator< Simplex_tree > Simplex_vertex_iterator
Iterator over the vertices of a simplex.
Definition: Simplex_tree.h:153
Definition: SimplicialComplexForAlpha.h:14
void print_hasse(std::ostream &os)
Write the hasse diagram of the simplicial complex in os.
Definition: Simplex_tree.h:1302
Key type used as simplex identifier.
Definition: SimplexKey.h:15
Siblings * root()
Definition: Simplex_tree.h:839
Options::Simplex_key Simplex_key
Key associated to each simplex.
Definition: Simplex_tree.h:71
bool operator!=(Simplex_tree &st2)
Checks if two simplex trees are different.
Definition: Simplex_tree.h:430
bool make_filtration_non_decreasing()
This function ensures that each simplex has a higher filtration value than its faces by increasing th...
Definition: Simplex_tree.h:1321
std::vector< Simplex_handle > Filtration_simplex_range
Range over the simplices of the simplicial complex, ordered by the filtration.
Definition: Simplex_tree.h:179
int dimension()
Returns the dimension of the simplicial complex.
Definition: Simplex_tree.h:562
Filtration_simplex_range const & filtration_simplex_range(Indexing_tag=Indexing_tag())
Returns a range over the simplices of the simplicial complex, in the order of the filtration...
Definition: Simplex_tree.h:236
void initialize_filtration()
Initializes the filtrations, i.e. sort the simplices according to their order in the filtration and i...
Definition: Simplex_tree.h:862
Simplex_handle find(const InputVertexRange &s)
Given a range of Vertex_handles, returns the Simplex_handle of the simplex in the simplicial complex ...
Definition: Simplex_tree.h:584
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension)
Compute the cofaces of a n simplex.
Definition: Simplex_tree.h:954
Complex_simplex_range complex_simplex_range()
Returns a range over the simplices of the simplicial complex.
Definition: Simplex_tree.h:202
Concept of the template parameter for the class Gudhi::Simplex_tree<SimplexTreeOptions>.
Definition: SimplexTreeOptions.h:15
size_t num_vertices() const
Returns the number of vertices in the complex.
Definition: Simplex_tree.h:515
void assign_filtration(Simplex_handle sh, Filtration_value fv)
Sets the filtration value of a simplex.
Definition: Simplex_tree.h:488
std::pair< Simplex_handle, Simplex_handle > endpoints(Simplex_handle sh)
Definition: Simplex_tree.h:823
Boundary_simplex_range boundary_simplex_range(SimplexHandle sh)
Returns a range over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:270
Complex_vertex_range complex_vertex_range()
Returns a range over the vertices of the simplicial complex. The order is increasing according to < o...
Definition: Simplex_tree.h:191
Simplex_vertex_range simplex_vertex_range(Simplex_handle sh)
Returns a range over the vertices of a simplex.
Definition: Simplex_tree.h:249
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition: Simplex_tree.h:75
Simplex_tree(Simplex_tree &&complex_source)
User-defined move constructor relocates the whole tree structure.
Definition: Simplex_tree.h:297
Simplex_tree & operator=(Simplex_tree &&complex_source)
User-defined move assignment relocates the whole tree structure.
Definition: Simplex_tree.h:331
Skeleton_simplex_range skeleton_simplex_range(int dim)
Returns a range over the simplices of the dim-skeleton of the simplicial complex. ...
Definition: Simplex_tree.h:216
boost::iterator_range< Boundary_simplex_iterator > Boundary_simplex_range
Range over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:163
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:571
Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex)
Compute the star of a n simplex.
Definition: Simplex_tree.h:943
void set_dimension(int dimension)
Set a dimension for the simplicial complex.
Definition: Simplex_tree.h:847
int upper_bound_dimension() const
Returns an upper bound on the dimension of the simplicial complex.
Definition: Simplex_tree.h:554
int dimension(Simplex_handle sh)
Returns the dimension of a simplex.
Definition: Simplex_tree.h:543
static Simplex_key null_key()
Returns a key different for all keys associated to the simplices of the simplicial complex...
Definition: Simplex_tree.h:504
static Filtration_value filtration(Simplex_handle sh)
Returns the filtration value of a simplex.
Definition: Simplex_tree.h:477
Definition: Simplex_tree.h:1535
Simplex_tree(const Simplex_tree &complex_source)
User-defined copy constructor reproduces the whole tree structure.
Definition: Simplex_tree.h:287
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
boost::transform_iterator< return_first, Dictionary_it > Complex_vertex_iterator
Iterator over the vertices of the simplicial complex.
Definition: Simplex_tree.h:147
~Simplex_tree()
Destructor; deallocates the whole tree structure.
Definition: Simplex_tree.h:309
void remove_maximal_simplex(Simplex_handle sh)
Remove a maximal simplex.
Definition: Simplex_tree.h:1447
static const bool store_filtration
If true, each simplex has extra storage for one Filtration_value, and this value is propagated by ope...
Definition: SimplexTreeOptions.h:27
size_t num_simplices()
returns the number of simplices in the simplex_tree.
Definition: Simplex_tree.h:521
boost::iterator_range< Complex_simplex_iterator > Complex_simplex_range
Range over the simplices of the simplicial complex.
Definition: Simplex_tree.h:169
Options::Filtration_value Filtration_value
Type for the value of the filtration function.
Definition: Simplex_tree.h:67
Simplex_tree()
Constructs an empty simplex tree.
Definition: Simplex_tree.h:280
Simplex_tree_boundary_simplex_iterator< Simplex_tree > Boundary_simplex_iterator
Iterator over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:161
boost::iterator_range< Skeleton_simplex_iterator > Skeleton_simplex_range
Range over the simplices of the skeleton of the simplicial complex, for a given dimension.
Definition: Simplex_tree.h:177
Simplex_tree_complex_simplex_iterator< Simplex_tree > Complex_simplex_iterator
Iterator over the simplices of the simplicial complex.
Definition: Simplex_tree.h:167
void insert_graph(const OneSkeletonGraph &skel_graph)
Inserts a 1-skeleton in an empty Simplex_tree.
Definition: Simplex_tree.h:1041
Simplex_handle simplex(Simplex_key idx) const
Returns the simplex that has index idx in the filtration.
Definition: Simplex_tree.h:468
This file includes common file reader for GUDHI.
boost::iterator_range< Simplex_vertex_iterator > Simplex_vertex_range
Range over the vertices of a simplex.
Definition: Simplex_tree.h:155
std::pair< Simplex_handle, bool > insert_simplex(const InputVertexRange &simplex, Filtration_value filtration=0)
Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex.
Definition: Simplex_tree.h:721
void expansion_with_blockers(int max_dim, Blocker block_simplex)
Expands a simplex tree containing only a graph. Simplices corresponding to cliques in the graph are a...
Definition: Simplex_tree.h:1201
std::vector< Simplex_handle > Cofaces_simplex_range
Range over the cofaces of a simplex.
Definition: Simplex_tree.h:157
GUDHI  Version 3.1.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Feb 7 2020 16:35:36 for GUDHI by Doxygen 1.8.13