Simplex_tree_interface.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): Vincent Rouvreau
4  *
5  * Copyright (C) 2016 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef INCLUDE_SIMPLEX_TREE_INTERFACE_H_
12 #define INCLUDE_SIMPLEX_TREE_INTERFACE_H_
13 
16 #include <gudhi/Simplex_tree.h>
17 #include <gudhi/Points_off_io.h>
18 #ifdef GUDHI_USE_EIGEN3
19 #include <gudhi/Flag_complex_edge_collapser.h>
20 #endif
21 
22 #include <iostream>
23 #include <vector>
24 #include <utility> // std::pair
25 #include <tuple>
26 #include <iterator> // for std::distance
27 
28 namespace Gudhi {
29 
30 template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>
31 class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> {
32  public:
35  using Vertex_handle = typename Base::Vertex_handle;
36  using Simplex_handle = typename Base::Simplex_handle;
37  using Insertion_result = typename std::pair<Simplex_handle, bool>;
38  using Simplex = std::vector<Vertex_handle>;
39  using Simplex_and_filtration = std::pair<Simplex, Filtration_value>;
40  using Filtered_simplices = std::vector<Simplex_and_filtration>;
41  using Skeleton_simplex_iterator = typename Base::Skeleton_simplex_iterator;
42  using Complex_simplex_iterator = typename Base::Complex_simplex_iterator;
43  using Extended_filtration_data = typename Base::Extended_filtration_data;
44  using Boundary_simplex_iterator = typename Base::Boundary_simplex_iterator;
45 
46  public:
47 
48  Extended_filtration_data efd;
49 
50  bool find_simplex(const Simplex& simplex) {
51  return (Base::find(simplex) != Base::null_simplex());
52  }
53 
54  void assign_simplex_filtration(const Simplex& simplex, Filtration_value filtration) {
55  Base::assign_filtration(Base::find(simplex), filtration);
57  }
58 
59  bool insert(const Simplex& simplex, Filtration_value filtration = 0) {
60  Insertion_result result = Base::insert_simplex_and_subfaces(simplex, filtration);
61  if (result.first != Base::null_simplex())
63  return (result.second);
64  }
65 
66  // Do not interface this function, only used in alpha complex interface for complex creation
67  bool insert_simplex(const Simplex& simplex, Filtration_value filtration = 0) {
68  Insertion_result result = Base::insert_simplex(simplex, filtration);
69  return (result.second);
70  }
71 
72  // Do not interface this function, only used in interface for complex creation
73  bool insert_simplex_and_subfaces(const Simplex& simplex, Filtration_value filtration = 0) {
74  Insertion_result result = Base::insert_simplex_and_subfaces(simplex, filtration);
75  return (result.second);
76  }
77 
78  // Do not interface this function, only used in strong witness interface for complex creation
79  bool insert_simplex(const std::vector<std::size_t>& simplex, Filtration_value filtration = 0) {
80  Insertion_result result = Base::insert_simplex(simplex, filtration);
81  return (result.second);
82  }
83 
84  // Do not interface this function, only used in strong witness interface for complex creation
85  bool insert_simplex_and_subfaces(const std::vector<std::size_t>& simplex, Filtration_value filtration = 0) {
86  Insertion_result result = Base::insert_simplex_and_subfaces(simplex, filtration);
87  return (result.second);
88  }
89 
90  Filtration_value simplex_filtration(const Simplex& simplex) {
91  return Base::filtration(Base::find(simplex));
92  }
93 
94  void remove_maximal_simplex(const Simplex& simplex) {
97  }
98 
99  Simplex_and_filtration get_simplex_and_filtration(Simplex_handle f_simplex) {
100  Simplex simplex;
101  for (auto vertex : Base::simplex_vertex_range(f_simplex)) {
102  simplex.insert(simplex.begin(), vertex);
103  }
104  return std::make_pair(std::move(simplex), Base::filtration(f_simplex));
105  }
106 
107  Filtered_simplices get_star(const Simplex& simplex) {
108  Filtered_simplices star;
109  for (auto f_simplex : Base::star_simplex_range(Base::find(simplex))) {
110  Simplex simplex_star;
111  for (auto vertex : Base::simplex_vertex_range(f_simplex)) {
112  simplex_star.insert(simplex_star.begin(), vertex);
113  }
114  star.push_back(std::make_pair(simplex_star, Base::filtration(f_simplex)));
115  }
116  return star;
117  }
118 
119  Filtered_simplices get_cofaces(const Simplex& simplex, int dimension) {
120  Filtered_simplices cofaces;
121  for (auto f_simplex : Base::cofaces_simplex_range(Base::find(simplex), dimension)) {
122  Simplex simplex_coface;
123  for (auto vertex : Base::simplex_vertex_range(f_simplex)) {
124  simplex_coface.insert(simplex_coface.begin(), vertex);
125  }
126  cofaces.push_back(std::make_pair(simplex_coface, Base::filtration(f_simplex)));
127  }
128  return cofaces;
129  }
130 
131  void compute_extended_filtration() {
132  this->efd = this->extend_filtration();
133  return;
134  }
135 
136  std::vector<std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>> compute_extended_persistence_subdiagrams(const std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>& dgm, Filtration_value min_persistence){
137  std::vector<std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>> new_dgm(4);
138  for (unsigned int i = 0; i < dgm.size(); i++){
139  std::pair<Filtration_value, Extended_simplex_type> px = this->decode_extended_filtration(dgm[i].second.first, this->efd);
140  std::pair<Filtration_value, Extended_simplex_type> py = this->decode_extended_filtration(dgm[i].second.second, this->efd);
141  std::pair<int, std::pair<Filtration_value, Filtration_value>> pd_point = std::make_pair(dgm[i].first, std::make_pair(px.first, py.first));
142  if(std::abs(px.first - py.first) > min_persistence){
143  //Ordinary
144  if (px.second == Extended_simplex_type::UP && py.second == Extended_simplex_type::UP){
145  new_dgm[0].push_back(pd_point);
146  }
147  // Relative
148  else if (px.second == Extended_simplex_type::DOWN && py.second == Extended_simplex_type::DOWN){
149  new_dgm[1].push_back(pd_point);
150  }
151  else{
152  // Extended+
153  if (px.first < py.first){
154  new_dgm[2].push_back(pd_point);
155  }
156  //Extended-
157  else{
158  new_dgm[3].push_back(pd_point);
159  }
160  }
161  }
162  }
163  return new_dgm;
164  }
165 
166  Simplex_tree_interface* collapse_edges(int nb_collapse_iteration) {
167 #ifdef GUDHI_USE_EIGEN3
168  using Filtered_edge = std::tuple<Vertex_handle, Vertex_handle, Filtration_value>;
169  std::vector<Filtered_edge> edges;
170  for (Simplex_handle sh : Base::skeleton_simplex_range(1)) {
171  if (Base::dimension(sh) == 1) {
173  auto vit = rg.begin();
174  Vertex_handle v = *vit;
175  Vertex_handle w = *++vit;
176  edges.emplace_back(v, w, Base::filtration(sh));
177  }
178  }
179 
180  for (int iteration = 0; iteration < nb_collapse_iteration; iteration++) {
182  }
183  Simplex_tree_interface* collapsed_stree_ptr = new Simplex_tree_interface();
184  // Copy the original 0-skeleton
185  for (Simplex_handle sh : Base::skeleton_simplex_range(0)) {
186  collapsed_stree_ptr->insert({*(Base::simplex_vertex_range(sh).begin())}, Base::filtration(sh));
187  }
188  // Insert remaining edges
189  for (auto remaining_edge : edges) {
190  collapsed_stree_ptr->insert({std::get<0>(remaining_edge), std::get<1>(remaining_edge)}, std::get<2>(remaining_edge));
191  }
192  return collapsed_stree_ptr;
193 #else
194  throw std::runtime_error("Unable to collapse edges as it requires Eigen3 >= 3.1.0.");
195 #endif
196  }
197 
198  // Iterator over the simplex tree
199  Complex_simplex_iterator get_simplices_iterator_begin() {
200  // this specific case works because the range is just a pair of iterators - won't work if range was a vector
201  return Base::complex_simplex_range().begin();
202  }
203 
204  Complex_simplex_iterator get_simplices_iterator_end() {
205  // this specific case works because the range is just a pair of iterators - won't work if range was a vector
206  return Base::complex_simplex_range().end();
207  }
208 
209  typename std::vector<Simplex_handle>::const_iterator get_filtration_iterator_begin() {
210  // Base::initialize_filtration(); already performed in filtration_simplex_range
211  // this specific case works because the range is just a pair of iterators - won't work if range was a vector
212  return Base::filtration_simplex_range().begin();
213  }
214 
215  typename std::vector<Simplex_handle>::const_iterator get_filtration_iterator_end() {
216  // this specific case works because the range is just a pair of iterators - won't work if range was a vector
217  return Base::filtration_simplex_range().end();
218  }
219 
220  Skeleton_simplex_iterator get_skeleton_iterator_begin(int dimension) {
221  // this specific case works because the range is just a pair of iterators - won't work if range was a vector
222  return Base::skeleton_simplex_range(dimension).begin();
223  }
224 
225  Skeleton_simplex_iterator get_skeleton_iterator_end(int dimension) {
226  // this specific case works because the range is just a pair of iterators - won't work if range was a vector
227  return Base::skeleton_simplex_range(dimension).end();
228  }
229 
230  std::pair<Boundary_simplex_iterator, Boundary_simplex_iterator> get_boundary_iterators(const Simplex& simplex) {
231  auto bd_sh = Base::find(simplex);
232  if (bd_sh == Base::null_simplex())
233  throw std::runtime_error("simplex not found - cannot find boundaries");
234  // this specific case works because the range is just a pair of iterators - won't work if range was a vector
235  auto boundary_srange = Base::boundary_simplex_range(bd_sh);
236  return std::make_pair(boundary_srange.begin(), boundary_srange.end());
237  }
238 };
239 
240 } // namespace Gudhi
241 
242 #endif // INCLUDE_SIMPLEX_TREE_INTERFACE_H_
Options::Filtration_value Filtration_value
Type for the value of the filtration function.
Definition: Simplex_tree.h:82
Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension)
Compute the cofaces of a n simplex.
Definition: Simplex_tree.h:993
void assign_filtration(Simplex_handle sh, Filtration_value fv)
Sets the filtration value of a simplex.
Definition: Simplex_tree.h:520
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:781
Dictionary::iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition: Simplex_tree.h:149
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:262
Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const
Returns a range over the vertices of a simplex.
Definition: Simplex_tree.h:273
void clear_filtration()
Clears the filtration cache produced by initialize_filtration().
Definition: Simplex_tree.h:919
static Filtration_value filtration(Simplex_handle sh)
Returns the filtration value of a simplex.
Definition: Simplex_tree.h:509
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:752
Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex)
Compute the star of a n simplex.
Definition: Simplex_tree.h:982
boost::iterator_range< Simplex_vertex_iterator > Simplex_vertex_range
Range over the vertices of a simplex.
Definition: Simplex_tree.h:181
void remove_maximal_simplex(Simplex_handle sh)
Remove a maximal simplex.
Definition: Simplex_tree.h:1489
Simplex_tree_boundary_simplex_iterator< Simplex_tree > Boundary_simplex_iterator
Iterator over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:187
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:615
Simplex_tree_complex_simplex_iterator< Simplex_tree > Complex_simplex_iterator
Iterator over the simplices of the simplicial complex.
Definition: Simplex_tree.h:193
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:1526
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:242
Extended_filtration_data extend_filtration()
Extend filtration for computing extended persistence. This function only uses the filtration values a...
Definition: Simplex_tree.h:1555
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition: Simplex_tree.h:90
Boundary_simplex_range boundary_simplex_range(SimplexHandle sh)
Returns a range over the simplices of the boundary of a simplex.
Definition: Simplex_tree.h:294
int dimension()
Returns the dimension of the simplicial complex.
Definition: Simplex_tree.h:593
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:200
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:530
Complex_simplex_range complex_simplex_range()
Returns a range over the simplices of the simplicial complex.
Definition: Simplex_tree.h:228
Abstract simplex used in Skeleton blockers data-structure.
Definition: Skeleton_blocker_simplex.h:38
Global distance functions.
Graph simplicial complex methods.
auto flag_complex_collapse_edges(const FilteredEdgeRange &edges)
Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the per...
Definition: Flag_complex_edge_collapser.h:363
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Aug 16 2022 14:01:50 for GUDHIdev by Doxygen 1.9.1