Regina Calculation Engine
|
Polytope vertex enumeration algorithms. More...
Classes | |
class | regina::DoubleDescription |
Implements a modified double description method for polytope vertex enumeration. More... | |
class | regina::HilbertCD |
Implements a modified Contejean-Devie algorithm for enumerating Hilbert bases. More... | |
class | regina::HilbertDual |
Implements a modified dual algorithm for enumerating Hilbert bases. More... | |
class | regina::HilbertPrimal |
Implements a modified primal algorithm for enumerating Hilbert bases. More... | |
class | regina::MaxAdmissible |
Used to enumerate all maximal admissible faces of a polyhedral cone under a given set of admissibility constraints. More... | |
class | regina::PosOrder |
A comparison object that sorts hyperplanes by position vectors. More... | |
class | regina::LPConstraintBase |
A base class for additional linear constraints that we can add to the tableaux of normal surface or angle structure matching equations. More... | |
class | regina::LPConstraintSubspace |
A subclass of LPConstraintBase used for constraints defined entirely by homogeneous linear equations. More... | |
class | regina::LPConstraintNone |
A do-nothing class that imposes no additional linear constraints on the tableaux of normal surface or angle structure matching equations. More... | |
class | regina::LPConstraintEuler |
A class that constraints the tableaux of normal surface matching equations to ensure that Euler characteristic is strictly positive. More... | |
class | regina::LPConstraintNonSpun |
A class that constraints the tableaux of normal surface matching equations to ensure that normal surfaces in an ideal triangulation are compact (thereby avoiding spun normal surfaces with infinitely many triangles). More... | |
class | regina::BanConstraintBase |
A base class for additional banning and marking constraints that we can place on tree traversal algorithms. More... | |
class | regina::BanNone |
A do-nothing class that bans no coordinates and marks no coordinates. More... | |
class | regina::BanBoundary |
A class that bans normal disc types that meet the boundary of the underlying triangulation. More... | |
class | regina::BanTorusBoundary |
A class that bans and marks disc types associated with torus boundary components. More... | |
class | regina::LPMatrix< IntType > |
A matrix class for use with linear programming. More... | |
struct | regina::LPCol< LPConstraint > |
Used by LPInitialTableaux<LPConstraint> to store a single column of the adjusted matching equation matrix in sparse form. More... | |
class | regina::LPInitialTableaux< LPConstraint > |
Stores an adjusted matrix of homogeneous linear matching equations based on a given triangulation, in sparse form. More... | |
class | regina::LPData< LPConstraint, IntType > |
Stores an intermediate tableaux for the dual simplex method, and contains all of the core machinery for using the dual simplex method. More... | |
class | regina::TreeTraversal< LPConstraint, BanConstraint, IntType > |
A base class for searches that employ the tree traversal algorithm for enumerating and locating vertex normal surfaces and taut angle structures. More... | |
class | regina::TreeEnumeration< LPConstraint, BanConstraint, IntType > |
The main entry point for the tree traversal algorithm to enumerate all vertex normal or almost normal surfaces in a 3-manifold triangulation. More... | |
class | regina::TautEnumeration< LPConstraint, BanConstraint, IntType > |
The main entry point for the tree traversal algorithm to enumerate all taut angle structures in a 3-manifold triangulation. More... | |
class | regina::TreeSingleSoln< LPConstraint, BanConstraint, IntType > |
The main entry point for the tree traversal / branching algorithm to locate a single non-trivial normal surface satisfying given constraints within a 3-manifold triangulation. More... | |
class | regina::TypeTrie< nTypes > |
A trie that stores a set of type vectors of a fixed length. More... | |
Typedefs | |
typedef DoubleDescription | regina::NDoubleDescription |
Deprecated typedef for backward compatibility. More... | |
typedef std::vector< std::set< unsigned long > > | regina::EnumConstraints |
Represents an individual validity constraint for use with polytope vertex enumeration. More... | |
typedef EnumConstraints | regina::NEnumConstraintList |
Deprecated typedef for backward compatibility. More... | |
typedef HilbertCD | regina::NHilbertCD |
Deprecated typedef for backward compatibility. More... | |
typedef HilbertDual | regina::NHilbertDual |
Deprecated typedef for backward compatibility. More... | |
typedef HilbertPrimal | regina::NHilbertPrimal |
Deprecated typedef for backward compatibility. More... | |
typedef PosOrder | regina::NPosOrder |
Deprecated typedef for backward compatibility. More... | |
template<class LPConstraint , typename BanConstraint , typename IntType > | |
using | regina::NTreeTraversal = TreeTraversal< LPConstraint, BanConstraint, IntType > |
Deprecated typedef for backward compatibility. More... | |
template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer> | |
using | regina::NTreeEnumeration = TreeEnumeration< LPConstraint, BanConstraint, IntType > |
Deprecated typedef for backward compatibility. More... | |
template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer> | |
using | regina::NTautEnumeration = TautEnumeration< LPConstraint, BanConstraint, IntType > |
Deprecated typedef for backward compatibility. More... | |
template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer> | |
using | regina::NTreeSingleSoln = TreeSingleSoln< LPConstraint, BanConstraint, IntType > |
Deprecated typedef for backward compatibility. More... | |
template<int nTypes> | |
using | regina::NTypeTrie = TypeTrie< nTypes > |
Deprecated typedef for backward compatibility. More... | |
Polytope vertex enumeration algorithms.
typedef std::vector<std::set<unsigned long> > regina::EnumConstraints |
Represents an individual validity constraint for use with polytope vertex enumeration.
Vertex enumeration routines such as DoubleDescription::enumerateExtremalRays() take a cone (specifically the non-negative orthant), form the intersection of that cone with a given linear subspace, and return the extremal rays of the new cone that results.
In some cases we are only interested in valid rays of the new cone. The EnumConstraints class stores a number of "validity constraints"; a ray is then "valid" if it satisfies all of these constraints.
Each individual constraint is presented as a set of integers; the meaning of such a constraint is as follows. We number the facets of the original cone 0,1,2,... (where the ith facet is the plane perpendicular to the ith coordinate axis). If a constraint is described by the integers x, y, z, ..., then it indicates that a ray can only lie outside at most one of the facets numbered x, y, z, ... .
In practice, this allows us to represent constraints in normal surface theory. For instance, to insist that some tetrahedron contains at most one quadrilateral disc type, we add a constraint with three integers, representing the original facets q1=0, q2=0, q3=0 (where q1, q2 and q3 are the three quadrilateral coordinates for that tetrahedron).
The EnumConstraints class is simply a std::vector of constraints, where each constraint is a std::set of unsigned integers. Typically one will create a vector containing the desired number of constraints and then walk through each constraint, filling the sets as appropriate.
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
typedef HilbertCD regina::NHilbertCD |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
typedef HilbertDual regina::NHilbertDual |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
typedef HilbertPrimal regina::NHilbertPrimal |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
typedef PosOrder regina::NPosOrder |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
using regina::NTautEnumeration = typedef TautEnumeration<LPConstraint, BanConstraint, IntType> |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
using regina::NTreeEnumeration = typedef TreeEnumeration<LPConstraint, BanConstraint, IntType> |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
using regina::NTreeSingleSoln = typedef TreeSingleSoln<LPConstraint, BanConstraint, IntType> |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
using regina::NTreeTraversal = typedef TreeTraversal<LPConstraint, BanConstraint, IntType> |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
using regina::NTypeTrie = typedef TypeTrie<nTypes> |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.