Recognition of series-parallel matrices. More...

#include <cmr/element.h>
#include <cmr/matrix.h>
#include <cmr/separation.h>

Classes
struct	CMR_SP_STATISTICS
	Statistics for series-parallel recognition algorithm. More...

struct	CMR_SP_REDUCTION
	Represents a series-parallel reduction. More...

Functions
CMR_EXPORT CMR_ERROR	CMRspStatsInit (CMR_SP_STATISTICS *stats)
	Initializes all statistics for series-parallel computations.

CMR_EXPORT CMR_ERROR	CMRspStatsPrint (FILE stream, CMR_SP_STATISTICS stats, const char *prefix)
	Prints statistics for series-parallel computations.

CMR_EXPORT char *	CMRspReductionString (CMR_SP_REDUCTION reduction, char *buffer)

static bool	CMRspIsRow (CMR_SP_REDUCTION reduction)
	Returns `true` if the series-parallel `reduction` removes a row, i.e., is series.

static bool	CMRspIsColumn (CMR_SP_REDUCTION reduction)
	Returns `true` if the series-parallel `reduction` removes a column, i.e., is parallel.

static bool	CMRspIsZero (CMR_SP_REDUCTION reduction)
	Returns `true` if the series-parallel `reduction` removes a zero vector.

static bool	CMRspIsUnit (CMR_SP_REDUCTION reduction)
	Returns `true` if the series-parallel `reduction` removes a unit vector.

static bool	CMRspIsCopy (CMR_SP_REDUCTION reduction)
	Returns `true` if the series-parallel `reduction` removes a vector that is a copy of another vector.

static bool	CMRspIsValid (CMR_SP_REDUCTION reduction)
	Returns `true` if the series-parallel `reduction` is valid.

CMR_EXPORT CMR_ERROR	CMRspTestBinary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the binary `matrix` \( A \).

CMR_EXPORT CMR_ERROR	CMRspTestTernary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the ternary `matrix` \( A \).

CMR_EXPORT CMR_ERROR	CMRspDecomposeBinary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t maxNumReductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SEPA pseparation, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the binary `matrix` \( A \).

CMR_EXPORT CMR_ERROR	CMRspDecomposeTernary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t maxNumReductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SEPA pseparation, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the ternary `matrix` \( A \).

Detailed Description

Recognition of series-parallel matrices.

Author: Matthias Walter

Function Documentation

◆ CMRspDecomposeBinary()

CMR_EXPORT CMR_ERROR CMRspDecomposeBinary	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisSeriesParallel,
		CMR_SP_REDUCTION *	reductions,
		size_t	maxNumReductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SEPA **	pseparation,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

Finds all series-parallel reductions for the binary matrix \( A \).

Let \( A \in \{0,1\}^{m \times n} \) with \( k \) nonzeros.

Denote by \( A' \) the (maximum) SP-reduced submatrix of \( A \). If premainingSubmatrix is not NULL, then the rows and columns of \( A' \) are stored.

If pviolatorSubmatrix is not NULL and matrix is not binary series-parallel, then a wheel-submatrix is stored (unless a 2-separation is found; see below). Note that the row/column indices refer to \( A \).

If pseparation is not NULL and during the search for a wheel-submatrix a 2-separation that does not correspond to an SP reduction is found then such a 2-separation is returned and the algorithm terminates without returning a wheel-submatrix. Note that *pseparation then contains row/column indices relative to \( A' \).

The running time is \( \mathcal{O} (m + n + k) \) assuming no hashtable collisions.

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
pisSeriesParallel	Pointer for storing the result.
reductions	Array for storing the SP-reductions. If not `NULL`, it must have capacity at least number of rows + number of columns.
maxNumReductions	Maximum number of SP-reductions. Stops when this would be exceeded.
pnumReductions	Pointer for storing the number of SP-reductions; stores `SIZE_MAX` if **< `maxNumReductions` was exceeded.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a wheel-submatrix (may be `NULL`).
pseparation	Pointer for storing a 2-separation (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRspDecomposeTernary()

CMR_EXPORT CMR_ERROR CMRspDecomposeTernary	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisSeriesParallel,
		CMR_SP_REDUCTION *	reductions,
		size_t	maxNumReductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SEPA **	pseparation,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

Finds all series-parallel reductions for the ternary matrix \( A \).

Let \( A \in \{-1,0,+1\}^{m \times n} \) with \( k \) nonzeros.

Denote by \( A' \) the (maximum) SP-reduced submatrix of \( A \). If premainingSubmatrix is not NULL, then the rows and columns of \( A' \) are stored.

If pviolatorSubmatrix is not NULL and matrix is not ternary series-parallel, then a signed wheel- or \( M_2 \)-submatrix is stored (unless a 2-separation is found; see below). Note that the row/column indices refer to \( A \).

If pseparation is not NULL and during the search for a signed wheel-submatrix a 2-separation that does not correspond to an SP reduction is found then such a 2-separation is returned and the algorithm terminates without returning a signed wheel- or \( M_2 \)-submatrix. Note that *pseparation then contains row/column indices relative to \( A' \).

The running time is \( \mathcal{O} (m + n + k) \) assuming no hashtable collisions.

See also: CMRsubmatZoomSubmat() for turning *pviolatorSubmatrix into a submatrix of the SP-reduced submatrix.

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
pisSeriesParallel	Pointer for storing the result.
reductions	Array for storing the SP-reductions. If not `NULL`, it must have capacity at least number of rows + number of columns.
maxNumReductions	Maximum number of SP-reductions. Stops when this would be exceeded.
pnumReductions	Pointer for storing the number of SP-reductions; stores `SIZE_MAX` if **< `maxNumReductions` was exceeded.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a signed wheel- or \( M_2 \)-submatrix (may be `NULL`).
pseparation	Pointer for storing a 2-separation (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRspIsColumn()

static bool CMRspIsColumn ( CMR_SP_REDUCTION reduction )

inlinestatic

Returns true if the series-parallel reduction removes a column, i.e., is parallel.

Parameters