regina::LPMatrix< IntType > Class Template Reference
Vertex Enumeration

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:

- by using the (rows, columns) constructor, which does everything for you;
- by using the default (no-arguments) constructor, then calling reserve(), and then calling one of the initialisation routines initClone() or initIdentity().

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

  rows | the number of rows in the new matrix. This must be strictly positive.
  cols | the 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

  destCoeff | the coefficient applied to row dest in the linear combination.
  dest | the index of the row to replace. This must be between 0 and rows()-1 inclusive.
  srcCoeff | the coefficient applied to row src in the linear combination.
  src | the index of the other row used in this linear combination. This must be between 0 and rows()-1 inclusive.
  div | the 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

  destCoeff | the coefficient applied to row dest in the linear combination.
  dest | the index of the row to replace. This must be between 0 and rows()-1 inclusive.
  srcCoeff | the coefficient applied to row src in the linear combination.
  src | the 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

  out | the 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

  row | the row of the requested element. This must be between 0 and rows()-1 inclusive.
  col | the 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

  row | the row of the requested element. This must be between 0 and rows()-1 inclusive.
  col | the 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

  clone | the 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

  size | the 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

  row | the 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

  maxRows | an upper bound on the number of rows that you will need for this matrix. This must be strictly positive.
  maxCols | an 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

  r1 | the index of the first row to swap. This must be between 0 and rows()-1 inclusive.
  r2 | the 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:

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