Regina Calculation Engine
Classes | Typedefs
Vertex Enumeration

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

Detailed Description

Polytope vertex enumeration algorithms.

Typedef Documentation

◆ EnumConstraints

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.

Python
Not present.

◆ NDoubleDescription

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NDoubleDescription has now been renamed to DoubleDescription.

◆ NEnumConstraintList

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NEnumConstraintList has now been renamed to EnumConstraints.

◆ NHilbertCD

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NHilbertCD has now been renamed to HilbertCD.

◆ NHilbertDual

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NHilbertDual has now been renamed to HilbertDual.

◆ NHilbertPrimal

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NHilbertPrimal has now been renamed to HilbertPrimal.

◆ NPosOrder

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NPosOrder has now been renamed to PosOrder.

◆ NTautEnumeration

template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer>
using regina::NTautEnumeration = typedef TautEnumeration<LPConstraint, BanConstraint, IntType>

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NTautEnumeration has now been renamed to TautEnumeration.

◆ NTreeEnumeration

template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer>
using regina::NTreeEnumeration = typedef TreeEnumeration<LPConstraint, BanConstraint, IntType>

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NTreeEnumeration has now been renamed to TreeEnumeration.

◆ NTreeSingleSoln

template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer>
using regina::NTreeSingleSoln = typedef TreeSingleSoln<LPConstraint, BanConstraint, IntType>

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NTreeSingleSoln has now been renamed to TreeSingleSoln.

◆ NTreeTraversal

template<class LPConstraint , typename BanConstraint , typename IntType >
using regina::NTreeTraversal = typedef TreeTraversal<LPConstraint, BanConstraint, IntType>

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NTreeTraversal has now been renamed to TreeTraversal.

◆ NTypeTrie

template<int nTypes>
using regina::NTypeTrie = typedef TypeTrie<nTypes>

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NTypeTrie has now been renamed to TypeTrie.

Copyright © 1999-2021, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).