regina::LPInitialTableaux< LPConstraint > Class Template Reference
Vertex Enumeration

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

`#include <enumerate/treelp.h>`

## Public Member Functions

| LPInitialTableaux (const Triangulation< 3 > *tri, NormalCoords coords, bool enumeration)
| Construts this adjusted sparse matrix of matching equations. More...
| ~LPInitialTableaux ()
| Destroys this matrix. More...
const Triangulation< 3 > * | tri () const
| Returns the underlying 3-manifold triangulation from which the matching equations were derived. More...
NormalCoords | coords () const
| Returns the coordinate system that is used for the matrix of matching equations. 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...
bool | constraintsBroken () const
| Indicates whether or not the extra constraints from the template parameter LPConstraints were added successfully. 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...

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

In some cases, it may be impossible to add the extra linear constraints that you would like (for instance, the constraints might require some preconditions on the underlying triangulation that are not met). If this is a possibility in your setting, you should call constraintsBroken() to test this as soon as the LPInitialTableaux has been constructed. Even if the constraints could not be added correctly, the tableaux will be left in a consistent state (the constraints will just be treated as zero functions instead).

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 can only work in quadrilateral normal coordinates (NS_QUAD), standard normal coordinates (NS_STANDARD), or angle structure coordinates (NS_ANGLE). No other coordinate systems are supported.

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:\n 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.

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.

Python:\n Not present.

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

- enumerate/treeconstraint.h
- enumerate/treelp.h

Copyright © 1999-2016, 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).