Regina Calculation Engine
Public Member Functions | List of all members
regina::LPData< LPConstraint, Integer > Class Template Reference

Stores an intermediate tableaux for the dual simplex method, and contains all of the core machinery for using the dual simplex method. More...

#include <enumerate/ntreelp.h>

Public Member Functions

 LPData ()
 Constructs a new tableaux. More...
 
 ~LPData ()
 Destroys this tableaux. More...
 
void reserve (const LPInitialTableaux< LPConstraint > *origTableaux)
 Reserves enough memory for this tableaux to work with. More...
 
void initStart ()
 Initialises this tableaux by beginning at the original starting tableaux and working our way to any feasible basis. More...
 
void initClone (const LPData &parent)
 Initialises this tableaux to be a clone of the given tableaux. More...
 
unsigned columns () const
 Returns the number of columns in this tableaux. More...
 
unsigned coordinateColumns () const
 Returns the number of columns in this tableaux that correspond to normal coordinates or angle structure coordinates. More...
 
bool isFeasible () const
 Returns whether or not this system is feasible. More...
 
bool isActive (unsigned pos) const
 Determines whether the given variable is currently active. More...
 
int sign (unsigned pos) const
 Returns the sign of the given variable under the current basis. More...
 
void constrainZero (unsigned pos)
 Constrains this system further by setting the given variable to zero and deactivating it. More...
 
void constrainPositive (unsigned pos)
 Constrains this system further by constraining the given variable to be strictly positive. More...
 
void constrainOct (unsigned quad1, unsigned quad2)
 Declares that two quadrilateral coordinates within a tetrahedron are to be combined into a single octagon coordinate, for use with almost normal surfaces, and constrains the system accordingly. More...
 
void dump (std::ostream &out) const
 Writes details of this tableaux to the given output stream. More...
 
void extractSolution (NRay &v, const char *type) const
 Extracts the values of the individual variables from the current basis, with some modifications (as described below). More...
 

Detailed Description

template<class LPConstraint, typename Integer>
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.

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.

This class is designed to represent a state partway through the tree traversal algorithm, where the tableaux has been altered to constrain some variables:

We do not store the full tableaux (which is dense and slow to work with). Instead we store the matrix of row operations that were applied to the original starting tableaux (in the notation of Burton and Ozlen, we store the matrix M_beta^{-1}, where M is the original matrix stored in the class LPInitialTableaux, and beta is the current basis).

If the system is infeasible (because the constraints on variables as described above are too severe), then the contents of the internal data members are undefined (other than the data member feasible_, which is guaranteed to be false). This is because the code is optimised to abort any operation as soon as infeasibility is detected, which may leave the data members in a broken state. If you are not sure, you should always call isFeasible() before performing any other query or operation on this tableaux.

This class is designed to be used in a backtracking search, which means the API is cumbersome but we can quickly rewrite and copy data. The rules are as follows:

Like LPInitialTableaux, this class can enforce additional linear constraints (such as positive Euler characteristic) through the template parameter LPConstraint. If there are no such constraints, simply use the template parameter LPConstraintNone.

In the context of normal surfaces (not angle structures): Although the underlying coordinate system is based on quadrilaterals and (optionally) triangles, this class has elementary support for octagons also, as seen in almost normal surface theory. For the purposes of this class, an octagon is represented as a pair of quadrilaterals of different types in the same tetrahedron: these meet the boundary of the tetrahedron in the same arcs as a single octagon, and therefore interact with the matching equations in the same way.

To declare that you will be using octagons in some tetrahedron, you must call constrainOct(quad1, quad2), where quad1 and quad2 are the two corresponding quadrilateral columns. This will have the following effects, all of which may alter the tableaux:

This class has been optimised to ensure that you only have one octagon type declared at any given time (which is consistent with the constraints of almost normal surface theory).

All tableaux elements are of the integer class Integer, which is supplied as a template argument. This same integer class will be used as a template argument for LPConstraint.

Precondition
The template parameter LPConstraint must be one of the subclasses of LPConstraintBase. See the LPConstraintBase class notes for further details.
The default constructor for the template class Integer must intialise each new integer to zero. The classes NInteger and NNativeInteger, for instance, have this property.
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).