regular.h File Reference

Recognition of regular matrices. More...

#include <cmr/env.h>
#include <cmr/matrix.h>
#include <cmr/matroid.h>
#include <cmr/graph.h>
#include <cmr/series_parallel.h>
#include <cmr/graphic.h>
#include <cmr/network.h>

Go to the source code of this file.

Classes
struct	CMR_REGULAR_PARAMS
struct	CMR_REGULAR_STATS
	Statistics for regular matroid recognition algorithm. More...

Enumerations
enum	CMR_DEC_CONSTRUCT { CMR_DEC_CONSTRUCT_NONE = 0 , CMR_DEC_CONSTRUCT_LEAVES = 1 , CMR_DEC_CONSTRUCT_ALL = 2 }
enum	CMR_REGULAR_TREE_FLAGS {   CMR_REGULAR_TREE_FLAGS_RECURSE = 1 , CMR_REGULAR_TREE_FLAGS_STOP_IRREGULAR = 2 , CMR_REGULAR_TREE_FLAGS_STOP_NONGRAPHIC = 4 , CMR_REGULAR_TREE_FLAGS_STOP_NONCOGRAPHIC = 8 ,   CMR_REGULAR_TREE_FLAGS_STOP_NONGRAPHIC_NONCOGRAPHIC = 16 , CMR_REGULAR_TREE_FLAGS_DEFAULT = CMR_REGULAR_TREE_FLAGS_RECURSE | CMR_REGULAR_TREE_FLAGS_STOP_IRREGULAR }
	Flags that control termination of the regular matroid decomposition algorithm. More...

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

Detailed Description

Recognition of regular matrices.

Author

Matthias Walter and Klaus Truemper

Enumeration Type Documentation

CMR_DEC_CONSTRUCT

enum CMR_DEC_CONSTRUCT

Enumerator
CMR_DEC_CONSTRUCT_NONE
CMR_DEC_CONSTRUCT_LEAVES
CMR_DEC_CONSTRUCT_ALL

CMR_REGULAR_TREE_FLAGS

enum CMR_REGULAR_TREE_FLAGS

Flags that control termination of the regular matroid decomposition algorithm.

See also

The desired types can be set by modifying CMR_REGULAR_PARAMS::treeFlags.

Enumerator
CMR_REGULAR_TREE_FLAGS_RECURSE	Do not process child nodes.
CMR_REGULAR_TREE_FLAGS_STOP_IRREGULAR	Stop if a (grand-)child is irregular.
CMR_REGULAR_TREE_FLAGS_STOP_NONGRAPHIC	Stop if a (grand-)child is non-graphic.
CMR_REGULAR_TREE_FLAGS_STOP_NONCOGRAPHIC	Stop if a (grand-)child is non-cographic.
CMR_REGULAR_TREE_FLAGS_STOP_NONGRAPHIC_NONCOGRAPHIC	Stop if a (grand-)child is non-graphic and non-cographic.
CMR_REGULAR_TREE_FLAGS_DEFAULT

Function Documentation

CMRregularCompleteDecomposition()

CMR_EXPORT CMR_ERROR CMRregularCompleteDecomposition	(	CMR *	cmr,
		CMR_MATROID_DEC *	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.s

Parameters

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

CMRregularParamsInit()

CMR_EXPORT 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.

CMRregularStatsInit()

CMR_EXPORT CMR_ERROR CMRregularStatsInit

(

CMR_REGULAR_STATS *

stats

)

Initializes all statistics for regularity test computations.

Parameters

stats

Pointer to statistics.

CMRregularStatsPrint()

CMR_EXPORT 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_EXPORT CMR_ERROR CMRregularTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisRegular,
		CMR_MATROID_DEC **	pdec,
		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.
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 (may be NULL for defaults).
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.