#include "seymour_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	dbgPrintDenseSequence (CMR cmr, CMR_SEYMOUR_NODE node)

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)
	Initializes the hashtable `majorHashtable` for unprocessed rows/columns.

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.

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, CMR_SEYMOUR_NODE dec, size_t pivotRow, size_t pivotColumn)
	Carries out a pivot in the dense matrix of `dec`.

static CMR_ERROR	applyPivots (CMR cmr, CMR_SEYMOUR_NODE dec, ElementData rowData, ElementData columnData, CMR_ELEMENT reachedTarget, CMR_ELEMENT *newElements)

static CMR_ERROR	addElement (CMR cmr, CMR_SEYMOUR_NODE dec, 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)

CMR_ERROR	CMRregularityExtendNestedMinorSequence (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Extends an incomplete sequence of nested 3-connected minors for the matrix of a decomposition node.

CMR_ERROR	CMRregularityInitNestedMinorSequence (CMR cmr, DecompositionTask task, CMR_SUBMAT *wheelSubmatrix)
	Initializes a sequence of nested minors with one minor, for a given `wheelSubmatrix`.

Function Documentation

◆ addElement()

static CMR_ERROR addElement	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	dec,
		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.
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,
		CMR_SEYMOUR_NODE *	dec,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_ELEMENT	reachedTarget,
		CMR_ELEMENT *	newElements
	)

static

Parameters

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

◆ CMRregularityExtendNestedMinorSequence()

CMR_ERROR CMRregularityExtendNestedMinorSequence	(	CMR *	cmr,
		DecompositionTask *	task,
		DecompositionQueue *	queue
	)

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.
task	Task to be processed; already removed from the list of unprocessed tasks.
queue	Queue of unprocessed nodes.

◆ CMRregularityInitNestedMinorSequence()

CMR_ERROR CMRregularityInitNestedMinorSequence	(	CMR *	cmr,
		DecompositionTask *	task,
		CMR_SUBMAT *	wheelSubmatrix
	)

Initializes a sequence of nested minors with one minor, for a given wheelSubmatrix.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
wheelSubmatrix	Wheel submatrix of `task->dec`.

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

◆ dbgPrintDenseSequence()

static CMR_ERROR dbgPrintDenseSequence	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node
	)

static

Parameters

cmr	CMR environment.
node	Seymour node whose dense matrix to print.

◆ 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

Initializes the hashtable majorHashtable for unprocessed rows/columns.

Initializes the hashtable majorHashtable for row/column vectors of unprocessed rows/columns with respect to those columns/rows that were already processed.

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.

◆ pivot()

static CMR_ERROR pivot	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	dec,
		size_t	pivotRow,
		size_t	pivotColumn
	)

static

Carries out a pivot in the dense matrix of dec.

Also swaps the element entries of dec->denseRowsOriginal and dec->denseColumnsOriginal.

Parameters

cmr	CMR environment.
dec	decomposition node.
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()

◆ CMRregularityExtendNestedMinorSequence()

◆ CMRregularityInitNestedMinorSequence()

◆ createHashVector()

◆ dbgPrintDenseSequence()

◆ initializeHashing()

◆ pivot()

◆ prepareSearch()

◆ searchShortestPath()

◆ updateHashtable()

◆ updateRepresentative()