tu.h File Reference

Recognition of totally unimodular matrices. More...

#include <cmr/env.h>
#include <cmr/regular.h>
#include <cmr/matrix.h>
#include <cmr/camion.h>

Go to the source code of this file.

Classes
struct	CMR_TU_PARAMS
struct	CMR_TU_STATS
	Statistics for recognition algorithm for totally unimodular matrices. More...

Enumerations
enum	CMR_TU_ALGORITHM { CMR_TU_ALGORITHM_DECOMPOSITION = 0 , CMR_TU_ALGORITHM_EULERIAN = 1 , CMR_TU_ALGORITHM_PARTITION = 2 }

Functions
CMR_EXPORT CMR_ERROR	CMRtuParamsInit (CMR_TU_PARAMS *params)
	Initializes the default parameters for recognition of totally unimodular matrices. More...
CMR_EXPORT CMR_ERROR	CMRtuStatsInit (CMR_TU_STATS *stats)
	Initializes all statistics for recognition algorithm for totally unimodular matrices. More...
CMR_EXPORT CMR_ERROR	CMRtuStatsPrint (FILE *stream, CMR_TU_STATS *stats, const char *prefix)
	Prints statistics for recognition algorithm for totally unimodular matrices. More...
CMR_EXPORT CMR_ERROR	CMRtuTest (CMR *cmr, CMR_CHRMAT *matrix, bool *pisTotallyUnimodular, CMR_MATROID_DEC **pdec, CMR_SUBMAT **psubmatrix, CMR_TU_PARAMS *params, CMR_TU_STATS *stats, double timeLimit)
	Tests a matrix \( M \) for being totally unimodular. More...
CMR_EXPORT CMR_ERROR	CMRtuCompleteDecomposition (CMR *cmr, CMR_MATROID_DEC *dec, CMR_TU_PARAMS *params, CMR_TU_STATS *stats, double timeLimit)
	Completes a subtree of an existing decomposition tree. More...

Detailed Description

Recognition of totally unimodular matrices.

Author

Matthias Walter and Klaus Truemper

Enumeration Type Documentation

CMR_TU_ALGORITHM

enum CMR_TU_ALGORITHM

Enumerator
CMR_TU_ALGORITHM_DECOMPOSITION	Algorithm based on Seymour's decomposition of regular matroids.
CMR_TU_ALGORITHM_EULERIAN	Enumeration algorithm based on Eulerian submatrices.
CMR_TU_ALGORITHM_PARTITION	Enumeration algorithm based on criterion of Ghouila-Houri.

Function Documentation

CMRtuCompleteDecomposition()

CMR_EXPORT CMR_ERROR CMRtuCompleteDecomposition	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		CMR_TU_PARAMS *	params,
		CMR_TU_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.

Note

Requires params.algorithm to be CMR_TU_ALGORITHM_DECOMPOSITION.

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.

CMRtuParamsInit()

CMR_EXPORT CMR_ERROR CMRtuParamsInit

(

CMR_TU_PARAMS *

params

)

Initializes the default parameters for recognition of totally unimodular matrices.

These are selected for minimum running time.

Parameters

params

Pointer to parameters.

CMRtuStatsInit()

CMR_EXPORT CMR_ERROR CMRtuStatsInit

(

CMR_TU_STATS *

stats

)

Initializes all statistics for recognition algorithm for totally unimodular matrices.

Parameters

stats

Pointer to statistics.

CMRtuStatsPrint()

CMR_EXPORT CMR_ERROR CMRtuStatsPrint	(	FILE *	stream,
		CMR_TU_STATS *	stats,
		const char *	prefix
	)

Prints statistics for recognition algorithm for 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).

CMRtuTest()

CMR_EXPORT CMR_ERROR CMRtuTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisTotallyUnimodular,
		CMR_MATROID_DEC **	pdec,
		CMR_SUBMAT **	psubmatrix,
		CMR_TU_PARAMS *	params,
		CMR_TU_STATS *	stats,
		double	timeLimit
	)

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

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

If \( M \) is totally unimodular and pdec != NULL, then *pdec will contain a decomposition tree of the regular matroid. The caller must release it via CMRdecFree().

If \( M \) is not totally unimodular and psubmatrix != NULL, then *psubmatrix will indicate a submatrix of \( M \) with determinant \( -2 \) or \( 2 \).

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisTotallyUnimodular	Pointer for storing whether \( M \) is totally unimodular.
pdec	Pointer for storing the decomposition tree (may be NULL).
psubmatrix	Pointer for storing a submatrix with non-ternary determinant (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.