Hasse_complex.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 HASSE_COMPLEX_H_
12 #define HASSE_COMPLEX_H_
13 
14 #include <gudhi/allocator.h>
15 
16 #include <boost/iterator/counting_iterator.hpp>
17 
18 #include <algorithm>
19 #include <utility> // for pair
20 #include <vector>
21 #include <limits> // for infinity value
22 
23 #ifdef GUDHI_USE_TBB
24 #include <tbb/parallel_for.h>
25 #endif
26 
27 namespace Gudhi {
28 
29 template < class HasseCpx >
30 struct Hasse_simplex {
31  // Complex_ds must verify that cpx->key(sh) is the order of sh in the filtration
32 
33  template< class Complex_ds >
34  Hasse_simplex(Complex_ds & cpx
35  , typename Complex_ds::Simplex_handle sh)
36  : filtration_(cpx.filtration(sh))
37  , boundary_() {
38  boundary_.reserve(cpx.dimension(sh) + 1);
39  for (auto b_sh : cpx.boundary_simplex_range(sh)) {
40  boundary_.push_back(cpx.key(b_sh));
41  }
42  }
43 
44  Hasse_simplex(typename HasseCpx::Simplex_key key
45  , typename HasseCpx::Filtration_value fil
46  , std::vector<typename HasseCpx::Simplex_handle> const& boundary)
47  : key_(key)
48  , filtration_(fil)
49  , boundary_(boundary) { }
50 
51  typename HasseCpx::Simplex_key key_;
52  typename HasseCpx::Filtration_value filtration_;
53  std::vector<typename HasseCpx::Simplex_handle> boundary_;
54 };
55 
64 template < typename FiltrationValue = double
65 , typename SimplexKey = int
66 , typename VertexHandle = int
67 >
68 class Hasse_complex {
69  public:
70  typedef Hasse_simplex<Hasse_complex> Hasse_simp;
72  typedef SimplexKey Simplex_key;
73  typedef int Simplex_handle; // index in vector complex_
74 
75  typedef boost::counting_iterator< Simplex_handle > Filtration_simplex_iterator;
76  typedef boost::iterator_range<Filtration_simplex_iterator> Filtration_simplex_range;
77 
78  typedef typename std::vector< Simplex_handle >::iterator Boundary_simplex_iterator;
79  typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
80 
81  typedef typename std::vector< Simplex_handle >::iterator Skeleton_simplex_iterator;
82  typedef boost::iterator_range< Skeleton_simplex_iterator > Skeleton_simplex_range;
83 
84  /* only dimension 0 skeleton_simplex_range(...) */
85  Skeleton_simplex_range skeleton_simplex_range(int dim = 0) {
86  if (dim != 0) {
87  std::cerr << "Dimension must be 0 \n";
88  }
89  return Skeleton_simplex_range(vertices_.begin(), vertices_.end());
90  }
91 
92  template < class Complex_ds >
93  Hasse_complex(Complex_ds & cpx)
94  : complex_(cpx.num_simplices())
95  , vertices_()
96  , num_vertices_()
97  , dim_max_(cpx.dimension()) {
98  int size = complex_.size();
99 #ifdef GUDHI_USE_TBB
100  tbb::parallel_for(0, size, [&](int idx){new (&complex_[idx]) Hasse_simp(cpx, cpx.simplex(idx));});
101  for (int idx=0; idx < size; ++idx)
102  if (complex_[idx].boundary_.empty())
103  vertices_.push_back(idx);
104 #else
105  for (int idx=0; idx < size; ++idx) {
106  new (&complex_[idx]) Hasse_simp(cpx, cpx.simplex(idx));
107  if (complex_[idx].boundary_.empty())
108  vertices_.push_back(idx);
109  }
110 #endif
111  }
112 
113  Hasse_complex()
114  : complex_()
115  , vertices_()
116  , num_vertices_(0)
117  , dim_max_(-1) { }
118 
119  size_t num_simplices() {
120  return complex_.size();
121  }
122 
123  Filtration_simplex_range filtration_simplex_range() {
124  return Filtration_simplex_range(Filtration_simplex_iterator(0)
125  , Filtration_simplex_iterator(complex_.size()));
126  }
127 
128  Simplex_key key(Simplex_handle sh) {
129  return complex_[sh].key_;
130  }
131 
132  Simplex_key null_key() {
133  return -1;
134  }
135 
136  Simplex_handle simplex(Simplex_key key) {
137  if (key == null_key()) return null_simplex();
138  return key;
139  }
140 
141  Simplex_handle null_simplex() {
142  return -1;
143  }
144 
145  Filtration_value filtration(Simplex_handle sh) {
146  if (sh == null_simplex()) {
147  return std::numeric_limits<Filtration_value>::infinity();
148  }
149  return complex_[sh].filtration_;
150  }
151 
152  int dimension(Simplex_handle sh) {
153  if (complex_[sh].boundary_.empty()) return 0;
154  return complex_[sh].boundary_.size() - 1;
155  }
156 
157  int dimension() {
158  return dim_max_;
159  }
160 
161  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
162  return std::pair<Simplex_handle, Simplex_handle>(complex_[sh].boundary_[0]
163  , complex_[sh].boundary_[1]);
164  }
165 
166  void assign_key(Simplex_handle sh, Simplex_key key) {
167  complex_[sh].key_ = key;
168  }
169 
170  Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) {
171  return Boundary_simplex_range(complex_[sh].boundary_.begin()
172  , complex_[sh].boundary_.end());
173  }
174 
175  void display_simplex(Simplex_handle sh) {
176  std::cout << dimension(sh) << " ";
177  for (auto sh_b : boundary_simplex_range(sh)) std::cout << sh_b << " ";
178  std::cout << " " << filtration(sh) << " key=" << key(sh);
179  }
180 
181  void initialize_filtration() {
182  // Setting the keys is done by pcoh, Simplex_tree doesn't do it either.
183 #if 0
184  Simplex_key key = 0;
185  for (auto & h_simp : complex_)
186  h_simp.key_ = key++;
187 #endif
188  }
189 
190  std::vector< Hasse_simp, Gudhi::no_init_allocator<Hasse_simp> > complex_;
191  std::vector<Simplex_handle> vertices_;
192  size_t num_vertices_;
193  int dim_max_;
194 };
195 
196 template< typename T1, typename T2, typename T3 >
197 std::istream& operator>>(std::istream & is
198  , Hasse_complex< T1, T2, T3 > & hcpx) {
199  assert(hcpx.num_simplices() == 0);
200 
201  size_t num_simp;
202  is >> num_simp;
203  hcpx.complex_.reserve(num_simp);
204 
205  std::vector< typename Hasse_complex<T1, T2, T3>::Simplex_key > boundary;
206  typename Hasse_complex<T1, T2, T3>::Filtration_value fil;
207  typename Hasse_complex<T1, T2, T3>::Filtration_value max_fil = 0;
208  int max_dim = -1;
209  int key = 0;
210  // read all simplices in the file as a list of vertices
211  while (read_hasse_simplex(is, boundary, fil)) {
212  // insert every simplex in the simplex tree
213  hcpx.complex_.emplace_back(key, fil, boundary);
214 
215  if (max_dim < hcpx.dimension(key)) {
216  max_dim = hcpx.dimension(key);
217  }
218  if (hcpx.dimension(key) == 0) {
219  hcpx.vertices_.push_back(key);
220  }
221  if (max_fil < fil) {
222  max_fil = fil;
223  }
224 
225  ++key;
226  boundary.clear();
227  }
228 
229  hcpx.dim_max_ = max_dim;
230 
231  return is;
232 }
233 
234 } // namespace Gudhi
235 
236 #endif // HASSE_COMPLEX_H_
FilteredComplex::filtration
Filtration_value filtration(Simplex_handle sh)
Returns the filtration value of a simplex.
FilteredComplex::assign_key
void assign_key(Simplex_handle sh, Simplex_key n)
Store a number for a simplex, which can later be retrieved with key(sh).
Gudhi::read_hasse_simplex
bool read_hasse_simplex(std::istream &in_, std::vector< Simplex_key > &boundary, Filtration_value &fil)
Read a hasse simplex from a file.
Definition: reader_utils.h:183
SimplexKey
Key type used as simplex identifier.
Definition: SimplexKey.h:15
FilteredComplex::boundary_simplex_range
Boundary_simplex_range boundary_simplex_range(Simplex_handle sh)
Returns a range giving access to all simplices of the boundary of a simplex, i.e. the set of codimens...
FilteredComplex::simplex
Simplex_handle simplex(size_t idx)
Returns the simplex that has index idx in the filtration.
VertexHandle
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
FilteredComplex::dimension
int dimension(Simplex_handle sh)
Returns the dimension of a simplex.
FilteredComplex::key
Simplex_key key(Simplex_handle sh)
Returns the number stored for a simplex by assign_key.
FiltrationValue
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
GUDHI  Version 3.1.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Mon Apr 25 2022 14:03:04 for GUDHI by Doxygen 1.8.17