#include <cmr/regular.h>

Functions
CMR_ERROR	CMRregularSearchThreeSeparation (CMR cmr, CMR_DEC dec, CMR_CHRMAT transpose, bool ternary, size_t firstNonCoGraphicMinor, CMR_SUBMAT psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Enumerates 3-separations for a 3-connected matrix. More...

CMR_ERROR	CMRregularThreeConnectedIsR10 (CMR cmr, CMR_DEC dec, bool *pisR10)
	Tests whether given 3-connected matrix represents \( R_{10} \). More...

CMR_ERROR	CMRregularSequenceGraphic (CMR cmr, CMR_CHRMAT matrix, CMR_CHRMAT transpose, size_t lengthSequence, size_t sequenceNumRows, size_t sequenceNumColumns, size_t plastGraphicMinor, CMR_GRAPH pgraph, CMR_ELEMENT pedgeElements, CMR_REGULAR_STATISTICS *stats, double timeLimit)
	Tests sequence of nested 3-connected minors for graphicness. More...

CMR_ERROR	CMRregularExtendNestedMinorSequence (CMR cmr, CMR_DEC dec, bool ternary, CMR_SUBMAT *psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Extends an incomplete sequence of nested 3-connected minors for the matrix of a decomposition node. More...

CMR_ERROR	CMRregularConstructNestedMinorSequence (CMR cmr, CMR_DEC dec, bool ternary, CMR_SUBMAT wheelSubmatrix, CMR_SUBMAT psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Constructs a sequence of nested 3-connected minors for the matrix of a decomposition node. More...

CMR_ERROR	CMRregularTestGraphic (CMR cmr, CMR_CHRMAT pmatrix, CMR_CHRMAT ptranspose, bool ternary, bool pisGraphic, CMR_GRAPH pgraph, CMR_GRAPH_EDGE pforest, CMR_GRAPH_EDGE pcoforest, bool parcsReversed, CMR_SUBMAT *psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Tests matrix for graphicness. More...

CMR_ERROR	CMRregularDecomposeSeriesParallel (CMR cmr, CMR_DEC pdec, bool ternary, CMR_SUBMAT psubmatrix, CMR_REGULAR_PARAMETERS params, CMR_REGULAR_STATISTICS *stats, double timeLimit)
	Splits off series-parallel elements from the matrix of a decomposition node. More...

CMR_ERROR	CMRregularDecomposeOneSum (CMR cmr, CMR_DEC dec)
	Performs a 1-sum decomposition of `matrix` and stores it in `dec`. More...

CMR_ERROR	CMRtestRegular (CMR cmr, CMR_CHRMAT matrix, bool ternary, bool pisRegular, CMR_DEC pdec, CMR_MINOR pminor, CMR_REGULAR_PARAMETERS params, CMR_REGULAR_STATISTICS *stats, double timeLimit)
	Tests ternary or binary linear matroid for regularity. More...

Function Documentation

◆ CMRregularConstructNestedMinorSequence()

CMR_ERROR CMRregularConstructNestedMinorSequence	(	CMR *	cmr,
		CMR_DEC *	dec,
		bool	ternary,
		CMR_SUBMAT *	wheelSubmatrix,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Constructs a sequence of nested 3-connected minors for the matrix of a decomposition node.

In case the matrix is not 3-connected, a 2-separation is applied to dec and the function terminates, filling the relevant variables of dec.

Parameters

cmr	CMR environment.
dec	Decomposition node.
ternary	Whether to consider the signs of the matrix.
wheelSubmatrix	Wheel submatrix to start with.
psubmatrix	Pointer for storing a violator matrix.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularDecomposeOneSum()

CMR_ERROR CMRregularDecomposeOneSum	(	CMR *	cmr,
		CMR_DEC *	dec
	)

Performs a 1-sum decomposition of matrix and stores it in dec.

If matrix is 1-connected, then dec remains unchanged. In particular, the matrix and transpose members remain NULL. Otherwise, dec will become a CMR_DEC_ONE_SUM node with children that are initialized to the 1-connected components. In this case, the matrix and transpose members of the child nodes are set.

Parameters

cmr	CMR environment.
dec	Initialized decomposition node with matrix attribute.

◆ CMRregularDecomposeSeriesParallel()

CMR_ERROR CMRregularDecomposeSeriesParallel	(	CMR *	cmr,
		CMR_DEC **	pdec,
		bool	ternary,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_PARAMETERS *	params,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Splits off series-parallel elements from the matrix of a decomposition node.

In case the matrix is Series-Parallel Matroids, then *pmatrix is set to NULL and *pdec is declared to be planar.

In case the matrix does not admit series-parallel reductions, then *pmatrix and *pdec remain unchanged, except The decomposition node *pdec and matrix *pmatrix are replaced by the SP-reduced ones, i.e., by the corresponding (grand-) children of the given decomposition and the corresponding matrix.

Parameters

cmr	CMR environment.
pdec	Pointer to decomposition node.
ternary	Whether to consider the signs of the matrix.
psubmatrix	Pointer for storing a violator matrix.
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularExtendNestedMinorSequence()

CMR_ERROR CMRregularExtendNestedMinorSequence	(	CMR *	cmr,
		CMR_DEC *	dec,
		bool	ternary,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Extends an incomplete sequence of nested 3-connected minors for the matrix of a decomposition node.

In case the matrix is not 3-connected, a 2-separation is applied to dec and the function terminates, filling the relevant variables of dec.

Parameters

cmr	CMR environment.
dec	Decomposition node.
ternary	Whether to consider the signs of the matrix.
psubmatrix	Pointer for storing a violator matrix.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularSearchThreeSeparation()

CMR_ERROR CMRregularSearchThreeSeparation	(	CMR *	cmr,
		CMR_DEC *	dec,
		CMR_CHRMAT *	transpose,
		bool	ternary,
		size_t	firstNonCoGraphicMinor,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Enumerates 3-separations for a 3-connected matrix.

Parameters

cmr	CMR environment.
dec	Decomposition node.
transpose	Transpose of nested-minors matrix of `dec`.
ternary	Whether to consider the signs of the matrix.
firstNonCoGraphicMinor	Index of first nested minor that is neither graphic nor cographic.
psubmatrix	Pointer for storing a violator matrix.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularSequenceGraphic()

CMR_ERROR CMRregularSequenceGraphic	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		size_t	lengthSequence,
		size_t *	sequenceNumRows,
		size_t *	sequenceNumColumns,
		size_t *	plastGraphicMinor,
		CMR_GRAPH **	pgraph,
		CMR_ELEMENT **	pedgeElements,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Tests sequence of nested 3-connected minors for graphicness.

Parameters

cmr	CMR environment.
matrix	Matrix.
transpose	Transpose.
lengthSequence	Length of the sequence of nested minors.
sequenceNumRows	Array with number of rows of each minor.
sequenceNumColumns	Array with number of columns of each minor.
plastGraphicMinor	Pointer for storing the last graphic minor.
pgraph	Pointer for storing the graph.
pedgeElements	Pointer for storing the mapping of edges to elements.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularTestGraphic()

CMR_ERROR CMRregularTestGraphic	(	CMR *	cmr,
		CMR_CHRMAT **	pmatrix,
		CMR_CHRMAT **	ptranspose,
		bool	ternary,
		bool *	pisGraphic,
		CMR_GRAPH **	pgraph,
		CMR_GRAPH_EDGE **	pforest,
		CMR_GRAPH_EDGE **	pcoforest,
		bool **	parcsReversed,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Tests matrix for graphicness.

Parameters

cmr	CMR environment.
pmatrix	Pointer to matrix.
ptranspose	Pointer to transpose.
ternary	Whether to also check the signs of the matrix.
pisGraphic	Pointer for storing the result.
pgraph	Pointer for storing the graph if the matrix is graph (may be `NULL`).
pforest	Pointer for storing the mapping of rows to forest edges.
pcoforest	Pointer for storing the mapping of rows to forest edges.
parcsReversed	Pointer for storing the array indicating which arcs are reversed.
psubmatrix	Pointer for storing a minimal non-graphic submatrix (may be `NULL`).
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularThreeConnectedIsR10()

CMR_ERROR CMRregularThreeConnectedIsR10	(	CMR *	cmr,
		CMR_DEC *	dec,
		bool *	pisR10
	)

Tests whether given 3-connected matrix represents \( R_{10} \).

Parameters

cmr	CMR environment.
dec	Decomposition.
pisR10	Pointer for storing whether `matrix` represents \( R_{10} \).

◆ CMRtestRegular()

CMR_ERROR CMRtestRegular	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool	ternary,
		bool *	pisRegular,
		CMR_DEC **	pdec,
		CMR_MINOR **	pminor,
		CMR_REGULAR_PARAMETERS *	params,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Tests ternary or binary linear matroid for regularity.

If pdec is not NULL, *pdec will be a (partial) decomposition tree.

If pminor is not NULL and matrix is not regular, then an \( F_7 \) or \( F_7^\star \) minor or a submatrix with non-ternary determinant is searched. This causes additional computational effort!

Parameters

cmr	CMR environment.
matrix	Input matrix.
ternary	Whether signs of `matrix` play a role.
pisRegular	Pointer for storing whether `matrix` is regular.
pdec	Pointer for storing the decomposition tree (may be `NULL`).
pminor	Pointer for storing an \( F_7 \) or \( F_7^\star \) minor.
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

Functions

Function Documentation

◆ CMRregularConstructNestedMinorSequence()

◆ CMRregularDecomposeOneSum()

◆ CMRregularDecomposeSeriesParallel()

◆ CMRregularExtendNestedMinorSequence()

◆ CMRregularSearchThreeSeparation()

◆ CMRregularSequenceGraphic()

◆ CMRregularTestGraphic()

◆ CMRregularThreeConnectedIsR10()

◆ CMRtestRegular()