|
class | regina::NDoubleDescription |
| Implements a modified double description method for polytope vertex enumeration. More...
|
|
class | regina::NEnumConstraintList |
| Represents an individual validity constraint for use with polytope vertex enumeration. More...
|
|
class | regina::NHilbertCD |
| Implements a modified Contejean-Devie algorithm for enumerating Hilbert bases. More...
|
|
class | regina::NHilbertDual |
| Implements a modified dual algorithm for enumerating Hilbert bases. More...
|
|
class | regina::NHilbertPrimal |
| Implements a modified primal algorithm for enumerating Hilbert bases. More...
|
|
class | regina::NMaxAdmissible |
| Used to enumerate all maximal admissible faces of a polyhedral cone under a given set of admissibility constraints. More...
|
|
struct | regina::LPConstraintBase::Coefficients |
| Stores the extra coefficients in a single column for the nConstraints additional rows that we add to the tableaux to describe the nConstraints additional linear equations or inequalities. 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...
|
|
struct | regina::LPConstraintNone::Coefficients |
| Stores the extra coefficients in the tableaux associated with this constraint class (which for this class is a no-op, since in this case there are no extra coefficients). 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...
|
|
struct | regina::LPConstraintEuler::Coefficients |
| Stores the extra coefficients in the tableaux associated with this constraint class (in this case, one extra integer per column). More...
|
|
class | regina::LPConstraintEuler |
| A class that constraints the tableaux of normal surface matching equations to ensure that Euler characteristic is strictly positive. More...
|
|
struct | regina::LPConstraintNonSpun::Coefficients |
| Stores the extra coefficients in the tableaux associated with this constraint class (in this case, two extra integers per column). 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< Integer > |
| 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, Integer > |
| 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::NTreeTraversal< LPConstraint, BanConstraint, Integer > |
| 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::NTreeEnumeration< LPConstraint, BanConstraint, Integer > |
| 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::NTautEnumeration< LPConstraint, BanConstraint, Integer > |
| The main entry point for the tree traversal algorithm to enumerate all taut angle structures in a 3-manifold triangulation. More...
|
|
class | regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer > |
| 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::NTypeTrie< nTypes > |
| A trie that stores a set of type vectors of a fixed length. More...
|
|
class | regina::NPosOrder |
| A comparison object that sorts hyperplanes by position vectors. More...
|
|
|
| regina::LPConstraintBase::Coefficients::Coefficients () |
| Creates an uninitialised set of coefficients for a single column. More...
|
|
template<typename Integer > |
void | regina::LPConstraintBase::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const |
| Explicitly fills the final row(s) of the given tableaux matrix with the coefficients stored in this Coefficients structure. More...
|
|
template<typename Integer > |
Integer | regina::LPConstraintBase::Coefficients::innerProduct (const LPMatrix< Integer > &m, unsigned mRow) const |
| Computes the inner product of (i) the final nConstraints entries in the given row of the given matrix with (ii) the nConstraints column coefficients stored in this data structure. More...
|
|
template<typename Integer > |
Integer | regina::LPConstraintBase::Coefficients::innerProductOct (const LPMatrix< Integer > &m, unsigned mRow) const |
| A variant of innerProduct() that takes into account any adjustments to these linear constraint(s) that are required when this is a quadrilateral column being used to represent an octagon type. More...
|
|
static bool | regina::LPConstraintBase::addRows (LPCol< LPConstraintBase > *col, const int *columnPerm, const NTriangulation *tri) |
| Explicitly constructs equations for the linear function(s) constrained by this class. More...
|
|
template<typename Integer > |
static void | regina::LPConstraintBase::constrain (LPData< LPConstraintNone, Integer > &lp, unsigned numCols) |
| Explicitly constraints each of these linear functions to an equality or inequality in the underlying tableaux. More...
|
|
static bool | regina::LPConstraintBase::verify (const NNormalSurface *s) |
| Ensures that the given normal surface satisfies the extra constraints described by this class. More...
|
|
static bool | regina::LPConstraintBase::verify (const NAngleStructure *s) |
| Ensures that the given angle structure satisfies the extra constraints described by this class. More...
|
|
static bool | regina::LPConstraintBase::supported (NormalCoords coords) |
| Indicates whether the given coordinate system is supported by this constraint class. More...
|
|
template<typename Integer > |
void | regina::LPConstraintNone::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const |
|
template<typename Integer > |
Integer | regina::LPConstraintNone::Coefficients::innerProduct (const LPMatrix< Integer > &, unsigned) const |
|
template<typename Integer > |
Integer | regina::LPConstraintNone::Coefficients::innerProductOct (const LPMatrix< Integer > &, unsigned) const |
|
static bool | regina::LPConstraintNone::addRows (LPCol< regina::LPConstraintNone > *, const int *, const NTriangulation *) |
|
template<typename Integer > |
static void | regina::LPConstraintNone::constrain (LPData< regina::LPConstraintNone, Integer > &, unsigned) |
|
static bool | regina::LPConstraintNone::verify (const NNormalSurface *) |
|
static bool | regina::LPConstraintNone::verify (const NAngleStructure *) |
|
static bool | regina::LPConstraintNone::supported (NormalCoords coords) |
|
template<typename Integer > |
void | regina::LPConstraintEuler::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const |
|
template<typename Integer > |
Integer | regina::LPConstraintEuler::Coefficients::innerProduct (const LPMatrix< Integer > &m, unsigned mRow) const |
|
template<typename Integer > |
Integer | regina::LPConstraintEuler::Coefficients::innerProductOct (const LPMatrix< Integer > &m, unsigned mRow) const |
|
static bool | regina::LPConstraintEuler::addRows (LPCol< regina::LPConstraintEuler > *col, const int *columnPerm, const NTriangulation *tri) |
|
template<typename Integer > |
static void | regina::LPConstraintEuler::constrain (LPData< regina::LPConstraintEuler, Integer > &lp, unsigned numCols) |
|
static bool | regina::LPConstraintEuler::verify (const NNormalSurface *s) |
|
static bool | regina::LPConstraintEuler::verify (const NAngleStructure *) |
|
static bool | regina::LPConstraintEuler::supported (NormalCoords coords) |
|
template<typename Integer > |
void | regina::LPConstraintNonSpun::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const |
|
template<typename Integer > |
Integer | regina::LPConstraintNonSpun::Coefficients::innerProduct (const LPMatrix< Integer > &m, unsigned mRow) const |
|
template<typename Integer > |
Integer | regina::LPConstraintNonSpun::Coefficients::innerProductOct (const LPMatrix< Integer > &m, unsigned mRow) const |
|
static bool | regina::LPConstraintNonSpun::addRows (LPCol< regina::LPConstraintNonSpun > *col, const int *columnPerm, const NTriangulation *tri) |
|
template<typename Integer > |
static void | regina::LPConstraintNonSpun::constrain (LPData< regina::LPConstraintNonSpun, Integer > &lp, unsigned numCols) |
|
static bool | regina::LPConstraintNonSpun::verify (const NNormalSurface *s) |
|
static bool | regina::LPConstraintNonSpun::verify (const NAngleStructure *) |
|
static bool | regina::LPConstraintNonSpun::supported (NormalCoords coords) |
|
| regina::BanConstraintBase::BanConstraintBase (const NTriangulation *tri, int coords) |
| Constructs and initialises the banned_ and marked_ arrays to be entirely false . More...
|
|
| regina::BanConstraintBase::~BanConstraintBase () |
| Destroys this object and all associated data. More...
|
|
template<class LPConstraint , typename Integer > |
void | regina::BanConstraintBase::enforceBans (LPData< LPConstraint, Integer > &lp) const |
| Enforces all bans described by this class in the given tableaux. More...
|
|
void | regina::BanConstraintBase::init (const int *columnPerm) |
| Identifies which coordinates to ban and mark, and records the corresponding tableaux columns in the banned_ and marked_ arrays respectively. More...
|
|
static bool | regina::BanConstraintBase::supported (NormalCoords coords) |
| Indicates whether the given coordinate system is supported by this constraint class. More...
|
|
| regina::BanNone::BanNone (const NTriangulation *tri, int coords) |
| Constructs and initialises the banned_ and marked_ arrays to be entirely false , as described in the BanConstraintBase superclass constructor. More...
|
|
void | regina::BanNone::init (const int *) |
|
static bool | regina::BanNone::supported (NormalCoords coords) |
|
| regina::BanBoundary::BanBoundary (const NTriangulation *tri, int coords) |
| Constructs and initialises the banned_ and marked_ arrays to be entirely false , as described in the BanConstraintBase superclass constructor. More...
|
|
void | regina::BanBoundary::init (const int *columnPerm) |
|
static bool | regina::BanBoundary::supported (NormalCoords coords) |
|
| regina::BanTorusBoundary::BanTorusBoundary (const NTriangulation *tri, int coords) |
| Constructs and initialises the banned_ and marked_ arrays to be entirely false , as described in the BanConstraintBase superclass constructor. More...
|
|
void | regina::BanTorusBoundary::init (const int *columnPerm) |
|
static bool | regina::BanTorusBoundary::supported (NormalCoords coords) |
|
Polytope vertex enumeration algorithms.
Explicitly constructs equations for the linear function(s) constrained by this class.
Specifically, this routine takes an array of Coefficients objects (one for each column of the initial tableaux) and fills in the necessary coefficient data.
The precise form of the linear function(s) will typically depend upon the underlying triangulation. For this reason, the triangulation is explicitly passed, along with the permutation that indicates which columns of the initial tableaux correspond to which normal or angle structure coordinates.
More precisely: recall that, for each linear function, the initial tableaux acquires one new variable x_i that evaluates this linear function f(x). This routine must create the corresponding row that sets f(x) - x_i = 0
. Thus it must construct the coefficients of f(x) in the columns corresponding to normal coordinates, and it must also set a coefficient of -1 in the column for the corresponding new variable.
For each subclass S of LPConstraintBase, the array col must be an array of objects of type LPCol<S>. The class LPCol<S> is itself a larger subclass of the Coefficients class. This exact type must be used because the compiler must know how large each column object is in order to correct access each element of the given array.
As described in the LPInitialTableaux class notes, it might not be possible to construct the linear functions (since the triangulation might not satisfy the necessary requirements). In this case, this routine should ensure that the linear functions are in fact the zero functions, and should return false
(but it must still set -1 coefficients for the new variables as described above). Otherwise (if the linear function were successfully constructed) this routine should return true
.
If you are implementing this routine in a subclass that works with angle structure coordinates, remember that your linear constraints must not interact with the scaling coordinate (the final angle structure coordinate that is used to projectivise the angle structure polytope into a polyhedral cone). Your implementation of this routine must ensure that your linear constraints all have coefficient zero in this column.
- Precondition
- For all coefficients in the array col, the Coefficients substructures have all been initialised with the default constructor and not modified since.
- Parameters
-
col | the array of columns as stored in the initial tableaux (i.e., the data member LPInitialTableaux::col_). |
columnPerm | the corresponding permutation of columns that describes how columns of the tableaux correspond to normal or angle structure coordinates in the underlying triangulation (i.e., the data member LPInitialTableaux::columnPerm_). |
tri | the underlying triangulation. |
- Returns
true
if the linear functions were successfully constructed, or false
if not (in which case they will be replaced with the zero functions instead).