1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
|
#ifndef LAZY_TOPLEX_MAP_H
#define LAZY_TOPLEX_MAP_H
#include <gudhi/Toplex_map.h>
#include <boost/heap/fibonacci_heap.hpp>
namespace Gudhi {
class Lazy_Toplex_map {
public:
/** Vertex is the type of vertices.
* \ingroup toplex_map */
typedef Toplex_map::Vertex Vertex;
/** Simplex is the type of simplices.
* \ingroup toplex_map */
typedef Toplex_map::Simplex Simplex;
/** The type of the pointers to maximal simplices.
* \ingroup toplex_map */
typedef Toplex_map::Simplex_ptr Simplex_ptr;
/** The type of the sets of Simplex_ptr.
* \ingroup toplex_map */
typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set;
template <typename Input_vertex_range>
void insert_max_simplex(const Input_vertex_range &vertex_range);
template <typename Input_vertex_range>
bool insert_simplex(const Input_vertex_range &vertex_range);
template <typename Input_vertex_range>
void remove_simplex(const Input_vertex_range &vertex_range);
template <typename Input_vertex_range>
bool membership(const Input_vertex_range &vertex_range);
template <typename Input_vertex_range>
bool all_facets_inside(const Input_vertex_range &vertex_range);
Vertex contraction(const Vertex x, const Vertex y);
std::size_t num_simplices() const;
std::unordered_map<Vertex, std::size_t> gamma0_lbounds;
private:
template <typename Input_vertex_range>
void erase_max(const Input_vertex_range &vertex_range);
template <typename Input_vertex_range>
Vertex best_index(const Input_vertex_range &vertex_range);
void clean(const Vertex v);
std::unordered_map<Vertex, Simplex_ptr_set> t0;
bool empty_toplex; // Is the empty simplex a toplex ?
typedef boost::heap::fibonacci_heap<std::pair<std::size_t,Vertex>> PriorityQueue;
PriorityQueue cleaning_priority;
std::unordered_map<Vertex, PriorityQueue::handle_type> cp_handles;
std::size_t get_gamma0_lbound(const Vertex v) const;
std::size_t size_lbound = 0;
std::size_t size = 0;
const double alpha = 2; //time
const double betta = 4; //memory
};
template <typename Input_vertex_range>
void Lazy_Toplex_map::insert_max_simplex(const Input_vertex_range &vertex_range){
for(const Vertex& v : vertex_range)
if(!gamma0_lbounds.count(v)) gamma0_lbounds.emplace(v,1);
else gamma0_lbounds[v]++;
size_lbound++;
insert_simplex(vertex_range);
}
template <typename Input_vertex_range>
bool Lazy_Toplex_map::insert_simplex(const Input_vertex_range &vertex_range){
Simplex sigma(vertex_range.begin(),vertex_range.end());
empty_toplex = (sigma.size()==0); //vérifier la gestion de empty face
Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
bool inserted = false;
for(const Vertex& v : sigma){
if(!t0.count(v)){
t0.emplace(v, Simplex_ptr_set());
auto v_handle = cleaning_priority.push(std::make_pair(0, v));
cp_handles.emplace(v, v_handle);
}
inserted = t0.at(v).emplace(sptr).second;
cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v),v));
}
if(inserted)
size++;
if(size > (size_lbound+1) * betta)
clean(cleaning_priority.top().second);
return inserted;
}
template <typename Input_vertex_range>
void Lazy_Toplex_map::remove_simplex(const Input_vertex_range &vertex_range){
if(vertex_range.begin()==vertex_range.end()){
t0.clear();
gamma0_lbounds.clear();
cleaning_priority.clear();
size_lbound = 0;
size = 0;
empty_toplex = false;
}
else {
const Vertex& v = best_index(vertex_range);
//Copy constructor needed because the set is modified
if(t0.count(v)) for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v)))
if(included(vertex_range, *sptr)){
erase_max(*sptr);
for(const Simplex& f : facets(vertex_range))
insert_max_simplex(f);
}
}
}
template <typename Input_vertex_range>
bool Lazy_Toplex_map::membership(const Input_vertex_range &vertex_range){
if(t0.size()==0 && !empty_toplex) return false; //empty complex
if(vertex_range.begin()==vertex_range.end()) return true; //empty query simplex
Vertex v = best_index(vertex_range);
if(!t0.count(v)) return false;
for(const Simplex_ptr& sptr : t0.at(v))
if(included(vertex_range, *sptr)) return true;
return false;
}
template <typename Input_vertex_range>
bool Lazy_Toplex_map::all_facets_inside(const Input_vertex_range &vertex_range){
Simplex sigma(vertex_range.begin(),vertex_range.end());
Vertex v = best_index(sigma);
if(!t0.count(v)) return false;
Simplex f = sigma; f.erase(v);
if(!membership(f)) return false;
std::unordered_set<Vertex> facets_inside;
for(const Simplex_ptr& sptr : t0.at(v))
for(const Vertex& w : sigma){
f = sigma; f.erase(w);
if(included(f, *sptr)) facets_inside.insert(w);
}
return facets_inside.size() == sigma.size() - 1;
}
/* Returns the remaining vertex */
Toplex_map::Vertex Lazy_Toplex_map::contraction(const Vertex x, const Vertex y){
if(!t0.count(x)) return y;
if(!t0.count(y)) return x;
Vertex k, d;
if(t0.at(x).size() > t0.at(y).size())
k=x, d=y;
else
k=y, d=x;
//Copy constructor needed because the set is modified
for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){
Simplex sigma(*sptr);
erase_max(sigma);
sigma.erase(d);
sigma.insert(k);
insert_simplex(sigma);
}
t0.erase(d);
return k;
}
/* No facets insert_simplexed */
template <typename Input_vertex_range>
inline void Lazy_Toplex_map::erase_max(const Input_vertex_range &vertex_range){
Simplex sigma(vertex_range.begin(),vertex_range.end());
empty_toplex = false;
Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
bool erased;
for(const Vertex& v : sigma){
erased = t0.at(v).erase(sptr) > 0;
if(t0.at(v).size()==0)
t0.erase(v);
}
if (erased)
size--;
}
template <typename Input_vertex_range>
Toplex_map::Vertex Lazy_Toplex_map::best_index(const Input_vertex_range &vertex_range){
Simplex tau(vertex_range.begin(),vertex_range.end());
std::size_t min = std::numeric_limits<size_t>::max(); Vertex arg_min = -1;
for(const Vertex& v : tau)
if(!t0.count(v)) return v;
else if(t0.at(v).size() < min)
min = t0.at(v).size(), arg_min = v;
if(min > alpha * get_gamma0_lbound(arg_min))
clean(arg_min);
return arg_min;
}
std::size_t Lazy_Toplex_map::get_gamma0_lbound(const Vertex v) const{
return gamma0_lbounds.count(v) ? gamma0_lbounds.at(v) : 0;
}
void Lazy_Toplex_map::clean(const Vertex v){
Toplex_map toplices;
std::unordered_map<int, std::vector<Simplex>> dsorted_simplices;
int max_dim = 0;
for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))){
if(sptr->size() > max_dim){
for(int d = max_dim+1; d<=sptr->size(); d++)
dsorted_simplices.emplace(d, std::vector<Simplex>());
max_dim = sptr->size();
}
dsorted_simplices[sptr->size()].emplace_back(*sptr);
erase_max(*sptr);
}
for(int d = max_dim; d>=1; d--)
for(const Simplex &s : dsorted_simplices.at(d))
if(!toplices.membership(s))
toplices.insert_independent_simplex(s);
Simplex sv; sv.insert(v);
auto clean_cofaces = toplices.maximal_cofaces(sv);
size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size();
gamma0_lbounds[v] = clean_cofaces.size();
for(const Simplex_ptr& sptr : clean_cofaces)
insert_simplex(*sptr);
}
std::size_t Lazy_Toplex_map::num_simplices() const{
return size;
}
} //namespace Gudhi
#endif /* LAZY_TOPLEX_MAP_H */
|
