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>
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 #include <tbb/parallel_sort.h>
31 #endif
32 
33 #include <utility>
34 #include <vector>
35 #include <functional> // for greater<>
36 #include <stdexcept>
37 #include <limits> // Inf
38 #include <initializer_list>
39 #include <algorithm> // for std::max
40 #include <cstdint> // for std::uint32_t
41 #include <iterator> // for std::distance
42 
43 namespace Gudhi {
44 
61 enum class Extended_simplex_type {UP, DOWN, EXTRA};
62 
63 struct Simplex_tree_options_full_featured;
64 
78 template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>
79 class Simplex_tree {
80  public:
82  typedef typename Options::Indexing_tag Indexing_tag;
95 
96  /* Type of node in the simplex tree. */
98  /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */
99  // Note: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a
100  // flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and
101  // Simplex_key next to each other).
102  typedef typename boost::container::flat_map<Vertex_handle, Node> Dictionary;
103 
106 
107 
108 
109  struct Key_simplex_base_real {
110  Key_simplex_base_real() : key_(-1) {}
111  void assign_key(Simplex_key k) { key_ = k; }
112  Simplex_key key() const { return key_; }
113  private:
114  Simplex_key key_;
115  };
116  struct Key_simplex_base_dummy {
117  Key_simplex_base_dummy() {}
118  // Undefined so it will not link
119  void assign_key(Simplex_key);
120  Simplex_key key() const;
121  };
122  struct Extended_filtration_data {
123  Filtration_value minval;
124  Filtration_value maxval;
125  Extended_filtration_data(){}
126  Extended_filtration_data(Filtration_value vmin, Filtration_value vmax): minval(vmin), maxval(vmax) {}
127  };
128  typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type
129  Key_simplex_base;
130 
131  struct Filtration_simplex_base_real {
132  Filtration_simplex_base_real() : filt_(0) {}
133  void assign_filtration(Filtration_value f) { filt_ = f; }
134  Filtration_value filtration() const { return filt_; }
135  private:
136  Filtration_value filt_;
137  };
138  struct Filtration_simplex_base_dummy {
139  Filtration_simplex_base_dummy() {}
140  void assign_filtration(Filtration_value GUDHI_CHECK_code(f)) { GUDHI_CHECK(f == 0, "filtration value specified for a complex that does not store them"); }
141  Filtration_value filtration() const { return 0; }
142  };
143  typedef typename std::conditional<Options::store_filtration, Filtration_simplex_base_real,
144  Filtration_simplex_base_dummy>::type Filtration_simplex_base;
145 
146  public:
152  typedef typename Dictionary::iterator Simplex_handle;
153 
154  private:
155  typedef typename Dictionary::iterator Dictionary_it;
156  typedef typename Dictionary_it::value_type Dit_value_t;
157 
158  struct return_first {
159  Vertex_handle operator()(const Dit_value_t& p_sh) const {
160  return p_sh.first;
161  }
162  };
163 
164  public:
176  typedef boost::transform_iterator<return_first, Dictionary_it> Complex_vertex_iterator;
178  typedef boost::iterator_range<Complex_vertex_iterator> Complex_vertex_range;
184  typedef boost::iterator_range<Simplex_vertex_iterator> Simplex_vertex_range;
186  typedef std::vector<Simplex_handle> Cofaces_simplex_range;
192  typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
198  typedef boost::iterator_range<Boundary_opposite_vertex_simplex_iterator> Boundary_opposite_vertex_simplex_range;
204  typedef boost::iterator_range<Complex_simplex_iterator> Complex_simplex_range;
212  typedef boost::iterator_range<Skeleton_simplex_iterator> Skeleton_simplex_range;
214  typedef std::vector<Simplex_handle> Filtration_simplex_range;
218  typedef typename Filtration_simplex_range::const_iterator Filtration_simplex_iterator;
219 
220  /* @} */ // end name range and iterator types
227  return Complex_vertex_range(
228  boost::make_transform_iterator(root_.members_.begin(), return_first()),
229  boost::make_transform_iterator(root_.members_.end(), return_first()));
230  }
231 
240  }
241 
254  }
255 
273  return filtration_vect_;
274  }
275 
283  GUDHI_CHECK(sh != null_simplex(), "empty simplex");
286  }
287 
302  template<class SimplexHandle>
306  }
307 
319  template<class SimplexHandle>
323  }
324  // end range and iterator methods
331  : null_vertex_(-1),
332  root_(nullptr, null_vertex_),
333  filtration_vect_(),
334  dimension_(-1) { }
335 
337  Simplex_tree(const Simplex_tree& complex_source) {
338 #ifdef DEBUG_TRACES
339  std::clog << "Simplex_tree copy constructor" << std::endl;
340 #endif // DEBUG_TRACES
341  copy_from(complex_source);
342  }
343 
347  Simplex_tree(Simplex_tree && complex_source) {
348 #ifdef DEBUG_TRACES
349  std::clog << "Simplex_tree move constructor" << std::endl;
350 #endif // DEBUG_TRACES
351  move_from(complex_source);
352 
353  // just need to set dimension_ on source to make it available again
354  // (filtration_vect_ and members are already set from the move)
355  complex_source.dimension_ = -1;
356  }
357 
360  root_members_recursive_deletion();
361  }
362 
364  Simplex_tree& operator= (const Simplex_tree& complex_source) {
365 #ifdef DEBUG_TRACES
366  std::clog << "Simplex_tree copy assignment" << std::endl;
367 #endif // DEBUG_TRACES
368  // Self-assignment detection
369  if (&complex_source != this) {
370  // We start by deleting root_ if not empty
371  root_members_recursive_deletion();
372 
373  copy_from(complex_source);
374  }
375  return *this;
376  }
377 
381  Simplex_tree& operator=(Simplex_tree&& complex_source) {
382 #ifdef DEBUG_TRACES
383  std::clog << "Simplex_tree move assignment" << std::endl;
384 #endif // DEBUG_TRACES
385  // Self-assignment detection
386  if (&complex_source != this) {
387  // root_ deletion in case it was not empty
388  root_members_recursive_deletion();
389 
390  move_from(complex_source);
391  }
392  return *this;
393  } // end constructor/destructor
395 
396  private:
397  // Copy from complex_source to "this"
398  void copy_from(const Simplex_tree& complex_source) {
399  null_vertex_ = complex_source.null_vertex_;
400  filtration_vect_.clear();
401  dimension_ = complex_source.dimension_;
402  auto root_source = complex_source.root_;
403 
404  // root members copy
405  root_.members() = Dictionary(boost::container::ordered_unique_range, root_source.members().begin(), root_source.members().end());
406  // Needs to reassign children
407  for (auto& map_el : root_.members()) {
408  map_el.second.assign_children(&root_);
409  }
410  rec_copy(&root_, &root_source);
411  }
412 
414  void rec_copy(Siblings *sib, Siblings *sib_source) {
415  for (auto sh = sib->members().begin(), sh_source = sib_source->members().begin();
416  sh != sib->members().end(); ++sh, ++sh_source) {
417  if (has_children(sh_source)) {
418  Siblings * newsib = new Siblings(sib, sh_source->first);
419  newsib->members_.reserve(sh_source->second.children()->members().size());
420  for (auto & child : sh_source->second.children()->members())
421  newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(newsib, child.second.filtration()));
422  rec_copy(newsib, sh_source->second.children());
423  sh->second.assign_children(newsib);
424  }
425  }
426  }
427 
428  // Move from complex_source to "this"
429  void move_from(Simplex_tree& complex_source) {
430  null_vertex_ = std::move(complex_source.null_vertex_);
431  root_ = std::move(complex_source.root_);
432  filtration_vect_ = std::move(complex_source.filtration_vect_);
433  dimension_ = std::move(complex_source.dimension_);
434 
435  // Need to update root members (children->oncles and children need to point on the new root pointer)
436  for (auto& map_el : root_.members()) {
437  if (map_el.second.children() != &(complex_source.root_)) {
438  // reset children->oncles with the moved root_ pointer value
439  map_el.second.children()->oncles_ = &root_;
440  } else {
441  // if simplex is of dimension 0, oncles_ shall be nullptr
442  GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr,
443  std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree"));
444  // and children points on root_ - to be moved
445  map_el.second.assign_children(&root_);
446  }
447  }
448  }
449 
450  // delete all root_.members() recursively
451  void root_members_recursive_deletion() {
452  for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) {
453  if (has_children(sh)) {
454  rec_delete(sh->second.children());
455  }
456  }
457  root_.members().clear();
458  }
459 
460  // Recursive deletion
461  void rec_delete(Siblings * sib) {
462  for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
463  if (has_children(sh)) {
464  rec_delete(sh->second.children());
465  }
466  }
467  delete sib;
468  }
469 
470  public:
473  if ((null_vertex_ != st2.null_vertex_) ||
474  (dimension_ != st2.dimension_))
475  return false;
476  return rec_equal(&root_, &st2.root_);
477  }
478 
481  return (!(*this == st2));
482  }
483 
484  private:
486  bool rec_equal(Siblings* s1, Siblings* s2) {
487  if (s1->members().size() != s2->members().size())
488  return false;
489  for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin();
490  (sh1 != s1->members().end() && sh2 != s2->members().end()); ++sh1, ++sh2) {
491  if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration())
492  return false;
493  if (has_children(sh1) != has_children(sh2))
494  return false;
495  // Recursivity on children only if both have children
496  else if (has_children(sh1))
497  if (!rec_equal(sh1->second.children(), sh2->second.children()))
498  return false;
499  }
500  return true;
501  }
502 
507  static Filtration_value filtration_(Simplex_handle sh) {
508  GUDHI_CHECK (sh != null_simplex(), "null simplex");
509  return sh->second.filtration();
510  }
511 
512  public:
519  return sh->second.key();
520  }
521 
527  return filtration_vect_[idx];
528  }
529 
536  if (sh != null_simplex()) {
537  return sh->second.filtration();
538  } else {
539  return std::numeric_limits<Filtration_value>::infinity();
540  }
541  }
542 
547  GUDHI_CHECK(sh != null_simplex(),
548  std::invalid_argument("Simplex_tree::assign_filtration - cannot assign filtration on null_simplex"));
549  sh->second.assign_filtration(fv);
550  }
551 
557  return Dictionary_it(nullptr);
558  }
559 
562  return -1;
563  }
564 
568  return null_vertex_;
569  }
570 
572  size_t num_vertices() const {
573  return root_.members_.size();
574  }
575 
576  public:
578  size_t num_simplices() {
579  return num_simplices(&root_);
580  }
581 
582  private:
584  size_t num_simplices(Siblings * sib) {
585  auto sib_begin = sib->members().begin();
586  auto sib_end = sib->members().end();
587  size_t simplices_number = sib_end - sib_begin;
588  for (auto sh = sib_begin; sh != sib_end; ++sh) {
589  if (has_children(sh)) {
590  simplices_number += num_simplices(sh->second.children());
591  }
592  }
593  return simplices_number;
594  }
595 
596  public:
601  Siblings * curr_sib = self_siblings(sh);
602  int dim = 0;
603  while (curr_sib != nullptr) {
604  ++dim;
605  curr_sib = curr_sib->oncles();
606  }
607  return dim - 1;
608  }
609 
611  int upper_bound_dimension() const {
612  return dimension_;
613  }
614 
619  int dimension() {
620  if (dimension_to_be_lowered_)
621  lower_upper_bound_dimension();
622  return dimension_;
623  }
624 
627  template<class SimplexHandle>
628  bool has_children(SimplexHandle sh) const {
629  // Here we rely on the root using null_vertex(), which cannot match any real vertex.
630  return (sh->second.children()->parent() == sh->first);
631  }
632 
640  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
641  Simplex_handle find(const InputVertexRange & s) {
642  auto first = std::begin(s);
643  auto last = std::end(s);
644 
645  if (first == last)
646  return null_simplex(); // ----->>
647 
648  // Copy before sorting
649  std::vector<Vertex_handle> copy(first, last);
650  std::sort(std::begin(copy), std::end(copy));
651  return find_simplex(copy);
652  }
653 
654  private:
656  Simplex_handle find_simplex(const std::vector<Vertex_handle> & simplex) {
657  Siblings * tmp_sib = &root_;
658  Dictionary_it tmp_dit;
659  auto vi = simplex.begin();
660  if (Options::contiguous_vertices) {
661  // Equivalent to the first iteration of the normal loop
662  GUDHI_CHECK(contiguous_vertices(), "non-contiguous vertices");
663  Vertex_handle v = *vi++;
664  if(v < 0 || v >= static_cast<Vertex_handle>(root_.members_.size()))
665  return null_simplex();
666  tmp_dit = root_.members_.begin() + v;
667  if (vi == simplex.end())
668  return tmp_dit;
669  if (!has_children(tmp_dit))
670  return null_simplex();
671  tmp_sib = tmp_dit->second.children();
672  }
673  for (;;) {
674  tmp_dit = tmp_sib->members_.find(*vi++);
675  if (tmp_dit == tmp_sib->members_.end())
676  return null_simplex();
677  if (vi == simplex.end())
678  return tmp_dit;
679  if (!has_children(tmp_dit))
680  return null_simplex();
681  tmp_sib = tmp_dit->second.children();
682  }
683  }
684 
687  Simplex_handle find_vertex(Vertex_handle v) {
688  if (Options::contiguous_vertices) {
689  assert(contiguous_vertices());
690  return root_.members_.begin() + v;
691  } else {
692  return root_.members_.find(v);
693  }
694  }
695 
696  public:
698  bool contiguous_vertices() const {
699  if (root_.members_.empty()) return true;
700  if (root_.members_.begin()->first != 0) return false;
701  if (std::prev(root_.members_.end())->first != static_cast<Vertex_handle>(root_.members_.size() - 1)) return false;
702  return true;
703  }
704 
705  private:
720  std::pair<Simplex_handle, bool> insert_vertex_vector(const std::vector<Vertex_handle>& simplex,
722  Siblings * curr_sib = &root_;
723  std::pair<Simplex_handle, bool> res_insert;
724  auto vi = simplex.begin();
725  for (; vi != simplex.end() - 1; ++vi) {
726  GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
727  res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration));
728  if (!(has_children(res_insert.first))) {
729  res_insert.first->second.assign_children(new Siblings(curr_sib, *vi));
730  }
731  curr_sib = res_insert.first->second.children();
732  }
733  GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
734  res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration));
735  if (!res_insert.second) {
736  // if already in the complex
737  if (res_insert.first->second.filtration() > filtration) {
738  // if filtration value modified
739  res_insert.first->second.assign_filtration(filtration);
740  return res_insert;
741  }
742  // if filtration value unchanged
743  return std::pair<Simplex_handle, bool>(null_simplex(), false);
744  }
745  // otherwise the insertion has succeeded - size is a size_type
746  if (static_cast<int>(simplex.size()) - 1 > dimension_) {
747  // Update dimension if needed
748  dimension_ = static_cast<int>(simplex.size()) - 1;
749  }
750  return res_insert;
751  }
752 
753  public:
777  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
778  std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex,
780  auto first = std::begin(simplex);
781  auto last = std::end(simplex);
782 
783  if (first == last)
784  return std::pair<Simplex_handle, bool>(null_simplex(), true); // ----->>
785 
786  // Copy before sorting
787  std::vector<Vertex_handle> copy(first, last);
788  std::sort(std::begin(copy), std::end(copy));
789  return insert_vertex_vector(copy, filtration);
790  }
791 
806  template<class InputVertexRange = std::initializer_list<Vertex_handle>>
807  std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex,
809  auto first = std::begin(Nsimplex);
810  auto last = std::end(Nsimplex);
811 
812  if (first == last)
813  return { null_simplex(), true }; // FIXME: false would make more sense to me.
814 
815  thread_local std::vector<Vertex_handle> copy;
816  copy.clear();
817  copy.insert(copy.end(), first, last);
818  std::sort(copy.begin(), copy.end());
819  auto last_unique = std::unique(copy.begin(), copy.end());
820  copy.erase(last_unique, copy.end());
821  GUDHI_CHECK_code(
822  for (Vertex_handle v : copy)
823  GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex");
824  )
825  // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain.
826  dimension_ = (std::max)(dimension_, static_cast<int>(std::distance(copy.begin(), copy.end())) - 1);
827 
828  return rec_insert_simplex_and_subfaces_sorted(root(), copy.begin(), copy.end(), filtration);
829  }
830 
831  private:
832  // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1.
833  template<class ForwardVertexIterator>
834  std::pair<Simplex_handle, bool> rec_insert_simplex_and_subfaces_sorted(Siblings* sib,
835  ForwardVertexIterator first,
836  ForwardVertexIterator last,
837  Filtration_value filt) {
838  // An alternative strategy would be:
839  // - try to find the complete simplex, if found (and low filtration) exit
840  // - insert all the vertices at once in sib
841  // - loop over those (new or not) simplices, with a recursive call(++first, last)
842  Vertex_handle vertex_one = *first;
843  auto&& dict = sib->members();
844  auto insertion_result = dict.emplace(vertex_one, Node(sib, filt));
845  Simplex_handle simplex_one = insertion_result.first;
846  bool one_is_new = insertion_result.second;
847  if (!one_is_new) {
848  if (filtration(simplex_one) > filt) {
849  assign_filtration(simplex_one, filt);
850  } else {
851  // FIXME: this interface makes no sense, and it doesn't seem to be tested.
852  insertion_result.first = null_simplex();
853  }
854  }
855  if (++first == last) return insertion_result;
856  if (!has_children(simplex_one))
857  // TODO: have special code here, we know we are building the whole subtree from scratch.
858  simplex_one->second.assign_children(new Siblings(sib, vertex_one));
859  auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt);
860  // No need to continue if the full simplex was already there with a low enough filtration value.
861  if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt);
862  return res;
863  }
864 
865  public:
869  sh->second.assign_key(key);
870  }
871 
875  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
876  assert(dimension(sh) == 1);
877  return { find_vertex(sh->first), find_vertex(self_siblings(sh)->parent()) };
878  }
879 
881  template<class SimplexHandle>
882  static Siblings* self_siblings(SimplexHandle sh) {
883  if (sh->second.children()->parent() == sh->first)
884  return sh->second.children()->oncles();
885  else
886  return sh->second.children();
887  }
888 
889  public:
892  return &root_;
893  }
894 
900  dimension_to_be_lowered_ = false;
901  dimension_ = dimension;
902  }
903 
904  public:
913  filtration_vect_.clear();
914  filtration_vect_.reserve(num_simplices());
916  filtration_vect_.push_back(sh);
917 
918  /* We use stable_sort here because with libstdc++ it is faster than sort.
919  * is_before_in_filtration is now a total order, but we used to call
920  * stable_sort for the following heuristic:
921  * The use of a depth-first traversal of the simplex tree, provided by
922  * complex_simplex_range(), combined with a stable sort is meant to
923  * optimize the order of simplices with same filtration value. The
924  * heuristic consists in inserting the cofaces of a simplex as soon as
925  * possible.
926  */
927 #ifdef GUDHI_USE_TBB
928  tbb::parallel_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
929 #else
930  std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
931 #endif
932  }
937  if (filtration_vect_.empty()) {
939  }
940  }
946  filtration_vect_.clear();
947  }
948 
949  private:
962  void rec_coface(std::vector<Vertex_handle> &vertices, Siblings *curr_sib, int curr_nbVertices,
963  std::vector<Simplex_handle>& cofaces, bool star, int nbVertices) {
964  if (!(star || curr_nbVertices <= nbVertices)) // dimension of actual simplex <= nbVertices
965  return;
966  for (Simplex_handle simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) {
967  if (vertices.empty()) {
968  // If we reached the end of the vertices, and the simplex has more vertices than the given simplex
969  // => we found a coface
970 
971  // Add a coface if we want the star or if the number of vertices of the current simplex matches with nbVertices
972  bool addCoface = (star || curr_nbVertices == nbVertices);
973  if (addCoface)
974  cofaces.push_back(simplex);
975  if ((!addCoface || star) && has_children(simplex)) // Rec call
976  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
977  } else {
978  if (simplex->first == vertices.back()) {
979  // If curr_sib matches with the top vertex
980  bool equalDim = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices
981  bool addCoface = vertices.size() == 1 && equalDim;
982  if (addCoface)
983  cofaces.push_back(simplex);
984  if ((!addCoface || star) && has_children(simplex)) {
985  // Rec call
986  Vertex_handle tmp = vertices.back();
987  vertices.pop_back();
988  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
989  vertices.push_back(tmp);
990  }
991  } else if (simplex->first > vertices.back()) {
992  return;
993  } else {
994  // (simplex->first < vertices.back()
995  if (has_children(simplex))
996  rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices);
997  }
998  }
999  }
1000  }
1001 
1002  public:
1009  return cofaces_simplex_range(simplex, 0);
1010  }
1011 
1020  Cofaces_simplex_range cofaces;
1021  // codimension must be positive or null integer
1022  assert(codimension >= 0);
1024  std::vector<Vertex_handle> copy(rg.begin(), rg.end());
1025  if (codimension + static_cast<int>(copy.size()) > dimension_ + 1 ||
1026  (codimension == 0 && static_cast<int>(copy.size()) > dimension_)) // n+codimension greater than dimension_
1027  return cofaces;
1028  // must be sorted in decreasing order
1029  assert(std::is_sorted(copy.begin(), copy.end(), std::greater<Vertex_handle>()));
1030  bool star = codimension == 0;
1031  rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast<int>(copy.size()));
1032  return cofaces;
1033  }
1034 
1035  private:
1043  bool reverse_lexicographic_order(Simplex_handle sh1, Simplex_handle sh2) {
1046  Simplex_vertex_iterator it1 = rg1.begin();
1047  Simplex_vertex_iterator it2 = rg2.begin();
1048  while (it1 != rg1.end() && it2 != rg2.end()) {
1049  if (*it1 == *it2) {
1050  ++it1;
1051  ++it2;
1052  } else {
1053  return *it1 < *it2;
1054  }
1055  }
1056  return ((it1 == rg1.end()) && (it2 != rg2.end()));
1057  }
1058 
1065  struct is_before_in_filtration {
1066  explicit is_before_in_filtration(Simplex_tree * st)
1067  : st_(st) { }
1068 
1069  bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const {
1070  // Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
1071  if (sh1->second.filtration() != sh2->second.filtration()) {
1072  return sh1->second.filtration() < sh2->second.filtration();
1073  }
1074  // is sh1 a proper subface of sh2
1075  return st_->reverse_lexicographic_order(sh1, sh2);
1076  }
1077 
1078  Simplex_tree * st_;
1079  };
1080 
1081  public:
1105  template<class OneSkeletonGraph>
1106  void insert_graph(const OneSkeletonGraph& skel_graph) {
1107  // the simplex tree must be empty
1108  assert(num_simplices() == 0);
1109 
1110  // is there a better way to let the compiler know that we don't mean Simplex_tree::num_vertices?
1111  using boost::num_vertices;
1112 
1113  if (num_vertices(skel_graph) == 0) {
1114  return;
1115  }
1116  if (num_edges(skel_graph) == 0) {
1117  dimension_ = 0;
1118  } else {
1119  dimension_ = 1;
1120  }
1121 
1122  root_.members_.reserve(num_vertices(skel_graph));
1123 
1124  typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator v_it,
1125  v_it_end;
1126  for (std::tie(v_it, v_it_end) = vertices(skel_graph); v_it != v_it_end;
1127  ++v_it) {
1128  root_.members_.emplace_hint(
1129  root_.members_.end(), *v_it,
1130  Node(&root_, get(vertex_filtration_t(), skel_graph, *v_it)));
1131  }
1132  std::pair<typename boost::graph_traits<OneSkeletonGraph>::edge_iterator,
1133  typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = edges(skel_graph);
1134  // boost_edges.first is the equivalent to boost_edges.begin()
1135  // boost_edges.second is the equivalent to boost_edges.end()
1136  for (; boost_edges.first != boost_edges.second; boost_edges.first++) {
1137  auto edge = *(boost_edges.first);
1138  auto u = source(edge, skel_graph);
1139  auto v = target(edge, skel_graph);
1140  if (u == v) throw "Self-loops are not simplicial";
1141  // We cannot skip edges with the wrong orientation and expect them to
1142  // come a second time with the right orientation, that does not always
1143  // happen in practice. emplace() should be a NOP when an element with the
1144  // same key is already there, so seeing the same edge multiple times is
1145  // ok.
1146  // Should we actually forbid multiple edges? That would be consistent
1147  // with rejecting self-loops.
1148  if (v < u) std::swap(u, v);
1149  auto sh = find_vertex(u);
1150  if (!has_children(sh)) {
1151  sh->second.assign_children(new Siblings(&root_, sh->first));
1152  }
1153 
1154  sh->second.children()->members().emplace(v,
1155  Node(sh->second.children(), get(edge_filtration_t(), skel_graph, edge)));
1156  }
1157  }
1158 
1170  void expansion(int max_dim) {
1171  if (max_dim <= 1) return;
1172  clear_filtration(); // Drop the cache.
1173  dimension_ = max_dim;
1174  for (Dictionary_it root_it = root_.members_.begin();
1175  root_it != root_.members_.end(); ++root_it) {
1176  if (has_children(root_it)) {
1177  siblings_expansion(root_it->second.children(), max_dim - 1);
1178  }
1179  }
1180  dimension_ = max_dim - dimension_;
1181  }
1182 
1183  private:
1185  void siblings_expansion(Siblings * siblings, // must contain elements
1186  int k) {
1187  if (dimension_ > k) {
1188  dimension_ = k;
1189  }
1190  if (k == 0)
1191  return;
1192  Dictionary_it next = siblings->members().begin();
1193  ++next;
1194 
1195  thread_local std::vector<std::pair<Vertex_handle, Node> > inter;
1196  for (Dictionary_it s_h = siblings->members().begin();
1197  s_h != siblings->members().end(); ++s_h, ++next) {
1198  Simplex_handle root_sh = find_vertex(s_h->first);
1199  if (has_children(root_sh)) {
1200  intersection(
1201  inter, // output intersection
1202  next, // begin
1203  siblings->members().end(), // end
1204  root_sh->second.children()->members().begin(),
1205  root_sh->second.children()->members().end(),
1206  s_h->second.filtration());
1207  if (inter.size() != 0) {
1208  Siblings * new_sib = new Siblings(siblings, // oncles
1209  s_h->first, // parent
1210  inter); // boost::container::ordered_unique_range_t
1211  inter.clear();
1212  s_h->second.assign_children(new_sib);
1213  siblings_expansion(new_sib, k - 1);
1214  } else {
1215  // ensure the children property
1216  s_h->second.assign_children(siblings);
1217  inter.clear();
1218  }
1219  }
1220  }
1221  }
1222 
1225  static void intersection(std::vector<std::pair<Vertex_handle, Node> >& intersection,
1226  Dictionary_it begin1, Dictionary_it end1,
1227  Dictionary_it begin2, Dictionary_it end2,
1228  Filtration_value filtration_) {
1229  if (begin1 == end1 || begin2 == end2)
1230  return; // ----->>
1231  while (true) {
1232  if (begin1->first == begin2->first) {
1233  Filtration_value filt = (std::max)({begin1->second.filtration(), begin2->second.filtration(), filtration_});
1234  intersection.emplace_back(begin1->first, Node(nullptr, filt));
1235  if (++begin1 == end1 || ++begin2 == end2)
1236  return; // ----->>
1237  } else if (begin1->first < begin2->first) {
1238  if (++begin1 == end1)
1239  return;
1240  } else /* begin1->first > begin2->first */ {
1241  if (++begin2 == end2)
1242  return; // ----->>
1243  }
1244  }
1245  }
1246 
1247  public:
1266  template< typename Blocker >
1267  void expansion_with_blockers(int max_dim, Blocker block_simplex) {
1268  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1269  for (auto& simplex : boost::adaptors::reverse(root_.members())) {
1270  if (has_children(&simplex)) {
1271  siblings_expansion_with_blockers(simplex.second.children(), max_dim, max_dim - 1, block_simplex);
1272  }
1273  }
1274  }
1275 
1276  private:
1278  template< typename Blocker >
1279  void siblings_expansion_with_blockers(Siblings* siblings, int max_dim, int k, Blocker block_simplex) {
1280  if (dimension_ < max_dim - k) {
1281  dimension_ = max_dim - k;
1282  }
1283  if (k == 0)
1284  return;
1285  // No need to go deeper
1286  if (siblings->members().size() < 2)
1287  return;
1288  // Reverse loop starting before the last one for 'next' to be the last one
1289  for (auto simplex = siblings->members().rbegin() + 1; simplex != siblings->members().rend(); simplex++) {
1290  std::vector<std::pair<Vertex_handle, Node> > intersection;
1291  for(auto next = siblings->members().rbegin(); next != simplex; next++) {
1292  bool to_be_inserted = true;
1293  Filtration_value filt = simplex->second.filtration();
1294  // If all the boundaries are present, 'next' needs to be inserted
1295  for (Simplex_handle border : boundary_simplex_range(simplex)) {
1296  Simplex_handle border_child = find_child(border, next->first);
1297  if (border_child == null_simplex()) {
1298  to_be_inserted=false;
1299  break;
1300  }
1301  filt = (std::max)(filt, filtration(border_child));
1302  }
1303  if (to_be_inserted) {
1304  intersection.emplace_back(next->first, Node(nullptr, filt));
1305  }
1306  }
1307  if (intersection.size() != 0) {
1308  // Reverse the order to insert
1309  Siblings * new_sib = new Siblings(siblings, // oncles
1310  simplex->first, // parent
1311  boost::adaptors::reverse(intersection)); // boost::container::ordered_unique_range_t
1312  simplex->second.assign_children(new_sib);
1313  std::vector<Vertex_handle> blocked_new_sib_vertex_list;
1314  // As all intersections are inserted, we can call the blocker function on all new_sib members
1315  for (auto new_sib_member = new_sib->members().begin();
1316  new_sib_member != new_sib->members().end();
1317  new_sib_member++) {
1318  bool blocker_result = block_simplex(new_sib_member);
1319  // new_sib member has been blocked by the blocker function
1320  // add it to the list to be removed - do not perform it while looping on it
1321  if (blocker_result) {
1322  blocked_new_sib_vertex_list.push_back(new_sib_member->first);
1323  }
1324  }
1325  if (blocked_new_sib_vertex_list.size() == new_sib->members().size()) {
1326  // Specific case where all have to be deleted
1327  delete new_sib;
1328  // ensure the children property
1329  simplex->second.assign_children(siblings);
1330  } else {
1331  for (auto& blocked_new_sib_member : blocked_new_sib_vertex_list) {
1332  new_sib->members().erase(blocked_new_sib_member);
1333  }
1334  // ensure recursive call
1335  siblings_expansion_with_blockers(new_sib, max_dim, k - 1, block_simplex);
1336  }
1337  } else {
1338  // ensure the children property
1339  simplex->second.assign_children(siblings);
1340  }
1341  }
1342  }
1343 
1348  Simplex_handle find_child(Simplex_handle sh, Vertex_handle vh) const {
1349  if (!has_children(sh))
1350  return null_simplex();
1351 
1352  Simplex_handle child = sh->second.children()->find(vh);
1353  // Specific case of boost::flat_map does not find, returns boost::flat_map::end()
1354  // in simplex tree we want a null_simplex()
1355  if (child == sh->second.children()->members().end())
1356  return null_simplex();
1357 
1358  return child;
1359  }
1360 
1361  public:
1368  void print_hasse(std::ostream& os) {
1369  os << num_simplices() << " " << std::endl;
1370  for (auto sh : filtration_simplex_range()) {
1371  os << dimension(sh) << " ";
1372  for (auto b_sh : boundary_simplex_range(sh)) {
1373  os << key(b_sh) << " ";
1374  }
1375  os << filtration(sh) << " \n";
1376  }
1377  }
1378 
1379  public:
1387  bool modified = false;
1388  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1389  for (auto& simplex : boost::adaptors::reverse(root_.members())) {
1390  if (has_children(&simplex)) {
1391  modified |= rec_make_filtration_non_decreasing(simplex.second.children());
1392  }
1393  }
1394  if(modified)
1395  clear_filtration(); // Drop the cache.
1396  return modified;
1397  }
1398 
1399  private:
1404  bool rec_make_filtration_non_decreasing(Siblings * sib) {
1405  bool modified = false;
1406 
1407  // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
1408  for (auto& simplex : boost::adaptors::reverse(sib->members())) {
1409  // Find the maximum filtration value in the border
1411  Boundary_simplex_iterator max_border = std::max_element(std::begin(boundary), std::end(boundary),
1412  [](Simplex_handle sh1, Simplex_handle sh2) {
1413  return filtration(sh1) < filtration(sh2);
1414  });
1415 
1416  Filtration_value max_filt_border_value = filtration(*max_border);
1417  // Replacing if(f<max) with if(!(f>=max)) would mean that if f is NaN, we replace it with the max of the children.
1418  // That seems more useful than keeping NaN.
1419  if (!(simplex.second.filtration() >= max_filt_border_value)) {
1420  // Store the filtration modification information
1421  modified = true;
1422  simplex.second.assign_filtration(max_filt_border_value);
1423  }
1424  if (has_children(&simplex)) {
1425  modified |= rec_make_filtration_non_decreasing(simplex.second.children());
1426  }
1427  }
1428  // Make the modified information to be traced by upper call
1429  return modified;
1430  }
1431 
1432  public:
1441  bool modified = rec_prune_above_filtration(root(), filtration);
1442  if(modified)
1443  clear_filtration(); // Drop the cache.
1444  return modified;
1445  }
1446 
1447  private:
1448  bool rec_prune_above_filtration(Siblings* sib, Filtration_value filt) {
1449  auto&& list = sib->members();
1450  auto last = std::remove_if(list.begin(), list.end(), [this,filt](Dit_value_t& simplex) {
1451  if (simplex.second.filtration() <= filt) return false;
1452  if (has_children(&simplex)) rec_delete(simplex.second.children());
1453  // dimension may need to be lowered
1454  dimension_to_be_lowered_ = true;
1455  return true;
1456  });
1457 
1458  bool modified = (last != list.end());
1459  if (last == list.begin() && sib != root()) {
1460  // Removing the whole siblings, parent becomes a leaf.
1461  sib->oncles()->members()[sib->parent()].assign_children(sib->oncles());
1462  delete sib;
1463  // dimension may need to be lowered
1464  dimension_to_be_lowered_ = true;
1465  return true;
1466  } else {
1467  // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones.
1468  list.erase(last, list.end());
1469  for (auto&& simplex : list)
1470  if (has_children(&simplex))
1471  modified |= rec_prune_above_filtration(simplex.second.children(), filt);
1472  }
1473  return modified;
1474  }
1475 
1476  private:
1482  bool lower_upper_bound_dimension() {
1483  // reset automatic detection to recompute
1484  dimension_to_be_lowered_ = false;
1485  int new_dimension = -1;
1486  // Browse the tree from the left to the right as higher dimension cells are more likely on the left part of the tree
1487  for (Simplex_handle sh : complex_simplex_range()) {
1488 #ifdef DEBUG_TRACES
1489  for (auto vertex : simplex_vertex_range(sh)) {
1490  std::clog << " " << vertex;
1491  }
1492  std::clog << std::endl;
1493 #endif // DEBUG_TRACES
1494 
1495  int sh_dimension = dimension(sh);
1496  if (sh_dimension >= dimension_)
1497  // Stop browsing as soon as the dimension is reached, no need to go further
1498  return false;
1499  new_dimension = (std::max)(new_dimension, sh_dimension);
1500  }
1501  dimension_ = new_dimension;
1502  return true;
1503  }
1504 
1505 
1506  public:
1516  // Guarantee the simplex has no children
1517  GUDHI_CHECK(!has_children(sh),
1518  std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children"));
1519 
1520  // Simplex is a leaf, it means the child is the Siblings owning the leaf
1521  Siblings* child = sh->second.children();
1522 
1523  if ((child->size() > 1) || (child == root())) {
1524  // Not alone, just remove it from members
1525  // Special case when child is the root of the simplex tree, just remove it from members
1526  child->erase(sh);
1527  } else {
1528  // Sibling is emptied : must be deleted, and its parent must point on his own Sibling
1529  child->oncles()->members().at(child->parent()).assign_children(child->oncles());
1530  delete child;
1531  // dimension may need to be lowered
1532  dimension_to_be_lowered_ = true;
1533  }
1534  }
1535 
1552  std::pair<Filtration_value, Extended_simplex_type> decode_extended_filtration(Filtration_value f, const Extended_filtration_data& efd){
1553  std::pair<Filtration_value, Extended_simplex_type> p;
1554  Filtration_value minval = efd.minval;
1555  Filtration_value maxval = efd.maxval;
1556  if (f >= -2 && f <= -1){
1557  p.first = minval + (maxval-minval)*(f + 2); p.second = Extended_simplex_type::UP;
1558  }
1559  else if (f >= 1 && f <= 2){
1560  p.first = minval - (maxval-minval)*(f - 2); p.second = Extended_simplex_type::DOWN;
1561  }
1562  else{
1563  p.first = std::numeric_limits<Filtration_value>::quiet_NaN(); p.second = Extended_simplex_type::EXTRA;
1564  }
1565  return p;
1566  };
1567 
1581  Extended_filtration_data extend_filtration() {
1582  clear_filtration(); // Drop the cache.
1583 
1584  // Compute maximum and minimum of filtration values
1585  Vertex_handle maxvert = std::numeric_limits<Vertex_handle>::min();
1586  Filtration_value minval = std::numeric_limits<Filtration_value>::infinity();
1587  Filtration_value maxval = -std::numeric_limits<Filtration_value>::infinity();
1588  for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh){
1589  Filtration_value f = this->filtration(sh);
1590  minval = std::min(minval, f);
1591  maxval = std::max(maxval, f);
1592  maxvert = std::max(sh->first, maxvert);
1593  }
1594 
1595  GUDHI_CHECK(maxvert < std::numeric_limits<Vertex_handle>::max(), std::invalid_argument("Simplex_tree contains a vertex with the largest Vertex_handle"));
1596  maxvert += 1;
1597 
1598  Simplex_tree st_copy = *this;
1599 
1600  // Add point for coning the simplicial complex
1601  this->insert_simplex({maxvert}, -3);
1602 
1603  // For each simplex
1604  std::vector<Vertex_handle> vr;
1605  for (auto sh_copy : st_copy.complex_simplex_range()){
1606 
1607  // Locate simplex
1608  vr.clear();
1609  for (auto vh : st_copy.simplex_vertex_range(sh_copy)){
1610  vr.push_back(vh);
1611  }
1612  auto sh = this->find(vr);
1613 
1614  // Create cone on simplex
1615  vr.push_back(maxvert);
1616  if (this->dimension(sh) == 0){
1617  Filtration_value v = this->filtration(sh);
1618  Filtration_value scaled_v = (v-minval)/(maxval-minval);
1619  // Assign ascending value between -2 and -1 to vertex
1620  this->assign_filtration(sh, -2 + scaled_v);
1621  // Assign descending value between 1 and 2 to cone on vertex
1622  this->insert_simplex(vr, 2 - scaled_v);
1623  }
1624  else{
1625  // Assign value -3 to simplex and cone on simplex
1626  this->assign_filtration(sh, -3);
1627  this->insert_simplex(vr, -3);
1628  }
1629  }
1630 
1631  // Automatically assign good values for simplices
1633 
1634  // Return the filtration data
1635  Extended_filtration_data efd(minval, maxval);
1636  return efd;
1637  }
1638 
1644  auto filt = filtration_(sh);
1645  for(auto v : simplex_vertex_range(sh))
1646  if(filtration_(find_vertex(v)) == filt)
1647  return v;
1648  return null_vertex();
1649  }
1650 
1658  // See issue #251 for potential speed improvements.
1659  auto&& vertices = simplex_vertex_range(sh); // vertices in decreasing order
1660  auto end = std::end(vertices);
1661  auto vi = std::begin(vertices);
1662  GUDHI_CHECK(vi != end, "empty simplex");
1663  auto v0 = *vi;
1664  ++vi;
1665  GUDHI_CHECK(vi != end, "simplex of dimension 0");
1666  if(std::next(vi) == end) return sh; // shortcut for dimension 1
1667  boost::container::static_vector<Vertex_handle, 40> suffix;
1668  suffix.push_back(v0);
1669  auto filt = filtration_(sh);
1670  do
1671  {
1672  Vertex_handle v = *vi;
1673  auto&& children1 = find_vertex(v)->second.children()->members_;
1674  for(auto w : suffix){
1675  // Can we take advantage of the fact that suffix is ordered?
1676  Simplex_handle s = children1.find(w);
1677  if(filtration_(s) == filt)
1678  return s;
1679  }
1680  suffix.push_back(v);
1681  }
1682  while(++vi != end);
1683  return null_simplex();
1684  }
1685 
1691  auto filt = filtration_(sh);
1692  // Naive implementation, it can be sped up.
1693  for(auto b : boundary_simplex_range(sh))
1694  if(filtration_(b) == filt)
1696  return sh; // None of its faces has the same filtration.
1697  }
1698 
1699  public:
1708  void reset_filtration(Filtration_value filt_value, int min_dim = 0) {
1709  rec_reset_filtration(&root_, filt_value, min_dim);
1710  clear_filtration(); // Drop the cache.
1711  }
1712 
1713  private:
1719  void rec_reset_filtration(Siblings * sib, Filtration_value filt_value, int min_depth) {
1720  for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
1721  if (min_depth <= 0) {
1722  sh->second.assign_filtration(filt_value);
1723  }
1724  if (has_children(sh)) {
1725  rec_reset_filtration(sh->second.children(), filt_value, min_depth - 1);
1726  }
1727  }
1728  }
1729 
1730  private:
1731  Vertex_handle null_vertex_;
1734  Siblings root_;
1736  std::vector<Simplex_handle> filtration_vect_;
1738  int dimension_;
1739  bool dimension_to_be_lowered_ = false;
1740 };
1741 
1742 // Print a Simplex_tree in os.
1743 template<typename...T>
1744 std::ostream& operator<<(std::ostream & os, Simplex_tree<T...> & st) {
1745  for (auto sh : st.filtration_simplex_range()) {
1746  os << st.dimension(sh) << " ";
1747  for (auto v : st.simplex_vertex_range(sh)) {
1748  os << v << " ";
1749  }
1750  os << st.filtration(sh) << "\n"; // TODO(VR): why adding the key ?? not read ?? << " " << st.key(sh) << " \n";
1751  }
1752  return os;
1753 }
1754 
1755 template<typename...T>
1756 std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
1757  typedef Simplex_tree<T...> ST;
1758  std::vector<typename ST::Vertex_handle> simplex;
1759  typename ST::Filtration_value fil;
1760  int max_dim = -1;
1761  while (read_simplex(is, simplex, fil)) {
1762  // read all simplices in the file as a list of vertices
1763  // Warning : simplex_size needs to be casted in int - Can be 0
1764  int dim = static_cast<int> (simplex.size() - 1);
1765  if (max_dim < dim) {
1766  max_dim = dim;
1767  }
1768  // insert every simplex in the simplex tree
1769  st.insert_simplex(simplex, fil);
1770  simplex.clear();
1771  }
1772  st.set_dimension(max_dim);
1773 
1774  return is;
1775 }
1776 
1783  typedef int Vertex_handle;
1784  typedef double Filtration_value;
1785  typedef std::uint32_t Simplex_key;
1786  static const bool store_key = true;
1787  static const bool store_filtration = true;
1788  static const bool contiguous_vertices = false;
1789 };
1790 
1799  typedef int Vertex_handle;
1800  typedef float Filtration_value;
1801  typedef std::uint32_t Simplex_key;
1802  static const bool store_key = true;
1803  static const bool store_filtration = true;
1804  static const bool contiguous_vertices = true;
1805 };
1806  // end addtogroup simplex_tree
1808 
1809 } // namespace Gudhi
1810 
1811 #endif // SIMPLEX_TREE_H_
Extended simplex type data structure for representing the type of simplices in an extended filtration...
Iterator over the simplices of the boundary of a simplex and their opposite vertices.
Definition: Simplex_tree_iterators.h:190
Iterator over the simplices of the boundary of a simplex.
Definition: Simplex_tree_iterators.h:83
Iterator over the simplices of a simplicial complex.
Definition: Simplex_tree_iterators.h:300
Iterator over the vertices of a simplex in a SimplexTree.
Definition: Simplex_tree_iterators.h:38
Iterator over the simplices of the skeleton of a given dimension of the simplicial complex.
Definition: Simplex_tree_iterators.h:374
Simplex Tree data structure for representing simplicial complexes.
Definition: Simplex_tree.h:79
Simplex_tree(Simplex_tree &&complex_source)
User-defined move constructor relocates the whole tree structure.
Definition: Simplex_tree.h:347
bool operator==(Simplex_tree &st2)
Checks if two simplex trees are equal.
Definition: Simplex_tree.h:472
Options::Filtration_value Filtration_value
Type for the value of the filtration function.
Definition: Simplex_tree.h:86
Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension)
Compute the cofaces of a n simplex.
Definition: Simplex_tree.h:1019
Simplex_tree_boundary_opposite_vertex_simplex_iterator< Simplex_tree > Boundary_opposite_vertex_simplex_iterator
Iterator over the simplices of the boundary of a simplex and their opposite vertices.
Definition: Simplex_tree.h:196
void reset_filtration(Filtration_value filt_value, int min_dim=0)
This function resets the filtration value of all the simplices of dimension at least min_dim....
Definition: Simplex_tree.h:1708
void assign_filtration(Simplex_handle sh, Filtration_value fv)
Sets the filtration value of a simplex.
Definition: Simplex_tree.h:546
Simplex_tree & operator=(Simplex_tree &&complex_source)
User-defined move assignment relocates the whole tree structure.
Definition: Simplex_tree.h:381
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:807
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:1386
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:152
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:1643
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:271
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:567
boost::iterator_range< Boundary_simplex_iterator > Boundary_simplex_range
Range over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:192
Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const
Returns a range over the vertices of a simplex.
Definition: Simplex_tree.h:282
void clear_filtration()
Clears the filtration cache produced by initialize_filtration().
Definition: Simplex_tree.h:945
Simplex_tree_simplex_vertex_iterator< Simplex_tree > Simplex_vertex_iterator
Iterator over the vertices of a simplex.
Definition: Simplex_tree.h:182
static Simplex_key key(Simplex_handle sh)
Returns the key associated to a simplex.
Definition: Simplex_tree.h:518
static Filtration_value filtration(Simplex_handle sh)
Returns the filtration value of a simplex.
Definition: Simplex_tree.h:535
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:778
bool operator!=(Simplex_tree &st2)
Checks if two simplex trees are different.
Definition: Simplex_tree.h:480
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by sh has children.
Definition: Simplex_tree.h:628
Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex)
Compute the star of a n simplex.
Definition: Simplex_tree.h:1008
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:1267
boost::iterator_range< Simplex_vertex_iterator > Simplex_vertex_range
Range over the vertices of a simplex.
Definition: Simplex_tree.h:184
void remove_maximal_simplex(Simplex_handle sh)
Remove a maximal simplex.
Definition: Simplex_tree.h:1515
Siblings * root()
Definition: Simplex_tree.h:891
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:868
Options::Simplex_key Simplex_key
Key associated to each simplex.
Definition: Simplex_tree.h:90
Simplex_tree()
Constructs an empty simplex tree.
Definition: Simplex_tree.h:330
void maybe_initialize_filtration()
Initializes the filtration cache if it isn't initialized yet.
Definition: Simplex_tree.h:936
boost::iterator_range< Complex_simplex_iterator > Complex_simplex_range
Range over the simplices of the simplicial complex.
Definition: Simplex_tree.h:204
Simplex_tree_boundary_simplex_iterator< Simplex_tree > Boundary_simplex_iterator
Iterator over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:190
Simplex_tree_siblings< Simplex_tree, Dictionary > Siblings
Set of nodes sharing a same parent in the simplex tree.
Definition: Simplex_tree.h:105
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:641
std::vector< Simplex_handle > Cofaces_simplex_range
Range over the cofaces of a simplex.
Definition: Simplex_tree.h:186
Boundary_opposite_vertex_simplex_range boundary_opposite_vertex_simplex_range(SimplexHandle sh)
Given a simplex, returns a range over the simplices of its boundary and their opposite vertices.
Definition: Simplex_tree.h:320
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:1657
Simplex_tree_complex_simplex_iterator< Simplex_tree > Complex_simplex_iterator
Iterator over the simplices of the simplicial complex.
Definition: Simplex_tree.h:202
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:1552
Simplex_handle simplex(Simplex_key idx) const
Returns the simplex that has index idx in the filtration.
Definition: Simplex_tree.h:526
void initialize_filtration()
Initializes the filtration cache, i.e. sorts the simplices according to their order in the filtration...
Definition: Simplex_tree.h:912
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:251
boost::transform_iterator< return_first, Dictionary_it > Complex_vertex_iterator
Iterator over the vertices of the simplicial complex.
Definition: Simplex_tree.h:176
std::vector< Simplex_handle > Filtration_simplex_range
Range over the simplices of the simplicial complex, ordered by the filtration.
Definition: Simplex_tree.h:214
Filtration_simplex_range::const_iterator Filtration_simplex_iterator
Iterator over the simplices of the simplicial complex, ordered by the filtration.
Definition: Simplex_tree.h:218
Extended_filtration_data extend_filtration()
Extend filtration for computing extended persistence. This function only uses the filtration values a...
Definition: Simplex_tree.h:1581
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:1690
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition: Simplex_tree.h:94
size_t num_vertices() const
Returns the number of vertices in the complex.
Definition: Simplex_tree.h:572
static Siblings * self_siblings(SimplexHandle sh)
Definition: Simplex_tree.h:882
void expansion(int max_dim)
Expands the Simplex_tree containing only its one skeleton until dimension max_dim.
Definition: Simplex_tree.h:1170
Simplex_tree(const Simplex_tree &complex_source)
User-defined copy constructor reproduces the whole tree structure.
Definition: Simplex_tree.h:337
boost::iterator_range< Complex_vertex_iterator > Complex_vertex_range
Range over the vertices of the simplicial complex.
Definition: Simplex_tree.h:178
static Simplex_key null_key()
Returns a fixed number not in the interval [0, num_simplices()).
Definition: Simplex_tree.h:561
Boundary_simplex_range boundary_simplex_range(SimplexHandle sh)
Returns a range over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:303
int dimension(Simplex_handle sh)
Returns the dimension of a simplex.
Definition: Simplex_tree.h:600
bool prune_above_filtration(Filtration_value filtration)
Prune above filtration value given as parameter.
Definition: Simplex_tree.h:1440
int upper_bound_dimension() const
Returns an upper bound on the dimension of the simplicial complex.
Definition: Simplex_tree.h:611
std::pair< Simplex_handle, Simplex_handle > endpoints(Simplex_handle sh)
Definition: Simplex_tree.h:875
int dimension()
Returns the dimension of the simplicial complex.
Definition: Simplex_tree.h:619
size_t num_simplices()
returns the number of simplices in the simplex_tree.
Definition: Simplex_tree.h:578
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:209
boost::iterator_range< Boundary_opposite_vertex_simplex_iterator > Boundary_opposite_vertex_simplex_range
Range over the simplices of the boundary of a simplex and their opposite vertices.
Definition: Simplex_tree.h:198
void insert_graph(const OneSkeletonGraph &skel_graph)
Inserts a 1-skeleton in an empty Simplex_tree.
Definition: Simplex_tree.h:1106
void set_dimension(int dimension)
Set a dimension for the simplicial complex.
Definition: Simplex_tree.h:899
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:212
void print_hasse(std::ostream &os)
Write the hasse diagram of the simplicial complex in os.
Definition: Simplex_tree.h:1368
~Simplex_tree()
Destructor; deallocates the whole tree structure.
Definition: Simplex_tree.h:359
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:556
Simplex_tree & operator=(const Simplex_tree &complex_source)
User-defined copy assignment reproduces the whole tree structure.
Definition: Simplex_tree.h:364
Complex_simplex_range complex_simplex_range()
Returns a range over the simplices of the simplicial complex.
Definition: Simplex_tree.h:237
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:226
Graph simplicial complex methods.
This file includes common file reader for GUDHI.
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
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
Node of a simplex tree with filtration value and simplex key.
Definition: Simplex_tree_node_explicit_storage.h:29
Definition: Simplex_tree.h:1797
Tag for a linear ordering of simplices.
Definition: indexing_tag.h:20
Concept describing an indexing scheme (see FilteredComplex) for applying continuous maps to a cell co...
Definition: IndexingTag.h:18
Key type used as simplex identifier.
Definition: SimplexKey.h:15
Concept of the template parameter for the class Gudhi::Simplex_tree<SimplexTreeOptions>.
Definition: SimplexTreeOptions.h:15
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15