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

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

#include <enumerate/treelp.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...
 
IntType & entry (unsigned row, unsigned col)
 Returns a read-write reference to the given element of this matrix. More...
 
const IntType & 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 IntType &destCoeff, unsigned dest, const IntType &srcCoeff, unsigned src, const IntType &div)
 Applies a particular row operation to this matrix. More...
 
IntType combRowAndNorm (const IntType &destCoeff, unsigned dest, const IntType &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 IntType>
class regina::LPMatrix< IntType >

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 IntType, which is supplied as a template argument.

Precondition
The default constructor for the template class IntType must intialise each new integer to zero. The classes Integer and NativeInteger, for instance, have this property.
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.
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.

Constructor & Destructor Documentation

◆ LPMatrix() [1/2]

template<typename IntType >
regina::LPMatrix< IntType >::LPMatrix ( )
inline

Creates an uninitialised matrix with no memory storage.

You must call reserve() and then either initClone() or initIdentity() before this matrix will become initialised.

◆ LPMatrix() [2/2]

template<typename IntType >
regina::LPMatrix< IntType >::LPMatrix ( unsigned  rows,
unsigned  cols 
)
inline

Creates a fully initialised rows by cols matrix with all elements set to zero.

This routine reserves space for precisely rows * cols elements. In other words, you may later re-initialise the matrix to become smaller if you like, but you cannot re-initialise the matrix to become larger.

Parameters
rowsthe number of rows in the new matrix. This must be strictly positive.
colsthe number of columns in the new matrix. This must be strictly positive.

◆ ~LPMatrix()

template<typename IntType >
regina::LPMatrix< IntType >::~LPMatrix ( )
inline

Destroys this matrix and all of the data it contains.

You can safely destroy a matrix that is uninitialised or only partially initialised (i.e., space has been reserved but the matrix size is not set).

Member Function Documentation

◆ columns()

template<typename IntType >
unsigned regina::LPMatrix< IntType >::columns ( ) const
inline

Returns the number of columns in this matrix.

This relates to the currently assigned matrix size, not the total amount of memory that was originally reserved.

Returns
the number of columns.

◆ combRow()

template<typename IntType >
void regina::LPMatrix< IntType >::combRow ( const IntType &  destCoeff,
unsigned  dest,
const IntType &  srcCoeff,
unsigned  src,
const IntType &  div 
)
inline

Applies a particular row operation to this matrix.

Specifically, row dest will be replaced with the linear combination: (destCoeff * row dest - srcCoeff * row src) / div.

Precondition
dest and src are not equal.
It is known in advance that every integer in (destCoeff * row dest - srcCoeff * row src) will be divisible by div. In other words, it is known in advance that we can use exact integer division without remainders.
Parameters
destCoeffthe coefficient applied to row dest in the linear combination.
destthe index of the row to replace. This must be between 0 and rows()-1 inclusive.
srcCoeffthe coefficient applied to row src in the linear combination.
srcthe index of the other row used in this linear combination. This must be between 0 and rows()-1 inclusive.
divthe integer to divide the final row by. This must be non-zero.

◆ combRowAndNorm()

template<typename IntType >
IntType regina::LPMatrix< IntType >::combRowAndNorm ( const IntType &  destCoeff,
unsigned  dest,
const IntType &  srcCoeff,
unsigned  src 
)
inline

Applies a particular row operation to this matrix, and then normalises.

Specifically, row dest will be replaced with the linear combination: (destCoeff * row dest - srcCoeff * row src); then, if row dest is non-zero, it will be normalised by dividing through by the gcd of its elements. Note that this gcd is always taken to be positive (i.e., the final normalisation will never change the signs of the elements in the row).

Precondition
dest and src are not equal.
Parameters
destCoeffthe coefficient applied to row dest in the linear combination.
destthe index of the row to replace. This must be between 0 and rows()-1 inclusive.
srcCoeffthe coefficient applied to row src in the linear combination.
srcthe index of the other row used in this linear combination. This must be between 0 and rows()-1 inclusive.
Returns
the positive gcd that row dest was scaled down by, or 0 if row dest is entirely zero.

◆ dump()

template<typename IntType >
void regina::LPMatrix< IntType >::dump ( std::ostream &  out) const

Writes this matrix to the given output stream.

The output is "rough" and wasteful, and is intended for debugging purposes only. The precise output format is subject to change in future versions of Regina.

Parameters
outthe output stream to write to.

◆ entry() [1/2]

template<typename IntType >
IntType & regina::LPMatrix< IntType >::entry ( unsigned  row,
unsigned  col 
)
inline

Returns a read-write reference to the given element of this matrix.

Parameters
rowthe row of the requested element. This must be between 0 and rows()-1 inclusive.
colthe column of the requested element. This must be between 0 and columns()-1 inclusive.

◆ entry() [2/2]

template<typename IntType >
const IntType & regina::LPMatrix< IntType >::entry ( unsigned  row,
unsigned  col 
) const
inline

Returns a read-only reference to the given element of this matrix.

Parameters
rowthe row of the requested element. This must be between 0 and rows()-1 inclusive.
colthe column of the requested element. This must be between 0 and columns()-1 inclusive.

◆ initClone()

template<typename IntType >
void regina::LPMatrix< IntType >::initClone ( const LPMatrix< IntType > &  clone)
inline

Initialises this matrix to a copy of the given matrix.

This matrix does not yet need to be initialised, but it does need to have enough space reserved.

You may call this routine on an already-initialised matrix, and you may use this routine to assign it a different size (as long as enough space was originally reserved).

Precondition
If this matrix has not been initialised before, then reserve() must have already been called.
This matrix has enough space reserved for at least clone.rows() * clone.columns() elements.
Parameters
clonethe matrix to copy.

◆ initIdentity()

template<typename IntType >
void regina::LPMatrix< IntType >::initIdentity ( unsigned  size)
inline

Initialises this matrix to the identity matrix of the given size.

This matrix does not yet need to be initialised, but it does need to have enough space reserved.

You may call this routine on an already-initialised matrix, and you may use this routine to assign it a different size (as long as enough space was originally reserved).

Precondition
If this matrix has not been initialised before, then reserve() must have already been called.
This matrix has enough space reserved for at least size * size elements.
Parameters
sizethe number of rows, and also the number of columns, that will be assigned to this matrix. This must be strictly positive.

◆ negateRow()

template<typename IntType >
void regina::LPMatrix< IntType >::negateRow ( unsigned  row)
inline

Negates all elements in the given row of this matrix.

Parameters
rowthe row whose elements should be negated. This must be between 0 and rows()-1 inclusive.

◆ reserve()

template<typename IntType >
void regina::LPMatrix< IntType >::reserve ( unsigned  maxRows,
unsigned  maxCols 
)
inline

Reserves enough space to store the elements of a maxRows by maxCols matrix.

This is just an upper bound: your matrix may end up using fewer elements than this, but it cannot use more.

This matrix will still not be initialised until you call either initClone() or initIdentity(). See the class notes for details.

Precondition
This matrix was created using the default (no-argument) constructor, and you have not called any other routines on this matrix since.
Warning
To elaborate on the precondition above: you can only call reserve() once, and if you did not use the default LPMatrix constructor then you cannot call it at all. Any additional calls to reserve() will result in a memory leak.
Parameters
maxRowsan upper bound on the number of rows that you will need for this matrix. This must be strictly positive.
maxColsan upper bound on the number of columns that you will need for this matrix. This must be strictly positive.

◆ rows()

template<typename IntType >
unsigned regina::LPMatrix< IntType >::rows ( ) const
inline

Returns the number of rows in this matrix.

This relates to the currently assigned matrix size, not the total amount of memory that was originally reserved.

Returns
the number of rows.

◆ swapRows()

template<typename IntType >
void regina::LPMatrix< IntType >::swapRows ( unsigned  r1,
unsigned  r2 
)
inline

Swaps the two given rows of this matrix.

The two arguments r1 and r2 may be equal (in which case the matrix will be left unchanged).

Parameters
r1the index of the first row to swap. This must be between 0 and rows()-1 inclusive.
r2the index of the second row to swap. This must be between 0 and rows()-1 inclusive.

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

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