hereditary_property.c File Reference

#include "hereditary_property.h"
#include <stdint.h>
#include <time.h>

Functions
static CMR_ERROR	testHereditaryPropertyNaive (CMR *cmr, CMR_CHRMAT *current, HereditaryPropertyTest testFunction, void *testData, CMR_SUBMAT **psubmatrix, size_t numRemainingRows, size_t *remainingRows, size_t numRemainingColumns, size_t *remainingColumns, double timeLimit)
	Tests a submatrix of the given current matrix for the hereditary property defined by a given testFunction. More...
CMR_ERROR	CMRtestHereditaryPropertyNaive (CMR *cmr, CMR_CHRMAT *matrix, HereditaryPropertyTest testFunction, void *testData, CMR_SUBMAT **psubmatrix, double timeLimit)
	Tests a given matrix for the hereditary property defined by a given testFunction. More...
CMR_ERROR	CMRtestHereditaryPropertyGreedy (CMR *cmr, CMR_CHRMAT *matrix, HereditaryPropertyTest testFunction, void *testData, CMR_SUBMAT **psubmatrix, double timeLimit)
	Greedily tests a given matrix for the hereditary property defined by a given testFunction. More...

Function Documentation

CMRtestHereditaryPropertyGreedy()

CMR_ERROR CMRtestHereditaryPropertyGreedy	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		HereditaryPropertyTest	testFunction,
		void *	testData,
		CMR_SUBMAT **	psubmatrix,
		double	timeLimit
	)

Greedily tests a given matrix for the hereditary property defined by a given testFunction.

The algorithm finds the submatrix by successively zeroing out sets of rows or columns.

Parameters

cmr	CMR environment.
matrix	Some matrix not having the hereditary property.
testFunction	Test function.
testData	Data to be forwarded to the test function.
psubmatrix	Pointer for storing a minimal submatrix not having the property.
timeLimit	Time limit to impose.

CMRtestHereditaryPropertyNaive()

CMR_ERROR CMRtestHereditaryPropertyNaive	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		HereditaryPropertyTest	testFunction,
		void *	testData,
		CMR_SUBMAT **	psubmatrix,
		double	timeLimit
	)

Tests a given matrix for the hereditary property defined by a given testFunction.

The algorithm finds the submatrix by successively single zeroing out rows or columns.

Parameters

cmr	CMR environment.
matrix	Some matrix not having the hereditary property.
testFunction	Test function.
testData	Data to be forwarded to the test function.
psubmatrix	Pointer for storing a minimal submatrix not having the property.
timeLimit	Time limit to impose.

testHereditaryPropertyNaive()

static CMR_ERROR testHereditaryPropertyNaive ( CMR *  cmr, CMR_CHRMAT *  current, HereditaryPropertyTest  testFunction, void *  testData, CMR_SUBMAT **  psubmatrix, size_t  numRemainingRows, size_t *  remainingRows, size_t  numRemainingColumns, size_t *  remainingColumns, double  timeLimit  )

static

Tests a submatrix of the given current matrix for the hereditary property defined by a given testFunction.

The algorithm finds the submatrix by successively single zeroing out rows or columns. The submatrix is specified by remainingRows and remainingColumns. The current matrix is modified and later deleted.

Parameters

cmr	CMR environment.
current	Some matrix not having the hereditary property.
testFunction	Test function.
testData	Data to be forwarded to the test function.
psubmatrix	Pointer for storing a minimal submatrix not having the property.
numRemainingRows	Number of rows of submatrix to search in.
remainingRows	Rows of submatrix to search in.
numRemainingColumns	Number of columns of submatrix to search in.
remainingColumns	Columns of submatrix to search in.
timeLimit	Time limit to impose.