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

A matrix class for use with linear programming. More...

#include <enumerate/ntreelp.h>

Public Member Functions

 LPMatrix ()
 Creates an uninitialised matrix with no memory storage. More...
 
 LPMatrix (unsigned rows, unsigned cols)
 Creates a fully initialised rows by cols matrix with all elements set to zero. More...
 
 ~LPMatrix ()
 Destroys this matrix and all of the data it contains. More...
 
void reserve (unsigned maxRows, unsigned maxCols)
 Reserves enough space to store the elements of a maxRows by maxCols matrix. More...
 
void initClone (const LPMatrix &clone)
 Initialises this matrix to a copy of the given matrix. More...
 
void initIdentity (unsigned size)
 Initialises this matrix to the identity matrix of the given size. More...
 
Integer & entry (unsigned row, unsigned col)
 Returns a read-write reference to the given element of this matrix. More...
 
const Integer & entry (unsigned row, unsigned col) const
 Returns a read-only reference to the given element of this matrix. More...
 
unsigned rows () const
 Returns the number of rows in this matrix. More...
 
unsigned columns () const
 Returns the number of columns in this matrix. More...
 
void swapRows (unsigned r1, unsigned r2)
 Swaps the two given rows of this matrix. More...
 
void combRow (const Integer &destCoeff, unsigned dest, const Integer &srcCoeff, unsigned src, const Integer &div)
 Applies a particular row operation to this matrix. More...
 
Integer combRowAndNorm (const Integer &destCoeff, unsigned dest, const Integer &srcCoeff, unsigned src)
 Applies a particular row operation to this matrix, and then normalises. More...
 
void negateRow (unsigned row)
 Negates all elements in the given row of this matrix. More...
 
void dump (std::ostream &out) const
 Writes this matrix to the given output stream. More...
 

Detailed Description

template<typename Integer>
class regina::LPMatrix< Integer >

A matrix class for use with linear programming.

This class is used in the tree traversal algorithms for enumerating and locating vertex 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 operations on this matrix class are tailored and optimised specifically for use with the dual simplex method in the context of a repetitive backtracking search. As a result, the API is cumbersome and highly specialised, which makes this matrix class inappropriate for general use.

It is critical that, before using such a matrix, you reserve space for its elements, and then fix a specific size. A matrix for which both tasks have been done will be called initialised. You can initialise a matrix in one of two ways:

You may call the initialisation initClone() and initIdentity() routines more than once (e.g., during a backtracking search), and you may use different matrix sizes each time. However, you may never use more elements than you originally reserved space for.

This matrix is stored in dense form. All elements are of the integer class Integer, which is supplied as a template argument.

Precondition
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 files:

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