regular.c File Reference

#include <cmr/regular.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include "env_internal.h"
#include "seymour_internal.h"

Functions
CMR_ERROR	CMRregularParamsInit (CMR_REGULAR_PARAMS *params)
	Initializes the default parameters for regularity testing.
CMR_ERROR	CMRregularStatsInit (CMR_REGULAR_STATS *stats)
	Initializes all statistics for regularity test computations.
CMR_ERROR	CMRregularStatsPrint (FILE *stream, CMR_REGULAR_STATS *stats, const char *prefix)
	Prints statistics for regularity test computations.
CMR_ERROR	CMRregularTest (CMR *cmr, CMR_CHRMAT *matrix, bool *pisRegular, CMR_SEYMOUR_NODE **proot, CMR_MINOR **pminor, CMR_REGULAR_PARAMS *params, CMR_REGULAR_STATS *stats, double timeLimit)
	Tests binary linear matroid for regularity.
CMR_ERROR	CMRregularCompleteDecomposition (CMR *cmr, CMR_SEYMOUR_NODE *dec, CMR_REGULAR_PARAMS *params, CMR_REGULAR_STATS *stats, double timeLimit)
	Completes a subtree of an existing decomposition tree.
CMR_ERROR	CMRregularRefineDecomposition (CMR *cmr, size_t numNodes, CMR_SEYMOUR_NODE **nodes, CMR_REGULAR_PARAMS *params, CMR_REGULAR_STATS *stats, double timeLimit)
	Refines a list of decomposition nodes.

Function Documentation

CMRregularCompleteDecomposition()

CMR_ERROR CMRregularCompleteDecomposition	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	dec,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		double	timeLimit
	)

Completes a subtree of an existing decomposition tree.

Replace the node's subtree by a new one even if it exists. Note that different parameters may yield a different subtree.

Parameters

cmr	CMR environment.
dec	Pointer to the decomposition node that is the root of the new subtree.
params	Parameters for the computation (may be NULL).
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.

CMRregularParamsInit()

CMR_ERROR CMRregularParamsInit

(

CMR_REGULAR_PARAMS *

params

)

Initializes the default parameters for regularity testing.

These are selected for minimum running time.

Parameters

params

Pointer to parameters.

CMRregularRefineDecomposition()

CMR_ERROR CMRregularRefineDecomposition	(	CMR *	cmr,
		size_t	numNodes,
		CMR_SEYMOUR_NODE **	nodes,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		double	timeLimit
	)

Refines a list of decomposition nodes.

Replace the nodes' subtrees by new ones even if they exist.

Parameters

cmr	CMR environment.
numNodes	Number of nodes to refine.
nodes	Array of decomposition nodes to refine.
params	Parameters for the computation (may be NULL).
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.

CMRregularStatsInit()

CMR_ERROR CMRregularStatsInit

(

CMR_REGULAR_STATS *

stats

)

Initializes all statistics for regularity test computations.

Parameters

stats

Pointer to statistics.

CMRregularStatsPrint()

CMR_ERROR CMRregularStatsPrint	(	FILE *	stream,
		CMR_REGULAR_STATS *	stats,
		const char *	prefix
	)

Prints statistics for regularity test computations.

Parameters

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

CMRregularTest()

CMR_ERROR CMRregularTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisRegular,
		CMR_SEYMOUR_NODE **	proot,
		CMR_MINOR **	pminor,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		double	timeLimit
	)

Tests binary linear matroid for regularity.

If pdec is not NULL, *pdec will be a (partial) decomposition tree. If completeTree is true, then the decomposition tree is complete. Otherwise, it must only contain sufficient information in order to determine regularity.

If pminor is not NULL and matrix is not regular, then an \( F_7 \) or \( F_7^\star \) minor is searched. This causes additional computational effort!

Parameters

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