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 #include <boost/container/static_vector.hpp>
28 
29 #ifdef GUDHI_USE_TBB
30 #ifndef Q_MOC_RUN
31 #include <tbb/parallel_sort.h>
32 #endif
33 #endif
34 
35 #include <utility>
36 #include <vector>
37 #include <functional> // for greater<>
38 #include <stdexcept>
39 #include <limits> // Inf
40 #include <initializer_list>
41 #include <algorithm> // for std::max
42 #include <cstdint> // for std::uint32_t
43 #include <iterator> // for std::distance
44 
45 namespace Gudhi {
46 
59 enum class Extended_simplex_type {UP, DOWN, EXTRA};
60 
61 struct Simplex_tree_options_full_featured;
62 
76 template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>
77 class Simplex_tree {
78  public:
80  typedef typename Options::Indexing_tag Indexing_tag;
93 
94  /* Type of node in the simplex tree. */
95  typedef Simplex_tree_node_explicit_storage<Simplex_tree> Node;
96  /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */
97  // Note: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a
98  // flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and
99  // Simplex_key next to each other).
100  typedef typename boost::container::flat_map<Vertex_handle, Node> Dictionary;
101 
102  /* \brief Set of nodes sharing a same parent in the simplex tree. */
103  /* \brief Set of nodes sharing a same parent in the simplex tree. */
104  typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings;
105 
106 
107 
108  struct Key_simplex_base_real {
109  Key_simplex_base_real() : key_(-1) {}
110  void assign_key(Simplex_key k) { key_ = k; }
111  Simplex_key key() const { return key_; }
112  private:
113  Simplex_key key_;
114  };
115  struct Key_simplex_base_dummy {
116  Key_simplex_base_dummy() {}
117  // Undefined so it will not link
118  void assign_key(Simplex_key);
119  Simplex_key key() const;
120  };
121  struct Extended_filtration_data {
122  Filtration_value minval;
123  Filtration_value maxval;
124  Extended_filtration_data(){}
125  Extended_filtration_data(Filtration_value vmin, Filtration_value vmax): minval(vmin), maxval(vmax) {}
126  };
127  typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type
128  Key_simplex_base;
129 
130  struct Filtration_simplex_base_real {
131  Filtration_simplex_base_real() : filt_(0) {}
132  void assign_filtration(Filtration_value f) { filt_ = f; }
133  Filtration_value filtration() const { return filt_; }
134  private:
135  Filtration_value filt_;
136  };
137  struct Filtration_simplex_base_dummy {
138  Filtration_simplex_base_dummy() {}
139  void assign_filtration(Filtration_value GUDHI_CHECK_code(f)) { GUDHI_CHECK(f == 0, "filtration value specified for a complex that does not store them"); }
140  Filtration_value filtration() const { return 0; }
141  };
142  typedef typename std::conditional<Options::store_filtration, Filtration_simplex_base_real,
143  Filtration_simplex_base_dummy>::type Filtration_simplex_base;
144 
145  public:
151  typedef typename Dictionary::iterator Simplex_handle;
152 
153  private:
154  typedef typename Dictionary::iterator Dictionary_it;
155  typedef typename Dictionary_it::value_type Dit_value_t;
156 
157  struct return_first {
158  Vertex_handle operator()(const Dit_value_t& p_sh) const {
159  return p_sh.first;
160  }
161  };
162 
163  public:
175  typedef boost::transform_iterator<return_first, Dictionary_it> Complex_vertex_iterator;
177  typedef boost::iterator_range<Complex_vertex_iterator> Complex_vertex_range;
181  typedef Simplex_tree_simplex_vertex_iterator<Simplex_tree> Simplex_vertex_iterator;
183  typedef boost::iterator_range<Simplex_vertex_iterator> Simplex_vertex_range;
185  typedef std::vector<Simplex_handle> Cofaces_simplex_range;
189  typedef Simplex_tree_boundary_simplex_iterator<Simplex_tree> Boundary_simplex_iterator;
191  typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
195  typedef Simplex_tree_complex_simplex_iterator<Simplex_tree> Complex_simplex_iterator;
197  typedef boost::iterator_range<Complex_simplex_iterator> Complex_simplex_range;
202  typedef Simplex_tree_skeleton_simplex_iterator<Simplex_tree> Skeleton_simplex_iterator;
205  typedef boost::iterator_range<Skeleton_simplex_iterator> Skeleton_simplex_range;
207  typedef std::vector<Simplex_handle> Filtration_simplex_range;
211  typedef typename Filtration_simplex_range::const_iterator Filtration_simplex_iterator;
212 
213  /* @} */ // end name range and iterator types
220  return Complex_vertex_range(
221  boost::make_transform_iterator(root_.members_.begin(), return_first()),
222  boost::make_transform_iterator(root_.members_.end(), return_first()));
223  }
224 
233  }
234 
247  }
248 
266  return filtration_vect_;
267  }
268 
276  GUDHI_CHECK(sh != null_simplex(), "empty simplex");
279  }
280 
295  template<class SimplexHandle>
299  }
300  // end range and iterator methods
307  : null_vertex_(-1),
308  root_(nullptr, null_vertex_),
309  filtration_vect_(),
310  dimension_(-1) { }
311 
313  Simplex_tree(const Simplex_tree& complex_source) {
314 #ifdef DEBUG_TRACES
315  std::clog << "Simplex_tree copy constructor" << std::endl;
316 #endif // DEBUG_TRACES
317  copy_from(complex_source);
318  }
319 
323  Simplex_tree(Simplex_tree && complex_source) {
324 #ifdef DEBUG_TRACES
325  std::clog << "Simplex_tree move constructor" << std::endl;
326 #endif // DEBUG_TRACES
327  move_from(complex_source);
328 
329  // just need to set dimension_ on source to make it available again
330  // (filtration_vect_ and members are already set from the move)
331  complex_source.dimension_ = -1;
332  }
333 
336  root_members_recursive_deletion();
337  }
338 
340  Simplex_tree& operator= (const Simplex_tree& complex_source) {
341 #ifdef DEBUG_TRACES
342  std::clog << "Simplex_tree copy assignment" << std::endl;
343 #endif // DEBUG_TRACES
344  // Self-assignment detection
345  if (&complex_source != this) {
346  // We start by deleting root_ if not empty
347  root_members_recursive_deletion();
348 
349  copy_from(complex_source);
350  }
351  return *this;
352  }
353 
357  Simplex_tree& operator=(Simplex_tree&& complex_source) {
358 #ifdef DEBUG_TRACES
359  std::clog << "Simplex_tree move assignment" << std::endl;
360 #endif // DEBUG_TRACES
361  // Self-assignment detection
362  if (&complex_source != this) {
363  // root_ deletion in case it was not empty
364  root_members_recursive_deletion();
365 
366  move_from(complex_source);
367  }
368  return *this;
369  } // end constructor/destructor
371 
372  private:
373  // Copy from complex_source to "this"
374  void copy_from(const Simplex_tree& complex_source) {
375  null_vertex_ = complex_source.null_vertex_;
376  filtration_vect_.clear();
377  dimension_ = complex_source.dimension_;
378  auto root_source = complex_source.root_;
379 
380  // root members copy
381  root_.members() = Dictionary(boost::container::ordered_unique_range, root_source.members().begin(), root_source.members().end());
382  // Needs to reassign children
383  for (auto& map_el : root_.members()) {
384  map_el.second.assign_children(&root_);
385  }
386  rec_copy(&root_, &root_source);
387  }
388 
390  void rec_copy(Siblings *sib, Siblings *sib_source) {
391  for (auto sh = sib->members().begin(), sh_source = sib_source->members().begin();
392  sh != sib->members().end(); ++sh, ++sh_source) {
393  if (has_children(sh_source)) {
394  Siblings * newsib = new Siblings(sib, sh_source->first);
395  newsib->members_.reserve(sh_source->second.children()->members().size());
396  for (auto & child : sh_source->second.children()->members())
397  newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(newsib, child.second.filtration()));
398  rec_copy(newsib, sh_source->second.children());
399  sh->second.assign_children(newsib);
400  }
401  }
402  }
403 
404  // Move from complex_source to "this"
405  void move_from(Simplex_tree& complex_source) {
406  null_vertex_ = std::move(complex_source.null_vertex_);
407  root_ = std::move(complex_source.root_);
408  filtration_vect_ = std::move(complex_source.filtration_vect_);
409  dimension_ = std::move(complex_source.dimension_);
410 
411  // Need to update root members (children->oncles and children need to point on the new root pointer)
412  for (auto& map_el : root_.members()) {
413  if (map_el.second.children() != &(complex_source.root_)) {
414  // reset children->oncles with the moved root_ pointer value
415  map_el.second.children()->oncles_ = &root_;
416  } else {
417  // if simplex is of dimension 0, oncles_ shall be nullptr
418  GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr,
419  std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree"));
420  // and children points on root_ - to be moved
421  map_el.second.assign_children(&root_);
422  }
423  }
424  }
425 
426  // delete all root_.members() recursively
427  void root_members_recursive_deletion() {
428  for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) {
429  if (has_children(sh)) {
430  rec_delete(sh->second.children());
431  }
432  }
433  root_.members().clear();
434  }
435 
436  // Recursive deletion
437  void rec_delete(Siblings * sib) {
438  for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
439  if (has_children(sh)) {
440  rec_delete(sh->second.children());
441  }
442  }
443  delete sib;
444  }
445 
446  public:
449  if ((null_vertex_ != st2.null_vertex_) ||
450  (dimension_ != st2.dimension_))
451  return false;
452  return rec_equal(&root_, &st2.root_);
453  }
454 
457  return (!(*this == st2));
458  }
459 
460  private:
462  bool rec_equal(Siblings* s1, Siblings* s2) {
463  if (s1->members().size() != s2->members().size())
464  return false;
465  for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin();
466  (sh1 != s1->members().end() && sh2 != s2->members().end()); ++sh1, ++sh2) {
467  if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration())
468  return false;
469  if (has_children(sh1) != has_children(sh2))
470  return false;
471  // Recursivity on children only if both have children
472  else if (has_children(sh1))
473  if (!rec_equal(sh1->second.children(), sh2->second.children()))
474  return false;
475  }
476  return true;
477  }
478 
483  static Filtration_value filtration_(Simplex_handle sh) {
484  GUDHI_CHECK (sh != null_simplex(), "null simplex");
485  return sh->second.filtration();
486  }
487 
488  public:
495  return sh->second.key();
496  }
497 
503  return filtration_vect_[idx];
504  }
505 
512  if (sh != null_simplex()) {
513  return sh->second.filtration();
514  } else {
515  return std::numeric_limits<Filtration_value>::infinity();
516  }
517  }
518 
523  GUDHI_CHECK(sh != null_simplex(),
524  std::invalid_argument("Simplex_tree::assign_filtration - cannot assign filtration on null_simplex"));
525  sh->second.assign_filtration(fv);
526  }
527 
533  return Dictionary_it(nullptr);
534  }
535 
538  return -1;
539  }
540 
544  return null_vertex_;
545  }
546 
548  size_t num_vertices() const {
549  return root_.members_.size();
550  }
551 
552  public:
554  size_t num_simplices() {
555  return num_simplices(&root_);
556  }
557 
558  private:
560  size_t num_simplices(Siblings * sib) {
561  auto sib_begin = sib->members().begin();
562  auto sib_end = sib->members().end();
563  size_t simplices_number = sib_end - sib_begin;
564  for (auto sh = sib_begin; sh != sib_end; ++sh) {
565  if (has_children(sh)) {
566  simplices_number += num_simplices(sh->second.children());
567  }
568  }
569  return simplices_number;
570  }
571 
572  public:
577  Siblings * curr_sib = self_siblings(sh);
578  int dim = 0;
579  while (curr_sib != nullptr) {
580  ++dim;
581  curr_sib = curr_sib->oncles();
582  }
583  return dim - 1;
584  }
585 
587  int upper_bound_dimension() const {
588  return dimension_;
589  }
590 
595  int dimension() {
596  if (dimension_to_be_lowered_)
597  lower_upper_bound_dimension();
598  return dimension_;
599  }
600 
603  template<class SimplexHandle>
604  bool has_children(SimplexHandle sh) const {
605  // Here we rely on the root using null_vertex(), which cannot match any real vertex.
606  return (sh->second.children()->parent() == sh->first);
607  }
608 
616  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
617  Simplex_handle find(const InputVertexRange & s) {
618  auto first = std::begin(s);
619  auto last = std::end(s);
620 
621  if (first == last)
622  return null_simplex(); // ----->>
623 
624  // Copy before sorting
625  std::vector<Vertex_handle> copy(first, last);
626  std::sort(std::begin(copy), std::end(copy));
627  return find_simplex(copy);
628  }
629 
630  private:
632  Simplex_handle find_simplex(const std::vector<Vertex_handle> & simplex) {
633  Siblings * tmp_sib = &root_;
634  Dictionary_it tmp_dit;
635  auto vi = simplex.begin();
637  // Equivalent to the first iteration of the normal loop
638  GUDHI_CHECK(contiguous_vertices(), "non-contiguous vertices");
639  Vertex_handle v = *vi++;
640  if(v < 0 || v >= static_cast<Vertex_handle>(root_.members_.size()))
641  return null_simplex();
642  tmp_dit = root_.members_.begin() + v;
643  if (vi == simplex.end())
644  return tmp_dit;
645  if (!has_children(tmp_dit))
646  return null_simplex();
647  tmp_sib = tmp_dit->second.children();
648  }
649  for (;;) {
650  tmp_dit = tmp_sib->members_.find(*vi++);
651  if (tmp_dit == tmp_sib->members_.end())
652  return null_simplex();
653  if (vi == simplex.end())
654  return tmp_dit;
655  if (!has_children(tmp_dit))
656  return null_simplex();
657  tmp_sib = tmp_dit->second.children();
658  }
659  }
660 
663  Simplex_handle find_vertex(Vertex_handle v) {
665  assert(contiguous_vertices());
666  return root_.members_.begin() + v;
667  } else {
668  return root_.members_.find(v);
669  }
670  }
671 
672  public:
674  bool contiguous_vertices() const {
675  if (root_.members_.empty()) return true;
676  if (root_.members_.begin()->first != 0) return false;
677  if (std::prev(root_.members_.end())->first != static_cast<Vertex_handle>(root_.members_.size() - 1)) return false;
678  return true;
679  }
680 
681  private:
696  std::pair<Simplex_handle, bool> insert_vertex_vector(const std::vector<Vertex_handle>& simplex,
698  Siblings * curr_sib = &root_;
699  std::pair<Simplex_handle, bool> res_insert;
700  auto vi = simplex.begin();
701  for (; vi != simplex.end() - 1; ++vi) {
702  GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
703  res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration));
704  if (!(has_children(res_insert.first))) {
705  res_insert.first->second.assign_children(new Siblings(curr_sib, *vi));
706  }
707  curr_sib = res_insert.first->second.children();
708  }
709  GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
710  res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration));
711  if (!res_insert.second) {
712  // if already in the complex
713  if (res_insert.first->second.filtration() > filtration) {
714  // if filtration value modified
715  res_insert.first->second.assign_filtration(filtration);
716  return res_insert;
717  }
718  // if filtration value unchanged
719  return std::pair<Simplex_handle, bool>(null_simplex(), false);
720  }
721  // otherwise the insertion has succeeded - size is a size_type
722  if (static_cast<int>(simplex.size()) - 1 > dimension_) {
723  // Update dimension if needed
724  dimension_ = static_cast<int>(simplex.size()) - 1;
725  }
726  return res_insert;
727  }
728 
729  public:
753  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
754  std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex,
756  auto first = std::begin(simplex);
757  auto last = std::end(simplex);
758 
759  if (first == last)
760  return std::pair<Simplex_handle, bool>(null_simplex(), true); // ----->>
761 
762  // Copy before sorting
763  std::vector<Vertex_handle> copy(first, last);
764  std::sort(std::begin(copy), std::end(copy));
765  return insert_vertex_vector(copy, filtration);
766  }
767 
782  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
783  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex,
785  auto first = std::begin(Nsimplex);
786  auto last = std::end(Nsimplex);
787 
788  if (first == last)
789  return { null_simplex(), true }; // FIXME: false would make more sense to me.
790 
791  thread_local std::vector<Vertex_handle> copy;
792  copy.clear();
793  copy.insert(copy.end(), first, last);
794  std::sort(copy.begin(), copy.end());
795  auto last_unique = std::unique(copy.begin(), copy.end());
796  copy.erase(last_unique, copy.end());
797  GUDHI_CHECK_code(
798  for (Vertex_handle v : copy)
799  GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
800  )
801  // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
802  dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(copy.begin(), copy.end())) - 1);
803 
804  return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration);
805  }
806 
807  private:
808  // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
809  template<class ForwardVertexIterator>
810  std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
811  ForwardVertexIterator first,
812  ForwardVertexIterator last,
813  Filtration_value filt) {
814  // An alternative strategy would be:
815  // - try to find the complete simplex, if found (and low filtration) exit
816  // - insert all the vertices at once in sib
817  // - loop over those (new or not) simplices, with a recursive call(++first, last)
818  Vertex_handle vertex_one = *first;
819  auto&& dict = sib->members();
820  auto insertion_result = dict.emplace(vertex_one, Node(sib, filt));
821  Simplex_handle simplex_one = insertion_result.first;
822  bool one_is_new = insertion_result.second;
823  if (!one_is_new) {
824  if (filtration(simplex_one) > filt) {
825  assign_filtration(simplex_one, filt);
826  } else {
827  // FIXME: this interface makes no sense, and it doesn't seem to be tested.
828  insertion_result.first = null_simplex();
829  }
830  }
831  if (++first == last) return insertion_result;
832  if (!has_children(simplex_one))
833  // TODO: have special code here, we know we are building the whole subtree from scratch.
834  simplex_one->second.assign_children(new Siblings(sib, vertex_one));
835  auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt);
836  // No need to continue if the full simplex was already there with a low enough filtration value.
837  if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt);
838  return res;
839  }
840 
841  public:
845  sh->second.assign_key(key);
846  }
847 
851  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
852  assert(dimension(sh) == 1);
853  return { find_vertex(sh->first), find_vertex(self_siblings(sh)->parent()) };
854  }
855 
857  template<class SimplexHandle>
858  static Siblings* self_siblings(SimplexHandle sh) {
859  if (sh->second.children()->parent() == sh->first)
860  return sh->second.children()->oncles();
861  else
862  return sh->second.children();
863  }
864 
865  public:
867  Siblings * root() {
868  return &root_;
869  }
870 
876  dimension_to_be_lowered_ = false;
877  dimension_ = dimension;
878  }
879 
880  public:
889  filtration_vect_.clear();
890  filtration_vect_.reserve(num_simplices());
892  filtration_vect_.push_back(sh);
893 
894  /* We use stable_sort here because with libstdc++ it is faster than sort.
895  * is_before_in_filtration is now a total order, but we used to call
896  * stable_sort for the following heuristic:
897  * The use of a depth-first traversal of the simplex tree, provided by
898  * complex_simplex_range(), combined with a stable sort is meant to
899  * optimize the order of simplices with same filtration value. The
900  * heuristic consists in inserting the cofaces of a simplex as soon as
901  * possible.
902  */
903 #ifdef GUDHI_USE_TBB
904  tbb::parallel_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
905 #else
906  std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
907 #endif
908  }
913  if (filtration_vect_.empty()) {
915  }
916  }
922  filtration_vect_.clear();
923  }
924 
925  private:
938  void rec_coface(std::vector<Vertex_handle> &vertices, Siblings *curr_sib, int curr_nbVertices,
939  std::vector<Simplex_handle>& cofaces, bool star, int nbVertices) {
940  if (!(star || curr_nbVertices <= nbVertices)) // dimension of actual simplex <= nbVertices
941  return;
942  for (Simplex_handle simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) {
943  if (vertices.empty()) {
944  // If we reached the end of the vertices, and the simplex has more vertices than the given simplex
945  // => we found a coface
946 
947  // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices
948  bool addCoface = (star || curr_nbVertices == nbVertices);
949  if (addCoface)
950  cofaces.push_back(simplex);
951  if ((!addCoface || star) && has_children(simplex)) // Rec call
952  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
953  } else {
954  if (simplex->first == vertices.back()) {
955  // If curr_sib matches with the top vertex
956  bool equalDim = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices
957  bool addCoface = vertices.size() == 1 && equalDim;
958  if (addCoface)
959  cofaces.push_back(simplex);
960  if ((!addCoface || star) && has_children(simplex)) {
961  // Rec call
962  Vertex_handle tmp = vertices.back();
963  vertices.pop_back();
964  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
965  vertices.push_back(tmp);
966  }
967  } else if (simplex->first > vertices.back()) {
968  return;
969  } else {
970  // (simplex->first < vertices.back()
971  if (has_children(simplex))
972  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
973  }
974  }
975  }
976  }
977 
978  public:
985  return cofaces_simplex_range(simplex, 0);
986  }
987 
996  Cofaces_simplex_range cofaces;
997  // codimension must be positive or null integer
998  assert(codimension >= 0);
1000  std::vector<Vertex_handle> copy(rg.begin(), rg.end());
1001  if (codimension + static_cast<int>(copy.size()) > dimension_ + 1 ||
1002  (codimension == 0 && static_cast<int>(copy.size()) > dimension_)) // n+codimension greater than dimension_
1003  return cofaces;
1004  // must be sorted in decreasing order
1005  assert(std::is_sorted(copy.begin(), copy.end(), std::greater<Vertex_handle>()));
1006  bool star = codimension == 0;
1007  rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast<int>(copy.size()));
1008  return cofaces;
1009  }
1010 
1011  private:
1019  bool reverse_lexicographic_order(Simplex_handle sh1, Simplex_handle sh2) {
1022  Simplex_vertex_iterator it1 = rg1.begin();
1023  Simplex_vertex_iterator it2 = rg2.begin();
1024  while (it1 != rg1.end() && it2 != rg2.end()) {
1025  if (*it1 == *it2) {
1026  ++it1;
1027  ++it2;
1028  } else {
1029  return *it1 < *it2;
1030  }
1031  }
1032  return ((it1 == rg1.end()) && (it2 != rg2.end()));
1033  }
1034 
1041  struct is_before_in_filtration {
1042  explicit is_before_in_filtration(Simplex_tree * st)
1043  : st_(st) { }
1044 
1045  bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const {
1046  // Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
1047  if (sh1->second.filtration() != sh2->second.filtration()) {
1048  return sh1->second.filtration() < sh2->second.filtration();
1049  }
1050  // is sh1 a proper subface of sh2
1051  return st_->reverse_lexicographic_order(sh1, sh2);
1052  }
1053 
1054  Simplex_tree * st_;
1055  };
1056 
1057  public:
1081  template<class OneSkeletonGraph>
1082  void insert_graph(const OneSkeletonGraph& skel_graph) {
1083  // the simplex tree must be empty
1084  assert(num_simplices() == 0);
1085 
1086  if (boost::num_vertices(skel_graph) == 0) {
1087  return;
1088  }
1089  if (num_edges(skel_graph) == 0) {
1090  dimension_ = 0;
1091  } else {
1092  dimension_ = 1;
1093  }
1094 
1095  root_.members_.reserve(boost::num_vertices(skel_graph));
1096 
1097  typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator v_it,
1098  v_it_end;
1099  for (std::tie(v_it, v_it_end) = boost::vertices(skel_graph); v_it != v_it_end;
1100  ++v_it) {
1101  root_.members_.emplace_hint(
1102  root_.members_.end(), *v_it,
1103  Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it)));
1104  }
1105  std::pair<typename boost::graph_traits<OneSkeletonGraph>::edge_iterator,
1106  typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = boost::edges(skel_graph);
1107  // boost_edges.first is the equivalent to boost_edges.begin()
1108  // boost_edges.second is the equivalent to boost_edges.end()
1109  for (; boost_edges.first != boost_edges.second; boost_edges.first++) {
1110  auto edge = *(boost_edges.first);
1111  auto u = source(edge, skel_graph);
1112  auto v = target(edge, skel_graph);
1113  if (u == v) throw "Self-loops are not simplicial";
1114  // We cannot skip edges with the wrong orientation and expect them to
1115  // come a second time with the right orientation, that does not always
1116  // happen in practice. emplace() should be a NOP when an element with the
1117  // same key is already there, so seeing the same edge multiple times is
1118  // ok.
1119  // Should we actually forbid multiple edges? That would be consistent
1120  // with rejecting self-loops.
1121  if (v < u) std::swap(u, v);
1122  auto sh = find_vertex(u);
1123  if (!has_children(sh)) {
1124  sh->second.assign_children(new Siblings(&root_, sh->first));
1125  }
1126 
1127  sh->second.children()->members().emplace(v,
1128  Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, edge)));
1129  }
1130  }
1131 
1143  void expansion(int max_dim) {
1144  if (max_dim <= 1) return;
1145  clear_filtration(); // Drop the cache.
1146  dimension_ = max_dim;
1147  for (Dictionary_it root_it = root_.members_.begin();
1148  root_it != root_.members_.end(); ++root_it) {
1149  if (has_children(root_it)) {
1150  siblings_expansion(root_it->second.children(), max_dim - 1);
1151  }
1152  }
1153  dimension_ = max_dim - dimension_;
1154  }
1155 
1156  private:
1158  void siblings_expansion(Siblings * siblings, // must contain elements
1159  int k) {
1160  if (dimension_ > k) {
1161  dimension_ = k;
1162  }
1163  if (k == 0)
1164  return;
1165  Dictionary_it next = siblings->members().begin();
1166  ++next;
1167 
1168  thread_local std::vector<std::pair<Vertex_handle, Node> > inter;
1169  for (Dictionary_it s_h = siblings->members().begin();
1170  s_h != siblings->members().end(); ++s_h, ++next) {
1171  Simplex_handle root_sh = find_vertex(s_h->first);
1172  if (has_children(root_sh)) {
1173  intersection(
1174  inter, // output intersection
1175  next, // begin
1176  siblings->members().end(), // end
1177  root_sh->second.children()->members().begin(),
1178  root_sh->second.children()->members().end(),
1179  s_h->second.filtration());
1180  if (inter.size() != 0) {
1181  Siblings * new_sib = new Siblings(siblings, // oncles
1182  s_h->first, // parent
1183  inter); // boost::container::ordered_unique_range_t
1184  inter.clear();
1185  s_h->second.assign_children(new_sib);
1186  siblings_expansion(new_sib, k - 1);
1187  } else {
1188  // ensure the children property
1189  s_h->second.assign_children(siblings);
1190  inter.clear();
1191  }
1192  }
1193  }
1194  }
1195 
1198  static void intersection(std::vector<std::pair<Vertex_handle, Node> >& intersection,
1199  Dictionary_it begin1, Dictionary_it end1,
1200  Dictionary_it begin2, Dictionary_it end2,
1201  Filtration_value filtration_) {
1202  if (begin1 == end1 || begin2 == end2)
1203  return; // ----->>
1204  while (true) {
1205  if (begin1->first == begin2->first) {
1206  Filtration_value filt = (std::max)({begin1->second.filtration(), begin2->second.filtration(), filtration_});
1207  intersection.emplace_back(begin1->first, Node(nullptr, filt));
1208  if (++begin1 == end1 || ++begin2 == end2)
1209  return; // ----->>
1210  } else if (begin1->first < begin2->first) {
1211  if (++begin1 == end1)
1212  return;
1213  } else /* begin1->first > begin2->first */ {
1214  if (++begin2 == end2)
1215  return; // ----->>
1216  }
1217  }
1218  }
1219 
1220  public:
1239  template< typename Blocker >
1240  void expansion_with_blockers(int max_dim, Blocker block_simplex) {
1241  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1242  for (auto& simplex : boost::adaptors::reverse(root_.members())) {
1243  if (has_children(&simplex)) {
1244  siblings_expansion_with_blockers(simplex.second.children(), max_dim, max_dim - 1, block_simplex);
1245  }
1246  }
1247  }
1248 
1249  private:
1251  template< typename Blocker >
1252  void siblings_expansion_with_blockers(Siblings* siblings, int max_dim, int k, Blocker block_simplex) {
1253  if (dimension_ < max_dim - k) {
1254  dimension_ = max_dim - k;
1255  }
1256  if (k == 0)
1257  return;
1258  // No need to go deeper
1259  if (siblings->members().size() < 2)
1260  return;
1261  // Reverse loop starting before the last one for 'next' to be the last one
1262  for (auto simplex = siblings->members().rbegin() + 1; simplex != siblings->members().rend(); simplex++) {
1263  std::vector<std::pair<Vertex_handle, Node> > intersection;
1264  for(auto next = siblings->members().rbegin(); next != simplex; next++) {
1265  bool to_be_inserted = true;
1266  Filtration_value filt = simplex->second.filtration();
1267  // If all the boundaries are present, 'next' needs to be inserted
1269  Simplex_handle border_child = find_child(border, next->first);
1270  if (border_child == null_simplex()) {
1271  to_be_inserted=false;
1272  break;
1273  }
1274  filt = (std::max)(filt, filtration(border_child));
1275  }
1276  if (to_be_inserted) {
1277  intersection.emplace_back(next->first, Node(nullptr, filt));
1278  }
1279  }
1280  if (intersection.size() != 0) {
1281  // Reverse the order to insert
1282  Siblings * new_sib = new Siblings(siblings, // oncles
1283  simplex->first, // parent
1284  boost::adaptors::reverse(intersection)); // boost::container::ordered_unique_range_t
1285  std::vector<Vertex_handle> blocked_new_sib_vertex_list;
1286  // As all intersections are inserted, we can call the blocker function on all new_sib members
1287  for (auto new_sib_member = new_sib->members().begin();
1288  new_sib_member != new_sib->members().end();
1289  new_sib_member++) {
1290  bool blocker_result = block_simplex(new_sib_member);
1291  // new_sib member has been blocked by the blocker function
1292  // add it to the list to be removed - do not perform it while looping on it
1293  if (blocker_result) {
1294  blocked_new_sib_vertex_list.push_back(new_sib_member->first);
1295  }
1296  }
1297  if (blocked_new_sib_vertex_list.size() == new_sib->members().size()) {
1298  // Specific case where all have to be deleted
1299  delete new_sib;
1300  // ensure the children property
1301  simplex->second.assign_children(siblings);
1302  } else {
1303  for (auto& blocked_new_sib_member : blocked_new_sib_vertex_list) {
1304  new_sib->members().erase(blocked_new_sib_member);
1305  }
1306  // ensure recursive call
1307  simplex->second.assign_children(new_sib);
1308  siblings_expansion_with_blockers(new_sib, max_dim, k - 1, block_simplex);
1309  }
1310  } else {
1311  // ensure the children property
1312  simplex->second.assign_children(siblings);
1313  }
1314  }
1315  }
1316 
1317  /* \private Returns the Simplex_handle composed of the vertex list (from the Simplex_handle), plus the given
1318  * Vertex_handle if the Vertex_handle is found in the Simplex_handle children list.
1319  * Returns null_simplex() if it does not exist
1320  */
1321  Simplex_handle find_child(Simplex_handle sh, Vertex_handle vh) const {
1322  if (!has_children(sh))
1323  return null_simplex();
1324 
1325  Simplex_handle child = sh->second.children()->find(vh);
1326  // Specific case of boost::flat_map does not find, returns boost::flat_map::end()
1327  // in simplex tree we want a null_simplex()
1328  if (child == sh->second.children()->members().end())
1329  return null_simplex();
1330 
1331  return child;
1332  }
1333 
1334  public:
1341  void print_hasse(std::ostream& os) {
1342  os << num_simplices() << " " << std::endl;
1343  for (auto sh : filtration_simplex_range()) {
1344  os << dimension(sh) << " ";
1345  for (auto b_sh : boundary_simplex_range(sh)) {
1346  os << key(b_sh) << " ";
1347  }
1348  os << filtration(sh) << " \n";
1349  }
1350  }
1351 
1352  public:
1360  bool modified = false;
1361  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1362  for (auto& simplex : boost::adaptors::reverse(root_.members())) {
1363  if (has_children(&simplex)) {
1364  modified |= rec_make_filtration_non_decreasing(simplex.second.children());
1365  }
1366  }
1367  if(modified)
1368  clear_filtration(); // Drop the cache.
1369  return modified;
1370  }
1371 
1372  private:
1377  bool rec_make_filtration_non_decreasing(Siblings * sib) {
1378  bool modified = false;
1379 
1380  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1381  for (auto& simplex : boost::adaptors::reverse(sib->members())) {
1382  // Find the maximum filtration value in the border
1384  Boundary_simplex_iterator max_border = std::max_element(std::begin(boundary), std::end(boundary),
1385  [](Simplex_handle sh1, Simplex_handle sh2) {
1386  return filtration(sh1) < filtration(sh2);
1387  });
1388 
1389  Filtration_value max_filt_border_value = filtration(*max_border);
1390  // Replacing if(f<max) with if(!(f>=max)) would mean that if f is NaN, we replace it with the max of the children.
1391  // That seems more useful than keeping NaN.
1392  if (!(simplex.second.filtration() >= max_filt_border_value)) {
1393  // Store the filtration modification information
1394  modified = true;
1395  simplex.second.assign_filtration(max_filt_border_value);
1396  }
1397  if (has_children(&simplex)) {
1398  modified |= rec_make_filtration_non_decreasing(simplex.second.children());
1399  }
1400  }
1401  // Make the modified information to be traced by upper call
1402  return modified;
1403  }
1404 
1405  public:
1414  bool modified = rec_prune_above_filtration(root(), filtration);
1415  if(modified)
1416  clear_filtration(); // Drop the cache.
1417  return modified;
1418  }
1419 
1420  private:
1421  bool rec_prune_above_filtration(Siblings* sib, Filtration_value filt) {
1422  auto&& list = sib->members();
1423  auto last = std::remove_if(list.begin(), list.end(), [this,filt](Dit_value_t& simplex) {
1424  if (simplex.second.filtration() <= filt) return false;
1425  if (has_children(&simplex)) rec_delete(simplex.second.children());
1426  // dimension may need to be lowered
1427  dimension_to_be_lowered_ = true;
1428  return true;
1429  });
1430 
1431  bool modified = (last != list.end());
1432  if (last == list.begin() && sib != root()) {
1433  // Removing the whole siblings, parent becomes a leaf.
1434  sib->oncles()->members()[sib->parent()].assign_children(sib->oncles());
1435  delete sib;
1436  // dimension may need to be lowered
1437  dimension_to_be_lowered_ = true;
1438  return true;
1439  } else {
1440  // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones.
1441  list.erase(last, list.end());
1442  for (auto&& simplex : list)
1443  if (has_children(&simplex))
1444  modified |= rec_prune_above_filtration(simplex.second.children(), filt);
1445  }
1446  return modified;
1447  }
1448 
1449  private:
1455  bool lower_upper_bound_dimension() {
1456  // reset automatic detection to recompute
1457  dimension_to_be_lowered_ = false;
1458  int new_dimension = -1;
1459  // Browse the tree from the left to the right as higher dimension cells are more likely on the left part of the tree
1460  for (Simplex_handle sh : complex_simplex_range()) {
1461 #ifdef DEBUG_TRACES
1462  for (auto vertex : simplex_vertex_range(sh)) {
1463  std::clog << " " << vertex;
1464  }
1465  std::clog << std::endl;
1466 #endif // DEBUG_TRACES
1467 
1468  int sh_dimension = dimension(sh);
1469  if (sh_dimension >= dimension_)
1470  // Stop browsing as soon as the dimension is reached, no need to go furter
1471  return false;
1472  new_dimension = (std::max)(new_dimension, sh_dimension);
1473  }
1474  dimension_ = new_dimension;
1475  return true;
1476  }
1477 
1478 
1479  public:
1489  // Guarantee the simplex has no children
1490  GUDHI_CHECK(!has_children(sh),
1491  std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children"));
1492 
1493  // Simplex is a leaf, it means the child is the Siblings owning the leaf
1494  Siblings* child = sh->second.children();
1495 
1496  if ((child->size() > 1) || (child == root())) {
1497  // Not alone, just remove it from members
1498  // Special case when child is the root of the simplex tree, just remove it from members
1499  child->erase(sh);
1500  } else {
1501  // Sibling is emptied : must be deleted, and its parent must point on his own Sibling
1502  child->oncles()->members().at(child->parent()).assign_children(child->oncles());
1503  delete child;
1504  // dimension may need to be lowered
1505  dimension_to_be_lowered_ = true;
1506  }
1507  }
1508 
1525  std::pair<Filtration_value, Extended_simplex_type> decode_extended_filtration(Filtration_value f, const Extended_filtration_data& efd){
1526  std::pair<Filtration_value, Extended_simplex_type> p;
1527  Filtration_value minval = efd.minval;
1528  Filtration_value maxval = efd.maxval;
1529  if (f >= -2 && f <= -1){
1530  p.first = minval + (maxval-minval)*(f + 2); p.second = Extended_simplex_type::UP;
1531  }
1532  else if (f >= 1 && f <= 2){
1533  p.first = minval - (maxval-minval)*(f - 2); p.second = Extended_simplex_type::DOWN;
1534  }
1535  else{
1536  p.first = std::numeric_limits<Filtration_value>::quiet_NaN(); p.second = Extended_simplex_type::EXTRA;
1537  }
1538  return p;
1539  };
1540 
1554  Extended_filtration_data extend_filtration() {
1555  clear_filtration(); // Drop the cache.
1556 
1557  // Compute maximum and minimum of filtration values
1558  Vertex_handle maxvert = std::numeric_limits<Vertex_handle>::min();
1559  Filtration_value minval = std::numeric_limits<Filtration_value>::infinity();
1560  Filtration_value maxval = -std::numeric_limits<Filtration_value>::infinity();
1561  for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh){
1562  Filtration_value f = this->filtration(sh);
1563  minval = std::min(minval, f);
1564  maxval = std::max(maxval, f);
1565  maxvert = std::max(sh->first, maxvert);
1566  }
1567 
1568  GUDHI_CHECK(maxvert < std::numeric_limits<Vertex_handle>::max(), std::invalid_argument("Simplex_tree contains a vertex with the largest Vertex_handle"));
1569  maxvert += 1;
1570 
1571  Simplex_tree st_copy = *this;
1572 
1573  // Add point for coning the simplicial complex
1574  this->insert_simplex({maxvert}, -3);
1575 
1576  // For each simplex
1577  std::vector<Vertex_handle> vr;
1578  for (auto sh_copy : st_copy.complex_simplex_range()){
1579 
1580  // Locate simplex
1581  vr.clear();
1582  for (auto vh : st_copy.simplex_vertex_range(sh_copy)){
1583  vr.push_back(vh);
1584  }
1585  auto sh = this->find(vr);
1586 
1587  // Create cone on simplex
1588  vr.push_back(maxvert);
1589  if (this->dimension(sh) == 0){
1590  Filtration_value v = this->filtration(sh);
1591  Filtration_value scaled_v = (v-minval)/(maxval-minval);
1592  // Assign ascending value between -2 and -1 to vertex
1593  this->assign_filtration(sh, -2 + scaled_v);
1594  // Assign descending value between 1 and 2 to cone on vertex
1595  this->insert_simplex(vr, 2 - scaled_v);
1596  }
1597  else{
1598  // Assign value -3 to simplex and cone on simplex
1599  this->assign_filtration(sh, -3);
1600  this->insert_simplex(vr, -3);
1601  }
1602  }
1603 
1604  // Automatically assign good values for simplices
1606 
1607  // Return the filtration data
1608  Extended_filtration_data efd(minval, maxval);
1609  return efd;
1610  }
1611 
1617  auto filt = filtration_(sh);
1618  for(auto v : simplex_vertex_range(sh))
1619  if(filtration_(find_vertex(v)) == filt)
1620  return v;
1621  return null_vertex();
1622  }
1623 
1631  // See issue #251 for potential speed improvements.
1632  auto&& vertices = simplex_vertex_range(sh); // vertices in decreasing order
1633  auto end = std::end(vertices);
1634  auto vi = std::begin(vertices);
1635  GUDHI_CHECK(vi != end, "empty simplex");
1636  auto v0 = *vi;
1637  ++vi;
1638  GUDHI_CHECK(vi != end, "simplex of dimension 0");
1639  if(std::next(vi) == end) return sh; // shortcut for dimension 1
1640  boost::container::static_vector<Vertex_handle, 40> suffix;
1641  suffix.push_back(v0);
1642  auto filt = filtration_(sh);
1643  do
1644  {
1645  Vertex_handle v = *vi;
1646  auto&& children1 = find_vertex(v)->second.children()->members_;
1647  for(auto w : suffix){
1648  // Can we take advantage of the fact that suffix is ordered?
1649  Simplex_handle s = children1.find(w);
1650  if(filtration_(s) == filt)
1651  return s;
1652  }
1653  suffix.push_back(v);
1654  }
1655  while(++vi != end);
1656  return null_simplex();
1657  }
1658 
1664  auto filt = filtration_(sh);
1665  // Naive implementation, it can be sped up.
1666  for(auto b : boundary_simplex_range(sh))
1667  if(filtration_(b) == filt)
1669  return sh; // None of its faces has the same filtration.
1670  }
1671 
1672  private:
1673  Vertex_handle null_vertex_;
1676  Siblings root_;
1678  std::vector<Simplex_handle> filtration_vect_;
1680  int dimension_;
1681  bool dimension_to_be_lowered_ = false;
1682 };
1683 
1684 // Print a Simplex_tree in os.
1685 template<typename...T>
1686 std::ostream& operator<<(std::ostream & os, Simplex_tree<T...> & st) {
1687  for (auto sh : st.filtration_simplex_range()) {
1688  os << st.dimension(sh) << " ";
1689  for (auto v : st.simplex_vertex_range(sh)) {
1690  os << v << " ";
1691  }
1692  os << st.filtration(sh) << "\n"; // TODO(VR): why adding the key ?? not read ?? << " " << st.key(sh) << " \n";
1693  }
1694  return os;
1695 }
1696 
1697 template<typename...T>
1698 std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
1699  typedef Simplex_tree<T...> ST;
1700  std::vector<typename ST::Vertex_handle> simplex;
1701  typename ST::Filtration_value fil;
1702  int max_dim = -1;
1703  while (read_simplex(is, simplex, fil)) {
1704  // read all simplices in the file as a list of vertices
1705  // Warning : simplex_size needs to be casted in int - Can be 0
1706  int dim = static_cast<int> (simplex.size() - 1);
1707  if (max_dim < dim) {
1708  max_dim = dim;
1709  }
1710  // insert every simplex in the simplex tree
1711  st.insert_simplex(simplex, fil);
1712  simplex.clear();
1713  }
1714  st.set_dimension(max_dim);
1715 
1716  return is;
1717 }
1718 
1725  typedef int Vertex_handle;
1726  typedef double Filtration_value;
1727  typedef std::uint32_t Simplex_key;
1728  static const bool store_key = true;
1729  static const bool store_filtration = true;
1730  static const bool contiguous_vertices = false;
1731 };
1732 
1741  typedef int Vertex_handle;
1742  typedef float Filtration_value;
1743  typedef std::uint32_t Simplex_key;
1744  static const bool store_key = true;
1745  static const bool store_filtration = true;
1746  static const bool contiguous_vertices = true;
1747 };
1748  // end defgroup simplex_tree
1750 
1751 } // namespace Gudhi
1752 
1753 #endif // SIMPLEX_TREE_H_
Gudhi::Simplex_tree::has_children
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:604
Gudhi::Simplex_tree::find
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:617
Gudhi::Simplex_tree::Filtration_simplex_range
std::vector< Simplex_handle > Filtration_simplex_range
Range over the simplices of the simplicial complex, ordered by the filtration.
Definition: Simplex_tree.h:207
Gudhi::Simplex_tree::Complex_simplex_iterator
Simplex_tree_complex_simplex_iterator< Simplex_tree > Complex_simplex_iterator
Iterator over the simplices of the simplicial complex.
Definition: Simplex_tree.h:195
Gudhi::Simplex_tree::Complex_simplex_range
boost::iterator_range< Complex_simplex_iterator > Complex_simplex_range
Range over the simplices of the simplicial complex.
Definition: Simplex_tree.h:197
Gudhi::Simplex_tree::simplex
Simplex_handle simplex(Simplex_key idx) const
Returns the simplex that has index idx in the filtration.
Definition: Simplex_tree.h:502
Gudhi::Simplex_tree::Simplex_tree
Simplex_tree()
Constructs an empty simplex tree.
Definition: Simplex_tree.h:306
Gudhi::Simplex_tree::num_vertices
size_t num_vertices() const
Returns the number of vertices in the complex.
Definition: Simplex_tree.h:548
Gudhi::Simplex_tree::minimal_simplex_with_same_filtration
Simplex_handle minimal_simplex_with_same_filtration(Simplex_handle sh)
Returns a minimal face of sh that has the same filtration value as sh.
Definition: Simplex_tree.h:1663
Gudhi::Simplex_tree::cofaces_simplex_range
Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension)
Compute the cofaces of a n simplex.
Definition: Simplex_tree.h:995
Gudhi::linear_indexing_tag
Tag for a linear ordering of simplices.
Definition: indexing_tag.h:20
Gudhi::Simplex_tree::simplex_vertex_range
Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const
Returns a range over the vertices of a simplex.
Definition: Simplex_tree.h:275
Gudhi::read_simplex
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
Gudhi::Simplex_tree::endpoints
std::pair< Simplex_handle, Simplex_handle > endpoints(Simplex_handle sh)
Definition: Simplex_tree.h:851
Gudhi::Simplex_tree::operator=
Simplex_tree & operator=(const Simplex_tree &complex_source)
User-defined copy assignment reproduces the whole tree structure.
Definition: Simplex_tree.h:340
SimplexKey
Key type used as simplex identifier.
Definition: SimplexKey.h:15
Gudhi::Simplex_tree::Simplex_handle
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:151
Gudhi::Simplex_tree::Boundary_simplex_range
boost::iterator_range< Boundary_simplex_iterator > Boundary_simplex_range
Range over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:191
Gudhi::Simplex_tree::num_simplices
size_t num_simplices()
returns the number of simplices in the simplex_tree.
Definition: Simplex_tree.h:554
Gudhi::Simplex_tree::Simplex_tree
Simplex_tree(const Simplex_tree &complex_source)
User-defined copy constructor reproduces the whole tree structure.
Definition: Simplex_tree.h:313
Gudhi::Simplex_tree::Complex_vertex_iterator
boost::transform_iterator< return_first, Dictionary_it > Complex_vertex_iterator
Iterator over the vertices of the simplicial complex.
Definition: Simplex_tree.h:175
Gudhi::Simplex_tree::Boundary_simplex_iterator
Simplex_tree_boundary_simplex_iterator< Simplex_tree > Boundary_simplex_iterator
Iterator over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:189
Gudhi::Simplex_tree::star_simplex_range
Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex)
Compute the star of a n simplex.
Definition: Simplex_tree.h:984
Gudhi::Simplex_tree::Skeleton_simplex_range
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:205
Gudhi::Simplex_tree::assign_key
void assign_key(Simplex_handle sh, Simplex_key key)
Assign a value 'key' to the key of the simplex represented by the Simplex_handle 'sh'.
Definition: Simplex_tree.h:844
SimplexTreeOptions::store_filtration
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
Extended_simplex_type
Extended simplex type data structure for representing the type of simplices in an extended filtration...
Gudhi::Simplex_tree::null_key
static Simplex_key null_key()
Returns a fixed number not in the interval [0, num_simplices()).
Definition: Simplex_tree.h:537
Gudhi::Simplex_tree::assign_filtration
void assign_filtration(Simplex_handle sh, Filtration_value fv)
Sets the filtration value of a simplex.
Definition: Simplex_tree.h:522
SimplexTreeOptions
Concept of the template parameter for the class Gudhi::Simplex_tree<SimplexTreeOptions>.
Definition: SimplexTreeOptions.h:15
Gudhi::Simplex_tree::Simplex_vertex_range
boost::iterator_range< Simplex_vertex_iterator > Simplex_vertex_range
Range over the vertices of a simplex.
Definition: Simplex_tree.h:183
Gudhi::Simplex_tree::dimension
int dimension(Simplex_handle sh)
Returns the dimension of a simplex.
Definition: Simplex_tree.h:576
Gudhi::Simplex_tree::skeleton_simplex_range
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:244
Gudhi::Simplex_tree::filtration
static Filtration_value filtration(Simplex_handle sh)
Returns the filtration value of a simplex.
Definition: Simplex_tree.h:511
Gudhi::Simplex_tree::expansion
void expansion(int max_dim)
Expands the Simplex_tree containing only its one skeleton until dimension max_dim.
Definition: Simplex_tree.h:1143
Gudhi::Simplex_tree::Simplex_vertex_iterator
Simplex_tree_simplex_vertex_iterator< Simplex_tree > Simplex_vertex_iterator
Iterator over the vertices of a simplex.
Definition: Simplex_tree.h:181
Gudhi::Simplex_tree::Skeleton_simplex_iterator
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:202
Gudhi::Simplex_tree::Filtration_simplex_iterator
Filtration_simplex_range::const_iterator Filtration_simplex_iterator
Iterator over the simplices of the simplicial complex, ordered by the filtration.
Definition: Simplex_tree.h:211
Gudhi::Simplex_tree::operator==
bool operator==(Simplex_tree &st2)
Checks if two simplex trees are equal.
Definition: Simplex_tree.h:448
Gudhi::Simplex_tree::set_dimension
void set_dimension(int dimension)
Set a dimension for the simplicial complex.
Definition: Simplex_tree.h:875
Gudhi::Simplex_tree::maybe_initialize_filtration
void maybe_initialize_filtration()
Initializes the filtration cache if it isn't initialized yet.
Definition: Simplex_tree.h:912
Gudhi::Simplex_tree::null_simplex
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:532
Gudhi::Simplex_tree::insert_graph
void insert_graph(const OneSkeletonGraph &skel_graph)
Inserts a 1-skeleton in an empty Simplex_tree.
Definition: Simplex_tree.h:1082
Gudhi::Simplex_tree::expansion_with_blockers
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:1240
Gudhi::Simplex_tree_options_fast_persistence
Definition: Simplex_tree.h:1739
Gudhi::Simplex_tree::Filtration_value
Options::Filtration_value Filtration_value
Type for the value of the filtration function.
Definition: Simplex_tree.h:84
Gudhi::Simplex_tree::~Simplex_tree
~Simplex_tree()
Destructor; deallocates the whole tree structure.
Definition: Simplex_tree.h:335
Gudhi::Simplex_tree::null_vertex
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:543
Gudhi::Simplex_tree::remove_maximal_simplex
void remove_maximal_simplex(Simplex_handle sh)
Remove a maximal simplex.
Definition: Simplex_tree.h:1488
Gudhi::Simplex_tree::initialize_filtration
void initialize_filtration()
Initializes the filtration cache, i.e. sorts the simplices according to their order in the filtration...
Definition: Simplex_tree.h:888
VertexHandle
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
Gudhi::Simplex_tree::insert_simplex_and_subfaces
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:783
Gudhi::Simplex_tree::boundary_simplex_range
Boundary_simplex_range boundary_simplex_range(SimplexHandle sh)
Returns a range over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:296
SimplexTreeOptions::contiguous_vertices
static constexpr bool contiguous_vertices
If true, the list of vertices present in the complex must always be 0, ..., num_vertices-1,...
Definition: SimplexTreeOptions.h:29
Gudhi::Simplex_tree::edge_with_same_filtration
Simplex_handle edge_with_same_filtration(Simplex_handle sh)
Returns an edge of sh that has the same filtration value as sh if it exists, and null_simplex() other...
Definition: Simplex_tree.h:1630
Gudhi::Simplex_tree::decode_extended_filtration
std::pair< Filtration_value, Extended_simplex_type > decode_extended_filtration(Filtration_value f, const Extended_filtration_data &efd)
Retrieve the original filtration value for a given simplex in the Simplex_tree. Since the computation...
Definition: Simplex_tree.h:1525
Gudhi::Simplex_tree::Cofaces_simplex_range
std::vector< Simplex_handle > Cofaces_simplex_range
Range over the cofaces of a simplex.
Definition: Simplex_tree.h:185
Gudhi::Simplex_tree::Vertex_handle
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition: Simplex_tree.h:92
Gudhi::Simplex_tree::clear_filtration
void clear_filtration()
Clears the filtration cache produced by initialize_filtration().
Definition: Simplex_tree.h:921
Gudhi::Simplex_tree::dimension
int dimension()
Returns the dimension of the simplicial complex.
Definition: Simplex_tree.h:595
Gudhi::Simplex_tree::self_siblings
static Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:858
Gudhi::Simplex_tree::insert_simplex
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:754
Gudhi::Simplex_tree::filtration_simplex_range
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:264
Gudhi::Simplex_tree::vertex_with_same_filtration
Vertex_handle vertex_with_same_filtration(Simplex_handle sh)
Returns a vertex of sh that has the same filtration value as sh if it exists, and null_vertex() other...
Definition: Simplex_tree.h:1616
Gudhi::Simplex_tree::Simplex_tree
Simplex_tree(Simplex_tree &&complex_source)
User-defined move constructor relocates the whole tree structure.
Definition: Simplex_tree.h:323
Gudhi::Simplex_tree::make_filtration_non_decreasing
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:1359
Gudhi::Simplex_tree::extend_filtration
Extended_filtration_data extend_filtration()
Extend filtration for computing extended persistence. This function only uses the filtration values a...
Definition: Simplex_tree.h:1554
Gudhi::Simplex_tree::prune_above_filtration
bool prune_above_filtration(Filtration_value filtration)
Prune above filtration value given as parameter.
Definition: Simplex_tree.h:1413
Gudhi::Simplex_tree::print_hasse
void print_hasse(std::ostream &os)
Write the hasse diagram of the simplicial complex in os.
Definition: Simplex_tree.h:1341
Gudhi::Simplex_tree::Complex_vertex_range
boost::iterator_range< Complex_vertex_iterator > Complex_vertex_range
Range over the vertices of the simplicial complex.
Definition: Simplex_tree.h:177
IndexingTag
Concept describing an indexing scheme (see FilteredComplex) for applying continuous maps to a cell co...
Definition: IndexingTag.h:18
Gudhi::Simplex_tree::complex_simplex_range
Complex_simplex_range complex_simplex_range()
Returns a range over the simplices of the simplicial complex.
Definition: Simplex_tree.h:230
FiltrationValue
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
Gudhi::Simplex_tree::upper_bound_dimension
int upper_bound_dimension() const
Returns an upper bound on the dimension of the simplicial complex.
Definition: Simplex_tree.h:587
Gudhi::Simplex_tree::key
static Simplex_key key(Simplex_handle sh)
Returns the key associated to a simplex.
Definition: Simplex_tree.h:494
Gudhi::Simplex_tree::root
Siblings * root()
Definition: Simplex_tree.h:867
Gudhi::Simplex_tree
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:77
Gudhi::Simplex_tree::complex_vertex_range
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:219
Gudhi::Simplex_tree::operator=
Simplex_tree & operator=(Simplex_tree &&complex_source)
User-defined move assignment relocates the whole tree structure.
Definition: Simplex_tree.h:357
Gudhi::Simplex_tree::Simplex_key
Options::Simplex_key Simplex_key
Key associated to each simplex.
Definition: Simplex_tree.h:88
reader_utils.h
This file includes common file reader for GUDHI.
Gudhi::Simplex_tree::operator!=
bool operator!=(Simplex_tree &st2)
Checks if two simplex trees are different.
Definition: Simplex_tree.h:456
GUDHI  Version 3.2.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Jul 10 2020 09:14:03 for GUDHI by Doxygen 1.8.17