Loading...
Searching...
No Matches
Skeleton_blocker_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_COMPLEX_H_
#define SKELETON_BLOCKER_COMPLEX_H_
#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h>
#include <gudhi/Skeleton_blocker_link_complex.h>
#include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h>
#include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h>
#include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h>
#include <gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h>
#include <gudhi/Skeleton_blocker/internal/Top_faces.h>
#include <gudhi/Skeleton_blocker/internal/Trie.h>
#include <gudhi/Debug_utils.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/adaptor/map.hpp>
#include <iostream>
#include <fstream>
#include <sstream>
#include <memory>
#include <map>
#include <list>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
namespace Gudhi {
namespace skeleton_blocker {
template<class SkeletonBlockerDS>
class Skeleton_blocker_complex {
template<class ComplexType> friend class Vertex_iterator;
template<class ComplexType> friend class Neighbors_vertices_iterator;
template<class ComplexType> friend class Edge_iterator;
template<class ComplexType> friend class Edge_around_vertex_iterator;
template<class ComplexType> friend class Skeleton_blocker_link_complex;
template<class ComplexType> friend class Skeleton_blocker_link_superior;
template<class ComplexType> friend class Skeleton_blocker_sub_complex;
public:
typedef typename SkeletonBlockerDS::Graph_vertex Graph_vertex;
typedef typename SkeletonBlockerDS::Graph_edge Graph_edge;
typedef typename SkeletonBlockerDS::Root_vertex_handle Root_vertex_handle;
typedef typename SkeletonBlockerDS::Vertex_handle Vertex_handle;
typedef typename Root_vertex_handle::boost_vertex_handle boost_vertex_handle;
typedef Skeleton_blocker_simplex<Vertex_handle> Simplex;
typedef Skeleton_blocker_simplex<Root_vertex_handle> Root_simplex_handle;
typedef Simplex* Blocker_handle;
typedef typename Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_iterator;
typedef typename Simplex::Simplex_vertex_const_iterator Simplex_handle_iterator;
protected:
typedef typename boost::adjacency_list<boost::setS, // edges
boost::vecS, // vertices
boost::undirectedS, Graph_vertex, Graph_edge> Graph;
// todo/remark : edges are not sorted, it heavily penalizes computation for SuperiorLink
// (eg Link with greater vertices)
// that burdens simplex iteration / complex initialization via list of simplices.
// to avoid that, one should modify the graph by storing two lists of adjacency for every
// vertex, the one with superior and the one with lower vertices, that way there is
// no more extra cost for computation of SuperiorLink
typedef typename boost::graph_traits<Graph>::vertex_iterator boost_vertex_iterator;
typedef typename boost::graph_traits<Graph>::edge_iterator boost_edge_iterator;
protected:
typedef typename boost::graph_traits<Graph>::adjacency_iterator boost_adjacency_iterator;
public:
typedef typename boost::graph_traits<Graph>::edge_descriptor Edge_handle;
protected:
typedef std::multimap<Vertex_handle, Simplex *> BlockerMap;
typedef typename std::multimap<Vertex_handle, Simplex *>::value_type BlockerPair;
typedef typename std::multimap<Vertex_handle, Simplex *>::iterator BlockerMapIterator;
typedef typename std::multimap<Vertex_handle, Simplex *>::const_iterator BlockerMapConstIterator;
protected:
size_t num_vertices_;
size_t num_blockers_;
typedef Skeleton_blocker_complex_visitor<Vertex_handle> Visitor;
// typedef Visitor* Visitor_ptr;
Visitor* visitor;
std::vector<boost_vertex_handle> degree_;
Graph skeleton;
BlockerMap blocker_map_;
public:
explicit Skeleton_blocker_complex(size_t num_vertices_ = 0, Visitor* visitor_ = NULL)
: visitor(visitor_) {
clear();
for (size_t i = 0; i < num_vertices_; ++i) {
add_vertex();
}
}
private:
// typedef Trie<Skeleton_blocker_complex<SkeletonBlockerDS>> STrie;
typedef Trie<Simplex> STrie;
public:
template<typename SimpleHandleOutputIterator>
Skeleton_blocker_complex(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end,
bool is_flag_complex = false, Visitor* visitor_ = NULL)
: num_vertices_(0),
num_blockers_(0),
visitor(visitor_) {
add_vertices_and_edges(simplices_begin, simplices_end);
if (!is_flag_complex)
// need to compute blockers
add_blockers(simplices_begin, simplices_end);
}
private:
template<typename SimpleHandleOutputIterator>
void add_vertices_and_edges(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) {
std::vector<std::pair<Vertex_handle, Vertex_handle>> edges;
// first pass to add vertices and edges
int num_vertex = -1;
for (auto s_it = simplices_begin; s_it != simplices_end; ++s_it) {
if (s_it->dimension() == 0) num_vertex = (std::max)(num_vertex, s_it->first_vertex().vertex);
if (s_it->dimension() == 1) edges.emplace_back(s_it->first_vertex(), s_it->last_vertex());
}
while (num_vertex-- >= 0) add_vertex();
for (const auto& e : edges)
add_edge_without_blockers(e.first, e.second);
}
template<typename SimpleHandleOutputIterator>
void add_blockers(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) {
Tries<Simplex> tries(num_vertices(), simplices_begin, simplices_end);
tries.init_next_dimension();
auto simplices(tries.next_dimension_simplices());
while (!simplices.empty()) {
simplices = tries.next_dimension_simplices();
for (auto& sigma : simplices) {
// common_positive_neighbors is the set of vertices u such that
// for all s in sigma, us is an edge and u>s
Simplex common_positive_neighbors(tries.positive_neighbors(sigma.last_vertex()));
for (auto sigma_it = sigma.rbegin(); sigma_it != sigma.rend(); ++sigma_it)
if (sigma_it != sigma.rbegin())
common_positive_neighbors.intersection(tries.positive_neighbors(*sigma_it));
for (auto x : common_positive_neighbors) {
// first test that all edges sx are here for all s in sigma
bool all_edges_here = true;
for (auto s : sigma)
if (!contains_edge(x, s)) {
all_edges_here = false;
break;
}
if (!all_edges_here) continue;
// all edges of sigma \cup x are here
// we have a blocker if all proper faces of sigma \cup x
// are in the complex and if sigma \cup x is not in the complex
// the first is equivalent at checking if blocks(sigma \cup x) is true
// as all blockers of lower dimension have already been computed
sigma.add_vertex(x);
if (!tries.contains(sigma) && !blocks(sigma))
add_blocker(sigma);
sigma.remove_vertex(x);
}
}
}
}
public:
// We cannot use the default copy constructor since we need
// to make a copy of each of the blockers
Skeleton_blocker_complex(const Skeleton_blocker_complex& copy) {
visitor = NULL;
degree_ = copy.degree_;
skeleton = Graph(copy.skeleton);
num_vertices_ = copy.num_vertices_;
num_blockers_ = 0;
// we copy the blockers
for (auto blocker : copy.const_blocker_range()) {
add_blocker(*blocker);
}
}
Skeleton_blocker_complex& operator=(const Skeleton_blocker_complex& copy) {
clear();
visitor = NULL;
degree_ = copy.degree_;
skeleton = Graph(copy.skeleton);
num_vertices_ = copy.num_vertices_;
num_blockers_ = 0;
// we copy the blockers
for (auto blocker : copy.const_blocker_range())
add_blocker(*blocker);
return *this;
}
bool operator==(const Skeleton_blocker_complex& other) const {
if (other.num_vertices() != num_vertices()) return false;
if (other.num_edges() != num_edges()) return false;
if (other.num_blockers() != num_blockers()) return false;
for (auto v : vertex_range())
if (!other.contains_vertex(v)) return false;
for (auto e : edge_range())
if (!other.contains_edge(first_vertex(e), second_vertex(e))) return false;
for (const auto b : const_blocker_range())
if (!other.contains_blocker(*b)) return false;
return true;
}
bool operator!=(const Skeleton_blocker_complex& other) const {
return !(*this == other);
}
virtual ~Skeleton_blocker_complex() {
clear();
}
virtual void clear() {
// xxx for now the responsabilty of freeing the visitor is for
// the user
visitor = NULL;
degree_.clear();
num_vertices_ = 0;
remove_blockers();
skeleton.clear();
}
void set_visitor(Visitor* other_visitor) {
visitor = other_visitor;
}
public:
Vertex_handle operator[](Root_vertex_handle global) const {
auto local(get_address(global));
assert(local);
return *local;
}
Graph_vertex& operator[](Vertex_handle address) {
assert(
0 <= address.vertex && address.vertex < boost::num_vertices(skeleton));
return skeleton[address.vertex];
}
const Graph_vertex& operator[](Vertex_handle address) const {
assert(
0 <= address.vertex && address.vertex < boost::num_vertices(skeleton));
return skeleton[address.vertex];
}
Vertex_handle add_vertex() {
Vertex_handle address(boost::add_vertex(skeleton));
num_vertices_++;
(*this)[address].activate();
// safe since we now that we are in the root complex and the field 'address' and 'id'
// are identical for every vertices
(*this)[address].set_id(Root_vertex_handle(address.vertex));
degree_.push_back(0);
if (visitor)
visitor->on_add_vertex(address);
return address;
}
void remove_vertex(Vertex_handle address) {
assert(contains_vertex(address));
// We remove b
boost::clear_vertex(address.vertex, skeleton);
(*this)[address].deactivate();
num_vertices_--;
degree_[address.vertex] = -1;
if (visitor)
visitor->on_remove_vertex(address);
}
bool contains_vertex(Vertex_handle u) const {
Vertex_handle num_vertices(boost::num_vertices(skeleton));
if (u.vertex < 0 || u.vertex >= num_vertices)
return false;
return (*this)[u].is_active();
}
bool contains_vertex(Root_vertex_handle u) const {
boost::optional<Vertex_handle> address = get_address(u);
return address && (*this)[*address].is_active();
}
bool contains_vertices(const Simplex & sigma) const {
for (auto vertex : sigma)
if (!contains_vertex(vertex))
return false;
return true;
}
virtual boost::optional<Vertex_handle> get_address(Root_vertex_handle id) const {
boost::optional<Vertex_handle> res;
int num_vertices = boost::num_vertices(skeleton);
if (id.vertex < num_vertices)
res = Vertex_handle(id.vertex);
return res;
}
Root_vertex_handle get_id(Vertex_handle local) const {
assert(0 <= local.vertex && local.vertex < boost::num_vertices(skeleton));
return (*this)[local].get_id();
}
Vertex_handle convert_handle_from_another_complex(const Skeleton_blocker_complex& other,
Vertex_handle vh_in_other) const {
auto vh_in_current_complex = get_address(other.get_id(vh_in_other));
assert(vh_in_current_complex);
return *vh_in_current_complex;
}
int degree(Vertex_handle local) const {
assert(0 <= local.vertex && local.vertex < boost::num_vertices(skeleton));
return degree_[local.vertex];
}
public:
boost::optional<Edge_handle> operator[](
const std::pair<Vertex_handle, Vertex_handle>& ab) const {
boost::optional<Edge_handle> res;
std::pair<Edge_handle, bool> edge_pair(
boost::edge(ab.first.vertex, ab.second.vertex, skeleton));
if (edge_pair.second)
res = edge_pair.first;
return res;
}
Graph_edge& operator[](Edge_handle edge_handle) {
return skeleton[edge_handle];
}
const Graph_edge& operator[](Edge_handle edge_handle) const {
return skeleton[edge_handle];
}
Vertex_handle first_vertex(Edge_handle edge_handle) const {
return static_cast<Vertex_handle> (source(edge_handle, skeleton));
}
Vertex_handle second_vertex(Edge_handle edge_handle) const {
return static_cast<Vertex_handle> (target(edge_handle, skeleton));
}
Simplex get_vertices(Edge_handle edge_handle) const {
auto edge((*this)[edge_handle]);
return Simplex((*this)[edge.first()], (*this)[edge.second()]);
}
Edge_handle add_edge(Vertex_handle a, Vertex_handle b) {
// if the edge is already there we musnt go further
// as we may add blockers that should not be here
if (contains_edge(a, b))
return *((*this)[std::make_pair(a, b)]);
auto res = add_edge_without_blockers(a, b);
add_blockers_after_simplex_insertion(Simplex(a, b));
return res;
}
void add_edge(const Simplex& s) {
for (auto i = s.begin(); i != s.end(); ++i)
for (auto j = i; ++j != s.end(); /**/)
add_edge(*i, *j);
}
Edge_handle add_edge_without_blockers(Vertex_handle a, Vertex_handle b) {
assert(contains_vertex(a) && contains_vertex(b));
assert(a != b);
auto edge_handle((*this)[std::make_pair(a, b)]);
if (!edge_handle) {
edge_handle = boost::add_edge(a.vertex, b.vertex, skeleton).first;
(*this)[*edge_handle].setId(get_id(a), get_id(b));
degree_[a.vertex]++;
degree_[b.vertex]++;
if (visitor)
visitor->on_add_edge_without_blockers(a, b);
}
return *edge_handle;
}
void add_edge_without_blockers(Simplex s) {
for (auto i = s.begin(); i != s.end(); ++i) {
for (auto j = i; ++j != s.end(); /**/)
add_edge_without_blockers(*i, *j);
}
}
virtual Edge_handle remove_edge(Vertex_handle a, Vertex_handle b) {
bool found;
Edge_handle edge;
tie(edge, found) = boost::edge(a.vertex, b.vertex, skeleton);
if (found) {
if (visitor)
visitor->on_remove_edge(a, b);
boost::remove_edge(a.vertex, b.vertex, skeleton);
degree_[a.vertex]--;
degree_[b.vertex]--;
}
return edge;
}
void remove_edge(Edge_handle edge) {
assert(contains_vertex(first_vertex(edge)));
assert(contains_vertex(second_vertex(edge)));
remove_edge(first_vertex(edge), second_vertex(edge));
}
void keep_only_vertices() {
remove_blockers();
for (auto u : vertex_range()) {
while (this->degree(u) > 0) {
Vertex_handle v(*(adjacent_vertices(u.vertex, this->skeleton).first));
this->remove_edge(u, v);
}
}
}
bool contains_edge(Vertex_handle a, Vertex_handle b) const {
// if (a.vertex<0 || b.vertex <0) return false;
return boost::edge(a.vertex, b.vertex, skeleton).second;
}
bool contains_edges(const Simplex & sigma) const {
for (auto i = sigma.begin(); i != sigma.end(); ++i) {
if (!contains_vertex(*i))
return false;
for (auto j = i; ++j != sigma.end();) {
if (!contains_edge(*i, *j))
return false;
}
}
return true;
}
Blocker_handle add_blocker(const Simplex& blocker) {
assert(blocker.dimension() > 1);
if (contains_blocker(blocker)) {
return 0;
} else {
if (visitor)
visitor->on_add_blocker(blocker);
Blocker_handle blocker_pt = new Simplex(blocker);
num_blockers_++;
auto vertex = blocker_pt->begin();
while (vertex != blocker_pt->end()) {
blocker_map_.insert(BlockerPair(*vertex, blocker_pt));
++vertex;
}
return blocker_pt;
}
}
protected:
void add_blocker(Blocker_handle blocker) {
if (contains_blocker(*blocker)) {
// std::cerr << "ATTEMPT TO ADD A BLOCKER ALREADY THERE ---> BLOCKER IGNORED" << endl;
return;
} else {
if (visitor)
visitor->on_add_blocker(*blocker);
num_blockers_++;
auto vertex = blocker->begin();
while (vertex != blocker->end()) {
blocker_map_.insert(BlockerPair(*vertex, blocker));
++vertex;
}
}
}
protected:
void remove_blocker(const Blocker_handle sigma, Vertex_handle v) {
Complex_blocker_around_vertex_iterator blocker;
for (blocker = blocker_range(v).begin(); blocker != blocker_range(v).end();
++blocker) {
if (*blocker == sigma)
break;
}
if (*blocker != sigma) {
std::cerr
<< "bug ((*blocker).second == sigma) ie try to remove a blocker not present\n";
assert(false);
} else {
blocker_map_.erase(blocker.current_position());
}
}
public:
void remove_blocker(const Blocker_handle sigma) {
for (auto vertex : *sigma)
remove_blocker(sigma, vertex);
num_blockers_--;
}
void remove_blockers() {
// Deallocate the blockers
while (!blocker_map_.empty()) {
delete_blocker(blocker_map_.begin()->second);
}
num_blockers_ = 0;
blocker_map_.clear();
}
protected:
void remove_blocker(const Simplex& sigma) {
assert(contains_blocker(sigma));
for (auto vertex : sigma)
remove_blocker(sigma, vertex);
num_blockers_--;
}
public:
void delete_blocker(Blocker_handle sigma) {
if (visitor)
visitor->on_delete_blocker(sigma);
remove_blocker(sigma);
delete sigma;
}
bool contains_blocker(const Blocker_handle s) const {
if (s->dimension() < 2)
return false;
Vertex_handle a = s->first_vertex();
for (const auto blocker : const_blocker_range(a)) {
if (s == *blocker)
return true;
}
return false;
}
bool contains_blocker(const Simplex & s) const {
if (s.dimension() < 2)
return false;
Vertex_handle a = s.first_vertex();
for (auto blocker : const_blocker_range(a)) {
if (s == *blocker)
return true;
}
return false;
}
private:
bool blocks(const Simplex & sigma) const {
for (auto s : sigma)
for (auto blocker : const_blocker_range(s))
if (sigma.contains(*blocker))
return true;
return false;
}
protected:
virtual void add_neighbours(Vertex_handle v, Simplex & n,
bool keep_only_superior = false) const {
boost_adjacency_iterator ai, ai_end;
for (tie(ai, ai_end) = adjacent_vertices(v.vertex, skeleton); ai != ai_end;
++ai) {
Vertex_handle value(*ai);
if (keep_only_superior) {
if (value > v.vertex) {
n.add_vertex(value);
}
} else {
n.add_vertex(value);
}
}
}
virtual void add_neighbours(const Simplex &alpha, Simplex & res,
bool keep_only_superior = false) const {
res.clear();
auto alpha_vertex = alpha.begin();
add_neighbours(*alpha_vertex, res, keep_only_superior);
for (alpha_vertex = (alpha.begin())++; alpha_vertex != alpha.end();
++alpha_vertex)
keep_neighbours(*alpha_vertex, res, keep_only_superior);
}
virtual void keep_neighbours(Vertex_handle v, Simplex& res,
bool keep_only_superior = false) const {
Simplex nv;
add_neighbours(v, nv, keep_only_superior);
res.intersection(nv);
}
virtual void remove_neighbours(Vertex_handle v, Simplex & res,
bool keep_only_superior = false) const {
Simplex nv;
add_neighbours(v, nv, keep_only_superior);
res.difference(nv);
}
public:
typedef Skeleton_blocker_link_complex<Skeleton_blocker_complex> Link_complex;
Link_complex link(Vertex_handle v) const {
return Link_complex(*this, Simplex(v));
}
Link_complex link(Edge_handle edge) const {
return Link_complex(*this, edge);
}
Link_complex link(const Simplex& simplex) const {
return Link_complex(*this, simplex);
}
// xxx rename get_address et place un using dans sub_complex
boost::optional<Simplex> get_simplex_address(
const Root_simplex_handle& s) const {
boost::optional<Simplex> res;
Simplex s_address;
// Root_simplex_const_iterator i;
for (auto i = s.begin(); i != s.end(); ++i) {
boost::optional<Vertex_handle> address = get_address(*i);
if (!address)
return res;
else
s_address.add_vertex(*address);
}
res = s_address;
return res;
}
Root_simplex_handle get_id(const Simplex& local_simplex) const {
Root_simplex_handle global_simplex;
for (auto x = local_simplex.begin(); x != local_simplex.end(); ++x) {
global_simplex.add_vertex(get_id(*x));
}
return global_simplex;
}
virtual bool contains(const Simplex & s) const {
if (s.dimension() == -1) {
return false;
} else if (s.dimension() == 0) {
return contains_vertex(s.first_vertex());
} else {
return (contains_edges(s) && !blocks(s));
}
}
/*
* @brief returns true iff the complex is empty.
*/
bool empty() const {
return num_vertices() == 0;
}
/*
* @brief returns the number of vertices in the complex.
*/
int num_vertices() const {
// remark boost::num_vertices(skeleton) counts deactivated vertices
return num_vertices_;
}
/*
* @brief returns the number of edges in the complex.
* @details currently in O(n)
*/
// todo cache the value
int num_edges() const {
return boost::num_edges(skeleton);
}
int num_triangles() const {
auto triangles = triangle_range();
return std::distance(triangles.begin(), triangles.end());
}
/*
* @brief returns the number of simplices of a given dimension in the complex.
*/
size_t num_simplices() const {
auto simplices = complex_simplex_range();
return std::distance(simplices.begin(), simplices.end());
}
/*
* @brief returns the number of simplices of a given dimension in the complex.
*/
size_t num_simplices(int dimension) const {
// TODO(DS): iterator on k-simplices
size_t res = 0;
for (const auto& s : complex_simplex_range())
if (s.dimension() == dimension)
++res;
return res;
}
/*
* @brief returns the number of blockers in the complex.
*/
size_t num_blockers() const {
return num_blockers_;
}
/*
* @brief returns true iff the graph of the 1-skeleton of the complex is complete.
*/
bool complete() const {
return (num_vertices() * (num_vertices() - 1)) / 2 == num_edges();
}
int num_connected_components() const {
int num_vert_collapsed = skeleton.vertex_set().size() - num_vertices();
std::vector<int> component(skeleton.vertex_set().size());
return boost::connected_components(this->skeleton, &component[0])
- num_vert_collapsed;
}
bool is_cone() const {
if (num_vertices() == 0)
return false;
if (num_vertices() == 1)
return true;
for (auto vi : vertex_range()) {
// xxx todo create a method: bool is_in_blocker(Vertex_handle)
if (blocker_map_.find(vi) == blocker_map_.end()) {
// no blocker passes through the vertex, we just need to
// check if the current vertex is linked to all others vertices of the complex
if (degree_[vi.vertex] == num_vertices() - 1)
return true;
}
}
return false;
}
bool is_popable_blocker(Blocker_handle sigma) const;
void remove_popable_blockers();
void remove_popable_blockers(Vertex_handle v);
void remove_all_popable_blockers(Vertex_handle v);
void remove_star(Vertex_handle v);
private:
void update_blockers_after_remove_star_of_vertex_or_edge(const Simplex& simplex_to_be_removed);
public:
void remove_star(Vertex_handle a, Vertex_handle b);
void remove_star(Edge_handle e);
void remove_star(const Simplex& sigma);
void add_simplex(const Simplex& sigma);
private:
void add_blockers_after_simplex_insertion(Simplex s);
void remove_blocker_containing_simplex(const Simplex& sigma);
void remove_blocker_include_in_simplex(const Simplex& sigma);
public:
enum simplifiable_status {
NOT_HOMOTOPY_EQ, MAYBE_HOMOTOPY_EQ, HOMOTOPY_EQ
};
simplifiable_status is_remove_star_homotopy_preserving(const Simplex& simplex) {
// todo write a virtual method 'link' in Skeleton_blocker_complex which will be overloaded by the current one of
// Skeleton_blocker_geometric_complex
// then call it there to build the link and return the value of link.is_contractible()
return MAYBE_HOMOTOPY_EQ;
}
enum contractible_status {
NOT_CONTRACTIBLE, MAYBE_CONTRACTIBLE, CONTRACTIBLE
};
virtual contractible_status is_contractible() const {
if (this->is_cone()) {
return CONTRACTIBLE;
} else {
return MAYBE_CONTRACTIBLE;
}
}
bool link_condition(Vertex_handle a, Vertex_handle b, bool ignore_popable_blockers = false) const {
for (auto blocker : this->const_blocker_range(a))
if (blocker->contains(b)) {
// false if ignore_popable_blockers is false
// otherwise the blocker has to be popable
return ignore_popable_blockers && is_popable_blocker(blocker);
}
return true;
}
bool link_condition(Edge_handle e, bool ignore_popable_blockers = false) const {
const Graph_edge& edge = (*this)[e];
assert(this->get_address(edge.first()));
assert(this->get_address(edge.second()));
Vertex_handle a(*this->get_address(edge.first()));
Vertex_handle b(*this->get_address(edge.second()));
return link_condition(a, b, ignore_popable_blockers);
}
protected:
void tip_blockers(Vertex_handle a, Vertex_handle b, std::vector<Simplex> & buffer) const;
private:
void swap_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x);
private:
void delete_blockers_around_vertex(Vertex_handle v);
void delete_blockers_around_edge(Vertex_handle a, Vertex_handle b);
public:
void contract_edge(Edge_handle edge) {
contract_edge(this->first_vertex(edge), this->second_vertex(edge));
}
void contract_edge(Vertex_handle a, Vertex_handle b);
private:
void get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b,
std::set<Simplex>& blockers_to_add);
void delete_blockers_around_vertices(Vertex_handle a, Vertex_handle b);
void update_edges_after_contraction(Vertex_handle a, Vertex_handle b);
void notify_changed_edges(Vertex_handle a);
public:
typedef Vertex_iterator<Skeleton_blocker_complex> Complex_vertex_iterator;
//
// Range over the vertices of the simplicial complex.
// Methods .begin() and .end() return a Complex_vertex_iterator.
//
typedef boost::iterator_range<Complex_vertex_iterator> Complex_vertex_range;
Complex_vertex_range vertex_range() const {
auto begin = Complex_vertex_iterator(this);
auto end = Complex_vertex_iterator(this, 0);
return Complex_vertex_range(begin, end);
}
typedef Neighbors_vertices_iterator<Skeleton_blocker_complex> Complex_neighbors_vertices_iterator;
typedef boost::iterator_range<Complex_neighbors_vertices_iterator> Complex_neighbors_vertices_range;
Complex_neighbors_vertices_range vertex_range(Vertex_handle v) const {
auto begin = Complex_neighbors_vertices_iterator(this, v);
auto end = Complex_neighbors_vertices_iterator(this, v, 0);
return Complex_neighbors_vertices_range(begin, end);
}
typedef Edge_iterator<Skeleton_blocker_complex> Complex_edge_iterator;
typedef boost::iterator_range<Complex_edge_iterator> Complex_edge_range;
Complex_edge_range edge_range() const {
auto begin = Complex_edge_iterator(this);
auto end = Complex_edge_iterator(this, 0);
return Complex_edge_range(begin, end);
}
typedef Edge_around_vertex_iterator<Skeleton_blocker_complex> Complex_edge_around_vertex_iterator;
typedef boost::iterator_range <Complex_edge_around_vertex_iterator> Complex_edge_around_vertex_range;
Complex_edge_around_vertex_range edge_range(Vertex_handle v) const {
auto begin = Complex_edge_around_vertex_iterator(this, v);
auto end = Complex_edge_around_vertex_iterator(this, v, 0);
return Complex_edge_around_vertex_range(begin, end);
}
private:
typedef Skeleton_blocker_link_complex<Skeleton_blocker_complex<SkeletonBlockerDS> > Link;
typedef Skeleton_blocker_link_superior<Skeleton_blocker_complex<SkeletonBlockerDS> > Superior_link;
public:
typedef Triangle_around_vertex_iterator<Skeleton_blocker_complex, Superior_link>
Superior_triangle_around_vertex_iterator;
typedef boost::iterator_range < Triangle_around_vertex_iterator<Skeleton_blocker_complex, Link> >
Complex_triangle_around_vertex_range;
Complex_triangle_around_vertex_range triangle_range(Vertex_handle v) const {
auto begin = Triangle_around_vertex_iterator<Skeleton_blocker_complex, Link>(this, v);
auto end = Triangle_around_vertex_iterator<Skeleton_blocker_complex, Link>(this, v, 0);
return Complex_triangle_around_vertex_range(begin, end);
}
typedef boost::iterator_range<Triangle_iterator<Skeleton_blocker_complex> > Complex_triangle_range;
typedef Triangle_iterator<Skeleton_blocker_complex> Complex_triangle_iterator;
Complex_triangle_range triangle_range() const {
auto end = Triangle_iterator<Skeleton_blocker_complex>(this, 0);
if (empty()) {
return Complex_triangle_range(end, end);
} else {
auto begin = Triangle_iterator<Skeleton_blocker_complex>(this);
return Complex_triangle_range(begin, end);
}
}
typedef Simplex_around_vertex_iterator<Skeleton_blocker_complex, Link> Complex_simplex_around_vertex_iterator;
typedef boost::iterator_range < Complex_simplex_around_vertex_iterator > Complex_simplex_around_vertex_range;
Complex_simplex_around_vertex_range star_simplex_range(Vertex_handle v) const {
assert(contains_vertex(v));
return Complex_simplex_around_vertex_range(
Complex_simplex_around_vertex_iterator(this, v),
Complex_simplex_around_vertex_iterator(this, v, true));
}
typedef Simplex_coboundary_iterator<Skeleton_blocker_complex, Link> Complex_simplex_coboundary_iterator;
typedef boost::iterator_range < Complex_simplex_coboundary_iterator > Complex_coboundary_range;
Complex_coboundary_range coboundary_range(const Simplex& s) const {
assert(contains(s));
return Complex_coboundary_range(Complex_simplex_coboundary_iterator(this, s),
Complex_simplex_coboundary_iterator(this, s, true));
}
// typedef Simplex_iterator<Skeleton_blocker_complex,Superior_link> Complex_simplex_iterator;
typedef Simplex_iterator<Skeleton_blocker_complex> Complex_simplex_iterator;
typedef boost::iterator_range < Complex_simplex_iterator > Complex_simplex_range;
Complex_simplex_range complex_simplex_range() const {
Complex_simplex_iterator end(this, true);
if (empty()) {
return Complex_simplex_range(end, end);
} else {
Complex_simplex_iterator begin(this);
return Complex_simplex_range(begin, end);
}
}
private:
typedef Blocker_iterator_around_vertex_internal<
typename std::multimap<Vertex_handle, Simplex *>::iterator,
Blocker_handle>
Complex_blocker_around_vertex_iterator;
typedef Blocker_iterator_around_vertex_internal<
typename std::multimap<Vertex_handle, Simplex *>::const_iterator,
const Blocker_handle>
Const_complex_blocker_around_vertex_iterator;
typedef boost::iterator_range <Complex_blocker_around_vertex_iterator> Complex_blocker_around_vertex_range;
typedef boost::iterator_range <Const_complex_blocker_around_vertex_iterator>
Const_complex_blocker_around_vertex_range;
public:
Complex_blocker_around_vertex_range blocker_range(Vertex_handle v) {
auto begin = Complex_blocker_around_vertex_iterator(blocker_map_.lower_bound(v));
auto end = Complex_blocker_around_vertex_iterator(blocker_map_.upper_bound(v));
return Complex_blocker_around_vertex_range(begin, end);
}
Const_complex_blocker_around_vertex_range const_blocker_range(Vertex_handle v) const {
auto begin = Const_complex_blocker_around_vertex_iterator(blocker_map_.lower_bound(v));
auto end = Const_complex_blocker_around_vertex_iterator(blocker_map_.upper_bound(v));
return Const_complex_blocker_around_vertex_range(begin, end);
}
private:
typedef Blocker_iterator_internal<
typename std::multimap<Vertex_handle, Simplex *>::iterator,
Blocker_handle>
Complex_blocker_iterator;
typedef Blocker_iterator_internal<
typename std::multimap<Vertex_handle, Simplex *>::const_iterator,
const Blocker_handle>
Const_complex_blocker_iterator;
typedef boost::iterator_range <Complex_blocker_iterator> Complex_blocker_range;
typedef boost::iterator_range <Const_complex_blocker_iterator> Const_complex_blocker_range;
public:
Complex_blocker_range blocker_range() {
auto begin = Complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end());
auto end = Complex_blocker_iterator(blocker_map_.end(), blocker_map_.end());
return Complex_blocker_range(begin, end);
}
Const_complex_blocker_range const_blocker_range() const {
auto begin = Const_complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end());
auto end = Const_complex_blocker_iterator(blocker_map_.end(), blocker_map_.end());
return Const_complex_blocker_range(begin, end);
}
public:
std::string to_string() const {
std::ostringstream stream;
stream << num_vertices() << " vertices:\n" << vertices_to_string() << std::endl;
stream << num_edges() << " edges:\n" << edges_to_string() << std::endl;
stream << num_blockers() << " blockers:\n" << blockers_to_string() << std::endl;
return stream.str();
}
std::string vertices_to_string() const {
std::ostringstream stream;
for (auto vertex : vertex_range()) {
stream << "{" << (*this)[vertex].get_id() << "} ";
}
stream << std::endl;
return stream.str();
}
std::string edges_to_string() const {
std::ostringstream stream;
for (auto edge : edge_range())
stream << "{" << (*this)[edge].first() << "," << (*this)[edge].second() << "} ";
stream << std::endl;
return stream.str();
}
std::string blockers_to_string() const {
std::ostringstream stream;
for (auto b : const_blocker_range())
stream << *b << std::endl;
return stream.str();
}
};
template<typename Complex, typename SimplexHandleIterator>
Complex make_complex_from_top_faces(SimplexHandleIterator simplices_begin, SimplexHandleIterator simplices_end,
bool is_flag_complex = false) {
// TODO(DS): use add_simplex instead! should be more efficient and more elegant :)
typedef typename Complex::Simplex Simplex;
std::vector<Simplex> simplices;
for (auto top_face = simplices_begin; top_face != simplices_end; ++top_face) {
auto subfaces_topface = subfaces(*top_face);
simplices.insert(simplices.end(), subfaces_topface.begin(), subfaces_topface.end());
}
return Complex(simplices.begin(), simplices.end(), is_flag_complex);
}
} // namespace skeleton_blocker
namespace skbl = skeleton_blocker;
} // namespace Gudhi
#include "Skeleton_blocker_simplifiable_complex.h"
#endif // SKELETON_BLOCKER_COMPLEX_H_
Gudhi::skeleton_blocker::Blocker_iterator_around_vertex_internal
Iterator through the blockers of a vertex.
Definition Skeleton_blockers_blockers_iterators.h:84
Gudhi::skeleton_blocker::Blocker_iterator_internal
Iterator through the blockers of a vertex.
Definition Skeleton_blockers_blockers_iterators.h:32
Gudhi::skeleton_blocker::Edge_iterator
Iterator on the edges of a simplicial complex.
Definition Skeleton_blockers_edges_iterators.h:88
Gudhi::skeleton_blocker::Simplex_around_vertex_iterator
Definition Skeleton_blockers_simplices_iterators.h:43
Gudhi::skeleton_blocker::Simplex_coboundary_iterator
Definition Skeleton_blockers_simplices_iterators.h:304
Gudhi::skeleton_blocker::Skeleton_blocker_complex_visitor
Interface for a visitor of a simplicial complex.
Definition Skeleton_blocker_complex_visitor.h:26
Gudhi::skeleton_blocker::Skeleton_blocker_complex
Abstract Simplicial Complex represented with a skeleton/blockers pair.
Definition Skeleton_blocker_complex.h:51
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::remove_edge
void remove_edge(Edge_handle edge)
Removes edge and its cofaces from the simplicial complex.
Definition Skeleton_blocker_complex.h:613
Gudhi::skeleton_blocker::Skeleton_blocker_complex::const_blocker_range
Const_complex_blocker_around_vertex_range const_blocker_range(Vertex_handle v) const
Returns a range of the blockers of the complex passing through a vertex.
Definition Skeleton_blocker_complex.h:1478
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::star_simplex_range
Complex_simplex_around_vertex_range star_simplex_range(Vertex_handle v) const
Returns a Complex_simplex_around_vertex_range over all the simplices around a vertex of the complex.
Definition Skeleton_blocker_complex.h:1398
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_popable_blockers
void remove_popable_blockers(Vertex_handle v)
Definition Skeleton_blocker_simplifiable_complex.h:73
Gudhi::skeleton_blocker::Skeleton_blocker_complex::link
Link_complex link(const Simplex &simplex) const
Definition Skeleton_blocker_complex.h:907
Gudhi::skeleton_blocker::Skeleton_blocker_complex::keep_only_vertices
void keep_only_vertices()
The complex is reduced to its set of vertices. All the edges and blockers are removed.
Definition Skeleton_blocker_complex.h:623
Gudhi::skeleton_blocker::Skeleton_blocker_complex::edge_range
Complex_edge_around_vertex_range edge_range(Vertex_handle v) const
Returns a Complex_edge_range over all edges of the simplicial complex that passes through 'v'.
Definition Skeleton_blocker_complex.h:1332
Gudhi::skeleton_blocker::Skeleton_blocker_complex::edge_range
Complex_edge_range edge_range() const
Returns a Complex_edge_range over all edges of the simplicial complex.
Definition Skeleton_blocker_complex.h:1316
Gudhi::skeleton_blocker::Skeleton_blocker_complex< Traits >::first_vertex
Vertex_handle first_vertex(Edge_handle edge_handle) const
Definition Skeleton_blocker_complex.h:512
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_star
void remove_star(Edge_handle e)
Definition Skeleton_blocker_simplifiable_complex.h:174
Gudhi::skeleton_blocker::Skeleton_blocker_complex::link
Link_complex link(Vertex_handle v) const
Definition Skeleton_blocker_complex.h:893
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< Traits >::Complex_simplex_around_vertex_range
boost::iterator_range< Complex_simplex_around_vertex_iterator > Complex_simplex_around_vertex_range
Definition Skeleton_blocker_complex.h:1393
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::coboundary_range
Complex_coboundary_range coboundary_range(const Simplex &s) const
Returns a Complex_simplex_coboundary_iterator over the simplices of the coboundary of a simplex.
Definition Skeleton_blocker_complex.h:1415
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::contains_blocker
bool contains_blocker(const Simplex &s) const
Definition Skeleton_blocker_complex.h:796
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_star
void remove_star(Vertex_handle a, Vertex_handle b)
Definition Skeleton_blocker_simplifiable_complex.h:164
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_star
void remove_star(const Simplex &sigma)
Definition Skeleton_blocker_simplifiable_complex.h:182
Gudhi::skeleton_blocker::Skeleton_blocker_complex::operator[]
boost::optional< Edge_handle > operator[](const std::pair< Vertex_handle, Vertex_handle > &ab) const
return an edge handle if the two vertices forms an edge in the complex
Definition Skeleton_blocker_complex.h:484
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::triangle_range
Complex_triangle_around_vertex_range triangle_range(Vertex_handle v) const
Range over triangles around a vertex of the simplicial complex. Methods .begin() and ....
Definition Skeleton_blocker_complex.h:1358
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::operator[]
const Graph_edge & operator[](Edge_handle edge_handle) const
returns the stored node associated to an edge
Definition Skeleton_blocker_complex.h:504
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::remove_blockers
void remove_blockers()
Remove all blockers, in other words, it expand the simplicial complex to the smallest flag complex th...
Definition Skeleton_blocker_complex.h:742
Gudhi::skeleton_blocker::Skeleton_blocker_complex::num_connected_components
int num_connected_components() const
returns the number of connected components in the graph of the 1-skeleton.
Definition Skeleton_blocker_complex.h:1029
Gudhi::skeleton_blocker::Skeleton_blocker_complex::operator[]
Graph_edge & operator[](Edge_handle edge_handle)
returns the stored node associated to an edge
Definition Skeleton_blocker_complex.h:497
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::clear
virtual void clear()
Definition Skeleton_blocker_complex.h:311
Gudhi::skeleton_blocker::Skeleton_blocker_complex< Traits >::Simplex
Skeleton_blocker_simplex< Vertex_handle > Simplex
Definition Skeleton_blocker_complex.h:83
Gudhi::skeleton_blocker::Skeleton_blocker_complex::get_address
virtual boost::optional< Vertex_handle > get_address(Root_vertex_handle id) const
Given an Id return the address of the vertex having this Id in the complex.
Definition Skeleton_blocker_complex.h:432
Gudhi::skeleton_blocker::Skeleton_blocker_complex::remove_blocker
void remove_blocker(const Blocker_handle sigma)
Removes the simplex from the set of blockers.
Definition Skeleton_blocker_complex.h:732
Gudhi::skeleton_blocker::Skeleton_blocker_complex< Traits >::Graph_vertex
Traits::Graph_vertex Graph_vertex
Definition Skeleton_blocker_complex.h:65
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::set_visitor
void set_visitor(Visitor *other_visitor)
allows to change the visitor.
Definition Skeleton_blocker_complex.h:327
Gudhi::skeleton_blocker::Skeleton_blocker_complex::add_edge_without_blockers
void add_edge_without_blockers(Simplex s)
Adds all edges of s in the complex without adding blockers.
Definition Skeleton_blocker_complex.h:585
Gudhi::skeleton_blocker::Skeleton_blocker_complex::get_vertices
Simplex get_vertices(Edge_handle edge_handle) const
returns the simplex made with the two vertices of the edge
Definition Skeleton_blocker_complex.h:529
Gudhi::skeleton_blocker::Skeleton_blocker_complex< Traits >::Blocker_handle
Simplex * Blocker_handle
Definition Skeleton_blocker_complex.h:89
Gudhi::skeleton_blocker::Skeleton_blocker_complex::link_condition
bool link_condition(Edge_handle e, bool ignore_popable_blockers=false) const
Definition Skeleton_blocker_complex.h:1199
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::operator[]
Vertex_handle operator[](Root_vertex_handle global) const
Return a local Vertex_handle of a vertex given a global one.
Definition Skeleton_blocker_complex.h:342
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::blocker_range
Complex_blocker_range blocker_range()
Returns a range of the blockers of the complex.
Definition Skeleton_blocker_complex.h:1508
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::operator[]
const Graph_vertex & operator[](Vertex_handle address) const
Return the vertex node associated to local Vertex_handle.
Definition Skeleton_blocker_complex.h:362
Gudhi::skeleton_blocker::Skeleton_blocker_complex::operator==
bool operator==(const Skeleton_blocker_complex &other) const
Definition Skeleton_blocker_complex.h:278
Gudhi::skeleton_blocker::Skeleton_blocker_complex::Skeleton_blocker_complex
Skeleton_blocker_complex(size_t num_vertices_=0, Visitor *visitor_=NULL)
constructs a simplicial complex with a given number of vertices and a visitor.
Definition Skeleton_blocker_complex.h:153
Gudhi::skeleton_blocker::Skeleton_blocker_complex::add_edge
void add_edge(const Simplex &s)
Adds all edges of s in the complex.
Definition Skeleton_blocker_complex.h:554
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::convert_handle_from_another_complex
Vertex_handle convert_handle_from_another_complex(const Skeleton_blocker_complex &other, Vertex_handle vh_in_other) const
Convert an address of a vertex of a complex to the address in the current complex.
Definition Skeleton_blocker_complex.h:458
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::link
Link_complex link(Edge_handle edge) const
Definition Skeleton_blocker_complex.h:900
Gudhi::skeleton_blocker::Skeleton_blocker_complex< Traits >::Vertex_handle
Traits::Vertex_handle Vertex_handle
Definition Skeleton_blocker_complex.h:77
Gudhi::skeleton_blocker::Skeleton_blocker_complex::is_cone
bool is_cone() const
Test if the complex is a cone.
Definition Skeleton_blocker_complex.h:1040
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::contract_edge
void contract_edge(Vertex_handle a, Vertex_handle b)
Definition Skeleton_blocker_simplifiable_complex.h:340
Gudhi::skeleton_blocker::Skeleton_blocker_complex< Traits >::Graph_edge
Traits::Graph_edge Graph_edge
Definition Skeleton_blocker_complex.h:70
Gudhi::skeleton_blocker::Skeleton_blocker_complex::triangle_range
Complex_triangle_range triangle_range() const
Range over triangles of the simplicial complex. Methods .begin() and .end() return a Triangle_around_...
Definition Skeleton_blocker_complex.h:1372
Gudhi::skeleton_blocker::Skeleton_blocker_complex::get_id
Root_vertex_handle get_id(Vertex_handle local) const
Definition Skeleton_blocker_complex.h:443
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< Traits >::Edge_handle
boost::graph_traits< Graph >::edge_descriptor Edge_handle
Definition Skeleton_blocker_complex.h:114
Gudhi::skeleton_blocker::Skeleton_blocker_complex::complex_simplex_range
Complex_simplex_range complex_simplex_range() const
Returns a Complex_simplex_range over all the simplices of the complex.
Definition Skeleton_blocker_complex.h:1429
Gudhi::skeleton_blocker::Skeleton_blocker_complex::get_simplex_address
boost::optional< Simplex > get_simplex_address(const Root_simplex_handle &s) const
Compute the local vertices of 's' in the current complex If one of them is not present in the complex...
Definition Skeleton_blocker_complex.h:919
Gudhi::skeleton_blocker::Skeleton_blocker_complex< Traits >::Complex_coboundary_range
boost::iterator_range< Complex_simplex_coboundary_iterator > Complex_coboundary_range
Definition Skeleton_blocker_complex.h:1410
Gudhi::skeleton_blocker::Skeleton_blocker_complex::~Skeleton_blocker_complex
virtual ~Skeleton_blocker_complex()
Definition Skeleton_blocker_complex.h:302
Gudhi::skeleton_blocker::Skeleton_blocker_complex::const_blocker_range
Const_complex_blocker_range const_blocker_range() const
Returns a range of the blockers of the complex.
Definition Skeleton_blocker_complex.h:1517
Gudhi::skeleton_blocker::Skeleton_blocker_complex::Skeleton_blocker_complex
Skeleton_blocker_complex(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end, bool is_flag_complex=false, Visitor *visitor_=NULL)
Constructor with a list of simplices.
Definition Skeleton_blocker_complex.h:171
Gudhi::skeleton_blocker::Skeleton_blocker_complex::get_id
Root_simplex_handle get_id(const Simplex &local_simplex) const
returns a simplex with vertices which are the id of vertices of the argument.
Definition Skeleton_blocker_complex.h:940
Gudhi::skeleton_blocker::Skeleton_blocker_complex::vertex_range
Complex_neighbors_vertices_range vertex_range(Vertex_handle v) const
Returns a Complex_edge_range over all edges of the simplicial complex that passes through v.
Definition Skeleton_blocker_complex.h:1296
Gudhi::skeleton_blocker::Skeleton_blocker_complex::operator[]
Graph_vertex & operator[](Vertex_handle address)
Return the vertex node associated to local Vertex_handle.
Definition Skeleton_blocker_complex.h:352
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_link_superior
Class representing the link of a simplicial complex encoded by a skeleton/blockers pair....
Definition Skeleton_blocker_link_superior.h:28
Gudhi::skeleton_blocker::Skeleton_blocker_simplex
Abstract simplex used in Skeleton blockers data-structure.
Definition Skeleton_blocker_simplex.h:38
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::first_vertex
T first_vertex() const
Definition Skeleton_blocker_simplex.h:210
Gudhi::skeleton_blocker::Skeleton_blocker_simplex::intersection
void intersection(const Skeleton_blocker_simplex &a)
Definition Skeleton_blocker_simplex.h:124
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::skeleton_blocker::Triangle_around_vertex_iterator
Iterator over the triangles that are adjacent to a vertex of the simplicial complex.
Definition Skeleton_blockers_triangles_iterators.h:31
Gudhi::skeleton_blocker::Triangle_iterator
Iterator over the triangles of the simplicial complex.
Definition Skeleton_blockers_triangles_iterators.h:106
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14
Gudhi::skeleton_blocker::SkeletonBlockerDS::Graph_edge
The type of edges that are stored the boost graph. An Edge must be Default Constructible and Equality...
Definition SkeletonBlockerDS.h:91
Gudhi::skeleton_blocker::SkeletonBlockerDS::Graph_vertex
The type of vertices that are stored the boost graph. A Vertex must be Default Constructible and Equa...
Definition SkeletonBlockerDS.h:67
Gudhi::skeleton_blocker::SkeletonBlockerDS::Root_vertex_handle
Root_vertex_handle and Vertex_handle are similar to global and local vertex descriptor used in boost ...
Definition SkeletonBlockerDS.h:47
Gudhi::skeleton_blocker::SkeletonBlockerDS::Vertex_handle
Definition SkeletonBlockerDS.h:56