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 (size_t rows, size_t 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 (size_t maxRows, size_t 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 (size_t size)
	Initialises this matrix to the identity matrix of the given size. More...

IntType &	entry (size_t row, size_t col)
	Returns a read-write reference to the given element of this matrix. More...

const IntType &	entry (size_t row, size_t col) const
	Returns a read-only reference to the given element of this matrix. More...

void	set (size_t row, size_t col, const IntType &value)
	Python-only routine that sets the given element of this matrix. More...

size_t	rows () const
	Returns the number of rows in this matrix. More...

size_t	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 (size_t r1, size_t r2)
	Swaps the two given rows of this matrix. More...

void	combRow (const IntType &destCoeff, size_t dest, const IntType &srcCoeff, size_t src, const IntType &div)
	Applies a particular row operation to this matrix. More...

IntType	combRowAndNorm (const IntType &destCoeff, size_t dest, const IntType &srcCoeff, size_t src)
	Applies a particular row operation to this matrix, and then normalises. More...

void	negateRow (size_t row)
	Negates all elements in the given row of this matrix. 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 or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release 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	(	size_t	rows,
		size_t	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 >

size_t 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,
		size_t	dest,
		const IntType &	srcCoeff,
		size_t	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,
		size_t	dest,
		const IntType &	srcCoeff,
		size_t	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.

◆ entry() [1/2]

template<typename IntType >

IntType & regina::LPMatrix< IntType >::entry	(	size_t	row,
		size_t	col
	)

inline

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

Python: In general, to assign values to matrix elements you should use the Python-only set() routine. This entry() routine does give read-write access to matrix elements in Python, but it 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; instead you will need to call matrix.set(r, c, value).

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	(	size_t	row,
		size_t	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 ( size_t 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 ( size_t 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	(	size_t	maxRows,
		size_t	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 >

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

◆ set()

template<typename IntType >

void regina::LPMatrix< IntType >::set	(	size_t	row,
		size_t	col,
		const IntType &	value
	)

Python-only routine that sets the given element of this matrix.

C++: Not present. For C++ users, entry() is used for both reading and writing: just write entry(row, column) = value.

Python: In general, to assign values to matrix elements you should use the syntax matrix.set(row, column, value). The entry() routine does give read-write access to matrix elements in Python, but it 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.

Parameters

row	the row of the entry to set; this must be between 0 and rows()-1 inclusive.
col	the column of the entry to set; this must be between 0 and columns()-1 inclusive.
value	the new entry to place in the given row and column.

◆ 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	(	size_t	r1,
		size_t	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()

◆ entry() [1/2]

◆ entry() [2/2]

◆ initClone()

◆ initIdentity()

◆ negateRow()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ reserve()

◆ rows()

◆ set()

◆ str()

◆ swap()

◆ swapRows()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()