regularity.c File Reference

#include "env_internal.h"
#include "regularity_internal.h"
#include <time.h>

Functions
CMR_ERROR	CMRregularityTaskCreateRoot (CMR *cmr, CMR_MATROID_DEC *dec, DecompositionTask **ptask, CMR_REGULAR_PARAMS *params, CMR_REGULAR_STATS *stats, clock_t startClock, double timeLimit)
	Creates a decomposition task for the root of the decomposition. More...
CMR_ERROR	CMRregularityTaskFree (CMR *cmr, DecompositionTask **ptask)
	Frees a decomposition task. More...
CMR_ERROR	CMRregularityQueueCreate (CMR *cmr, DecompositionQueue **pqueue)
	Initializes a decomposition queue. More...
CMR_ERROR	CMRregularityQueueFree (CMR *cmr, DecompositionQueue **pqueue)
	Frees the decomposition queue. More...
bool	CMRregularityQueueEmpty (DecompositionQueue *queue)
	Returns whether a queue is empty. More...
DecompositionTask *	CMRregularityQueueRemove (DecompositionQueue *queue)
	Removes a task from a decomposition queue. More...
void	CMRregularityQueueAdd (DecompositionQueue *queue, DecompositionTask *task)
	Adds a task to a decomposition queue. More...
static CMR_ERROR	CMRregularityTaskRun (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Runs a task for processing the associated decomposition node. More...
CMR_ERROR	CMRregularityTest (CMR *cmr, CMR_CHRMAT *matrix, bool ternary, bool *pisRegular, CMR_MATROID_DEC **pdec, CMR_MINOR **pminor, CMR_REGULAR_PARAMS *params, CMR_REGULAR_STATS *stats, double timeLimit)
	Tests ternary or binary linear matroid for regularity. More...
CMR_ERROR	CMRregularityCompleteDecomposition (CMR *cmr, CMR_MATROID_DEC *subtree, CMR_REGULAR_PARAMS *params, CMR_REGULAR_STATS *stats, double timeLimit)
	Replaces the subtree of a matroid decomposition tree by a new one. More...

Function Documentation

CMRregularityCompleteDecomposition()

CMR_ERROR CMRregularityCompleteDecomposition	(	CMR *	cmr,
		CMR_MATROID_DEC *	subtree,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		double	timeLimit
	)

Replaces the subtree of a matroid decomposition tree by a new one.

Parameters

cmr	CMR environment.
subtree	Decomposition node of the subtree root.
params	Parameters for the computation.
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.

CMRregularityQueueAdd()

void CMRregularityQueueAdd	(	DecompositionQueue *	queue,
		DecompositionTask *	task
	)

Adds a task to a decomposition queue.

Parameters

queue	Queue.
task	Task.

CMRregularityQueueCreate()

CMR_ERROR CMRregularityQueueCreate	(	CMR *	cmr,
		DecompositionQueue **	pqueue
	)

Initializes a decomposition queue.

Parameters

cmr	CMR environment.
pqueue	Pointer for storing the queue.

CMRregularityQueueEmpty()

bool CMRregularityQueueEmpty

(

DecompositionQueue *

queue

)

Returns whether a queue is empty.

Parameters

queue

Queue.

CMRregularityQueueFree()

CMR_ERROR CMRregularityQueueFree	(	CMR *	cmr,
		DecompositionQueue **	pqueue
	)

Frees the decomposition queue.

Parameters

cmr	CMR environment.
pqueue	Pointer to queue.

CMRregularityQueueRemove()

DecompositionTask* CMRregularityQueueRemove

(

DecompositionQueue *

queue

)

Removes a task from a decomposition queue.

Parameters

queue

Queue.

CMRregularityTaskCreateRoot()

CMR_ERROR CMRregularityTaskCreateRoot	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		DecompositionTask **	ptask,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		clock_t	startClock,
		double	timeLimit
	)

Creates a decomposition task for the root of the decomposition.

Parameters

cmr	CMR environment.
dec	Decomposition node.
ptask	Pointer for storing the new task.
params	Parameters for the computation.
stats	Statistics for the computation (may be NULL).
startClock	Clock for the start time.
timeLimit	Time limit to impose.

CMRregularityTaskFree()

CMR_ERROR CMRregularityTaskFree	(	CMR *	cmr,
		DecompositionTask **	ptask
	)

Frees a decomposition task.

Parameters

cmr	CMR environment.
ptask	Pointer to task.

CMRregularityTaskRun()

static CMR_ERROR CMRregularityTaskRun ( CMR *  cmr, DecompositionTask *  task, DecompositionQueue *  queue  )

static

Runs a task for processing the associated decomposition node.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
queue	Queue of unprocessed tasks.

CMRregularityTest()

CMR_ERROR CMRregularityTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool	ternary,
		bool *	pisRegular,
		CMR_MATROID_DEC **	pdec,
		CMR_MINOR **	pminor,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		double	timeLimit
	)

Tests ternary or binary linear matroid for regularity.

If pdec is not NULL, *pdec will be a (partial) decomposition tree.

If pminor is not NULL and matrix is not regular, then an \( F_7 \) or \( F_7^\star \) minor or a submatrix with non-ternary determinant is searched. This causes additional computational effort!

Parameters

cmr	CMR environment.
matrix	Input matrix.
ternary	Whether the matrix shall be considered ternary.
pisRegular	Pointer for storing whether matrix is regular.
pdec	Pointer for storing the decomposition tree (may be NULL).
pminor	Pointer for storing an \( F_7 \) or \( F_7^\star \) minor.
params	Parameters for the computation.
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.