Stores an adjusted matrix of homogeneous linear matching equations based on a given triangulation, in sparse form. More...

#include <enumerate/treelp.h>

Inheritance diagram for regina::LPInitialTableaux< LPConstraint >:

Public Member Functions
	LPInitialTableaux (const Triangulation< 3 > &tri, NormalEncoding enc, bool enumeration=true)
	Construts this adjusted sparse matrix of matching equations. More...

	LPInitialTableaux (const LPInitialTableaux &src)
	Creates a new copy of the given matrix. More...

	LPInitialTableaux (LPInitialTableaux &&src) noexcept
	Moves the contents of the given matrix into this new matrix. More...

	~LPInitialTableaux ()
	Destroys this matrix. More...

LPInitialTableaux &	operator= (const LPInitialTableaux &src)
	Sets this to be a copy of the given matrix. More...

LPInitialTableaux &	operator= (LPInitialTableaux &&src) noexcept
	Moves the contents of the given matrix into this matrix. More...

void	swap (LPInitialTableaux &other) noexcept
	Swaps the contents of this and the given matrix. More...

const Triangulation< 3 > &	tri () const
	Returns the underlying 3-manifold triangulation from which the matching equations were derived. More...

LPSystem	system () const
	Returns the broad class of vector encodings that this tableaux works with. More...

unsigned	rank () const
	Returns the rank of this matrix. More...

unsigned	columns () const
	Returns the number of columns in this matrix. More...

unsigned	coordinateColumns () const
	Returns the number of columns that correspond to normal coordinates or angle structure coordinates. More...

const int *	columnPerm () const
	Returns the permutation that describes how the columns of the matching equation matrix were reordered. More...

template<typename IntType >
IntType	multColByRow (const LPMatrix< IntType > &m, unsigned mRow, unsigned thisCol) const
	Computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix. More...

template<typename IntType >
IntType	multColByRowOct (const LPMatrix< IntType > &m, unsigned mRow, unsigned thisCol) const
	A variant of multColByRow() that takes into account any adjustments to the tableaux that are required when this is a quadrilateral column being used to represent an octagon type. More...

template<typename IntType >
void	fillInitialTableaux (LPMatrix< IntType > &m) const
	Fills the given matrix with the contents of this matrix. More...

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream. More...

void	writeTextLong (std::ostream &out) const
	Writes a detailed text representation of this object to the given output stream. More...

std::string	str () const
	Returns a short text representation of this object. More...

std::string	utf8 () const
	Returns a short text representation of this object using unicode characters. More...

std::string	detail () const
	Returns a detailed text representation of this object. More...

Detailed Description

template<class LPConstraint>
class regina::LPInitialTableaux< LPConstraint >

Stores an adjusted matrix of homogeneous linear matching equations based on a given triangulation, in sparse form.

Typically these will be the normal surface matching equations in some coordinate system, or the angle structure equations.

This class forms part of the tree traversal algorithms for enumerating and locating normal surfaces, as described in "A tree traversal algorithm for decision problems in knot theory and 3-manifold topology", Burton and Ozlen, Algorithmica 65:4 (2013), pp. 772-801, and "A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour", Burton and Ozlen, arXiv:1211.1079. It is also used for locating a single strict angle structure, and for enumerating all taut angle structures.

The adjustments (which are all carried out in the LPInitialTableaux class constructor) are as follows:

the rows of the matching equation matrix have been reordered so that the first rank() rows are full rank;
the columns of the matching equation matrix have been reordered according to the permutation returned by columnPerm(). This is a heuristic reordering designed to improve the performance of the tree traversal algorithm; see columnPerm() for a list of constraints that such a reordering must satisfy.

There is also optional support for adding extra linear constraints (such as a constraint on Euler characteristic for normal surfaces). These extra constraints are supplied by the template parameter LPConstraint, and will generate LPConstraint::nConstraints additional rows and columns (used by the additional variables that evaluate the corresponding linear functions). If there are no additional constraints, simply use the template parameter LPConstraintNone.

For some LPConstraint template arguments, Regina may discover at runtime that it is impossible to add the corresponding extra linear constraints (e.g., the constraints might require some preconditions on the underlying triangulation that are not met). In this case, the LPInitialTableaux class constructor will throw an exception, as noted in the constructor documentation below.

This class is optimised for working with columns of the matrix (in particular, multiplying columns of this matrix by rows of some other matrix).

This class works with a broad class of vector encodings for normal surfaces or angle structures, as described by the LPSystem class, and within that broad class it does not know which particular encoding or underlying coordinate system is being used. In particular, the matching equations it uses will always be one of the standard tri-quad normal matching equations (if LPSystem::standard() is true), the quad normal matching equations (if LPSystem::quad() is true), or the homogeneous angle equations (if LPSystem::angles() is true). If you need to add extra matching equations beyond these, use the LPConstraint template argument as outlined above. If you need to support more exotic vector encodings (e.g., for octagonal almost normal surfaces), you will need to find a way to represent it using one of these three broad classes; see the LPData class notes for how this is done with octagons.

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

Warning: The implementation of this class relies on the fact that the sum of absolute values of all coefficients in each column is at most four (not counting the rows for any optional extra constraints). If you are extending this class to work with more general matching equation matrices, you may need to change the implementation accordingly.

Precondition: The template parameter LPConstraint must be one of the subclasses of LPConstraintBase. See the LPConstraintBase class notes for further details.

Headers: Parts of this template class are implemented in a separate header (treelp-impl.h), which is not included automatically by this file. Most end users should not need this extra header, since Regina's calculation engine already includes explicit instantiations for common combinations of template arguments.

Python: This is a heavily templated class; nevertheless, many variants are now made available to Python users. Each class name is of the form LPInitialTableaux_LPConstraint, where the suffix LPConstraint is an abbreviated version of the LPConstraint template parameter; this suffix is omitted entirely for the common case LPConstraintNone. An example of such a Python class name is LPInitialTableaux_NonSpun. You are encouraged to look through the Regina namespace to see which constraint classes are supported under Python.

Warning: The API for this class has not yet been finalised. This means that the class interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please watch the detailed changelogs upon new releases to see if you need to make changes to your code.

Constructor & Destructor Documentation

◆ LPInitialTableaux() [1/3]

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::LPInitialTableaux	(	const Triangulation< 3 > &	tri,
		NormalEncoding	enc,
		bool	enumeration = `true`
	)

Construts this adjusted sparse matrix of matching equations.

Note that LPInitialTableaux does not copy the given triangulation; it merely keeps a reference to it. The triangulation should not change during the lifespan of this object.

Precondition: The given triangulation is non-empty.

Exceptions

InvalidArgument	it was not possible to add the extra constraints from the LPConstraint template argument, due to an error which should have been preventable with the right checks in advance. Such exceptions are generated by the LPConstraint class, and so you should consult the class documentation for your chosen LPConstraint template argument to see if this is a possibility.
InvalidArgument	it was not possible to add the extra constraints from the LPConstraint template argument, due to an error that was "genuinely" unforseeable. Again, such exceptions are generated by your chosen LPConstraint class, and you should consult its documentation to see if this is a possibility.

Parameters

tri	the underlying 3-manifold triangulation.
enc	the normal surface vector encoding that we are using for our enumeration task. This may be any valid NormalEncoding object, including the special angle structure encoding.
enumeration	`true` if we should optimise the tableaux for a full enumeration of vertex surfaces or taut angle structures, or `false` if we should optimise the tableaux for an existence test (such as searching for a non-trivial normal disc or sphere, or a strict angle structure).

◆ LPInitialTableaux() [2/3]

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::LPInitialTableaux ( const LPInitialTableaux< LPConstraint > & src )

inline

Creates a new copy of the given matrix.

Parameters

src	the matrix to copy.

◆ LPInitialTableaux() [3/3]

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::LPInitialTableaux ( LPInitialTableaux< LPConstraint > && src )

inlinenoexcept

Moves the contents of the given matrix into this new matrix.

This is a fast (constant time) operation.

The matrix that is passed (src) will no longer be usable.

Parameters

src	the matrix to move.

◆ ~LPInitialTableaux()

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::~LPInitialTableaux

inline

Destroys this matrix.

Member Function Documentation

◆ columnPerm()

template<class LPConstraint >

const int * regina::LPInitialTableaux< LPConstraint >::columnPerm

inline

Returns the permutation that describes how the columns of the matching equation matrix were reordered.

This permutation maps column numbers in this adjusted matching equation matrix to column numbers in the original (unmodified) matching equation matrix that was originally derived from the triangulation.

The permutation is returned as an array of columns() integers, such that column i of this adjusted matrix corresponds to column columnPerm()[i] of the original matrix.

If you are imposing additional constraints through the template parameter LPConstraint, then the corresponding extra variables will be included in the permutation; however, these are never moved and will always remain the rightmost variables in this system (i.e., the columns of highest index).

As well as the requirement that this is a genuine permutation of 0,...,columns()-1, this array will also adhere to the following constraints. In the following discussion, n refers to the number of tetrahedra in the underlying triangulation.

The quadrilateral coordinate columns must appear as the first 3n columns of the adjusted matrix. In particular, when working in the 7n-dimensional standard normal coordinate system, the remaining 4n triangle coordinate columns must appear last.
The quadrilateral coordinate columns must be grouped by tetrahedron and ordered by quadrilateral type. In other words, for each i = 0,...,n-1, there will be some tetrahedron j for which the three columns 3i, 3i+1 and 3i+2 refer to the quadrilaterals in tetrahedron j of types 0, 1 and 2 respectively. Phrased loosely, we are allowed to reorder the tetrahedra, but not the quadrilateral coordinates within each tetrahedron.
The triangle coordinate columns (if we are working in standard normal coordinates) must likewise be grouped by tetrahedron, and these tetrahedra must appear in the same order as for the quadrilateral types. In other words, for each i = 0,...,n-1, the quadrilateral columns 3i, 3i+1 and 3i+2 and the triangle columns 3n+4i, 3n+4i+1, 3n+4i+2 and 3n+4i+3 all refer to the same tetrahedron.
For angle structure coordinates, the constraints are analogous to those for quadrilateral coordinates: the angle coordinates must be grouped by tetrahedron and ordered by angle type, and the final scaling coordinate must remain last.

Python: This routine returns a Python list.

Returns: details of the permutation describing how columns were reordered.

◆ columns()

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::columns

inline

Returns the number of columns in this matrix.

Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the number of columns will be larger than in the original matching equation matrix.

Returns: the number of columns.

◆ coordinateColumns()

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::coordinateColumns

inline

Returns the number of columns that correspond to normal coordinates or angle structure coordinates.

This is precisely the number of columns in the original matrix of matching equations.

Returns: the number of normal or angle structure coordinate columns.

◆ detail()

std::string regina::Output< LPInitialTableaux< LPConstraint > , false >::detail ( ) const

inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns: a detailed text representation of this object.

◆ fillInitialTableaux()

template<class LPConstraint >

template<typename IntType >

void regina::LPInitialTableaux< LPConstraint >::fillInitialTableaux ( LPMatrix< IntType > & m ) const

inline

Fills the given matrix with the contents of this matrix.

This effectively copies this sparse but highly specialised matrix representation into a dense but more flexible matrix representation.

Precondition: The given matrix has already been initialised to size rank() * columns(), and all of its elements have already been set to zero. Note that this can all be arranged by calling the constructor LPMatrix::LPMatrix(unsigned, unsigned).

Parameters

m	the matrix to fill.

◆ multColByRow()

template<class LPConstraint >

template<typename IntType >

IntType regina::LPInitialTableaux< LPConstraint >::multColByRow	(	const LPMatrix< IntType > &	m,
		unsigned	mRow,
		unsigned	thisCol
	)		const

inline

Computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix.

This routine is optimised to use the sparse representation of columns in this matrix.

Precondition: The given matrix m has precisely rank() columns.

Parameters

m	the matrix whose row we will use in the inner product.
mRow	the row of the matrix m to use in the inner product.
thisCol	the column of this matrix to use in the inner product.

Returns: the resulting inner product.

◆ multColByRowOct()

template<class LPConstraint >

template<typename IntType >

IntType regina::LPInitialTableaux< LPConstraint >::multColByRowOct	(	const LPMatrix< IntType > &	m,
		unsigned	mRow,
		unsigned	thisCol
	)		const

inline

A variant of multColByRow() that takes into account any adjustments to the tableaux that are required when this is a quadrilateral column being used 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 where we are using additional constraints through the template parameter LPConstraint, these extra constraints 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 routine effectively allows us to adjust the tableaux accordingly.

Specifically: this routine computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix. We assume that the given column of this matrix describes one of the two quadrilateral coordinates in some tetrahedron that together form an octagon type, and (via the information given by LPConstraint::octAdjustment) we implicitly adjust the coefficients of our extra constraints accordingly.

This routine is optimised to use the sparse representation of columns in this matrix.

This routine is not used with angle structure coordinates.

Precondition: The given matrix m has precisely rank() columns.; Column thisCol of this matrix describes one of the two quadrilateral coordinates that are being combined to form an octagon type within some tetrahedron.

Parameters

m	the matrix whose row we will use in the adjusted inner product.
mRow	the row of the matrix m to use in the adjusted inner product.
thisCol	the column of this matrix to use in the adjusted inner product.

Returns: the resulting adjusted inner product.

◆ operator=() [1/2]

template<class LPConstraint >

LPInitialTableaux< LPConstraint > & regina::LPInitialTableaux< LPConstraint >::operator= ( const LPInitialTableaux< LPConstraint > & src )

inline

Sets this to be a copy of the given matrix.

It does not matter if this and the given matrix have different sizes and/or work with different vector encodings; if so then these properties will be copied across also.

Parameters

src	the matrix to copy.

Returns: a reference to this matrix.

◆ operator=() [2/2]

template<class LPConstraint >

LPInitialTableaux< LPConstraint > & regina::LPInitialTableaux< LPConstraint >::operator= ( LPInitialTableaux< LPConstraint > && src )

inlinenoexcept

Moves the contents of the given matrix into this matrix.

This is a fast (constant time) operation.

It does not matter if this and the given matrix have different sizes and/or work with different vector encodings; if so then these properties will be moved across also.

The matrix that is passed (src) will no longer be usable.

Parameters

src	the matrix to move.

Returns: a reference to this matrix.

◆ rank()

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::rank

inline

Returns the rank of this matrix.

Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the rank will be larger than the rank of the original matching equation matrix.

Returns: the matrix rank.

◆ str()

std::string regina::Output< LPInitialTableaux< LPConstraint > , false >::str ( ) const

inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python str() and repr() functions.

Python: The Python "stringification" function str() will use precisely this function, and for most classes the Python repr() function will incorporate this into its output.

Returns: a short text representation of this object.

◆ swap()

template<class LPConstraint >

void regina::LPInitialTableaux< LPConstraint >::swap ( LPInitialTableaux< LPConstraint > & other )

inlinenoexcept

Swaps the contents of this and the given matrix.

It does not matter if the two matrices have different sizes, and/or work with different vector encodings; if so then these properties will be swapped also.

Parameters

other the matrix whose contents should be swapped with this.

◆ system()

template<class LPConstraint >

LPSystem regina::LPInitialTableaux< LPConstraint >::system

inline

Returns the broad class of vector encodings that this tableaux works with.

This broad class is deduced from the vector encoding that was passed to the class constructor, and it completely determines which matching equations were generated as a result.

See the LPInitialTableaux class notes for more information on these three broad classes and how they affect the tableaux.

Returns: the class of vector encodings used by this tableaux.

◆ tri()

template<class LPConstraint >

const Triangulation< 3 > & regina::LPInitialTableaux< LPConstraint >::tri

inline

Returns the underlying 3-manifold triangulation from which the matching equations were derived.

Returns: the underlying triangulation.

◆ utf8()

std::string regina::Output< LPInitialTableaux< LPConstraint > , false >::utf8 ( ) const

inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns: a short text representation of this object.

◆ writeTextLong()

template<class LPConstraint >

void regina::LPInitialTableaux< LPConstraint >::writeTextLong ( std::ostream & out ) const

Writes a detailed text representation of this object to the given output stream.

Python: Not present; use detail() instead.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

template<class LPConstraint >

void regina::LPInitialTableaux< LPConstraint >::writeTextShort ( std::ostream & out ) const

Writes a short text representation of this object to the given output stream.

Python: Not present; use str() instead.

Parameters

out	the output stream to which to write.

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

enumerate/treeconstraint.h
enumerate/treelp.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LPInitialTableaux() [1/3]

◆ LPInitialTableaux() [2/3]

◆ LPInitialTableaux() [3/3]

◆ ~LPInitialTableaux()

Member Function Documentation

◆ columnPerm()

◆ columns()

◆ coordinateColumns()

◆ detail()

◆ fillInitialTableaux()

◆ multColByRow()

◆ multColByRowOct()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ rank()

◆ str()

◆ swap()

◆ system()

◆ tri()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()