Loading...
Searching...
No Matches
Lazy_toplex_map.h
/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* Author: François Godi, Vincent Rouvreau
*
* Copyright (C) 2018 INRIA
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#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:
using Vertex = Toplex_map::Vertex;
using Simplex = Toplex_map::Simplex;
using Simplex_ptr = Toplex_map::Simplex_ptr;
using Simplex_ptr_set = Toplex_map::Simplex_ptr_set;
template <typename Input_vertex_range>
void insert_independent_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_maximal_simplices() const { return size; }
std::size_t num_vertices() const { return t0.size(); }
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, std::size_t> gamma0_lbounds;
std::unordered_map<Vertex, Simplex_ptr_set> t0;
bool empty_toplex = true; // 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 = 4; // time
const double BETTA = 8; // memory
};
template <typename Input_vertex_range>
void Lazy_toplex_map::insert_independent_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());
// Check empty face management
empty_toplex = (sigma.size() == 0);
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_independent_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 */
Lazy_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 = false;
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>
Lazy_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;
std::size_t max_dim = 0;
for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(v))) {
if (sptr->size() > max_dim) {
for (std::size_t 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 (std::size_t 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);
}
} // namespace Gudhi
#endif /* LAZY_TOPLEX_MAP_H */
Gudhi::Lazy_toplex_map
Lazy toplex map data structure for representing unfiltered simplicial complexes.
Definition Lazy_toplex_map.h:26
Gudhi::Lazy_toplex_map::Vertex
Toplex_map::Vertex Vertex
Definition Lazy_toplex_map.h:29
Gudhi::Lazy_toplex_map::insert_simplex
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
Gudhi::Lazy_toplex_map::Simplex_ptr
Toplex_map::Simplex_ptr Simplex_ptr
Definition Lazy_toplex_map.h:35
Gudhi::Lazy_toplex_map::num_maximal_simplices
std::size_t num_maximal_simplices() const
Number of maximal simplices.
Definition Lazy_toplex_map.h:69
Gudhi::Lazy_toplex_map::Simplex
Toplex_map::Simplex Simplex
Definition Lazy_toplex_map.h:32
Gudhi::Lazy_toplex_map::remove_simplex
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
Gudhi::Lazy_toplex_map::membership
bool membership(const Input_vertex_range &vertex_range)
Definition Lazy_toplex_map.h:153
Gudhi::Lazy_toplex_map::insert_independent_simplex
void insert_independent_simplex(const Input_vertex_range &vertex_range)
Definition Lazy_toplex_map.h:100
Gudhi::Lazy_toplex_map::all_facets_inside
bool all_facets_inside(const Input_vertex_range &vertex_range)
Definition Lazy_toplex_map.h:164
Gudhi::Lazy_toplex_map::num_vertices
std::size_t num_vertices() const
Number of vertices.
Definition Lazy_toplex_map.h:72
Gudhi::Lazy_toplex_map::contraction
Vertex contraction(const Vertex x, const Vertex y)
Definition Lazy_toplex_map.h:182
Gudhi::Lazy_toplex_map::Simplex_ptr_set
Toplex_map::Simplex_ptr_set Simplex_ptr_set
Definition Lazy_toplex_map.h:38
Gudhi::Toplex_map::Simplex_ptr_set
std::unordered_set< Toplex_map::Simplex_ptr, Sptr_hash, Sptr_equal > Simplex_ptr_set
Definition Toplex_map.h:49
Gudhi::Toplex_map::Simplex_ptr
std::shared_ptr< Toplex_map::Simplex > Simplex_ptr
Definition Toplex_map.h:38
Gudhi::Toplex_map::Simplex
std::set< Vertex > Simplex
Definition Toplex_map.h:35
Gudhi::Toplex_map::Vertex
std::size_t Vertex
Definition Toplex_map.h:32
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14