matroid_internal.h File Reference

#include "densematrix.h"
#include <cmr/matroid.h>
#include <cmr/series_parallel.h>

Go to the source code of this file.

Classes
struct	_CMR_MATROID_DEC

Functions
char *	CMRmatroiddecConsistency (CMR_MATROID_DEC *dec, bool recurse)
	Checks a matroid decomposition node for consistency. More...
CMR_EXPORT CMR_ERROR	CMRmatroiddecPrintChild (CMR *cmr, CMR_MATROID_DEC *child, CMR_MATROID_DEC *parent, size_t childIndex, FILE *stream, size_t indent, bool printChildren, bool printParentElements, bool printMatrices, bool printGraphs, bool printReductions, bool printPivots)
	Prints the decomposition child to stream. More...
CMR_ERROR	CMRmatroiddecSetNumChildren (CMR *cmr, CMR_MATROID_DEC *dec, size_t numChildren)
	Sets the number of children and allocates memory accordingly. More...
CMR_ERROR	CMRmatroiddecUpdateOneSum (CMR *cmr, CMR_MATROID_DEC *dec, size_t numChildren)
	Initialize an existing unknown decomposition node as a 1-sum with numChildren children. More...
CMR_ERROR	CMRmatroiddecCreateChildFromMatrices (CMR *cmr, CMR_MATROID_DEC *parent, size_t childIndex, CMR_CHRMAT *matrix, CMR_CHRMAT *transpose, CMR_ELEMENT *rowsToParent, CMR_ELEMENT *columnsToParent)
	Creates a decomposition node as a child. More...
CMR_ERROR	CMRmatroiddecUpdateSubmatrix (CMR *cmr, CMR_MATROID_DEC *dec, CMR_SUBMAT *submatrix, CMR_MATROID_DEC_TYPE type)
	Initialize an existing unknown decomposition node as a submatrix node whose child is of given type. More...
CMR_ERROR	CMRmatroiddecUpdateTwoSum (CMR *cmr, CMR_MATROID_DEC *dec, CMR_SEPA *separation)
	Initialize an existing unknown decomposition node as a 2-separation node according to the given separation. More...
CMR_ERROR	CMRmatroiddecUpdatePivots (CMR *cmr, CMR_MATROID_DEC *dec, size_t numPivots, size_t *pivotRows, size_t *pivotColumns, CMR_CHRMAT *matrix, CMR_CHRMAT *transpose)
	Initialize an existing unknown decomposition node as a pivot node according to the given arrays of pivots. More...
CMR_ERROR	CMRmatroiddecUpdateThreeSumInit (CMR *cmr, CMR_MATROID_DEC *dec)
	Initialize an existing unknown decomposition node as a 3-sum node. More...
CMR_ERROR	CMRmatroiddecUpdateThreeSumCreateWideFirstChild (CMR *cmr, CMR_MATROID_DEC *dec, CMR_SEPA *separation, size_t *rowsToChild, size_t *columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraRow, size_t extraColumn1, size_t extraColumn2, int8_t extraEntry)
	Creates wide first child of an initialized 3-sum node. More...
CMR_ERROR	CMRmatroiddecUpdateThreeSumCreateWideSecondChild (CMR *cmr, CMR_MATROID_DEC *dec, CMR_SEPA *separation, size_t *rowsToChild, size_t *columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraRow, size_t extraColumn1, size_t extraColumn2, int8_t extraEntry)
	Creates wide second child of an initialized 3-sum node. More...
CMR_ERROR	CMRmatroiddecUpdateThreeSumCreateMixedFirstChild (CMR *cmr, CMR_MATROID_DEC *dec, CMR_SEPA *separation, size_t *rowsToChild, size_t *columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraRow1, size_t extraRow2, int8_t extraEntry)
	Creates mixed first child of an initialized 3-sum node. More...
CMR_ERROR	CMRmatroiddecUpdateThreeSumCreateMixedSecondChild (CMR *cmr, CMR_MATROID_DEC *dec, CMR_SEPA *separation, size_t *rowsToChild, size_t *columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraColumn1, size_t extraColumn2, int8_t extraEntry)
	Creates mixed second child of an initialized 3-sum node. More...
CMR_ERROR	CMRmatroiddecSetAttributes (CMR_MATROID_DEC *dec)
	Set regularity and (co)graphicness attributes of a decomposition tree. More...

Function Documentation

CMRmatroiddecConsistency()

char* CMRmatroiddecConsistency	(	CMR_MATROID_DEC *	dec,
		bool	recurse
	)

Checks a matroid decomposition node for consistency.

Checks all requirements defined in Representation of Matroids and their Decomposition.

Returns

NULL if consistent. Otherwise, an explanation string is returned, which must freed with free().

See also

CMRconsistencyAssert() for checking the returned string and aborting in case of inconsistency.

Parameters

dec	Decomposition.
recurse	Whether all (grand-)children shall be checked, too.

CMRmatroiddecCreateChildFromMatrices()

CMR_ERROR CMRmatroiddecCreateChildFromMatrices	(	CMR *	cmr,
		CMR_MATROID_DEC *	parent,
		size_t	childIndex,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		CMR_ELEMENT *	rowsToParent,
		CMR_ELEMENT *	columnsToParent
	)

Creates a decomposition node as a child.

Copies matrix and transpose into the node.

Parameters

cmr	CMR environment.
parent	Parent node.
childIndex	Child index of parent.
matrix	The matrix corresponding to this node.
transpose	The transpose matrix corresponding to this node.
rowsToParent	Array for mapping rows to elements of parent.
columnsToParent	Array for mapping columns to elements of parent.

CMRmatroiddecPrintChild()

CMR_EXPORT CMR_ERROR CMRmatroiddecPrintChild	(	CMR *	cmr,
		CMR_MATROID_DEC *	child,
		CMR_MATROID_DEC *	parent,
		size_t	childIndex,
		FILE *	stream,
		size_t	indent,
		bool	printChildren,
		bool	printParentElements,
		bool	printMatrices,
		bool	printGraphs,
		bool	printReductions,
		bool	printPivots
	)

Prints the decomposition child to stream.

Parameters

cmr	CMR environment.
child	Decomposition node of parent.
parent	Decomposition node of parent.
childIndex	Index of child as a child of parent.
stream	Stream to write to.
indent	Indentation of this node.
printChildren	Whether to recurse.
printParentElements	Whether to print mapping of rows/columns to parent elements (if parent is not NULL).
printMatrices	Whether to print matrices.
printGraphs	Whether to print graphs.
printReductions	Whether to print series-parallel reductions.
printPivots	Whether to print pivots.

CMRmatroiddecSetAttributes()

CMR_ERROR CMRmatroiddecSetAttributes

(

CMR_MATROID_DEC *

dec

)

Set regularity and (co)graphicness attributes of a decomposition tree.

Parameters

dec	Decomposition node.

CMRmatroiddecSetNumChildren()

CMR_ERROR CMRmatroiddecSetNumChildren	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		size_t	numChildren
	)

Sets the number of children and allocates memory accordingly.

Parameters

cmr	CMR environment.
dec	Decomposition node.
numChildren	Number of children.

CMRmatroiddecUpdateOneSum()

CMR_ERROR CMRmatroiddecUpdateOneSum	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		size_t	numChildren
	)

Initialize an existing unknown decomposition node as a 1-sum with numChildren children.

Parameters

cmr	CMR environment.
dec	Decomposition node.
numChildren	Number of child nodes.

CMRmatroiddecUpdatePivots()

CMR_ERROR CMRmatroiddecUpdatePivots	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		size_t	numPivots,
		size_t *	pivotRows,
		size_t *	pivotColumns,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose
	)

Initialize an existing unknown decomposition node as a pivot node according to the given arrays of pivots.

The unique child node will be of type CMR_MATROID_DEC_TYPE_UNKNOWN.

Parameters

cmr	CMR environment.
dec	Decomposition node.
numPivots	Number of pivots.
pivotRows	Array with pivot rows.
pivotColumns	Array with pivot columns.
matrix	New matrix.
transpose	Transpose of matrix.

CMRmatroiddecUpdateSubmatrix()

CMR_ERROR CMRmatroiddecUpdateSubmatrix	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		CMR_SUBMAT *	submatrix,
		CMR_MATROID_DEC_TYPE	type
	)

Initialize an existing unknown decomposition node as a submatrix node whose child is of given type.

Parameters

cmr	CMR environment.
dec	Decomposition node.
submatrix	Submatrix.
type	Type of submatrix node.

CMRmatroiddecUpdateThreeSumCreateMixedFirstChild()

CMR_ERROR CMRmatroiddecUpdateThreeSumCreateMixedFirstChild	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		CMR_SEPA *	separation,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraRow1,
		size_t	extraRow2,
		int8_t	extraEntry
	)

Creates mixed first child of an initialized 3-sum node.

A nonzero extraEntry indicates the bottom-right nonzero entry.

Parameters

cmr	CMR environment.
dec	Decomposition node (initialized with CMRmatroiddecUpdateThreeSumInit).
separation	Separation.
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraRow1	Index of the first extra row.
extraRow2	Index of the second extra row.
extraEntry	Sign of the extra entry.

CMRmatroiddecUpdateThreeSumCreateMixedSecondChild()

CMR_ERROR CMRmatroiddecUpdateThreeSumCreateMixedSecondChild	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		CMR_SEPA *	separation,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraColumn1,
		size_t	extraColumn2,
		int8_t	extraEntry
	)

Creates mixed second child of an initialized 3-sum node.

A nonzero extraEntry indicates the top-left nonzero entry.

Parameters

cmr	CMR environment.
dec	Decomposition node (initialized with CMRmatroiddecUpdateThreeSumInit).
separation	Separation.
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraColumn1	Index of the first extra column.
extraColumn2	Index of the second extra column.
extraEntry	Sign of the extra entry.

CMRmatroiddecUpdateThreeSumCreateWideFirstChild()

CMR_ERROR CMRmatroiddecUpdateThreeSumCreateWideFirstChild	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		CMR_SEPA *	separation,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraRow,
		size_t	extraColumn1,
		size_t	extraColumn2,
		int8_t	extraEntry
	)

Creates wide first child of an initialized 3-sum node.

A nonzero extraEntry indicates the bottom-right nonzero entry.

Parameters

cmr	CMR environment.
dec	Decomposition node (initialized with CMRmatroiddecUpdateThreeSumInit).
separation	Separation.
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraRow	Index of the extra row.
extraColumn1	Index of 1st extra column.
extraColumn2	Index of 2nd extra column, parallel to extraColumn1; equality is allowed.
extraEntry	Sign of the extra entry.

CMRmatroiddecUpdateThreeSumCreateWideSecondChild()

CMR_ERROR CMRmatroiddecUpdateThreeSumCreateWideSecondChild	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		CMR_SEPA *	separation,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraRow,
		size_t	extraColumn1,
		size_t	extraColumn2,
		int8_t	extraEntry
	)

Creates wide second child of an initialized 3-sum node.

A nonzero extraEntry indicates the bottom-right nonzero entry.

Parameters

cmr	CMR environment.
dec	Decomposition node (initialized with CMRmatroiddecUpdateThreeSumInit).
separation	Separation.
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraRow	Index of the extra row.
extraColumn1	Index of 1st extra column.
extraColumn2	Index of 2nd extra column, parallel to extraColumn1; equality is allowed.
extraEntry	Sign of the extra entry, if known.

CMRmatroiddecUpdateThreeSumInit()

CMR_ERROR CMRmatroiddecUpdateThreeSumInit	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec
	)

Initialize an existing unknown decomposition node as a 3-sum node.

The two child nodes remain uninitialized.

Parameters

cmr	CMR environment.
dec	Decomposition node.

CMRmatroiddecUpdateTwoSum()

CMR_ERROR CMRmatroiddecUpdateTwoSum	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		CMR_SEPA *	separation
	)

Initialize an existing unknown decomposition node as a 2-separation node according to the given separation.

The two child nodes will be of type CMR_MATROID_DEC_TYPE_UNKNOWN.

Parameters

cmr	CMR environment.
dec	Decomposition node.
separation	2-separation.