#include <cmr/balanced.h>
#include <cmr/camion.h>
#include <cmr/series_parallel.h>
#include "env_internal.h"
#include "block_decomposition.h"
#include "sort.h"
#include "matrix_internal.h"
#include "camion_internal.h"
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <time.h>

Classes
struct	CMR_BALANCED_ENUMERATION
	Data for enumeration. More...

Functions
CMR_ERROR	CMRbalancedParamsInit (CMR_BALANCED_PARAMS *params)
	Initializes the default parameters for recognition of balanced matrices.

CMR_ERROR	CMRbalancedStatsInit (CMR_BALANCED_STATS *stats)
	Initializes all statistics for recognition algorithm for balanced matrices.

CMR_ERROR	CMRbalancedStatsPrint (FILE stream, CMR_BALANCED_STATS stats, const char *prefix)
	Prints statistics for recognition algorithm for balanced matrices.

static CMR_ERROR	balancedTestEnumerateColumns (CMR_BALANCED_ENUMERATION *enumeration, size_t numColumns)
	Recursive enumeration of column subsets and subsequent testing of balancedness.

static bool	balancedTestEnumerateRows (CMR_BALANCED_ENUMERATION *enumeration, size_t numRows)
	Recursive enumeration of row subsets and subsequent testing of balancedness.

static CMR_ERROR	balancedTestEnumerate (CMR cmr, CMR_CHRMAT matrix, bool pisBalanced, CMR_SUBMAT psubmatrix, CMR_BALANCED_STATS stats, double timeLimit, bool isTransposed)
	Tests a connected series-parallel reduced matrix \( M \) for being balanced using the enumeration algorithm.

static CMR_ERROR	balancedTestGraph (CMR cmr, CMR_CHRMAT matrix, bool pisBalanced, CMR_SUBMAT psubmatrix, CMR_BALANCED_PARAMS params, CMR_BALANCED_STATS *stats, double timeLimit)
	Tests a connected series-parallel reduced matrix \( M \) for being balanced using the graph-based algorithm.

static CMR_ERROR	balancedTestChooseAlgorithm (CMR cmr, CMR_CHRMAT matrix, bool pisBalanced, CMR_SUBMAT psubmatrix, CMR_BALANCED_PARAMS params, CMR_BALANCED_STATS *stats, double timeLimit)
	Tests a connected (potentially SP-reduced) matrix \( M \) for being balanced.

static CMR_ERROR	balancedTestConnected (CMR cmr, CMR_CHRMAT matrix, bool pisBalanced, CMR_SUBMAT psubmatrix, CMR_BALANCED_PARAMS params, CMR_BALANCED_STATS *stats, double timeLimit)
	Tests a connected matrix \( M \) for being balanced.

int	compareBlockComponents (const void a, const void b)
	Compares two matrix blocks according to minimum of number of rows and number of columns.

CMR_ERROR	CMRbalancedTest (CMR cmr, CMR_CHRMAT matrix, bool pisBalanced, CMR_SUBMAT psubmatrix, CMR_BALANCED_PARAMS params, CMR_BALANCED_STATS *stats, double timeLimit)
	Tests a matrix \( M \) for being balanced.

Function Documentation

◆ balancedTestChooseAlgorithm()

static CMR_ERROR balancedTestChooseAlgorithm	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisBalanced,
		CMR_SUBMAT **	psubmatrix,
		CMR_BALANCED_PARAMS *	params,
		CMR_BALANCED_STATS *	stats,
		double	timeLimit
	)

static

Tests a connected (potentially SP-reduced) matrix \( M \) for being balanced.

Calls the algorithm requested by params.

If \( M \) is not balanced and psubmatrix != NULL, then *psubmatrix will indicate a submatrix of \( M \) with exactly two nonzeros in each row and in each column and with determinant \( -2 \) or \( 2 \).

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisBalanced	Pointer for storing whether \( M \) is balanced.
psubmatrix	Pointer for storing a minimal nonbalanced submatrix (may be `NULL`).
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ balancedTestConnected()

static CMR_ERROR balancedTestConnected	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisBalanced,
		CMR_SUBMAT **	psubmatrix,
		CMR_BALANCED_PARAMS *	params,
		CMR_BALANCED_STATS *	stats,
		double	timeLimit
	)

static

Tests a connected matrix \( M \) for being balanced.

Tries to apply series-parallel reductions and then calls balancedTestChooseAlgorithm.

If \( M \) is not balanced and psubmatrix != NULL, then *psubmatrix will indicate a submatrix of \( M \) with exactly two nonzeros in each row and in each column and with determinant \( -2 \) or \( 2 \).

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisBalanced	Pointer for storing whether \( M \) is balanced.
psubmatrix	Pointer for storing a minimal nonbalanced submatrix (may be `NULL`).
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ balancedTestEnumerate()

static CMR_ERROR balancedTestEnumerate	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisBalanced,
		CMR_SUBMAT **	psubmatrix,
		CMR_BALANCED_STATS *	stats,
		double	timeLimit,
		bool	isTransposed
	)

static

Tests a connected series-parallel reduced matrix \( M \) for being balanced using the enumeration algorithm.

If \( M \) is not balanced and psubmatrix != NULL, then *psubmatrix will indicate a submatrix of \( M \) with exactly two nonzeros in each row and in each column and with determinant \( -2 \) or \( 2 \).

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisBalanced	Pointer for storing whether \( M \) is balanced.
psubmatrix	Pointer for storing a minimal nonbalanced submatrix (may be `NULL`).
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.
isTransposed	Whether we're dealing with the transposed matrix.

◆ balancedTestEnumerateColumns()

static CMR_ERROR balancedTestEnumerateColumns	(	CMR_BALANCED_ENUMERATION *	enumeration,
		size_t	numColumns
	)

static

Recursive enumeration of column subsets and subsequent testing of balancedness.

Parameters

enumeration	Enumeration information.
numColumns	Number of already selected columns.

◆ balancedTestEnumerateRows()

static bool balancedTestEnumerateRows	(	CMR_BALANCED_ENUMERATION *	enumeration,
		size_t	numRows
	)

static

Recursive enumeration of row subsets and subsequent testing of balancedness.

Returns: true if we can stop (due to time limit or a found violating submatrix).

Parameters

enumeration	Enumeration information.
numRows	Number of already selected rows.

◆ balancedTestGraph()

static CMR_ERROR balancedTestGraph	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisBalanced,
		CMR_SUBMAT **	psubmatrix,
		CMR_BALANCED_PARAMS *	params,
		CMR_BALANCED_STATS *	stats,
		double	timeLimit
	)

static

Tests a connected series-parallel reduced matrix \( M \) for being balanced using the graph-based algorithm.

If \( M \) is not balanced and psubmatrix != NULL, then *psubmatrix will indicate a submatrix of \( M \) with exactly two nonzeros in each row and in each column and with determinant \( -2 \) or \( 2 \).

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisBalanced	Pointer for storing whether \( M \) is balanced.
psubmatrix	Pointer for storing a minimal nonbalanced submatrix (may be `NULL`).
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRbalancedParamsInit()

CMR_ERROR CMRbalancedParamsInit ( CMR_BALANCED_PARAMS * params )

Initializes the default parameters for recognition of balanced matrices.

Parameters

params Pointer to parameters.

◆ CMRbalancedStatsInit()

CMR_ERROR CMRbalancedStatsInit ( CMR_BALANCED_STATS * stats )

Initializes all statistics for recognition algorithm for balanced matrices.

Parameters

stats Pointer to statistics.

◆ CMRbalancedStatsPrint()

CMR_ERROR CMRbalancedStatsPrint	(	FILE *	stream,
		CMR_BALANCED_STATS *	stats,
		const char *	prefix
	)

Prints statistics for recognition algorithm for balanced matrices.

Parameters

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

◆ CMRbalancedTest()

CMR_ERROR CMRbalancedTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisBalanced,
		CMR_SUBMAT **	psubmatrix,
		CMR_BALANCED_PARAMS *	params,
		CMR_BALANCED_STATS *	stats,
		double	timeLimit
	)

Tests a matrix \( M \) for being balanced.

Tests if matrix \( M \) is balanced and sets *pisBalanced accordingly. Automatically decides which algorithm to use.

If \( M \) is not balanced and psubmatrix != NULL, then *psubmatrix will indicate a submatrix of \( M \) with exactly two nonzeros in each row and in each column and with determinant \( -2 \) or \( 2 \).

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisBalanced	Pointer for storing whether \( M \) is balanced.
psubmatrix	Pointer for storing a minimal nonbalanced submatrix (may be `NULL`).
params	Parameters for the computation (may be `NULL` for defaults).
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ compareBlockComponents()

int compareBlockComponents	(	const void *	a,
		const void *	b
	)

Compares two matrix blocks according to minimum of number of rows and number of columns.

Classes

Functions

Function Documentation

◆ balancedTestChooseAlgorithm()

◆ balancedTestConnected()

◆ balancedTestEnumerate()

◆ balancedTestEnumerateColumns()

◆ balancedTestEnumerateRows()

◆ balancedTestGraph()

◆ CMRbalancedParamsInit()

◆ CMRbalancedStatsInit()

◆ CMRbalancedStatsPrint()

◆ CMRbalancedTest()

◆ compareBlockComponents()