Regina Calculation Engine
Classes | Public Member Functions | List of all members
regina::LPInitialTableaux< LPConstraint > Class Template Reference

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

#include <enumerate/ntreelp.h>

Classes

struct  Col
 Stores a single column of the adjusted matching equation matrix in sparse form. More...
 

Public Member Functions

 LPInitialTableaux (const NTriangulation *tri, NormalCoords coords, bool enumeration)
 Construts this adjusted sparse matrix of matching equations. More...
 
 ~LPInitialTableaux ()
 Destroys this matrix. More...
 
const NTriangulationtri () 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 Integer >
Integer multColByRow (const LPMatrix< Integer > &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 Integer >
Integer multColByRowOct (const LPMatrix< Integer > &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 Integer >
void fillInitialTableaux (LPMatrix< Integer > &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:

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.
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:
Not present.

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

Copyright © 1999-2014, 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@debian.org).