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 #ifndef Q_MOC_RUN
25 #include <tbb/parallel_for.h>
26 #endif
27 #endif
28 
29 namespace Gudhi {
30 
31 template < class HasseCpx >
32 struct Hasse_simplex {
33  // Complex_ds must verify that cpx->key(sh) is the order of sh in the filtration
34 
35  template< class Complex_ds >
36  Hasse_simplex(Complex_ds & cpx
37  , typename Complex_ds::Simplex_handle sh)
38  : filtration_(cpx.filtration(sh))
39  , boundary_() {
40  boundary_.reserve(cpx.dimension(sh) + 1);
41  for (auto b_sh : cpx.boundary_simplex_range(sh)) {
42  boundary_.push_back(cpx.key(b_sh));
43  }
44  }
45 
46  Hasse_simplex(typename HasseCpx::Simplex_key key
47  , typename HasseCpx::Filtration_value fil
48  , std::vector<typename HasseCpx::Simplex_handle> const& boundary)
49  : key_(key)
50  , filtration_(fil)
51  , boundary_(boundary) { }
52 
53  typename HasseCpx::Simplex_key key_;
54  typename HasseCpx::Filtration_value filtration_;
55  std::vector<typename HasseCpx::Simplex_handle> boundary_;
56 };
57 
66 template < typename FiltrationValue = double
67 , typename SimplexKey = int
68 , typename VertexHandle = int
69 >
70 class Hasse_complex {
71  public:
72  typedef Hasse_simplex<Hasse_complex> Hasse_simp;
74  typedef SimplexKey Simplex_key;
75  typedef int Simplex_handle; // index in vector complex_
76 
77  typedef boost::counting_iterator< Simplex_handle > Filtration_simplex_iterator;
78  typedef boost::iterator_range<Filtration_simplex_iterator> Filtration_simplex_range;
79 
80  typedef typename std::vector< Simplex_handle >::iterator Boundary_simplex_iterator;
81  typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
82 
83  typedef typename std::vector< Simplex_handle >::iterator Skeleton_simplex_iterator;
84  typedef boost::iterator_range< Skeleton_simplex_iterator > Skeleton_simplex_range;
85 
86  /* only dimension 0 skeleton_simplex_range(...) */
87  Skeleton_simplex_range skeleton_simplex_range(int dim = 0) {
88  if (dim != 0) {
89  std::cerr << "Dimension must be 0 \n";
90  }
91  return Skeleton_simplex_range(vertices_.begin(), vertices_.end());
92  }
93 
94  template < class Complex_ds >
95  Hasse_complex(Complex_ds & cpx)
96  : complex_(cpx.num_simplices())
97  , vertices_()
98  , num_vertices_()
99  , dim_max_(cpx.dimension()) {
100  int size = complex_.size();
101 #ifdef GUDHI_USE_TBB
102  tbb::parallel_for(0, size, [&](int idx){new (&complex_[idx]) Hasse_simp(cpx, cpx.simplex(idx));});
103  for (int idx=0; idx < size; ++idx)
104  if (complex_[idx].boundary_.empty())
105  vertices_.push_back(idx);
106 #else
107  for (int idx=0; idx < size; ++idx) {
108  new (&complex_[idx]) Hasse_simp(cpx, cpx.simplex(idx));
109  if (complex_[idx].boundary_.empty())
110  vertices_.push_back(idx);
111  }
112 #endif
113  }
114 
115  Hasse_complex()
116  : complex_()
117  , vertices_()
118  , num_vertices_(0)
119  , dim_max_(-1) { }
120 
121  size_t num_simplices() {
122  return complex_.size();
123  }
124 
125  Filtration_simplex_range filtration_simplex_range() {
126  return Filtration_simplex_range(Filtration_simplex_iterator(0)
127  , Filtration_simplex_iterator(complex_.size()));
128  }
129 
130  Simplex_key key(Simplex_handle sh) {
131  return complex_[sh].key_;
132  }
133 
134  Simplex_key null_key() {
135  return -1;
136  }
137 
138  Simplex_handle simplex(Simplex_key key) {
139  if (key == null_key()) return null_simplex();
140  return key;
141  }
142 
143  Simplex_handle null_simplex() {
144  return -1;
145  }
146 
147  Filtration_value filtration(Simplex_handle sh) {
148  if (sh == null_simplex()) {
149  return std::numeric_limits<Filtration_value>::infinity();
150  }
151  return complex_[sh].filtration_;
152  }
153 
154  int dimension(Simplex_handle sh) {
155  if (complex_[sh].boundary_.empty()) return 0;
156  return complex_[sh].boundary_.size() - 1;
157  }
158 
159  int dimension() {
160  return dim_max_;
161  }
162 
163  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
164  return std::pair<Simplex_handle, Simplex_handle>(complex_[sh].boundary_[0]
165  , complex_[sh].boundary_[1]);
166  }
167 
168  void assign_key(Simplex_handle sh, Simplex_key key) {
169  complex_[sh].key_ = key;
170  }
171 
172  Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) {
173  return Boundary_simplex_range(complex_[sh].boundary_.begin()
174  , complex_[sh].boundary_.end());
175  }
176 
177  void display_simplex(Simplex_handle sh) {
178  std::clog << dimension(sh) << " ";
179  for (auto sh_b : boundary_simplex_range(sh)) std::clog << sh_b << " ";
180  std::clog << " " << filtration(sh) << " key=" << key(sh);
181  }
182 
183  void initialize_filtration() {
184  // Setting the keys is done by pcoh, Simplex_tree doesn't do it either.
185 #if 0
186  Simplex_key key = 0;
187  for (auto & h_simp : complex_)
188  h_simp.key_ = key++;
189 #endif
190  }
191 
192  std::vector< Hasse_simp, Gudhi::no_init_allocator<Hasse_simp> > complex_;
193  std::vector<Simplex_handle> vertices_;
194  size_t num_vertices_;
195  int dim_max_;
196 };
197 
198 template< typename T1, typename T2, typename T3 >
199 std::istream& operator>>(std::istream & is
200  , Hasse_complex< T1, T2, T3 > & hcpx) {
201  assert(hcpx.num_simplices() == 0);
202 
203  size_t num_simp;
204  is >> num_simp;
205  hcpx.complex_.reserve(num_simp);
206 
207  std::vector< typename Hasse_complex<T1, T2, T3>::Simplex_key > boundary;
208  typename Hasse_complex<T1, T2, T3>::Filtration_value fil;
209  typename Hasse_complex<T1, T2, T3>::Filtration_value max_fil = 0;
210  int max_dim = -1;
211  int key = 0;
212  // read all simplices in the file as a list of vertices
213  while (read_hasse_simplex(is, boundary, fil)) {
214  // insert every simplex in the simplex tree
215  hcpx.complex_.emplace_back(key, fil, boundary);
216 
217  if (max_dim < hcpx.dimension(key)) {
218  max_dim = hcpx.dimension(key);
219  }
220  if (hcpx.dimension(key) == 0) {
221  hcpx.vertices_.push_back(key);
222  }
223  if (max_fil < fil) {
224  max_fil = fil;
225  }
226 
227  ++key;
228  boundary.clear();
229  }
230 
231  hcpx.dim_max_ = max_dim;
232 
233  return is;
234 }
235 
236 } // namespace Gudhi
237 
238 #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.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