Loading...
Searching...
No Matches
Skeleton_blocker_simplifiable_complex.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(s): David Salinas
*
* Copyright (C) 2014 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_
#define SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_
#include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h>
#include <list>
#include <vector>
#include <set>
namespace Gudhi {
namespace skeleton_blocker {
template<typename SkeletonBlockerDS>
bool Skeleton_blocker_complex<SkeletonBlockerDS>::is_popable_blocker(Blocker_handle sigma) const {
assert(this->contains_blocker(*sigma));
Skeleton_blocker_link_complex<Skeleton_blocker_complex> link_blocker_sigma;
build_link_of_blocker(*this, *sigma, link_blocker_sigma);
return link_blocker_sigma.is_contractible() == CONTRACTIBLE;
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_popable_blockers() {
std::list<Vertex_handle> vertex_to_check;
for (auto v : this->vertex_range())
vertex_to_check.push_front(v);
while (!vertex_to_check.empty()) {
Vertex_handle v = vertex_to_check.front();
vertex_to_check.pop_front();
bool blocker_popable_found = true;
while (blocker_popable_found) {
blocker_popable_found = false;
for (auto block : this->blocker_range(v)) {
if (this->is_popable_blocker(block)) {
for (Vertex_handle nv : *block)
if (nv != v) vertex_to_check.push_back(nv);
this->delete_blocker(block);
blocker_popable_found = true;
break;
}
}
}
}
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_popable_blockers(Vertex_handle v) {
bool blocker_popable_found = true;
while (blocker_popable_found) {
blocker_popable_found = false;
for (auto block : this->blocker_range(v)) {
if (is_popable_blocker(block)) {
this->delete_blocker(block);
blocker_popable_found = true;
}
}
}
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_all_popable_blockers(Vertex_handle v) {
std::list<Vertex_handle> vertex_to_check;
vertex_to_check.push_front(v);
while (!vertex_to_check.empty()) {
Vertex_handle v = vertex_to_check.front();
vertex_to_check.pop_front();
bool blocker_popable_found = true;
while (blocker_popable_found) {
blocker_popable_found = false;
for (auto block : this->blocker_range(v)) {
if (this->is_popable_blocker(block)) {
for (Vertex_handle nv : *block)
if (nv != v) vertex_to_check.push_back(nv);
this->delete_blocker(block);
blocker_popable_found = true;
break;
}
}
}
}
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle v) {
// we remove the blockers that are not consistent anymore
update_blockers_after_remove_star_of_vertex_or_edge(Simplex(v));
while (this->degree(v) > 0) {
Vertex_handle w(* (adjacent_vertices(v.vertex, this->skeleton).first));
this->remove_edge(v, w);
}
this->remove_vertex(v);
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_star_of_vertex_or_edge(const Simplex& simplex_to_be_removed) {
std::list <Blocker_handle> blockers_to_update;
if (simplex_to_be_removed.empty()) return;
auto v0 = simplex_to_be_removed.first_vertex();
for (auto blocker : this->blocker_range(v0)) {
if (blocker->contains(simplex_to_be_removed))
blockers_to_update.push_back(blocker);
}
for (auto blocker_to_update : blockers_to_update) {
Simplex sub_blocker_to_be_added;
bool sub_blocker_need_to_be_added =
(blocker_to_update->dimension() - simplex_to_be_removed.dimension()) >= 2;
if (sub_blocker_need_to_be_added) {
sub_blocker_to_be_added = *blocker_to_update;
sub_blocker_to_be_added.difference(simplex_to_be_removed);
}
this->delete_blocker(blocker_to_update);
if (sub_blocker_need_to_be_added)
this->add_blocker(sub_blocker_to_be_added);
}
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle a, Vertex_handle b) {
update_blockers_after_remove_star_of_vertex_or_edge(Simplex(a, b));
// we remove the edge
this->remove_edge(a, b);
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Edge_handle e) {
return remove_star(this->first_vertex(e), this->second_vertex(e));
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex& sigma) {
assert(this->contains(sigma));
if (sigma.dimension() == 0) {
remove_star(sigma.first_vertex());
} else if (sigma.dimension() == 1) {
remove_star(sigma.first_vertex(), sigma.last_vertex());
} else {
remove_blocker_containing_simplex(sigma);
this->add_blocker(sigma);
}
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::add_simplex(const Simplex& sigma) {
// to add a simplex s, all blockers included in s are first removed
// and then all simplex in the coboundary of s are added as blockers
assert(!this->contains(sigma));
assert(sigma.dimension() > 1);
if (!contains_vertices(sigma)) {
std::cerr << "add_simplex: Some vertices were not present in the complex, adding them" << std::endl;
size_t num_vertices_to_add = sigma.last_vertex() - this->num_vertices() + 1;
for (size_t i = 0; i < num_vertices_to_add; ++i)
this->add_vertex();
}
assert(contains_vertices(sigma));
if (!contains_edges(sigma))
add_edge(sigma);
remove_blocker_include_in_simplex(sigma);
add_blockers_after_simplex_insertion(sigma);
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::add_blockers_after_simplex_insertion(Simplex sigma) {
if (sigma.dimension() < 1) return;
for (auto s : coboundary_range(sigma)) {
this->add_blocker(s);
}
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simplex(const Simplex& sigma) {
std::vector <Blocker_handle> blockers_to_remove;
for (auto blocker : this->blocker_range(sigma.first_vertex())) {
if (blocker->contains(sigma))
blockers_to_remove.push_back(blocker);
}
for (auto blocker_to_update : blockers_to_remove)
this->delete_blocker(blocker_to_update);
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_include_in_simplex(const Simplex& sigma) {
// TODO(DS): write efficiently by using only superior blockers
// eg for all s, check blockers whose vertices are all greater than s
std::set <Blocker_handle> blockers_to_remove;
for (auto s : sigma) {
for (auto blocker : this->blocker_range(s)) {
if (sigma.contains(*blocker))
blockers_to_remove.insert(blocker);
}
}
for (auto blocker_to_update : blockers_to_remove) {
auto s = *blocker_to_update;
this->delete_blocker(blocker_to_update);
// now if there is a vertex v in the link of s
// and v is not included in sigma then v.s is a blocker
// (all faces of v.s are there since v belongs to the link of s)
for (const auto& b : coboundary_range(s))
if (!sigma.contains(b))
this->add_blocker(b);
}
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::tip_blockers(Vertex_handle a, Vertex_handle b,
std::vector<Simplex> & buffer) const {
for (auto const blocker : this->const_blocker_range(a)) {
Simplex beta = (*blocker);
beta.remove_vertex(a);
buffer.push_back(beta);
}
Simplex n;
this->add_neighbours(b, n);
this->remove_neighbours(a, n);
n.remove_vertex(a);
for (Vertex_handle y : n) {
Simplex beta;
beta.add_vertex(y);
buffer.push_back(beta);
}
}
template<typename SkeletonBlockerDS>
void
Skeleton_blocker_complex<SkeletonBlockerDS>::swap_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) {
this->add_edge_without_blockers(a, x);
if (this->visitor) this->visitor->on_swaped_edge(a, b, x);
this->remove_edge(b, x);
}
template<typename SkeletonBlockerDS>
void
Skeleton_blocker_complex<SkeletonBlockerDS>::delete_blockers_around_vertex(Vertex_handle v) {
std::list <Blocker_handle> blockers_to_delete;
for (auto blocker : this->blocker_range(v)) {
blockers_to_delete.push_back(blocker);
}
while (!blockers_to_delete.empty()) {
this->remove_blocker(blockers_to_delete.back());
blockers_to_delete.pop_back();
}
}
template<typename SkeletonBlockerDS>
void
Skeleton_blocker_complex<SkeletonBlockerDS>::delete_blockers_around_edge(Vertex_handle a, Vertex_handle b) {
std::list<Blocker_handle> blocker_to_delete;
for (auto blocker : this->blocker_range(a))
if (blocker->contains(b)) blocker_to_delete.push_back(blocker);
while (!blocker_to_delete.empty()) {
this->delete_blocker(blocker_to_delete.back());
blocker_to_delete.pop_back();
}
}
template<typename SkeletonBlockerDS>
void
Skeleton_blocker_complex<SkeletonBlockerDS>::contract_edge(Vertex_handle a, Vertex_handle b) {
assert(this->contains_vertex(a));
assert(this->contains_vertex(b));
if (this->contains_edge(a, b))
this->add_edge_without_blockers(a, b);
// if some blockers passes through 'ab', we need to remove them.
if (!link_condition(a, b))
delete_blockers_around_edge(a, b);
std::set<Simplex> blockers_to_add;
get_blockers_to_be_added_after_contraction(a, b, blockers_to_add);
delete_blockers_around_vertices(a, b);
update_edges_after_contraction(a, b);
this->remove_vertex(b);
notify_changed_edges(a);
for (auto block : blockers_to_add)
this->add_blocker(block);
assert(this->contains_vertex(a));
assert(!this->contains_vertex(b));
}
template<typename SkeletonBlockerDS>
void Skeleton_blocker_complex<SkeletonBlockerDS>::get_blockers_to_be_added_after_contraction(Vertex_handle a,
Vertex_handle b,
std::set<Simplex>& blockers_to_add) {
blockers_to_add.clear();
typedef Skeleton_blocker_link_complex<Skeleton_blocker_complex<SkeletonBlockerDS> > LinkComplexType;
LinkComplexType link_a(*this, a);
LinkComplexType link_b(*this, b);
std::vector<Simplex> vector_alpha, vector_beta;
tip_blockers(a, b, vector_alpha);
tip_blockers(b, a, vector_beta);
for (auto alpha = vector_alpha.begin(); alpha != vector_alpha.end(); ++alpha) {
for (auto beta = vector_beta.begin(); beta != vector_beta.end(); ++beta) {
Simplex sigma = *alpha;
sigma.union_vertices(*beta);
Root_simplex_handle sigma_id = this->get_id(sigma);
if (this->contains(sigma) &&
proper_faces_in_union<Skeleton_blocker_complex < SkeletonBlockerDS >> (sigma_id, link_a, link_b)) {
// Blocker_handle blocker = new Simplex(sigma);
sigma.add_vertex(a);
blockers_to_add.insert(sigma);
}
}
}
}
template<typename SkeletonBlockerDS>
void
Skeleton_blocker_complex<SkeletonBlockerDS>::delete_blockers_around_vertices(Vertex_handle a, Vertex_handle b) {
std::vector<Blocker_handle> blocker_to_delete;
for (auto bl : this->blocker_range(a))
blocker_to_delete.push_back(bl);
for (auto bl : this->blocker_range(b))
blocker_to_delete.push_back(bl);
while (!blocker_to_delete.empty()) {
this->delete_blocker(blocker_to_delete.back());
blocker_to_delete.pop_back();
}
}
template<typename SkeletonBlockerDS>
void
Skeleton_blocker_complex<SkeletonBlockerDS>::update_edges_after_contraction(Vertex_handle a, Vertex_handle b) {
// We update the set of edges
this->remove_edge(a, b);
// For all edges {b,x} incident to b,
// we remove {b,x} and add {a,x} if not already there.
while (this->degree(b) > 0) {
Vertex_handle x(*(adjacent_vertices(b.vertex, this->skeleton).first));
if (!this->contains_edge(a, x))
// we 'replace' the edge 'bx' by the edge 'ax'
this->swap_edge(a, b, x);
else
this->remove_edge(b, x);
}
}
template<typename SkeletonBlockerDS>
void
Skeleton_blocker_complex<SkeletonBlockerDS>::notify_changed_edges(Vertex_handle a) {
// We notify the visitor that all edges incident to 'a' had changed
boost_adjacency_iterator v, v_end;
for (tie(v, v_end) = adjacent_vertices(a.vertex, this->skeleton); v != v_end; ++v)
if (this->visitor) this->visitor->on_changed_edge(a, Vertex_handle(*v));
}
} // namespace skeleton_blocker
namespace skbl = skeleton_blocker;
} // namespace Gudhi
#endif // SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_
Gudhi::skeleton_blocker::Skeleton_blocker_complex::is_contractible
virtual contractible_status is_contractible() const
Test if the complex is reducible using a strategy defined in the class (by default it tests if the co...
Definition Skeleton_blocker_complex.h:1162
Gudhi::skeleton_blocker::Skeleton_blocker_complex::blocker_range
Complex_blocker_around_vertex_range blocker_range(Vertex_handle v)
Returns a range of the blockers of the complex passing through a vertex.
Definition Skeleton_blocker_complex.h:1469
Gudhi::skeleton_blocker::Skeleton_blocker_complex::contains_vertices
bool contains_vertices(const Simplex &sigma) const
Definition Skeleton_blocker_complex.h:421
Gudhi::skeleton_blocker::Skeleton_blocker_complex::add_edge_without_blockers
Edge_handle add_edge_without_blockers(Vertex_handle a, Vertex_handle b)
Adds an edge between vertices a and b without blockers.
Definition Skeleton_blocker_complex.h:566
Gudhi::skeleton_blocker::Skeleton_blocker_complex::first_vertex
Vertex_handle first_vertex(Edge_handle edge_handle) const
returns the first vertex of an edge
Definition Skeleton_blocker_complex.h:512
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_edge
virtual Edge_handle remove_edge(Vertex_handle a, Vertex_handle b)
Removes an edge from the simplicial complex and all its cofaces.
Definition Skeleton_blocker_complex.h:596
Gudhi::skeleton_blocker::Skeleton_blocker_complex::contract_edge
void contract_edge(Edge_handle edge)
Definition Skeleton_blocker_complex.h:1244
Gudhi::skeleton_blocker::Skeleton_blocker_complex::degree
int degree(Vertex_handle local) const
return the graph degree of a vertex.
Definition Skeleton_blocker_complex.h:468
Gudhi::skeleton_blocker::Skeleton_blocker_complex::link_condition
bool link_condition(Vertex_handle a, Vertex_handle b, bool ignore_popable_blockers=false) const
Definition Skeleton_blocker_complex.h:1182
Gudhi::skeleton_blocker::Skeleton_blocker_complex::second_vertex
Vertex_handle second_vertex(Edge_handle edge_handle) const
returns the first vertex of an edge
Definition Skeleton_blocker_complex.h:520
Gudhi::skeleton_blocker::Skeleton_blocker_complex::add_simplex
void add_simplex(const Simplex &sigma)
add a simplex and all its faces.
Definition Skeleton_blocker_simplifiable_complex.h:195
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_all_popable_blockers
void remove_all_popable_blockers(Vertex_handle v)
Removes all the popable blockers of the complex passing through v and delete them....
Definition Skeleton_blocker_simplifiable_complex.h:92
Gudhi::skeleton_blocker::Skeleton_blocker_complex::contains
virtual bool contains(const Simplex &s) const
returns true iff the simplex s belongs to the simplicial complex.
Definition Skeleton_blocker_complex.h:952
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_popable_blockers
void remove_popable_blockers()
Definition Skeleton_blocker_simplifiable_complex.h:44
Gudhi::skeleton_blocker::Skeleton_blocker_complex::add_blocker
Blocker_handle add_blocker(const Simplex &blocker)
Adds the simplex to the set of blockers and returns a Blocker_handle toward it if was not present bef...
Definition Skeleton_blocker_complex.h:669
Gudhi::skeleton_blocker::Skeleton_blocker_complex::contains_edges
bool contains_edges(const Simplex &sigma) const
Definition Skeleton_blocker_complex.h:647
Gudhi::skeleton_blocker::Skeleton_blocker_complex::Simplex
Skeleton_blocker_simplex< Vertex_handle > Simplex
A ordered set of integers that represents a simplex.
Definition Skeleton_blocker_complex.h:83
Gudhi::skeleton_blocker::Skeleton_blocker_complex::add_vertex
Vertex_handle add_vertex()
Adds a vertex to the simplicial complex and returns its Vertex_handle.
Definition Skeleton_blocker_complex.h:372
Gudhi::skeleton_blocker::Skeleton_blocker_complex::Blocker_handle
Simplex * Blocker_handle
Handle to a blocker of the complex.
Definition Skeleton_blocker_complex.h:89
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_star
void remove_star(Vertex_handle v)
Definition Skeleton_blocker_simplifiable_complex.h:120
Gudhi::skeleton_blocker::Skeleton_blocker_complex::delete_blocker
void delete_blocker(Blocker_handle sigma)
Definition Skeleton_blocker_complex.h:770
Gudhi::skeleton_blocker::Skeleton_blocker_complex::is_popable_blocker
bool is_popable_blocker(Blocker_handle sigma) const
Definition Skeleton_blocker_simplifiable_complex.h:33
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_vertex
void remove_vertex(Vertex_handle address)
Remove a vertex from the simplicial complex.
Definition Skeleton_blocker_complex.h:390
Gudhi::skeleton_blocker::Skeleton_blocker_complex::vertex_range
Complex_vertex_range vertex_range() const
Returns a Complex_vertex_range over all vertices of the complex.
Definition Skeleton_blocker_complex.h:1282
Gudhi::skeleton_blocker::Skeleton_blocker_complex::add_edge
Edge_handle add_edge(Vertex_handle a, Vertex_handle b)
Adds an edge between vertices a and b.
Definition Skeleton_blocker_complex.h:541
Gudhi::skeleton_blocker::Skeleton_blocker_complex::Vertex_handle
SkeletonBlockerDS::Vertex_handle Vertex_handle
The type of an handle to a vertex of the complex.
Definition Skeleton_blocker_complex.h:77
Gudhi::skeleton_blocker::Skeleton_blocker_complex::contains_edge
bool contains_edge(Vertex_handle a, Vertex_handle b) const
Definition Skeleton_blocker_complex.h:638
Gudhi::skeleton_blocker::Skeleton_blocker_complex::contains_blocker
bool contains_blocker(const Blocker_handle s) const
Definition Skeleton_blocker_complex.h:780
Gudhi::skeleton_blocker::Skeleton_blocker_complex::Edge_handle
boost::graph_traits< Graph >::edge_descriptor Edge_handle
Handle to an edge of the complex.
Definition Skeleton_blocker_complex.h:114
Gudhi::skeleton_blocker::Skeleton_blocker_link_complex
Class representing the link of a simplicial complex encoded by a skeleton/blockers pair....
Definition Skeleton_blocker_link_complex.h:31
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::first_vertex
T first_vertex() const
Definition Skeleton_blocker_simplex.h:210
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::union_vertices
void union_vertices(const Skeleton_blocker_simplex &a)
Definition Skeleton_blocker_simplex.h:155
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::last_vertex
T last_vertex() const
Definition Skeleton_blocker_simplex.h:220
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::remove_vertex
void remove_vertex(T v)
Definition Skeleton_blocker_simplex.h:117
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::difference
void difference(const Skeleton_blocker_simplex &a)
Definition Skeleton_blocker_simplex.h:139
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::dimension
int dimension() const
Definition Skeleton_blocker_simplex.h:197
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::add_vertex
void add_vertex(T v)
Definition Skeleton_blocker_simplex.h:110
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14