regina::LPConstraintBase Class Reference

A base class for additional linear constraints that we can add to the tableaux of normal surface or angle structure matching equations. More...

#include <enumerate/treeconstraint.h>

Inheritance diagram for regina::LPConstraintBase:

Public Types
using	Coefficient = int
	The type used to store each coefficient for each of these additional linear constraints. More...

Static Public Member Functions
static void	addRows (LPCol< LPConstraintBase > *col, const LPInitialTableaux< LPConstraintBase > &init)
	Explicitly constructs equations for the linear function(s) constrained by this class. More...
template<typename IntType >
static void	constrain (LPData< LPConstraintNone, IntType > &lp, size_t numCols)
	Explicitly constraints each of these linear functions to an equality or inequality in the underlying tableaux. More...
static bool	verify (const NormalSurface &s)
	Ensures that the given normal surface satisfies the extra constraints described by this class. More...
static bool	verify (const AngleStructure &s)
	Ensures that the given angle structure satisfies the extra constraints described by this class. More...
static bool	supported (NormalEncoding enc)
	Indicates whether the given vector encoding is supported by this constraint class. More...

Static Public Attributes
static constexpr int	nConstraints = 0
	The number of additional linear constraints that we impose. More...
static constexpr Coefficient	octAdjustment = 0
	Indicates if/how to adjust the coefficients of these linear constraints when using two quadrilateral columns to represent an octagon type. More...

Detailed Description

A base class for additional linear constraints that we can add to the tableaux of normal surface or angle structure matching equations.

This is used with TreeEnumeration, TreeSingleSoln and related algorithms for enumerating and locating normal surfaces or angle structures in a 3-manifold triangulation. See the LPInitialTableaux class notes for details on how these constraints interact with the tableaux of matching equations.

The linear constraints may be equalities or inequalities, and there may be more than one such constraint. If all constraints are homogeneous equalities, the class should derive from LPConstraintSubspace instead (not this base class).

In angle structure coordinates, these linear constraints must not involve the scaling coordinate (the final coordinate that is used to convert the angle structure polytope into a polyhedral cone). The coefficient for the final scaling coordinate in each additional linear constraint will be assumed to be zero.

Bear in mind that the tableaux that these constraints are working with will not necessarily use the same coordinates as the underlying enumeration task (e.g., the tableaux will never include separate columns for octagon coordinates). See LPInitialTableaux for a more detailed discussion of this.

This base class provides no functionality. For documentation's sake only, the notes here describe the functionality that any subclass must implement. We note again that LPConstraintBase does not provide any implementations at all, and subclasses are completely responsible for their own implementations.

All constraint classes provide their functionality through static routines: they do not contain any member data, and it is unnecessary (but harmless) to construct them.

These linear constraint classes are designed mainly to act as C++ template arguments, and end users will typically not need to construct their own object of these classes. Instead, to use a linear constraint class, pass it as a template parameter to one of the tree traversal subclasses (e.g., TreeEnumeration, TreeSingleSolution, or TautEnumeration).

Python

This base class is not present, but all of the "real" linear constraint subclasses are available. However, as noted above, it is rare that you would need to access any of these constraint classes directly through Python. Instead, to use a linear constraint class, you would typically create a tree traversal object with the appropriate class suffix (e.g., one such Python class is TreeEnumeration_NonSpun).

Warning

The API for this class or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release to see if you need to make changes to your code.

Member Typedef Documentation

Coefficient

using regina::LPConstraintBase::Coefficient = int

The type used to store each coefficient for each of these additional linear constraints.

The type should:

• be able to be constructed or assigned from the value 0;
• support multiplication of the form IntType * Coefficient and assignment of the form IntType = Coefficient, where IntType is any integer type that could be used with the LPData and LPMatrix classes that use these constraints.

Member Function Documentation

addRows()

static void regina::LPConstraintBase::addRows ( LPCol< LPConstraintBase > *  col, const LPInitialTableaux< LPConstraintBase > &  init  )

static

Explicitly constructs equations for the linear function(s) constrained by this class.

Specifically, this routine takes an array of columns in the initial tableaux and fills in the necessary coefficient data.

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.

As described in the LPInitialTableaux class notes, it might not be possible to construct the linear functions (since the underlying triangulation might not satisfy the necessary requirements). In such cases this routine should throw an exception, as described below, and the corresponding constraint class must mention this possibility in its class documentation.

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.

The precise form of the linear function(s) will typically depend upon the underlying triangulation, as well as the permutation that indicates which columns of the initial tableaux correspond to which normal or angle structure coordinates. All of this information is read from the given initial tableaux init.

Note that the tableaux init may still be under construction (and indeed, the column array col to be filled will typically be the internal column array from init itself). This routine should not read any of the tableaux entries; it should only access the underlying triangulation (LPInitialTableaux.tri()) and the permutation of columns (LPInitialTableaux.columnPerm()).

For each subclass Sub of LPConstraintBase, the array col must be an array of objects of type LPCol<Sub>, and the tableaux init must be of type LPInitialTableaux<Sub>.

This routine should only write to the coefficients stored in LPCol::extra. You may assume that these coefficients have all been initialised to zero by the LPCol constructor.

Precondition

For all columns in the array col, the members LPCol::extra have all been initialised to zero.

Exceptions

InvalidArgument	It was not possible to create the linear functions for these constraints, due to an error which should have been preventable with the right checks in advance. Any constraint class that could throw exceptions in this way must describe this behaviour in its own class documentation.
UnsolvedCase	It was not possible to create the linear functions for these constraints, due to an error that was "genuinely" unforseeable. Again, any constraint class that could throw exceptions in this way must describe this behaviour in its own class documentation.

Python

The argument col is not present, since LPCol is only designed to be used as part of the internal data storage for LPInitialTableaux. Instead, this routine returns a Python list of constraints, where each constraint is presented as a Python list of coefficients. Each of these inner lists will have size init.columns().

Parameters

col	the array of columns as stored in the initial tableaux (i.e., the data member LPInitialTableaux::col_).
init	the tableaux through which this routine can acces the underlying triangulation and permutation of columns. Typically this will be the tableaux holding the column array col.

constrain()

template<typename IntType >

static void regina::LPConstraintBase::constrain ( LPData< LPConstraintNone, IntType > &  lp, size_t  numCols  )

static

Explicitly constraints each of these linear functions to an equality or inequality in the underlying tableaux.

This will typically consist of a series of calls to LPData::constrainZero() and/or LPData::constrainPositive().

The variables for these extra linear functions are stored in columns numCols - nConstraints, ..., numCols - 1 of the given tableaux, and so your calls to LPData::constrainZero() and/or LPData::constrainPositive() should operate on these (and only these) columns.

Precondition

These column coefficients belong to the initial starting tableaux (LPInitialTableaux) from which the given tableaux is derived.

Parameters

lp	the tableaux in which to constrain these linear functions.
numCols	the number of columns in the given tableaux.

supported()

static bool regina::LPConstraintBase::supported ( NormalEncoding  enc )

static

Indicates whether the given vector encoding is supported by this constraint class.

This routine assumes that the given encoding is already known to be supported by the generic tree traversal infrastructure, and only returns false if there are additional prerequisites imposed by this particular constraint class that the given encoding does not satisfy. If this constraint class does not impose any of its own additional conditions, this routine may simply return true.

The only features of the encoding that this routine should examine are what coordinates are stored (e.g., NormalEncoding::storesTriangles()). In particular, this routine will not look at any "semantic guarantees" (e.g. NormalEncoding::couldBeNonCompact()).

Parameters

enc	the vector encoding being queried. This must be one of the vector encodings known to be supported by the generic TreeTraversal infrastructure, and in particular it may be the special angle structure encoding.

Returns

true if and only if this vector encoding is also supported by this specific constraint class.

verify() [1/2]

static bool regina::LPConstraintBase::verify ( const AngleStructure &  s )

static

Ensures that the given angle structure satisfies the extra constraints described by this class.

Ideally this test is not based on explicitly recomputing the linear function(s), but instead runs independent tests; see the related routine verify(const NormalSurface&) for examples.

If these linear constraints work with normal or almost normal surfaces (not angle structure coordinates), then this routine should return false.

Parameters

s	the angle structure to test.

Returns

true if the given angle structure satisfies these linear constraints, or false if it does not.

verify() [2/2]

static bool regina::LPConstraintBase::verify ( const NormalSurface &  s )

static

Ensures that the given normal surface satisfies the extra constraints described by this class.

Ideally this test is not based on explicitly recomputing the linear function(s), but instead runs independent tests. For instance, if this class is used to constraint Euler characteristic, then ideally this routine would call s.eulerChar() and test the return value of that routine instead.

If these linear constraints work with angle structure coordinates (not normal or almost normal surfaces), then this routine should return false.

Parameters

s	the surface to test.

Returns

true if the given surface satisfies these linear constraints, or false if it does not.

Member Data Documentation

nConstraints

constexpr int regina::LPConstraintBase::nConstraints = 0

staticconstexpr

The number of additional linear constraints that we impose.

Each constraint will generate one new variable (column) and one new equation (row) in the tableaux.

octAdjustment

constexpr Coefficient regina::LPConstraintBase::octAdjustment = 0

staticconstexpr

Indicates if/how to adjust the coefficients of these linear constraints when using two quadrilateral columns to represent an octagon type.

The LPData class offers support for octagonal almost normal surfaces, in which exactly one tetrahedron is allowed to have exactly one octagon type. We represent such an octagon as a pair of incompatible quadrilaterals within the same tetrahedron. See the LPData class notes for details on how this works.

In some settings, our extra linear constraints must behave differently in the presence of octagons (i.e., the coefficient of the octagon type is not just the sum of coefficients of the two constituent quadrilateral types). This constant effectively allows us to adjust the tableaux accordingly.

Specifically: for each of the two quadrilateral columns being used to represent an octagon type, the coefficient for each of these additional linear constraints will be adjusted by adding octAdjustment.

This adjustment is not used with angle structure coordinates.

Currently this is a very blunt mechanism: it assumes that the adjustment can be made by adding a compile-time constant, and it assumes that if there are multiple constraints (i.e., nConstraints > 1) then they can all be adjusted in the same way. This mechanism will be made more flexible if/when this becomes necessary.

---

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

• enumerate/treeconstraint.h