#include <cmr/tu.h>
#include "matrix_internal.h"
#include "block_decomposition.h"
#include "camion_internal.h"
#include "hereditary_property.h"
#include "seymour_internal.h"
#include <stdlib.h>
#include <assert.h>
#include <time.h>

Classes
struct	CMR_TU_ENUMERATION
	Data for enumeration. More...

Functions
CMR_ERROR	CMRtuParamsInit (CMR_TU_PARAMS *params)
	Initializes the default parameters for recognition of totally unimodular matrices.

CMR_ERROR	CMRtuStatsInit (CMR_TU_STATS *stats)
	Initializes all statistics for recognition algorithm for totally unimodular matrices.

CMR_ERROR	CMRtuStatsPrint (FILE stream, CMR_TU_STATS stats, const char *prefix)
	Prints statistics for recognition algorithm for totally unimodular matrices.

static CMR_ERROR	tuDecomposition (CMR cmr, CMR_CHRMAT matrix, void data, bool pisTotallyUnimodular, CMR_SUBMAT **psubmatrix, double timeLimit)

static CMR_ERROR	tuEulerianColumns (CMR_TU_ENUMERATION *enumeration, size_t numColumns)
	Recursive enumeration of column subsets and subsequent testing of Eulerian submatrix.

static bool	tuEulerianRows (CMR_TU_ENUMERATION *enumeration, size_t numRows)
	Recursive enumeration of row subsets and subsequent testing of total unimodularity.

static CMR_ERROR	tuEulerian (CMR cmr, CMR_CHRMAT matrix, bool isTransposed, bool pisTotallyUnimodular, CMR_SUBMAT psubmatrix, CMR_TU_STATS stats, double timeLimit)
	Submatrix test.

static bool	tuPartitionSearch (CMR cmr, CMR_CHRMAT matrix, int8_t selection, size_t current, int columnSum)
	Recursively assigns +1 or -1 to each row that is part of the subset to test Ghouila-Houri.

static int	tuPartitionSubset (CMR cmr, CMR_CHRMAT matrix, bool transposed, int8_t selection, size_t current, int columnSum, CMR_TU_STATS *stats, clock_t startClock, double timeLimit)
	Recursively selects a row subset and tests Ghouila-Houri for each.

static CMR_ERROR	tuPartition (CMR cmr, CMR_CHRMAT matrix, bool transposed, bool pisTotallyUnimodular, CMR_TU_STATS stats, double timeLimit)
	Partition test based on Ghouila-Houri.

CMR_ERROR	CMRtuTest (CMR cmr, CMR_CHRMAT matrix, bool pisTotallyUnimodular, CMR_SEYMOUR_NODE proot, CMR_SUBMAT psubmatrix, CMR_TU_PARAMS params, CMR_TU_STATS *stats, double timeLimit)
	Tests a matrix \( M \) for being totally unimodular.

CMR_ERROR	CMRtuCompleteDecomposition (CMR cmr, CMR_SEYMOUR_NODE dec, CMR_TU_PARAMS params, CMR_TU_STATS stats, double timeLimit)
	Completes a subtree of an existing decomposition tree.

Function Documentation

◆ CMRtuCompleteDecomposition()

CMR_ERROR CMRtuCompleteDecomposition	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	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_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_ERROR CMRtuStatsInit ( CMR_TU_STATS * stats )

Initializes all statistics for recognition algorithm for totally unimodular matrices.

Parameters

stats Pointer to statistics.

◆ CMRtuStatsPrint()

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_ERROR CMRtuTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisTotallyUnimodular,
		CMR_SEYMOUR_NODE **	proot,
		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.
proot	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.

◆ tuDecomposition()

static CMR_ERROR tuDecomposition	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		void *	data,
		bool *	pisTotallyUnimodular,
		CMR_SUBMAT **	psubmatrix,
		double	timeLimit
	)

static

Parameters

cmr	CMR environment.
matrix	Some matrix to be tested for total unimodularity.
data	Additional data (must be `NULL`).
pisTotallyUnimodular	Pointer for storing whether `matrix` is totally unimodular.
psubmatrix	Pointer for storing a proper non-totally unimodular submatrix of `matrix`.
timeLimit	Time limit to impose.

◆ tuEulerian()

static CMR_ERROR tuEulerian	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool	isTransposed,
		bool *	pisTotallyUnimodular,
		CMR_SUBMAT **	psubmatrix,
		CMR_TU_STATS *	stats,
		double	timeLimit
	)

static

Submatrix test.

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
isTransposed	Whether we're dealing with the transpose.
pisTotallyUnimodular	Pointer for storing whether \( M \) is totally unimodular.
psubmatrix	Pointer for storing the submatrix.
stats	Statistics.
timeLimit	Time limit to impose.

◆ tuEulerianColumns()

static CMR_ERROR tuEulerianColumns	(	CMR_TU_ENUMERATION *	enumeration,
		size_t	numColumns
	)

static

Recursive enumeration of column subsets and subsequent testing of Eulerian submatrix.

Parameters

enumeration	Enumeration information.
numColumns	Number of already selected columns.

◆ tuEulerianRows()

static bool tuEulerianRows	(	CMR_TU_ENUMERATION *	enumeration,
		size_t	numRows
	)

static

Recursive enumeration of row subsets and subsequent testing of total unimodularity.

Returns: true if we can stop (due to time limit or a found violating submatrix).

Parameters

enumeration	Enumeration information.
numRows	Number of already selected rows.

◆ tuPartition()

static CMR_ERROR tuPartition	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool	transposed,
		bool *	pisTotallyUnimodular,
		CMR_TU_STATS *	stats,
		double	timeLimit
	)

static

Partition test based on Ghouila-Houri.

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
transposed	Whether we're dealing with the transposed .
pisTotallyUnimodular	Pointer for storing whether \( M \) is totally unimodular.
stats	Statistics.
timeLimit	Time limit to impose.

◆ tuPartitionSearch()

static bool tuPartitionSearch	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		int8_t *	selection,
		size_t	current,
		int *	columnSum
	)

static

Recursively assigns +1 or -1 to each row that is part of the subset to test Ghouila-Houri.

Returns: whether a feasible assignment was found.

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
selection	Array with selection.
current	Index to decide for selection.
columnSum	Array for computing column sums.

◆ tuPartitionSubset()

static int tuPartitionSubset	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool	transposed,
		int8_t *	selection,
		size_t	current,
		int *	columnSum,
		CMR_TU_STATS *	stats,
		clock_t	startClock,
		double	timeLimit
	)

static

Recursively selects a row subset and tests Ghouila-Houri for each.

Returns: 1 if totally unimodular, 0 if not, and -1 if time limit was reached.

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
transposed	Whether we're dealing with the transpose.
selection	Array with selection.
current	Index to decide for selection.
columnSum	Array for computing column sums.
stats	Statistics.
startClock	Clock for start for computation.
timeLimit	Time limit for computation.

Classes

Functions

Function Documentation

◆ CMRtuCompleteDecomposition()

◆ CMRtuParamsInit()

◆ CMRtuStatsInit()

◆ CMRtuStatsPrint()

◆ CMRtuTest()

◆ tuDecomposition()

◆ tuEulerian()

◆ tuEulerianColumns()

◆ tuEulerianRows()

◆ tuPartition()

◆ tuPartitionSearch()

◆ tuPartitionSubset()