Lazy_toplex_map.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: François Godi, Vincent Rouvreau
4  *
5  * Copyright (C) 2018 INRIA
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef LAZY_TOPLEX_MAP_H
12 #define LAZY_TOPLEX_MAP_H
13 
14 #include <gudhi/Toplex_map.h>
15 #include <boost/heap/fibonacci_heap.hpp>
16 
17 namespace Gudhi {
18 
27  public:
30 
33 
36 
39 
42  template <typename Input_vertex_range>
43  void insert_independent_simplex(const Input_vertex_range &vertex_range);
44 
47  template <typename Input_vertex_range>
48  bool insert_simplex(const Input_vertex_range &vertex_range);
49 
52  template <typename Input_vertex_range>
53  void remove_simplex(const Input_vertex_range &vertex_range);
54 
56  template <typename Input_vertex_range>
57  bool membership(const Input_vertex_range &vertex_range);
58 
60  template <typename Input_vertex_range>
61  bool all_facets_inside(const Input_vertex_range &vertex_range);
62 
66  Vertex contraction(const Vertex x, const Vertex y);
67 
69  std::size_t num_maximal_simplices() const { return size; }
70 
72  std::size_t num_vertices() const { return t0.size(); }
73 
74  private:
75  template <typename Input_vertex_range>
76  void erase_max(const Input_vertex_range &vertex_range);
77  template <typename Input_vertex_range>
78  Vertex best_index(const Input_vertex_range &vertex_range);
79  void clean(const Vertex v);
80 
81  std::unordered_map<Vertex, std::size_t> gamma0_lbounds;
82 
83  std::unordered_map<Vertex, Simplex_ptr_set> t0;
84  bool empty_toplex = true; // Is the empty simplex a toplex ?
85 
86  typedef boost::heap::fibonacci_heap<std::pair<std::size_t, Vertex>> PriorityQueue;
87  PriorityQueue cleaning_priority;
88  std::unordered_map<Vertex, PriorityQueue::handle_type> cp_handles;
89 
90  std::size_t get_gamma0_lbound(const Vertex v) const;
91 
92  std::size_t size_lbound = 0;
93  std::size_t size = 0;
94 
95  const double ALPHA = 4; // time
96  const double BETTA = 8; // memory
97 };
98 
99 template <typename Input_vertex_range>
100 void Lazy_toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range) {
101  for (const Vertex &v : vertex_range)
102  if (!gamma0_lbounds.count(v))
103  gamma0_lbounds.emplace(v, 1);
104  else
105  gamma0_lbounds[v]++;
106  size_lbound++;
107  insert_simplex(vertex_range);
108 }
109 
110 template <typename Input_vertex_range>
111 bool Lazy_toplex_map::insert_simplex(const Input_vertex_range &vertex_range) {
112  Simplex sigma(vertex_range.begin(), vertex_range.end());
113  // Check empty face management
114  empty_toplex = (sigma.size() == 0);
115  Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
116  bool inserted = false;
117  for (const Vertex &v : sigma) {
118  if (!t0.count(v)) {
119  t0.emplace(v, Simplex_ptr_set());
120  auto v_handle = cleaning_priority.push(std::make_pair(0, v));
121  cp_handles.emplace(v, v_handle);
122  }
123  inserted = t0.at(v).emplace(sptr).second;
124  cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v), v));
125  }
126  if (inserted) size++;
127  if (size > (size_lbound + 1) * BETTA) clean(cleaning_priority.top().second);
128  return inserted;
129 }
130 
131 template <typename Input_vertex_range>
132 void Lazy_toplex_map::remove_simplex(const Input_vertex_range &vertex_range) {
133  if (vertex_range.begin() == vertex_range.end()) {
134  t0.clear();
135  gamma0_lbounds.clear();
136  cleaning_priority.clear();
137  size_lbound = 0;
138  size = 0;
139  empty_toplex = false;
140  } else {
141  const Vertex &v = best_index(vertex_range);
142  // Copy constructor needed because the set is modified
143  if (t0.count(v))
144  for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(v)))
145  if (included(vertex_range, *sptr)) {
146  erase_max(*sptr);
147  for (const Simplex &f : facets(vertex_range)) insert_independent_simplex(f);
148  }
149  }
150 }
151 
152 template <typename Input_vertex_range>
153 bool Lazy_toplex_map::membership(const Input_vertex_range &vertex_range) {
154  if (t0.size() == 0 && !empty_toplex) return false; // empty complex
155  if (vertex_range.begin() == vertex_range.end()) return true; // empty query simplex
156  Vertex v = best_index(vertex_range);
157  if (!t0.count(v)) return false;
158  for (const Simplex_ptr &sptr : t0.at(v))
159  if (included(vertex_range, *sptr)) return true;
160  return false;
161 }
162 
163 template <typename Input_vertex_range>
164 bool Lazy_toplex_map::all_facets_inside(const Input_vertex_range &vertex_range) {
165  Simplex sigma(vertex_range.begin(), vertex_range.end());
166  Vertex v = best_index(sigma);
167  if (!t0.count(v)) return false;
168  Simplex f = sigma;
169  f.erase(v);
170  if (!membership(f)) return false;
171  std::unordered_set<Vertex> facets_inside;
172  for (const Simplex_ptr &sptr : t0.at(v))
173  for (const Vertex &w : sigma) {
174  f = sigma;
175  f.erase(w);
176  if (included(f, *sptr)) facets_inside.insert(w);
177  }
178  return facets_inside.size() == sigma.size() - 1;
179 }
180 
181 /* Returns the remaining vertex */
183  if (!t0.count(x)) return y;
184  if (!t0.count(y)) return x;
185  Vertex k, d;
186  if (t0.at(x).size() > t0.at(y).size())
187  k = x, d = y;
188  else
189  k = y, d = x;
190  // Copy constructor needed because the set is modified
191  for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(d))) {
192  Simplex sigma(*sptr);
193  erase_max(sigma);
194  sigma.erase(d);
195  sigma.insert(k);
196  insert_simplex(sigma);
197  }
198  t0.erase(d);
199  return k;
200 }
201 
202 /* No facets insert_simplexed */
203 template <typename Input_vertex_range>
204 inline void Lazy_toplex_map::erase_max(const Input_vertex_range &vertex_range) {
205  Simplex sigma(vertex_range.begin(), vertex_range.end());
206  empty_toplex = false;
207  Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
208  bool erased = false;
209  for (const Vertex &v : sigma) {
210  erased = t0.at(v).erase(sptr) > 0;
211  if (t0.at(v).size() == 0) t0.erase(v);
212  }
213  if (erased) size--;
214 }
215 
216 template <typename Input_vertex_range>
217 Lazy_toplex_map::Vertex Lazy_toplex_map::best_index(const Input_vertex_range &vertex_range) {
218  Simplex tau(vertex_range.begin(), vertex_range.end());
219  std::size_t min = std::numeric_limits<size_t>::max();
220  Vertex arg_min = -1;
221  for (const Vertex &v : tau)
222  if (!t0.count(v))
223  return v;
224  else if (t0.at(v).size() < min)
225  min = t0.at(v).size(), arg_min = v;
226  if (min > ALPHA * get_gamma0_lbound(arg_min)) clean(arg_min);
227  return arg_min;
228 }
229 
230 std::size_t Lazy_toplex_map::get_gamma0_lbound(const Vertex v) const {
231  return gamma0_lbounds.count(v) ? gamma0_lbounds.at(v) : 0;
232 }
233 
234 void Lazy_toplex_map::clean(const Vertex v) {
235  Toplex_map toplices;
236  std::unordered_map<int, std::vector<Simplex>> dsorted_simplices;
237  std::size_t max_dim = 0;
238  for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(v))) {
239  if (sptr->size() > max_dim) {
240  for (std::size_t d = max_dim + 1; d <= sptr->size(); d++) dsorted_simplices.emplace(d, std::vector<Simplex>());
241  max_dim = sptr->size();
242  }
243  dsorted_simplices[sptr->size()].emplace_back(*sptr);
244  erase_max(*sptr);
245  }
246  for (std::size_t d = max_dim; d >= 1; d--)
247  for (const Simplex &s : dsorted_simplices.at(d))
248  if (!toplices.membership(s)) toplices.insert_independent_simplex(s);
249  Simplex sv;
250  sv.insert(v);
251  auto clean_cofaces = toplices.maximal_cofaces(sv);
252  size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size();
253  gamma0_lbounds[v] = clean_cofaces.size();
254  for (const Simplex_ptr &sptr : clean_cofaces) insert_simplex(*sptr);
255 }
256 
257 } // namespace Gudhi
258 
259 #endif /* LAZY_TOPLEX_MAP_H */
std::unordered_set< Toplex_map::Simplex_ptr, Sptr_hash, Sptr_equal > Simplex_ptr_set
Definition: Toplex_map.h:49
void insert_independent_simplex(const Input_vertex_range &vertex_range)
Definition: Lazy_toplex_map.h:100
Toplex_map::Vertex Vertex
Definition: Lazy_toplex_map.h:29
Toplex_map::Simplex Simplex
Definition: Lazy_toplex_map.h:32
Definition: SimplicialComplexForAlpha.h:14
std::shared_ptr< Toplex_map::Simplex > Simplex_ptr
Definition: Toplex_map.h:38
void insert_independent_simplex(const Input_vertex_range &vertex_range)
Definition: Toplex_map.h:245
bool membership(const Input_vertex_range &vertex_range) const
Definition: Toplex_map.h:169
bool insert_simplex(const Input_vertex_range &vertex_range)
Adds the given simplex to the complex. Nothing happens if the simplex is already in the complex (i...
Definition: Lazy_toplex_map.h:111
std::size_t Vertex
Definition: Toplex_map.h:32
bool membership(const Input_vertex_range &vertex_range)
Definition: Lazy_toplex_map.h:153
Toplex_map::Simplex_ptr Simplex_ptr
Definition: Lazy_toplex_map.h:35
Toplex_map::Simplex_ptr_set maximal_cofaces(const Input_vertex_range &vertex_range, const std::size_t max_number=0) const
Definition: Toplex_map.h:187
std::set< Vertex > Simplex
Definition: Toplex_map.h:35
Toplex_map::Simplex_ptr_set Simplex_ptr_set
Definition: Lazy_toplex_map.h:38
void remove_simplex(const Input_vertex_range &vertex_range)
Removes the given simplex and its cofaces from the complex. Its faces are kept inside.
Definition: Lazy_toplex_map.h:132
Vertex contraction(const Vertex x, const Vertex y)
Definition: Lazy_toplex_map.h:182
std::size_t num_vertices() const
Number of vertices.
Definition: Lazy_toplex_map.h:72
Lazy toplex map data structure for representing unfiltered simplicial complexes.
Definition: Lazy_toplex_map.h:26
bool all_facets_inside(const Input_vertex_range &vertex_range)
Definition: Lazy_toplex_map.h:164
Toplex map data structure for representing unfiltered simplicial complexes.
Definition: Toplex_map.h:29
std::size_t num_maximal_simplices() const
Number of maximal simplices.
Definition: Lazy_toplex_map.h:69
GUDHI  Version 3.1.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Feb 7 2020 16:35:36 for GUDHI by Doxygen 1.8.13