#include "regularity_internal.h"
#include "env_internal.h"
#include "matroid_internal.h"
#include <time.h>

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

Functions
static bool	findRank1 (CMR_CHRMAT matrix, ElementData rowData, ElementData *columnData, size_t rowRepresentative[2][2], size_t columnRepresentative[2][2], short part)
	Checks whether the submatrix with rows assigned to `part` and columns assigned to the other has at least rank 1. More...

static bool	findRank2 (CMR_CHRMAT matrix, ElementData rowData, ElementData *columnData, size_t rowRepresentative[2][2], size_t columnRepresentative[2][2], short part)
	Checks whether the submatrix with rows assigned to `part` and columns assigned to the other has at least rank 2. More...

static bool	findRank3 (CMR_CHRMAT matrix, ElementData rowData, ElementData *columnData, size_t rowRepresentative[2][2], short part)
	Checks whether the submatrix with rows assigned to `part` and columns assigned to the other has at least rank 3. More...

static void	determineType (CMR_CHRMAT matrix, ElementData rowData, ElementData *columnData, size_t rowRepresentative[2][2], size_t row, short part, bool isRow)
	Checks whether the given `row` can be attached to `part`. More...

static bool	assignRow (CMR_CHRMAT matrix, ElementData rowData, ElementData columnData, size_t columnRepresentative[2][2], CMR_ELEMENT queue, size_t *pqueueBeyond, size_t row, short part, bool isRow)
	Assigns `row` to `part`, updating `rowData` and `columnData`. More...

static CMR_ERROR	extendMinorSeparation (CMR cmr, CMR_CHRMAT matrix, CMR_CHRMAT transpose, ElementData rowData, ElementData columnData, size_t partRows[2], size_t partNumRows[2], size_t partColumns[2], size_t partNumColumns[2], CMR_ELEMENT queue, CMR_SEPA **pseparation)

CMR_ERROR	CMRregularityNestedMinorSequenceSearchThreeSeparation (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Searches for 3-separations along the sequence of nested minors and decomposes as a 3-sum. More...

Function Documentation

◆ assignRow()

static bool assignRow	(	CMR_CHRMAT *	matrix,
		ElementData *	rowData,
		ElementData *	columnData,
		size_t	columnRepresentative[2][2],
		CMR_ELEMENT *	queue,
		size_t *	pqueueBeyond,
		size_t	row,
		short	part,
		bool	isRow
	)

static

Assigns row to part, updating rowData and columnData.

Returns: true if one of the unassigned columns cannot be assigned to any part.

Parameters

matrix	Matrix.
rowData	Row element data.
columnData	Column element data.
columnRepresentative	Column representatives for each part.
queue	Queue.
pqueueBeyond	Pointer for the end of the queue.
row	Row to be added.
part	Part the row is to be added to.
isRow	Whether we're actually assigning a row.

◆ CMRregularityNestedMinorSequenceSearchThreeSeparation()

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

Searches for 3-separations along the sequence of nested minors and decomposes as a 3-sum.

Parameters

cmr	CMR environment.
task	Task to be processed; already removed from the list of unprocessed tasks.
queue	Queue of unprocessed nodes.

◆ determineType()

static void determineType	(	CMR_CHRMAT *	matrix,
		ElementData *	rowData,
		ElementData *	columnData,
		size_t	rowRepresentative[2][2],
		size_t	row,
		short	part,
		bool	isRow
	)

static

Checks whether the given row can be attached to part.

Parameters

matrix	Matrix.
rowData	Row element data.
columnData	Column element data.
rowRepresentative	Row representatives for each part.
row	Row index to check.
part	Part to which the investigated rows belong.
isRow	Whether we're actually dealing with rows.

◆ extendMinorSeparation()

static CMR_ERROR extendMinorSeparation	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		ElementData *	rowData,
		ElementData *	columnData,
		size_t *	partRows[2],
		size_t	partNumRows[2],
		size_t *	partColumns[2],
		size_t	partNumColumns[2],
		CMR_ELEMENT *	queue,
		CMR_SEPA **	pseparation
	)

static

Parameters

cmr	CMR environment.
matrix	Matrix.
transpose	Transpose of `matrix`.
rowData	Row element data.
columnData	Column element data.
partRows	For each part, an array with its already assigned rows.
partNumRows	For each part, the number of already assigned rows.
partColumns	For each part, an array with its already assigned columns.
partNumColumns	For each part, the number of already assigned columns.
queue	Memory for a queue of elements.
pseparation	Pointer for storing the 3-separation or `NULL` if none was found.

◆ findRank1()

static bool findRank1	(	CMR_CHRMAT *	matrix,
		ElementData *	rowData,
		ElementData *	columnData,
		size_t	rowRepresentative[2][2],
		size_t	columnRepresentative[2][2],
		short	part
	)

static

Checks whether the submatrix with rows assigned to part and columns assigned to the other has at least rank 1.

If the rank is at least 1, the row and column of a corresponding nonzero are stored in rowRepresentative and columnRepresentative, respectively.

Parameters

matrix	Matrix.
rowData	Row element data.
columnData	Column element data.
rowRepresentative	Row representatives for each part.
columnRepresentative	Column representatives for each part.
part	Part to which the investigated rows belong.

◆ findRank2()

static bool findRank2	(	CMR_CHRMAT *	matrix,
		ElementData *	rowData,
		ElementData *	columnData,
		size_t	rowRepresentative[2][2],
		size_t	columnRepresentative[2][2],
		short	part
	)

static

Checks whether the submatrix with rows assigned to part and columns assigned to the other has at least rank 2.

Assumes that rowRepresentative already contains the first nonzero row in that matrix. If the rank is at least 2, rowRepresentative and columnRepresentative are extended as to indicate a rank-2 submatrix.

Parameters

matrix	Matrix.
rowData	Row element data.
columnData	Column element data.
rowRepresentative	Row representatives for each part.
columnRepresentative	Column representatives for each part.
part	Part to which the investigated rows belong.

◆ findRank3()

static bool findRank3	(	CMR_CHRMAT *	matrix,
		ElementData *	rowData,
		ElementData *	columnData,
		size_t	rowRepresentative[2][2],
		short	part
	)

static

Checks whether the submatrix with rows assigned to part and columns assigned to the other has at least rank 3.

Assumes that rowRepresentative already contains two distinct nonzero rows in that submatrix.

Parameters

matrix	Matrix.
rowData	Row element data.
columnData	Column element data.
rowRepresentative	Row representatives for each part.
part	Part to which the investigated rows belong.

Classes

Functions

Function Documentation

◆ assignRow()

◆ CMRregularityNestedMinorSequenceSearchThreeSeparation()

◆ determineType()

◆ extendMinorSeparation()

◆ findRank1()

◆ findRank2()

◆ findRank3()