11 #ifndef LAZY_TOPLEX_MAP_H 12 #define LAZY_TOPLEX_MAP_H 14 #include <gudhi/Toplex_map.h> 15 #include <boost/heap/fibonacci_heap.hpp> 42 template <
typename Input_vertex_range>
47 template <
typename Input_vertex_range>
52 template <
typename Input_vertex_range>
56 template <
typename Input_vertex_range>
57 bool membership(
const Input_vertex_range &vertex_range);
60 template <
typename Input_vertex_range>
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);
81 std::unordered_map<Vertex, std::size_t> gamma0_lbounds;
83 std::unordered_map<Vertex, Simplex_ptr_set> t0;
84 bool empty_toplex =
true;
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;
90 std::size_t get_gamma0_lbound(
const Vertex v)
const;
92 std::size_t size_lbound = 0;
95 const double ALPHA = 4;
96 const double BETTA = 8;
99 template <
typename Input_vertex_range>
101 for (
const Vertex &v : vertex_range)
102 if (!gamma0_lbounds.count(v))
103 gamma0_lbounds.emplace(v, 1);
110 template <
typename Input_vertex_range>
112 Simplex sigma(vertex_range.begin(), vertex_range.end());
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) {
120 auto v_handle = cleaning_priority.push(std::make_pair(0, v));
121 cp_handles.emplace(v, v_handle);
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));
126 if (inserted) size++;
127 if (size > (size_lbound + 1) * BETTA) clean(cleaning_priority.top().second);
131 template <
typename Input_vertex_range>
133 if (vertex_range.begin() == vertex_range.end()) {
135 gamma0_lbounds.clear();
136 cleaning_priority.clear();
139 empty_toplex =
false;
141 const Vertex &v = best_index(vertex_range);
145 if (included(vertex_range, *sptr)) {
152 template <
typename Input_vertex_range>
154 if (t0.size() == 0 && !empty_toplex)
return false;
155 if (vertex_range.begin() == vertex_range.end())
return true;
156 Vertex v = best_index(vertex_range);
157 if (!t0.count(v))
return false;
159 if (included(vertex_range, *sptr))
return true;
163 template <
typename Input_vertex_range>
165 Simplex sigma(vertex_range.begin(), vertex_range.end());
166 Vertex v = best_index(sigma);
167 if (!t0.count(v))
return false;
171 std::unordered_set<Vertex> facets_inside;
173 for (
const Vertex &w : sigma) {
176 if (included(f, *sptr)) facets_inside.insert(w);
178 return facets_inside.size() == sigma.size() - 1;
183 if (!t0.count(x))
return y;
184 if (!t0.count(y))
return x;
186 if (t0.at(x).size() > t0.at(y).size())
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);
209 for (
const Vertex &v : sigma) {
210 erased = t0.at(v).erase(sptr) > 0;
211 if (t0.at(v).size() == 0) t0.erase(v);
216 template <
typename Input_vertex_range>
218 Simplex tau(vertex_range.begin(), vertex_range.end());
219 std::size_t min = std::numeric_limits<size_t>::max();
221 for (
const Vertex &v : tau)
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);
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;
234 void Lazy_toplex_map::clean(
const Vertex v) {
236 std::unordered_map<int, std::vector<Simplex>> dsorted_simplices;
237 std::size_t max_dim = 0;
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();
243 dsorted_simplices[sptr->size()].emplace_back(*sptr);
246 for (std::size_t d = max_dim; d >= 1; d--)
247 for (
const Simplex &s : dsorted_simplices.at(d))
252 size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size();
253 gamma0_lbounds[v] = clean_cofaces.size();
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