series_parallel.h File Reference

Recognition of series-parallel matrices. More...

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

Go to the source code of this file.

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. More...
CMR_EXPORT CMR_ERROR	CMRspStatsPrint (FILE *stream, CMR_SP_STATISTICS *stats, const char *prefix)
	Prints statistics for series-parallel computations. More...
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. More...
static bool	CMRspIsColumn (CMR_SP_REDUCTION reduction)
	Returns true if the series-parallel reduction removes a column, i.e., is parallel. More...
static bool	CMRspIsZero (CMR_SP_REDUCTION reduction)
	Returns true if the series-parallel reduction removes a zero vector. More...
static bool	CMRspIsUnit (CMR_SP_REDUCTION reduction)
	Returns true if the series-parallel reduction removes a unit vector. More...
static bool	CMRspIsCopy (CMR_SP_REDUCTION reduction)
	Returns true if the series-parallel reduction removes a vector that is a copy of another vector. More...
static bool	CMRspIsValid (CMR_SP_REDUCTION reduction)
	Returns true if the series-parallel reduction is valid. More...
CMR_EXPORT CMR_ERROR	CMRtestBinarySeriesParallel (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 \). More...
CMR_EXPORT CMR_ERROR	CMRtestTernarySeriesParallel (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 \). More...
CMR_EXPORT CMR_ERROR	CMRdecomposeBinarySeriesParallel (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 \). More...
CMR_EXPORT CMR_ERROR	CMRdecomposeTernarySeriesParallel (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 \). More...

Detailed Description

Recognition of series-parallel matrices.

Author

Matthias Walter

Function Documentation

CMRdecomposeBinarySeriesParallel()

CMR_EXPORT CMR_ERROR CMRdecomposeBinarySeriesParallel	(	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.

CMRdecomposeTernarySeriesParallel()

CMR_EXPORT CMR_ERROR CMRdecomposeTernarySeriesParallel	(	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

reduction

Series-parallel reduction.

CMRspIsCopy()

static bool CMRspIsCopy ( CMR_SP_REDUCTION  reduction )

inlinestatic

Returns true if the series-parallel reduction removes a vector that is a copy of another vector.

Parameters

reduction

Series-parallel reduction.

CMRspIsRow()

static bool CMRspIsRow ( CMR_SP_REDUCTION  reduction )

inlinestatic

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

Parameters

reduction

Series-parallel reduction.

CMRspIsUnit()

static bool CMRspIsUnit ( CMR_SP_REDUCTION  reduction )

inlinestatic

Returns true if the series-parallel reduction removes a unit vector.

Parameters

reduction

Series-parallel reduction.

CMRspIsValid()

static bool CMRspIsValid ( CMR_SP_REDUCTION  reduction )

inlinestatic

Returns true if the series-parallel reduction is valid.

Parameters

reduction

Series-parallel reduction.

CMRspIsZero()

static bool CMRspIsZero ( CMR_SP_REDUCTION  reduction )

inlinestatic

Returns true if the series-parallel reduction removes a zero vector.

Parameters

reduction

Series-parallel reduction.

CMRspReductionString()

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

Prints the series-parallel reduction to buffer.

Parameters

reduction	Series-parallel reduction.
buffer	Buffer to write to. If NULL, a static one is used which will be overwritten in the next call. Otherwise, it must hold at least 51 bytes.

CMRspStatsInit()

CMR_EXPORT CMR_ERROR CMRspStatsInit

(

CMR_SP_STATISTICS *

stats

)

Initializes all statistics for series-parallel computations.

Parameters

stats

Pointer to statistics.

CMRspStatsPrint()

CMR_EXPORT CMR_ERROR CMRspStatsPrint	(	FILE *	stream,
		CMR_SP_STATISTICS *	stats,
		const char *	prefix
	)

Prints statistics for series-parallel computations.

Parameters

stream	File stream to print to.
stats	Pointer to statistics.
prefix	Prefix string to prepend to each printed line (may be NULL).

CMRtestBinarySeriesParallel()

CMR_EXPORT CMR_ERROR CMRtestBinarySeriesParallel	(	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 \).

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 binary series-parallel, then a wheel-submatrix is stored.

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.
pnumReductions	Pointer for storing the number of SP-reductions.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be NULL).
pviolatorSubmatrix	Pointer for storing a wheel-submatrix (may be NULL).
stats	Pointer to statistics (may be NULL).
timeLimit	Time limit to impose.

CMRtestTernarySeriesParallel()

CMR_EXPORT CMR_ERROR CMRtestTernarySeriesParallel	(	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 \).

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.

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.
pnumReductions	Pointer for storing the number of SP-reductions.
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).
stats	Pointer to statistics (may be NULL).
timeLimit	Time limit to impose.