Matroid decomposition

Classes
struct	CMR_MINOR
	A minor of a matroid. More...

Enumerations
enum	CMR_MINOR_TYPE {   CMR_MINOR_TYPE_DETERMINANT = -2 , CMR_MINOR_TYPE_ENTRY = -1 , CMR_MINOR_TYPE_CUSTOM = 0 , CMR_MINOR_TYPE_U24 = 1 ,   CMR_MINOR_TYPE_FANO = 2 , CMR_MINOR_TYPE_FANO_DUAL = 3 , CMR_MINOR_TYPE_K5 = 4 , CMR_MINOR_TYPE_K5_DUAL = 5 ,   CMR_MINOR_TYPE_K33 = 6 , CMR_MINOR_TYPE_K33_DUAL = 7 }

Functions
CMR_EXPORT CMR_ERROR	CMRchrmatBinaryPivot (CMR *cmr, CMR_CHRMAT *matrix, size_t pivotRow, size_t pivotColumn, CMR_CHRMAT **presult)
	Apply a pivot to matrix and returns the resulting matrix in *presult.
CMR_EXPORT CMR_ERROR	CMRchrmatTernaryPivot (CMR *cmr, CMR_CHRMAT *matrix, size_t pivotRow, size_t pivotColumn, CMR_CHRMAT **presult)
	Applies a pivot to matrix and returns the resulting matrix in *presult.
CMR_EXPORT CMR_ERROR	CMRchrmatRegularPivot (CMR *cmr, CMR_CHRMAT *matrix, size_t pivotRow, size_t pivotColumn, CMR_SUBMAT **pviolator, CMR_CHRMAT **presult)
	Applies a pivot to matrix and returns the resulting matrix in *presult.
CMR_EXPORT CMR_ERROR	CMRchrmatBinaryPivots (CMR *cmr, CMR_CHRMAT *matrix, size_t numPivots, size_t *pivotRows, size_t *pivotColumns, CMR_CHRMAT **presult)
	Applies a sequence of pivots to matrix and returns the resulting matrix in *presult.
CMR_EXPORT CMR_ERROR	CMRchrmatTernaryPivots (CMR *cmr, CMR_CHRMAT *matrix, size_t numPivots, size_t *pivotRows, size_t *pivotColumns, CMR_CHRMAT **presult)
	Applies a sequence of pivots to matrix and returns the resulting matrix in *presult.
CMR_EXPORT CMR_ERROR	CMRchrmatRegularPivots (CMR *cmr, CMR_CHRMAT *matrix, size_t numPivots, size_t *pivotRows, size_t *pivotColumns, CMR_SUBMAT **pviolator, CMR_CHRMAT **presult)
	Applies a sequence of pivots to matrix and returns the resulting matrix in *presult.
CMR_EXPORT CMR_ERROR	CMRminorCreate (CMR *cmr, CMR_MINOR **pminor, size_t numPivots, CMR_SUBMAT *submatrix, CMR_MINOR_TYPE type)
	Creates a minor, allocating space for numPivots pivots and a remaining submatrix.
CMR_EXPORT CMR_ERROR	CMRminorFree (CMR *cmr, CMR_MINOR **pminor)
	Frees the minor *pminor (if pminor is not NULL).
CMR_EXPORT CMR_MINOR_TYPE	CMRminorType (CMR_MINOR *minor)
	Returns the type of minor.
CMR_EXPORT size_t	CMRminorNumPivots (CMR_MINOR *minor)
	Returns the number of pivots needed to make a minor visible.
CMR_EXPORT size_t *	CMRminorPivotRows (CMR_MINOR *minor)
	Returns the array with pivot rows to make a minor visible.
CMR_EXPORT size_t *	CMRminorPivotColumns (CMR_MINOR *minor)
	Returns the array with pivot columns to make a minor visible.
CMR_EXPORT CMR_SUBMAT *	CMRminorSubmatrix (CMR_MINOR *minor)
	Returns the submatrix to take (after applying pivots) to make a minor visible.
CMR_EXPORT CMR_ERROR	CMRminorPrint (CMR *cmr, CMR_MINOR *minor, size_t numRows, size_t numColumns, FILE *stream)
	Writes the minor minor to stream by means of lists of row and column indices as well as pivot entries.
CMR_EXPORT CMR_ERROR	CMRminorWriteToFile (CMR *cmr, CMR_MINOR *minor, size_t numRows, size_t numColumns, const char *fileName)
	Writes the minor minor to the file fileName by means of lists of row and column indices as well as pivot entries.

Detailed Description

Enumeration Type Documentation

CMR_MINOR_TYPE

enum CMR_MINOR_TYPE

Enumerator
CMR_MINOR_TYPE_DETERMINANT	A submatrix \( M \) with \( |\det(M)| = 2 \).
CMR_MINOR_TYPE_ENTRY	A submatrix \( M \) of size 1-by-1 exhibiting a bad entry.
CMR_MINOR_TYPE_CUSTOM	A custom minor.
CMR_MINOR_TYPE_U24	A minor representing \( U^2_4 \).
CMR_MINOR_TYPE_FANO	A minor representing \( F_7 \).
CMR_MINOR_TYPE_FANO_DUAL	A minor representing \( F_7^\star \).
CMR_MINOR_TYPE_K5	A minor representing \( M(K_5) \).
CMR_MINOR_TYPE_K5_DUAL	A minor representing \( M(K_5)^\star \).
CMR_MINOR_TYPE_K33	A minor representing \( M(K_{3,3}) \).
CMR_MINOR_TYPE_K33_DUAL	A minor representing \( M(K_{3,3})^\star \).

Function Documentation

CMRchrmatBinaryPivot()

CMR_EXPORT CMR_ERROR CMRchrmatBinaryPivot	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	pivotRow,
		size_t	pivotColumn,
		CMR_CHRMAT **	presult
	)

Apply a pivot to matrix and returns the resulting matrix in *presult.

Calculations are done over the binary field.

Parameters

cmr	CMR environment.
matrix	Matrix to work with.
pivotRow	Row of the pivot.
pivotColumn	Column of the pivot.
presult	Pointer for storing the resulting matrix.

CMRchrmatBinaryPivots()

CMR_EXPORT CMR_ERROR CMRchrmatBinaryPivots	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	numPivots,
		size_t *	pivotRows,
		size_t *	pivotColumns,
		CMR_CHRMAT **	presult
	)

Applies a sequence of pivots to matrix and returns the resulting matrix in *presult.

Calculations are done over the ternary field.

Parameters

cmr	CMR environment.
matrix	Matrix to work with.
numPivots	Number of pivots to carry out.
pivotRows	Array with rows of the pivots.
pivotColumns	Array with columns of the pivots.
presult	Pointer for storing the resulting matrix.

CMRchrmatRegularPivot()

CMR_EXPORT CMR_ERROR CMRchrmatRegularPivot	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	pivotRow,
		size_t	pivotColumn,
		CMR_SUBMAT **	pviolator,
		CMR_CHRMAT **	presult
	)

Applies a pivot to matrix and returns the resulting matrix in *presult.

Calculations are done over the ternary field, but must be consistent with those over every field. If an inconsistency is detected, *presult will be NULL and *pviolator will be an irregular 2-by-2 submatrix.

Parameters

cmr	CMR environment.
matrix	Matrix to work with.
pivotRow	Row of the pivot.
pivotColumn	Column of the pivot.
pviolator	Pointer for storing a violating (irregular) submatrix.
presult	Pointer for storing the resulting matrix.

CMRchrmatRegularPivots()

CMR_EXPORT CMR_ERROR CMRchrmatRegularPivots	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	numPivots,
		size_t *	pivotRows,
		size_t *	pivotColumns,
		CMR_SUBMAT **	pviolator,
		CMR_CHRMAT **	presult
	)

Applies a sequence of pivots to matrix and returns the resulting matrix in *presult.

Calculations are done over the ternary field, but must be consistent with those over every field. If an inconsistency is detected, *presult will be NULL and *pviolator will be an irregular submatrix.

Parameters

cmr	CMR environment.
matrix	Matrix to work with.
numPivots	Number of pivots to carry out.
pivotRows	Array with rows of the pivots.
pivotColumns	Array with columns of the pivots.
pviolator	Pointer for storing a violating (irregular) submatrix.
presult	Pointer for storing the resulting matrix.

CMRchrmatTernaryPivot()

CMR_EXPORT CMR_ERROR CMRchrmatTernaryPivot	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	pivotRow,
		size_t	pivotColumn,
		CMR_CHRMAT **	presult
	)

Applies a pivot to matrix and returns the resulting matrix in *presult.

Calculations are done over the ternary field.

Parameters

cmr	CMR environment.
matrix	Matrix to work with.
pivotRow	Row of the pivot.
pivotColumn	Column of the pivot.
presult	Pointer for storing the resulting matrix.

CMRchrmatTernaryPivots()

CMR_EXPORT CMR_ERROR CMRchrmatTernaryPivots	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	numPivots,
		size_t *	pivotRows,
		size_t *	pivotColumns,
		CMR_CHRMAT **	presult
	)

Applies a sequence of pivots to matrix and returns the resulting matrix in *presult.

Calculations are done over the ternary field.

Parameters

cmr	CMR environment.
matrix	Matrix to work with.
numPivots	Number of pivots to carry out.
pivotRows	Array with rows of the pivots.
pivotColumns	Array with columns of the pivots.
presult	Pointer for storing the resulting matrix.

CMRminorCreate()

CMR_EXPORT CMR_ERROR CMRminorCreate	(	CMR *	cmr,
		CMR_MINOR **	pminor,
		size_t	numPivots,
		CMR_SUBMAT *	submatrix,
		CMR_MINOR_TYPE	type
	)

Creates a minor, allocating space for numPivots pivots and a remaining submatrix.

Takes ownership of submatrix.

Parameters

cmr	CMR environment.
pminor	Pointer for storing the minor.
numPivots	Number of pivots.
submatrix	Submatrix (may be NULL; is not copied).
type	Type of minor.

CMRminorFree()

CMR_EXPORT CMR_ERROR CMRminorFree	(	CMR *	cmr,
		CMR_MINOR **	pminor
	)

Frees the minor *pminor (if pminor is not NULL).

Parameters

cmr	CMR environment.
pminor	Pointer to the minor (may be NULL).

CMRminorNumPivots()

CMR_EXPORT size_t CMRminorNumPivots

(

CMR_MINOR *

minor

)

Returns the number of pivots needed to make a minor visible.

Parameters

minor

Minor.

CMRminorPivotColumns()

CMR_EXPORT size_t * CMRminorPivotColumns

(

CMR_MINOR *

minor

)

Returns the array with pivot columns to make a minor visible.

Parameters

minor

Minor.

CMRminorPivotRows()

CMR_EXPORT size_t * CMRminorPivotRows

(

CMR_MINOR *

minor

)

Returns the array with pivot rows to make a minor visible.

Parameters

minor

Minor.

CMRminorPrint()

CMR_EXPORT CMR_ERROR CMRminorPrint	(	CMR *	cmr,
		CMR_MINOR *	minor,
		size_t	numRows,
		size_t	numColumns,
		FILE *	stream
	)

Writes the minor minor to stream by means of lists of row and column indices as well as pivot entries.

Parameters

cmr	CMR environment.
minor	Minor to write.
numRows	Number of rows of original matrix.
numColumns	Number of columns of original matrix.
stream	File stream to save minor to..

CMRminorSubmatrix()

CMR_EXPORT CMR_SUBMAT * CMRminorSubmatrix

(

CMR_MINOR *

minor

)

Returns the submatrix to take (after applying pivots) to make a minor visible.

Parameters

minor

Minor.

CMRminorType()

CMR_EXPORT CMR_MINOR_TYPE CMRminorType

(

CMR_MINOR *

minor

)

Returns the type of minor.

Parameters

minor

Minor.

CMRminorWriteToFile()

CMR_EXPORT CMR_ERROR CMRminorWriteToFile	(	CMR *	cmr,
		CMR_MINOR *	minor,
		size_t	numRows,
		size_t	numColumns,
		const char *	fileName
	)

Writes the minor minor to the file fileName by means of lists of row and column indices as well as pivot entries.

Parameters

cmr	CMR environment.
minor	Minor to write.
numRows	Number of rows of original matrix.
numColumns	Number of columns of original matrix.
fileName	File name to save minor to; NULL indicates stdout.