Abstract Simplicial Complex represented with a skeleton/blockers pair. More...

#include <Skeleton_blocker_complex.h>

Public Types
typedef SkeletonBlockerDS::Graph_vertex	Graph_vertex
	The type of stored vertex node, specified by the template SkeletonBlockerDS.

typedef SkeletonBlockerDS::Graph_edge	Graph_edge
	The type of stored edge node, specified by the template SkeletonBlockerDS.

typedef SkeletonBlockerDS::Vertex_handle	Vertex_handle
	The type of an handle to a vertex of the complex.

typedef Skeleton_blocker_simplex < Vertex_handle >	Simplex_handle
	A ordered set of integers that represents a simplex.

typedef Simplex_handle *	Blocker_handle
	Handle to a blocker of the complex.

typedef boost::graph_traits < Graph >::edge_descriptor	Edge_handle
	Handle to an edge of the complex.

Public Member Functions
Link_complex	link (Vertex_handle v) const

Link_complex	link (Edge_handle edge) const

Link_complex	link (const Simplex_handle &simplex) const

boost::optional< Simplex_handle >	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 then the return value is uninitialized.

Root_simplex_handle	get_id (const Simplex_handle &local_simplex) const
	returns a simplex with vertices which are the id of vertices of the argument.

virtual bool	contains (const Simplex_handle &s) const
	returns true iff the simplex s belongs to the simplicial complex.

int	num_connected_components () const
	returns the number of connected components in the graph of the 1-skeleton.

bool	is_cone () const
	Test if the complex is a cone. More...

Vertices operations
Vertex_handle	operator[] (Root_vertex_handle global) const
	Return a local Vertex_handle of a vertex given a global one. More...

Graph_vertex &	operator[] (Vertex_handle address)
	Return the vertex node associated to local Vertex_handle. More...

const Graph_vertex &	operator[] (Vertex_handle address) const
	Return the vertex node associated to local Vertex_handle. More...

Vertex_handle	add_vertex ()
	Adds a vertex to the simplicial complex and returns its Vertex_handle.

void	remove_vertex (Vertex_handle address)
	Remove a vertex from the simplicial complex. More...

bool	contains_vertex (Vertex_handle u) const

bool	contains_vertex (Root_vertex_handle u) const

bool	contains_vertices (const Simplex_handle &sigma) const

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. More...

Root_vertex_handle	get_id (Vertex_handle local) const

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. More...

int	degree (Vertex_handle local) const
	return the graph degree of a vertex.

Edges operations
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

Graph_edge &	operator[] (Edge_handle edge_handle)
	returns the stored node associated to an edge

const Graph_edge &	operator[] (Edge_handle edge_handle) const
	returns the stored node associated to an edge

Vertex_handle	first_vertex (Edge_handle edge_handle) const
	returns the first vertex of an edge More...

Vertex_handle	second_vertex (Edge_handle edge_handle) const
	returns the first vertex of an edge More...

Simplex_handle	get_vertices (Edge_handle edge_handle) const
	returns the simplex made with the two vertices of the edge More...

Edge_handle	add_edge (Vertex_handle a, Vertex_handle b)
	Adds an edge between vertices a and b and all its cofaces.

void	add_edges (const Simplex_handle &sigma)
	Adds all edges and their cofaces of a simplex to the simplicial complex.

virtual Edge_handle	remove_edge (Vertex_handle a, Vertex_handle b)
	Removes an edge from the simplicial complex and all its cofaces. More...

void	remove_edge (Edge_handle edge)
	Removes edge and its cofaces from the simplicial complex.

void	keep_only_vertices ()
	The complex is reduced to its set of vertices. All the edges and blockers are removed.

bool	contains_edge (Vertex_handle a, Vertex_handle b) const

bool	contains_edges (const Simplex_handle &sigma) const

Print and IO methods
std::string	to_string () const

std::string	vertices_to_string () const

std::string	edges_to_string () const

std::string	blockers_to_string () const

Constructors, Destructors
	Skeleton_blocker_complex (int num_vertices_=0, Visitor *visitor_=NULL)
	constructs a simplicial complex with a given number of vertices and a visitor.

template<typename SimpleHandleOutputIterator >
	Skeleton_blocker_complex (SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end, bool is_flag_complex=false, Visitor *visitor_=NULL)
	Constructor with a list of simplices. More...

	Skeleton_blocker_complex (const Skeleton_blocker_complex &copy)

Skeleton_blocker_complex &	operator= (const Skeleton_blocker_complex &copy)

bool	operator== (const Skeleton_blocker_complex &other) const

bool	operator!= (const Skeleton_blocker_complex &other) const

virtual	~Skeleton_blocker_complex ()

virtual void	clear ()

void	set_visitor (Visitor *other_visitor)
	allows to change the visitor.

Blockers operations
Blocker_handle	add_blocker (const Simplex_handle &blocker)
	Adds the simplex to the set of blockers and returns a Blocker_handle toward it if was not present before and 0 otherwise.

void	remove_blocker (const Blocker_handle sigma)
	Removes the simplex from the set of blockers. More...

void	remove_blockers ()
	Remove all blockers, in other words, it expand the simplicial complex to the smallest flag complex that contains it.

void	delete_blocker (Blocker_handle sigma)

bool	contains_blocker (const Blocker_handle s) const

bool	contains_blocker (const Simplex_handle &s) const

Simplification operations
enum	simplifiable_status

enum	contractible_status

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)
	Removes all the popable blockers of the complex passing through v and delete them. Also remove popable blockers in the neighborhood if they became popable.

void	remove_star (Vertex_handle v)

void	remove_star (Vertex_handle a, Vertex_handle b)

void	remove_star (Edge_handle e)

void	remove_star (const Simplex_handle &sigma)

void	add_simplex (const Simplex_handle &sigma)
	add a maximal simplex plus all its cofaces. More...

simplifiable_status	is_remove_star_homotopy_preserving (const Simplex_handle &simplex)

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 complex is a cone) More...

Edge contraction operations
bool	link_condition (Vertex_handle a, Vertex_handle b, bool ignore_popable_blockers=false) const

bool	link_condition (Edge_handle e, bool ignore_popable_blockers=false) const

void	contract_edge (Edge_handle edge)

void	contract_edge (Vertex_handle a, Vertex_handle b)

Vertex iterators
typedef Vertex_iterator < Skeleton_blocker_complex >	Complex_vertex_iterator

typedef boost::iterator_range < Complex_vertex_iterator >	Complex_vertex_range

typedef Neighbors_vertices_iterator < Skeleton_blocker_complex >	Complex_neighbors_vertices_iterator

typedef boost::iterator_range < Complex_neighbors_vertices_iterator >	Complex_neighbors_vertices_range

Complex_vertex_range	vertex_range () const
	Returns a Complex_vertex_range over all vertices of the complex.

Complex_neighbors_vertices_range	vertex_range (Vertex_handle v) const
	Returns a Complex_edge_range over all edges of the simplicial complex that passes trough v.

Edge iterators
typedef Edge_iterator < Skeleton_blocker_complex >	Complex_edge_iterator

typedef boost::iterator_range < Complex_edge_iterator >	Complex_edge_range

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_range	edge_range () const
	Returns a Complex_edge_range over all edges of the simplicial complex.

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'.

Triangles iterators
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

typedef boost::iterator_range < Triangle_iterator < Skeleton_blocker_complex > >	Complex_triangle_range

typedef Triangle_iterator < Skeleton_blocker_complex >	Complex_triangle_iterator

Complex_triangle_around_vertex_range	triangle_range (Vertex_handle v) const
	Range over triangles around a vertex of the simplicial complex. Methods .begin() and .end() return a Triangle_around_vertex_iterator.

Complex_triangle_range	triangle_range () const
	Range over triangles of the simplicial complex. Methods .begin() and .end() return a Triangle_around_vertex_iterator.

Simplices iterators
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
	Range over the simplices of the simplicial complex around a vertex. Methods .begin() and .end() return a Complex_simplex_around_vertex_iterator.

typedef Simplex_iterator < Skeleton_blocker_complex >	Complex_simplex_iterator

typedef boost::iterator_range < Complex_simplex_iterator >	Complex_simplex_range

Complex_simplex_around_vertex_range	simplex_range (Vertex_handle v) const
	Returns a Complex_simplex_around_vertex_range over all the simplices around a vertex of the complex.

Complex_simplex_range	simplex_range () const
	Returns a Complex_simplex_range over all the simplices of the complex.

Blockers iterators
Complex_blocker_around_vertex_range	blocker_range (Vertex_handle v)
	Returns a range of the blockers of the complex passing through a vertex.

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.

Complex_blocker_range	blocker_range ()
	Returns a range of the blockers of the complex.

Const_complex_blocker_range	const_blocker_range () const
	Returns a range of the blockers of the complex.

Detailed Description

template<class SkeletonBlockerDS>
class Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >

Abstract Simplicial Complex represented with a skeleton/blockers pair.

Constructor & Destructor Documentation

template<class SkeletonBlockerDS>

template<typename SimpleHandleOutputIterator >

Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::Skeleton_blocker_complex	(	SimpleHandleOutputIterator	simplex_begin,
		SimpleHandleOutputIterator	simplex_end,
		bool	is_flag_complex = `false`,
		Visitor *	visitor_ = `NULL`
	)

inline

Constructor with a list of simplices.

is_flag_complex indicates if the complex is a flag complex or not (to know if blockers have to be computed or not).

template<class SkeletonBlockerDS>

virtual Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::~Skeleton_blocker_complex ( )

inlinevirtual

The destructor delete all blockers allocated.

Member Function Documentation

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::add_simplex ( const Simplex_handle & sigma )

add a maximal simplex plus all its cofaces.

add a maximal simplex plus all its cofaces. All vertices lower than the higher vertex of sigma must already be present.

the simplex must have dimension greater than one (otherwise use add_vertex or add_edge).

template<class SkeletonBlockerDS>

virtual void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::clear ( )

inlinevirtual

Clears the simplicial complex. After a call to this function, blockers are destroyed. The 1-skeleton and the set of blockers are both empty.

Reimplemented in Gudhi::skbl::Skeleton_blocker_sub_complex< ComplexType >.

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::contains_blocker ( const Blocker_handle s ) const

inline

Returns: true iff s is a blocker of the simplicial complex

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::contains_blocker ( const Simplex_handle & s ) const

inline

Returns: true iff s is a blocker of the simplicial complex

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::contains_edge	(	Vertex_handle	a,
		Vertex_handle	b
	)		const

inline

Returns: true iff the simplicial complex contains an edge between vertices a and b

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::contains_edges ( const Simplex_handle & sigma ) const

inline

Returns: true iff the simplicial complex contains all vertices and all edges of simplex sigma

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::contains_vertices ( const Simplex_handle & sigma ) const

inline

Returns: true iff the simplicial complex contains all vertices of simplex sigma

template<class SkeletonBlockerDS>

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::contract_edge ( Edge_handle edge )

inline

Contracts the edge.

Remarks: If the link condition Link(ab) = Link(a) inter Link(b) is not satisfied, it removes first all blockers passing through 'ab'

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::contract_edge	(	Vertex_handle	a,
		Vertex_handle	b
	)

Contracts the edge connecting vertices a and b.

Remarks: If the link condition Link(ab) = Link(a) inter Link(b) is not satisfied, it removes first all blockers passing through 'ab'

template<class SkeletonBlockerDS>

Vertex_handle Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::convert_handle_from_another_complex	(	const Skeleton_blocker_complex< SkeletonBlockerDS > &	other,
		Vertex_handle	vh_in_other
	)		const

inline

Convert an address of a vertex of a complex to the address in the current complex.

If the current complex is a sub (or sup) complex of 'other', it converts the address of a vertex v expressed in 'other' to the address of the vertex v in the current one.

Remarks: this methods uses Root_vertex_handle to identify the vertex and assumes the vertex is present in the current complex.

template<class SkeletonBlockerDS>

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::delete_blocker ( Blocker_handle sigma )

inline

Removes the simplex s from the set of blockers and desallocate s.

template<class SkeletonBlockerDS>

Vertex_handle Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::first_vertex ( Edge_handle edge_handle ) const

inline

returns the first vertex of an edge

it assumes that the edge is present in the complex

template<class SkeletonBlockerDS>

virtual boost::optional<Vertex_handle> Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::get_address ( Root_vertex_handle id ) const

inlinevirtual

Given an Id return the address of the vertex having this Id in the complex.

Remarks: For a simplicial complex, the address is the id but it may not be the case for a SubComplex.

template<class SkeletonBlockerDS>

Root_vertex_handle Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::get_id ( Vertex_handle local ) const

inline

return the id of a vertex of adress local present in the graph

template<class SkeletonBlockerDS>

Simplex_handle Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::get_vertices ( Edge_handle edge_handle ) const

inline

returns the simplex made with the two vertices of the edge

it assumes that the edge is present in the complex

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::is_cone ( ) const

inline

Test if the complex is a cone.

Runs in O(n) where n is the number of vertices.

template<class SkeletonBlockerDS>

virtual contractible_status Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::is_contractible ( ) const

inlinevirtual

Test if the complex is reducible using a strategy defined in the class (by default it tests if the complex is a cone)

Note that NO could be returned if some invariant ensures that the complex is not a point (for instance if the euler characteristic is different from 1). This function will surely have to return MAYBE in some case because the associated problem is undecidable but it in practice, it can often be solved with the help of geometry.

template<typename SkeletonBlockerDS >

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::is_popable_blocker ( Blocker_handle sigma ) const

Returns true iff the blocker 'sigma' is popable. To define popable, let us call 'L' the complex that consists in the current complex without the blocker 'sigma'. A blocker 'sigma' is then "popable" if the link of 'sigma' in L is reducible.

template<class SkeletonBlockerDS>

Link_complex Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::link ( Vertex_handle v ) const

inline

Constructs the link of 'simplex' with points coordinates.

template<class SkeletonBlockerDS>

Link_complex Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::link ( Edge_handle edge ) const

inline

Constructs the link of 'simplex' with points coordinates.

template<class SkeletonBlockerDS>

Link_complex Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::link ( const Simplex_handle & simplex ) const

inline

Constructs the link of 'simplex' with points coordinates.

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::link_condition	(	Vertex_handle	a,
		Vertex_handle	b,
		bool	ignore_popable_blockers = `false`
	)		const

inline

Returns: If ignore_popable_blockers is true then the result is true iff the link condition at edge ab is satisfied or equivalently iff no blocker contains ab. If ignore_popable_blockers is false then the result is true iff all blocker containing ab are popable.

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::link_condition	(	Edge_handle	e,
		bool	ignore_popable_blockers = `false`
	)		const

inline

Returns: If ignore_popable_blockers is true then the result is true iff the link condition at edge ab is satisfied or equivalently iff no blocker contains ab. If ignore_popable_blockers is false then the result is true iff all blocker containing ab are popable.

template<class SkeletonBlockerDS>

bool Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::operator== ( const Skeleton_blocker_complex< SkeletonBlockerDS > & other ) const

inline

return true if both complexes have the same simplices.

template<class SkeletonBlockerDS>

Vertex_handle Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::operator[] ( Root_vertex_handle global ) const

inline

Return a local Vertex_handle of a vertex given a global one.

Remarks: Assume that the vertex is present in the complex.

template<class SkeletonBlockerDS>

Graph_vertex& Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::operator[] ( Vertex_handle address )

inline

Return the vertex node associated to local Vertex_handle.

Remarks: Assume that the vertex is present in the complex.

template<class SkeletonBlockerDS>

const Graph_vertex& Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::operator[] ( Vertex_handle address ) const

inline

Return the vertex node associated to local Vertex_handle.

Remarks: Assume that the vertex is present in the complex.

template<class SkeletonBlockerDS>

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_blocker ( const Blocker_handle sigma )

inline

Removes the simplex from the set of blockers.

Remarks: sigma has to belongs to the set of blockers

template<class SkeletonBlockerDS>

virtual Edge_handle Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_edge	(	Vertex_handle	a,
		Vertex_handle	b
	)

inlinevirtual

Removes an edge from the simplicial complex and all its cofaces.

returns the former Edge_handle representing the edge

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_popable_blockers ( )

Removes all the popable blockers of the complex and delete them.

Returns: the number of popable blockers deleted

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_popable_blockers ( Vertex_handle v )

Removes all the popable blockers of the complex passing through v and delete them.

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_star ( Vertex_handle v )

Remove the star of the vertex 'v'

Remove the star of the vertice 'v'

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_star	(	Vertex_handle	a,
		Vertex_handle	b
	)

Remove the star of the edge connecting vertices a and b.

Returns: the number of blocker that have been removed

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_star ( Edge_handle e )

Remove the star of the edge 'e'.

template<typename SkeletonBlockerDS >

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_star ( const Simplex_handle & sigma )

Remove the star of the simplex 'sigma' which needs to belong to the complex

template<class SkeletonBlockerDS>

void Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::remove_vertex ( Vertex_handle address )

inline

Remove a vertex from the simplicial complex.

Remarks: It just deactivates the vertex with a boolean flag but does not remove it from vertices from complexity issues.

template<class SkeletonBlockerDS>

Vertex_handle Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >::second_vertex ( Edge_handle edge_handle ) const

inline

returns the first vertex of an edge

it assumes that the edge is present in the complex

The documentation for this class was generated from the following files:

include/gudhi/Skeleton_blocker_complex.h
include/gudhi/Skeleton_blocker_simplifiable_complex.h

Public Types

Public Member Functions

Constructors, Destructors

Blockers operations

Simplification operations

Edge contraction operations

Vertex iterators

Edge iterators

Triangles iterators

Simplices iterators

Blockers iterators

Detailed Description

template<class SkeletonBlockerDS> class Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >

Constructor & Destructor Documentation

Member Function Documentation

template<class SkeletonBlockerDS>
class Gudhi::skbl::Skeleton_blocker_complex< SkeletonBlockerDS >