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

#include <enumerate/treelp.h>

Inheritance diagram for regina::LPMatrix< IntType >:

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 (LPMatrix &&src) noexcept
	Moves the contents of the given matrix into this new matrix. More...

	~LPMatrix ()
	Destroys this matrix and all of the data it contains. More...

LPMatrix &	operator= (LPMatrix &&src) noexcept
	Moves the contents of the given matrix into this matrix. More...

void	swap (LPMatrix &other) noexcept
	Swaps the contents of this and the given matrix. 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...

bool	operator== (const LPMatrix &other) const
	Determines whether this and the given matrix are equal. More...

bool	operator!= (const LPMatrix &other) const
	Determines whether this and the given matrix are not equal. 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
	Deprecated routine that writes this matrix to the given output stream. More...

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream. More...

void	writeTextLong (std::ostream &out) const
	Writes a detailed text representation of this object to the given output stream. More...

	LPMatrix (const LPMatrix &)=delete

LPMatrix &	operator= (const LPMatrix &)=delete

std::string	str () const
	Returns a short text representation of this object. More...

std::string	utf8 () const
	Returns a short text representation of this object using unicode characters. More...

std::string	detail () const
	Returns a detailed text representation of this object. 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. If you just want a general-use integer matrix class, use MatrixInt instead.

It is critical that, before using an LPMatrix, 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.

This class implements C++ move semantics and adheres to the C++ Swappable requirement. However, due to the unusual create-reserve-initialise procedure, it does not support copying (either by copy construction or copy assignment). Because of the move semantics, this class avoids deep copies, even when passing or returning objects by value.

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.

Python: The template argument IntType is taken to be regina::Integer.

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.

Constructor & Destructor Documentation

◆ LPMatrix() [1/3]

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/3]

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() [3/3]

template<typename IntType >

regina::LPMatrix< IntType >::LPMatrix ( LPMatrix< IntType > && src )

inlinenoexcept

Moves the contents of the given matrix into this new matrix.

This is a fast (constant time) operation.

If the given matrix is uninitialised, then this new matrix will be uninitialised also.

The matrix that is passed (src) will no longer be usable.

Parameters

src	the matrix to move.

◆ ~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

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
	)

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
	)

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.

◆ detail()

std::string regina::Output< LPMatrix< IntType > , false >::detail ( ) const

inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns: a detailed text representation of this object.

◆ dump()

template<typename IntType >

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

Deprecated routine that 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.

Deprecated:: This has been replaced by writeTextLong() (which uses a slightly tighter output format), for compatibility with Regina's usual text output facilities.

Python: Not present, but you can call detail() instead.

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.

Python: The entry() routine gives direct read-write access to matrix elements, but does not allow them to be set using the assignment operator. In other words, code such as matrix.entry(r, c).negate() will work, but matrix.entry(r, c) = value will not. To assign values to matrix elements, you should instead use the syntax matrix.set(row, column, value). This set() routine returns nothing, and is provided for python only (i.e., it is not part of the C++ calculation engine).

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.

◆ operator!=()

template<typename IntType >

bool regina::LPMatrix< IntType >::operator!= ( const LPMatrix< IntType > & other ) const

inline

Determines whether this and the given matrix are not equal.

Two matrices are equal if and only if their dimensions are the same, and the corresponding elements of each matrix are equal.

It is safe to compare matrices of different dimensions, and it is safe to compare matrices that might not yet be initialised. Two uninitialised matrices will compare as equal.

Parameters

other the matrix to compare with this.

Returns: true if and only if the two matrices are not equal.

◆ operator=()

template<typename IntType >

LPMatrix< IntType > & regina::LPMatrix< IntType >::operator= ( LPMatrix< IntType > && src )

inlinenoexcept

Moves the contents of the given matrix into this matrix.

This is a fast (constant time) operation.

If the given matrix is uninitialised, then this matrix will become uninitialised also.

The matrix that is passed (src) will no longer be usable.

Parameters

src	the matrix to move.

Returns: a reference to this matrix.

◆ operator==()

template<typename IntType >

bool regina::LPMatrix< IntType >::operator== ( const LPMatrix< IntType > & other ) const

inline

Determines whether this and the given matrix are equal.

Two matrices are equal if and only if their dimensions are the same, and the corresponding elements of each matrix are equal.

It is safe to compare matrices of different dimensions, and it is safe to compare matrices that might not yet be initialised. Two uninitialised matrices will compare as equal.

Parameters

other the matrix to compare with this.

Returns: true if and only if the two matrices are equal.

◆ 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

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.

◆ str()

std::string regina::Output< LPMatrix< IntType > , false >::str ( ) const

inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python str() and repr() functions.

Python: The Python "stringification" function str() will use precisely this function, and for most classes the Python repr() function will incorporate this into its output.

Returns: a short text representation of this object.

◆ swap()

template<typename IntType >

void regina::LPMatrix< IntType >::swap ( LPMatrix< IntType > & other )

inlinenoexcept

Swaps the contents of this and the given matrix.

It does not matter if the two matrices have different sizes, or if one or both is unintialised; if so then these properties will be swapped also.

Parameters

other the matrix whose contents should be swapped with this.

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

◆ utf8()

std::string regina::Output< LPMatrix< IntType > , false >::utf8 ( ) const

inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns: a short text representation of this object.

◆ writeTextLong()

template<typename IntType >

void regina::LPMatrix< IntType >::writeTextLong ( std::ostream & out ) const

Writes a detailed text representation of this object to the given output stream.

Python: Not present; use detail() instead.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

template<typename IntType >

void regina::LPMatrix< IntType >::writeTextShort ( std::ostream & out ) const

Writes a short text representation of this object to the given output stream.

Python: Not present; use str() instead.

Parameters

out	the output stream to which to write.

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

enumerate/treeconstraint.h
enumerate/treelp.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LPMatrix() [1/3]

◆ LPMatrix() [2/3]

◆ LPMatrix() [3/3]

◆ ~LPMatrix()

Member Function Documentation

◆ columns()

◆ combRow()

◆ combRowAndNorm()

◆ detail()

◆ dump()

◆ entry() [1/2]

◆ entry() [2/2]

◆ initClone()

◆ initIdentity()

◆ negateRow()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ reserve()

◆ rows()

◆ str()

◆ swap()

◆ swapRows()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()