/* Copyright (c) 1997-2006
Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
http://www.math.tu-berlin.de/polymake, mailto:polymake@math.tu-berlin.de
This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version: http://www.gnu.org/licenses/gpl.txt.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
*/
#ifndef _POLYMAKE_COMPLEX_TOOLS_H
#define _POLYMAKE_COMPLEX_TOOLS_H "$Project: polymake $$Id: complex_tools.h 7462 2006-11-13 19:28:29Z witte $"
#include <list>
#include <string>
#include <Array.h>
#include <PowerSet.h>
#include <HasseDiagram.h>
#include <FacetList.h>
/** Tools to treat simplicial complexes.
*
* A simplicial complex is represented as a list of its FACETS, encode as their vertex sets.
* Therefore any container of GenericSet of int (template <typename Complex>) may be used to
* represent a complex. In the following std::list< polymake::Set<int> >, polymake::PowerSet<int>
* and polymake::Array< polymake::Set<int> > are used.
*/
namespace polymake { namespace topaz {
// Computes the k_skeleton of a simplicial complex.
template <typename Complex>
PowerSet<int> k_skeleton(const Complex& C, const int k);
template <typename Complex, typename Set>
struct link_helper {
typedef pm::SelectedContainerPairSubset< const Complex&, pm::masquerade_keep_ref<pm::unlimited_constant_container, const Set&>,
operations::includes >
selected_facets;
typedef pm::SelectedContainerPairSubset< const Complex&, pm::masquerade_keep_ref<pm::unlimited_constant_container, const Set&>,
operations::composed21<operations::includes,operations::logical_not> >
deletion_type;
typedef pm::TransformedContainerPair< selected_facets, pm::masquerade_keep_ref<pm::unlimited_constant_container, const Set&>,
operations::sub >
result_type;
};
// Computes the star of a given face F.
template <typename Complex, typename Set> inline
typename link_helper<Complex,Set>::selected_facets
star(const Complex& C, const GenericSet< Set,int >& F)
{
return typename link_helper<Complex,Set>::selected_facets(C, F.top());
}
// Computes the deletion of a given face F.
template <typename Complex, typename Set> inline
typename link_helper<Complex,Set>::deletion_type
deletion(const Complex& C, const GenericSet< Set,int >& F)
{
return typename link_helper<Complex,Set>::deletion_type(C, F.top());
}
// Computes the link of a given face F.
template <typename Complex, typename Set> inline
typename link_helper<Complex,Set>::result_type
link(const Complex& C, const GenericSet< Set,int >& F)
{
return typename link_helper<Complex,Set>::result_type(star(C,F), F.top());
}
// Computes the star of a face (specified by it's index in the
// HasseDiagram.
FacetList star_in_HD (const HasseDiagram<>& HD, const int f);
// Computes the link of a face (specified by it's index in the
// HasseDiagram.
FacetList link_in_HD (const HasseDiagram<>& HD, const int f);
// Computes the vertex star of a complex represented as a
// Hasse Diagram and a given vertex v.
std::list< Set<int> > vertexStar_of_HD(const HasseDiagram<>& HD, const int v);
// Computes the vertex link of a complex represented as a
// Hasse Diagram and a given vertex v.
std::list< Set<int> > vertexLink_of_HD(const HasseDiagram<>& HD, const int v);
// Computes the vertex set of the link of the vertex v.
Set<int> vert_of_vertexLink(const HasseDiagram<>& HD, const int v);
// Computes the Hasse Diagram of a complex C. The parameter d
// is a lower bound for the dimension of the complex, default is 0.
// The parameter end_dim determines which levels (starting at
// the top) of the Hasse Diagram are computed.
template <typename VertexSet, typename Complex>
HasseDiagram<VertexSet> hasse_diagram(const Complex& C, const int d=0, const int end_dim=0);
template <typename Complex> inline
HasseDiagram<> hasse_diagram(const Complex& C, const int d=0, const int end_dim=0) {
return hasse_diagram< Set<int> >(C,d,end_dim);
}
// Computes the Hasse Diagram of a PURE complex C.
// The parameter end_dim determines which levels (starting at
// the top) of the Hasse Diagram are computed.
template <typename VertexSet, typename Complex>
HasseDiagram<VertexSet> pure_hasse_diagram(const Complex& C, const int end_dim=0);
template <typename Complex> inline
HasseDiagram<> pure_hasse_diagram(const Complex& C, const int end_dim=0) {
return pure_hasse_diagram< Set<int> >(C,end_dim);
}
class out_degree_checker {
public:
typedef void argument_type;
typedef bool result_type;
out_degree_checker(int degree_arg=0) : degree(degree_arg) { }
template <typename Iterator>
result_type operator() (const Iterator& node_it) const
{
return node_it.out_degree()==degree;
}
protected:
int degree;
};
// Computes the boundary complex (= ridges contained in one facet only)
// of a PSEUDO_MANIFOLD. The complex is encoded as a Hasse Diagrams.
typedef pm::SelectedSubset< pm::IndexedSubset<HasseDiagram<>::const_node_container_ref, sequence>, out_degree_checker>
Boundary_of_PseudoManifold;
inline
Boundary_of_PseudoManifold boundary_of_pseudo_manifold (const HasseDiagram<>& PM)
{
return Boundary_of_PseudoManifold( pm::IndexedSubset<HasseDiagram<>::const_node_container_ref, sequence>(nodes(PM), PM.nodes_of_dim(-2)),
out_degree_checker(1) );
}
// Removes the vertex star of v from a complex C, represented as a Hasse Diagram.
void remove_vertex_star(HasseDiagram<>& HD, const int v);
// Removes a facet F from a simplicial complex, represented as a Hasse Diagram.
template <typename VertexSet, typename Set>
void remove_facet (HasseDiagram<VertexSet>& HD, const GenericSet< Set,int >& F);
// Checks whether a 1-complex (graph) is a 1-ball or 1-sphere.
template <typename Complex>
bool C1_is_BOS (const Complex& C);
// Checks whether a 1-complex (graph) is a manifold.
template <typename Complex>
bool C1_is_manifold (const Complex& C);
// Checks whether a 2-complex is a 2-ball or 2-sphere.
template <typename Complex>
bool C2_is_BOS (const Complex& C);
// Checks whether a 2-complex is a manifold.
template <typename Complex>
bool C2_is_manifold (const Complex& C);
// Checks whether a 3-complex is a manifold.
template <typename Complex>
bool C3_is_manifold (std::ostream& os, const Complex& C, const bool quiet=false);
template <typename Complex>
bool C3_is_manifold (const Complex& C) {
return C3_is_manifold(std::cout,C);
}
/// Adjusts the vertex numbers to 0..n-1.
/// @retval true if the numbering has been adjusted
template <typename Complex, typename Set>
bool adj_numbering (Complex& C, const Set& V);
// Checks whether a complex, represented as a Hasse Diagram, is a closed pseudo manifold.
bool is_closed_pseudo_manifold (const HasseDiagram<>& HD);
// Checks whether a complex, represented as a Hasse Diagram, is a pseudo manifold
// and computes its boundary.
template <typename VertexSet, typename OutputIterator>
bool is_pseudo_manifold (const HasseDiagram<VertexSet>& HD, OutputIterator boundary_consumer, const bool verbose=false);
// Checks whether a complex, represented as a Hasse Diagram, is a pseudo manifold.
template <typename VertexSet> inline
bool is_pseudo_manifold (const HasseDiagram<VertexSet>& HD, const bool verbose)
{
return is_pseudo_manifold (HD, black_hole< Set<int> >(), verbose);
}
// The torus.
Array< Set<int> > torus();
// The projective plane.
Array< Set<int> > projective_plane();
} }
#include <complex_tools.tcc>
#include <subcomplex_tools.tcc>
#include <1D_tools.tcc>
#include <2D_tools.tcc>
#include <3D_tools.tcc>
#endif // _POLYMAKE_COMPLEX_TOOLS_H
// Local Variables:
// mode:C++
// c-basic-offset:3
// End:
syntax highlighted by Code2HTML, v. 0.9.1