ctu.c File Reference

#include <cmr/ctu.h>
#include <cmr/tu.h>
#include "env_internal.h"
#include <assert.h>
#include <stdint.h>
#include <time.h>
#include <float.h>

Functions
CMR_ERROR	CMRctuParamsInit (CMR_CTU_PARAMS *params)
	Initializes the default parameters for recognition of complement totally unimodular matrices. More...
CMR_ERROR	CMRstatsComplementTotalUnimodularityInit (CMR_CTU_STATISTICS *stats)
	Initializes all statistics for recognition algorithm for complement totally unimodular matrices. More...
CMR_ERROR	CMRstatsComplementTotalUnimodularityPrint (FILE *stream, CMR_CTU_STATISTICS *stats, const char *prefix)
	Prints statistics for recognition algorithm for complement totally unimodular matrices. More...
CMR_ERROR	CMRctuComplementRowColumn (CMR *cmr, CMR_CHRMAT *matrix, size_t complementRow, size_t complementColumn, CMR_CHRMAT **presult)
	Carries out a row- and column-complement operations on the binary matrix. More...
CMR_ERROR	CMRctuTest (CMR *cmr, CMR_CHRMAT *matrix, bool *pisComplementTotallyUnimodular, size_t *pcomplementRow, size_t *pcomplementColumn, CMR_CTU_PARAMS *params, CMR_CTU_STATISTICS *stats, double timeLimit)
	Tests a matrix \( M \) for being complement totally unimodular. More...

Function Documentation

CMRctuComplementRowColumn()

CMR_ERROR CMRctuComplementRowColumn	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	complementRow,
		size_t	complementColumn,
		CMR_CHRMAT **	presult
	)

Carries out a row- and column-complement operations on the binary matrix.

Parameters

cmr	CMR environment
matrix	Input matrix.
complementRow	Row to be complemented (SIZE_MAX for no row complement).
complementColumn	Column to be complemented (SIZE_MAX for no column complement).
presult	Resulting matrix.

CMRctuParamsInit()

CMR_ERROR CMRctuParamsInit

(

CMR_CTU_PARAMS *

params

)

Initializes the default parameters for recognition of complement totally unimodular matrices.

These are selected for minimum running time.

Parameters

params

Pointer to parameters.

CMRctuTest()

CMR_ERROR CMRctuTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisComplementTotallyUnimodular,
		size_t *	pcomplementRow,
		size_t *	pcomplementColumn,
		CMR_CTU_PARAMS *	params,
		CMR_CTU_STATISTICS *	stats,
		double	timeLimit
	)

Tests a matrix \( M \) for being complement totally unimodular.

Tests if matrix \( M \) is complement totally unimodular and sets *pisComplementTotallyUnimodular accordingly.

If \( M \) is not complement totally unimodular and pcomplementRow != NULL and pcomplementColumn != NULL, then *pcomplementRow and *pcomplementColumn will indicate the row and column that need to be complemented for obtaining a matrix that is not totally unimodular. If no row/column needs to be complemented, then the respective variables are set to SIZE_MAX.

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisComplementTotallyUnimodular	Pointer for storing whether \( M \) is complement totally unimodular.
pcomplementRow	Pointer for storing the row to be complemented (may be NULL).
pcomplementColumn	Pointer for storing the column to be complemented (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.

CMRstatsComplementTotalUnimodularityInit()

CMR_ERROR CMRstatsComplementTotalUnimodularityInit

(

CMR_CTU_STATISTICS *

stats

)

Initializes all statistics for recognition algorithm for complement totally unimodular matrices.

Parameters

stats

Pointer to statistics.

CMRstatsComplementTotalUnimodularityPrint()

CMR_ERROR CMRstatsComplementTotalUnimodularityPrint	(	FILE *	stream,
		CMR_CTU_STATISTICS *	stats,
		const char *	prefix
	)

Prints statistics for recognition algorithm for complement totally unimodular matrices.

Parameters

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