#include "dec_internal.h"
#include "regular_internal.h"
#include "env_internal.h"
#include "densematrix.h"
#include "hashtable.h"
#include <time.h>

Classes
struct	ElementData
	Element specific data for the enumeration of 3-separations. More...

Functions
static CMR_ERROR	createHashVector (CMR cmr, long long *phashVector, size_t size)

static CMR_ERROR	initializeHashing (CMR cmr, DenseBinaryMatrix dense, ElementData majorData, CMR_LISTHASHTABLE majorHashtable, size_t numMajors, size_t processedMinors, size_t numProcessedMinors, long long hashVector, bool isRow)

static CMR_ERROR	updateRepresentative (CMR cmr, DenseBinaryMatrix dense, ElementData majorData, CMR_LISTHASHTABLE majorHashtable, size_t *processedMinors, size_t numProcessedMinors, size_t majorIndex, bool isRow)
	Ensures that the representative entry for row/column `index` is correct. More...

static CMR_ERROR	updateHashtable (CMR cmr, ElementData majorData, size_t processedMajors, size_t numProcessedMajors, CMR_LISTHASHTABLE majorHashtable)

static CMR_ERROR	prepareSearch (CMR cmr, DenseBinaryMatrix matrix, ElementData rowData, ElementData columnData, CMR_ELEMENT *pstartElement)

static CMR_ERROR	searchShortestPath (CMR cmr, DenseBinaryMatrix dense, ElementData rowData, ElementData columnData, CMR_ELEMENT *preachedTarget)

static CMR_ERROR	pivot (CMR cmr, DenseBinaryMatrix dense, size_t pivotRow, size_t pivotColumn)

static CMR_ERROR	applyPivots (CMR cmr, DenseBinaryMatrix dense, ElementData rowData, ElementData columnData, CMR_ELEMENT reachedTarget, CMR_ELEMENT *newElements)

static CMR_ERROR	addElement (CMR cmr, CMR_DEC dec, DenseBinaryMatrix dense, ElementData majorData, ElementData minorData, CMR_LISTHASHTABLE minorHashtable, long long hashVector, size_t numMinor, size_t processedMajors, size_t pnumProcessedMajors, size_t newMajor, size_t nestedMinorsElements, bool isRow)

static CMR_ELEMENT	mapGivenToOriginal (CMR_DEC *dec, CMR_ELEMENT given)
	Maps an element from the matrix given the extension algorithm to the element of the original node's matrix. More...

static CMR_ERROR	combineMaps (CMR_DEC dec, size_t nestedMinorsElements, size_t numElements, ElementData elementData, CMR_ELEMENT combinedMap)
	Computes the mapping rows/columns to elements of the original matrix. More...

static CMR_ERROR	extendNestedMinorSequence (CMR cmr, CMR_DEC dec, bool ternary, DenseBinaryMatrix dense, size_t nestedMinorsRows, size_t nestedMinorsColumns, CMR_SUBMAT psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Continues the construction of a sequence of nested 3-connected minors for the matrix of a decomposition node. More...

CMR_ERROR	CMRregularConstructNestedMinorSequence (CMR cmr, CMR_DEC dec, bool ternary, CMR_SUBMAT wheelSubmatrix, CMR_SUBMAT psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Constructs a sequence of nested 3-connected minors for the matrix of a decomposition node. More...

CMR_ERROR	CMRregularExtendNestedMinorSequence (CMR cmr, CMR_DEC dec, bool ternary, CMR_SUBMAT *psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Extends an incomplete sequence of nested 3-connected minors for the matrix of a decomposition node. More...

Function Documentation

◆ addElement()

static CMR_ERROR addElement	(	CMR *	cmr,
		CMR_DEC *	dec,
		DenseBinaryMatrix *	dense,
		ElementData *	majorData,
		ElementData *	minorData,
		CMR_LISTHASHTABLE *	minorHashtable,
		long long *	hashVector,
		size_t	numMinor,
		size_t *	processedMajors,
		size_t *	pnumProcessedMajors,
		size_t	newMajor,
		size_t *	nestedMinorsElements,
		bool	isRow
	)

static

Parameters

cmr	CMR environment.
dec	Decomposition node.
dense	Matrix.
majorData	Major index data.
minorData	Minor index data.
minorHashtable	Minor index hashtable.
hashVector	Hash vector.
numMinor	Number of minor indices.
processedMajors	Array of processed major indices.
pnumProcessedMajors	Pointer to number of processed major indices.
newMajor	Major index to add.
nestedMinorsElements	Mapping from nested minor elements to elements of matrix.
isRow	Whether major means row.

◆ applyPivots()

static CMR_ERROR applyPivots	(	CMR *	cmr,
		DenseBinaryMatrix *	dense,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_ELEMENT	reachedTarget,
		CMR_ELEMENT *	newElements
	)

static

Parameters

cmr	CMR environment.
dense	Remaining matrix.
rowData	Row data.
columnData	Column data.
reachedTarget	Reached target row/column.
newElements	Array of length 3 for storing the new elements (followed by 0s).

◆ CMRregularConstructNestedMinorSequence()

CMR_ERROR CMRregularConstructNestedMinorSequence	(	CMR *	cmr,
		CMR_DEC *	dec,
		bool	ternary,
		CMR_SUBMAT *	wheelSubmatrix,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Constructs a sequence of nested 3-connected minors for the matrix of a decomposition node.

In case the matrix is not 3-connected, a 2-separation is applied to dec and the function terminates, filling the relevant variables of dec.

Parameters

cmr	CMR environment.
dec	Decomposition node.
ternary	Whether to consider the signs of the matrix.
wheelSubmatrix	Wheel submatrix to start with.
psubmatrix	Pointer for storing a violator matrix.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularExtendNestedMinorSequence()

CMR_ERROR CMRregularExtendNestedMinorSequence	(	CMR *	cmr,
		CMR_DEC *	dec,
		bool	ternary,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Extends an incomplete sequence of nested 3-connected minors for the matrix of a decomposition node.

In case the matrix is not 3-connected, a 2-separation is applied to dec and the function terminates, filling the relevant variables of dec.

Parameters

cmr	CMR environment.
dec	Decomposition node.
ternary	Whether to consider the signs of the matrix.
psubmatrix	Pointer for storing a violator matrix.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ combineMaps()

static CMR_ERROR combineMaps	(	CMR_DEC *	dec,
		size_t *	nestedMinorsElements,
		size_t	numElements,
		ElementData *	elementData,
		CMR_ELEMENT *	combinedMap
	)

static

Computes the mapping rows/columns to elements of the original matrix.

First, using nestedMinorsElements, the index of the nested sequence is mapped to that of the dense matrix. Second, using elementData, the corresponding element of the matrix passed to the nested minor extension algorithm is determined (which may have changed since pivots exchange elements). Third, using nestedMinorsRowsOriginal or nestedMinorsColumnsOriginal of dec, the element of the matrix that was passed is mapped to the element of the original matrix.

Parameters

dec	Decomposition node.
nestedMinorsElements	Mapping from rows/columns of nested minor sequence to rows/columns of dense matrix.
numElements	Number of rows/columns in nested minor sequence.
elementData	Element data for rows/columns.
combinedMap	Computed map.

◆ createHashVector()

static CMR_ERROR createHashVector	(	CMR *	cmr,
		long long **	phashVector,
		size_t	size
	)

static

Parameters

cmr	CMR environment.
phashVector	Pointer for storing the hash vector.
size	Size of hash vector.

◆ extendNestedMinorSequence()

static CMR_ERROR extendNestedMinorSequence	(	CMR *	cmr,
		CMR_DEC *	dec,
		bool	ternary,
		DenseBinaryMatrix *	dense,
		size_t *	nestedMinorsRows,
		size_t *	nestedMinorsColumns,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

static

Continues the construction of a sequence of nested 3-connected minors for the matrix of a decomposition node.

In case the matrix is not 3-connected, a 2-separation is applied to dec and the function terminates, filling the relevant variables of dec.

Parameters

cmr	CMR environment.
dec	Decomposition node.
ternary	Whether to consider the signs of the matrix.
dense	Dense matrix.
nestedMinorsRows	Mapping of rows of the nested minor sequence to rows of `dense`.
nestedMinorsColumns	Mapping of columns of the nested minor sequence to columns of `dense`.
psubmatrix	Pointer for storing a violator matrix.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ initializeHashing()

static CMR_ERROR initializeHashing	(	CMR *	cmr,
		DenseBinaryMatrix *	dense,
		ElementData *	majorData,
		CMR_LISTHASHTABLE *	majorHashtable,
		size_t	numMajors,
		size_t *	processedMinors,
		size_t	numProcessedMinors,
		long long *	hashVector,
		bool	isRow
	)

static

Parameters

cmr	CMR environment.
dense	Matrix.
majorData	Major index data.
majorHashtable	Major index hashtable.
numMajors	Number of major indices.
processedMinors	Array with processed minor indices.
numProcessedMinors	Number of processed minor indices.
hashVector	Hash vector.
isRow	Whether major means row.

◆ mapGivenToOriginal()

static CMR_ELEMENT mapGivenToOriginal	(	CMR_DEC *	dec,
		CMR_ELEMENT	given
	)

static

Maps an element from the matrix given the extension algorithm to the element of the original node's matrix.

Parameters

dec	Decomposition node.
given	Some element from the given matrix.

◆ pivot()

static CMR_ERROR pivot	(	CMR *	cmr,
		DenseBinaryMatrix *	dense,
		size_t	pivotRow,
		size_t	pivotColumn
	)

static

Parameters

cmr	CMR environment.
dense	Remaining matrix.
pivotRow	Pivot row.
pivotColumn	Pivot column.

◆ prepareSearch()

static CMR_ERROR prepareSearch	(	CMR *	cmr,
		DenseBinaryMatrix *	matrix,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_ELEMENT *	pstartElement
	)

static

Parameters

cmr	CMR environment.
matrix	Nested matrix.
rowData	Row data.
columnData	Column data.
pstartElement	Pointer for storing an element for starting the search.

◆ searchShortestPath()

static CMR_ERROR searchShortestPath	(	CMR *	cmr,
		DenseBinaryMatrix *	dense,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_ELEMENT *	preachedTarget
	)

static

Parameters

cmr	CMR environment.
dense	Remaining matrix.
rowData	Row data.
columnData	Column data.
preachedTarget	Pointer for storing the reached target row/column.

◆ updateHashtable()

static CMR_ERROR updateHashtable	(	CMR *	cmr,
		ElementData *	majorData,
		size_t *	processedMajors,
		size_t	numProcessedMajors,
		CMR_LISTHASHTABLE *	majorHashtable
	)

static

Parameters

cmr	CMR environment.
majorData	Major index data.
processedMajors	Array of processed major indices.
numProcessedMajors	Number of processed major indices.
majorHashtable	Major index hashtable.

◆ updateRepresentative()

static CMR_ERROR updateRepresentative	(	CMR *	cmr,
		DenseBinaryMatrix *	dense,
		ElementData *	majorData,
		CMR_LISTHASHTABLE *	majorHashtable,
		size_t *	processedMinors,
		size_t	numProcessedMinors,
		size_t	majorIndex,
		bool	isRow
	)

static

Ensures that the representative entry for row/column index is correct.

Checks the respective hashtable.

Parameters

cmr	CMR environment.
dense	Matrix.
majorData	Major index data.
majorHashtable	Major index hashtable.
processedMinors	Array of processed minor indices.
numProcessedMinors	Number of processed minor indices.
majorIndex	Major index to update.
isRow	Whether major means rows.

Classes

Functions

Function Documentation

◆ addElement()

◆ applyPivots()

◆ CMRregularConstructNestedMinorSequence()

◆ CMRregularExtendNestedMinorSequence()

◆ combineMaps()

◆ createHashVector()

◆ extendNestedMinorSequence()

◆ initializeHashing()

◆ mapGivenToOriginal()

◆ pivot()

◆ prepareSearch()

◆ searchShortestPath()

◆ updateHashtable()

◆ updateRepresentative()