Hasse_complex.h
1 /* This file is part of the Gudhi Library. The Gudhi library
2  * (Geometric Understanding in Higher Dimensions) is a generic C++
3  * library for computational topology.
4  *
5  * Author(s): ClĂ©ment Maria
6  *
7  * Copyright (C) 2014 Inria
8  *
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef HASSE_COMPLEX_H_
24 #define HASSE_COMPLEX_H_
25 
26 #include <gudhi/allocator.h>
27 
28 #include <boost/iterator/counting_iterator.hpp>
29 
30 #include <algorithm>
31 #include <utility> // for pair
32 #include <vector>
33 #include <limits> // for infinity value
34 
35 #ifdef GUDHI_USE_TBB
36 #include <tbb/parallel_for.h>
37 #endif
38 
39 namespace Gudhi {
40 
41 template < class HasseCpx >
42 struct Hasse_simplex {
43  // Complex_ds must verify that cpx->key(sh) is the order of sh in the filtration
44 
45  template< class Complex_ds >
46  Hasse_simplex(Complex_ds & cpx
47  , typename Complex_ds::Simplex_handle sh)
48  : filtration_(cpx.filtration(sh))
49  , boundary_() {
50  boundary_.reserve(cpx.dimension(sh) + 1);
51  for (auto b_sh : cpx.boundary_simplex_range(sh)) {
52  boundary_.push_back(cpx.key(b_sh));
53  }
54  }
55 
56  Hasse_simplex(typename HasseCpx::Simplex_key key
57  , typename HasseCpx::Filtration_value fil
58  , std::vector<typename HasseCpx::Simplex_handle> const& boundary)
59  : key_(key)
60  , filtration_(fil)
61  , boundary_(boundary) { }
62 
63  typename HasseCpx::Simplex_key key_;
64  typename HasseCpx::Filtration_value filtration_;
65  std::vector<typename HasseCpx::Simplex_handle> boundary_;
66 };
67 
76 template < typename FiltrationValue = double
77 , typename SimplexKey = int
78 , typename VertexHandle = int
79 >
80 class Hasse_complex {
81  public:
82  typedef Hasse_simplex<Hasse_complex> Hasse_simp;
84  typedef SimplexKey Simplex_key;
85  typedef int Simplex_handle; // index in vector complex_
86 
87  typedef boost::counting_iterator< Simplex_handle > Filtration_simplex_iterator;
88  typedef boost::iterator_range<Filtration_simplex_iterator> Filtration_simplex_range;
89 
90  typedef typename std::vector< Simplex_handle >::iterator Boundary_simplex_iterator;
91  typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
92 
93  typedef typename std::vector< Simplex_handle >::iterator Skeleton_simplex_iterator;
94  typedef boost::iterator_range< Skeleton_simplex_iterator > Skeleton_simplex_range;
95 
96  /* only dimension 0 skeleton_simplex_range(...) */
97  Skeleton_simplex_range skeleton_simplex_range(int dim = 0) {
98  if (dim != 0) {
99  std::cerr << "Dimension must be 0 \n";
100  }
101  return Skeleton_simplex_range(vertices_.begin(), vertices_.end());
102  }
103 
104  template < class Complex_ds >
105  Hasse_complex(Complex_ds & cpx)
106  : complex_(cpx.num_simplices())
107  , vertices_()
108  , num_vertices_()
109  , dim_max_(cpx.dimension()) {
110  int size = complex_.size();
111 #ifdef GUDHI_USE_TBB
112  tbb::parallel_for(0, size, [&](int idx){new (&complex_[idx]) Hasse_simp(cpx, cpx.simplex(idx));});
113  for (int idx=0; idx < size; ++idx)
114  if (complex_[idx].boundary_.empty())
115  vertices_.push_back(idx);
116 #else
117  for (int idx=0; idx < size; ++idx) {
118  new (&complex_[idx]) Hasse_simp(cpx, cpx.simplex(idx));
119  if (complex_[idx].boundary_.empty())
120  vertices_.push_back(idx);
121  }
122 #endif
123  }
124 
125  Hasse_complex()
126  : complex_()
127  , vertices_()
128  , num_vertices_(0)
129  , dim_max_(-1) { }
130 
131  size_t num_simplices() {
132  return complex_.size();
133  }
134 
135  Filtration_simplex_range filtration_simplex_range() {
136  return Filtration_simplex_range(Filtration_simplex_iterator(0)
137  , Filtration_simplex_iterator(complex_.size()));
138  }
139 
140  Simplex_key key(Simplex_handle sh) {
141  return complex_[sh].key_;
142  }
143 
144  Simplex_key null_key() {
145  return -1;
146  }
147 
148  Simplex_handle simplex(Simplex_key key) {
149  if (key == null_key()) return null_simplex();
150  return key;
151  }
152 
153  Simplex_handle null_simplex() {
154  return -1;
155  }
156 
157  Filtration_value filtration(Simplex_handle sh) {
158  if (sh == null_simplex()) {
159  return std::numeric_limits<Filtration_value>::infinity();
160  }
161  return complex_[sh].filtration_;
162  }
163 
164  int dimension(Simplex_handle sh) {
165  if (complex_[sh].boundary_.empty()) return 0;
166  return complex_[sh].boundary_.size() - 1;
167  }
168 
169  int dimension() {
170  return dim_max_;
171  }
172 
173  std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) {
174  return std::pair<Simplex_handle, Simplex_handle>(complex_[sh].boundary_[0]
175  , complex_[sh].boundary_[1]);
176  }
177 
178  void assign_key(Simplex_handle sh, Simplex_key key) {
179  complex_[sh].key_ = key;
180  }
181 
182  Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) {
183  return Boundary_simplex_range(complex_[sh].boundary_.begin()
184  , complex_[sh].boundary_.end());
185  }
186 
187  void display_simplex(Simplex_handle sh) {
188  std::cout << dimension(sh) << " ";
189  for (auto sh_b : boundary_simplex_range(sh)) std::cout << sh_b << " ";
190  std::cout << " " << filtration(sh) << " key=" << key(sh);
191  }
192 
193  void initialize_filtration() {
194  // Setting the keys is done by pcoh, Simplex_tree doesn't do it either.
195 #if 0
196  Simplex_key key = 0;
197  for (auto & h_simp : complex_)
198  h_simp.key_ = key++;
199 #endif
200  }
201 
202  std::vector< Hasse_simp, Gudhi::no_init_allocator<Hasse_simp> > complex_;
203  std::vector<Simplex_handle> vertices_;
204  size_t num_vertices_;
205  int dim_max_;
206 };
207 
208 template< typename T1, typename T2, typename T3 >
209 std::istream& operator>>(std::istream & is
210  , Hasse_complex< T1, T2, T3 > & hcpx) {
211  assert(hcpx.num_simplices() == 0);
212 
213  size_t num_simp;
214  is >> num_simp;
215  hcpx.complex_.reserve(num_simp);
216 
217  std::vector< typename Hasse_complex<T1, T2, T3>::Simplex_key > boundary;
218  typename Hasse_complex<T1, T2, T3>::Filtration_value fil;
219  typename Hasse_complex<T1, T2, T3>::Filtration_value max_fil = 0;
220  int max_dim = -1;
221  int key = 0;
222  // read all simplices in the file as a list of vertices
223  while (read_hasse_simplex(is, boundary, fil)) {
224  // insert every simplex in the simplex tree
225  hcpx.complex_.emplace_back(key, fil, boundary);
226 
227  if (max_dim < hcpx.dimension(key)) {
228  max_dim = hcpx.dimension(key);
229  }
230  if (hcpx.dimension(key) == 0) {
231  hcpx.vertices_.push_back(key);
232  }
233  if (max_fil < fil) {
234  max_fil = fil;
235  }
236 
237  ++key;
238  boundary.clear();
239  }
240 
241  hcpx.dim_max_ = max_dim;
242 
243  return is;
244 }
245 
246 } // namespace Gudhi
247 
248 #endif // HASSE_COMPLEX_H_
Definition: SimplicialComplexForAlpha.h:26
Key type used as simplex identifier.
Definition: SimplexKey.h:27
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:32
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:195
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:27
GUDHI  Version 2.3.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Fri Oct 18 2019 18:40:54 for GUDHI by Doxygen 1.8.13