#include "regular_internal.h"
#include "env_internal.h"
#include "dec_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)

static CMR_ERROR	transformSeparationNested (CMR cmr, CMR_DEC dec, CMR_SEPA *separation)
	Transforms a `separation` of the nested minors matrix to the matrix of `dec`. More...

CMR_ERROR	CMRregularSearchThreeSeparation (CMR cmr, CMR_DEC dec, CMR_CHRMAT transpose, bool ternary, size_t firstNonCoGraphicMinor, CMR_SUBMAT psubmatrix, CMR_REGULAR_STATISTICS stats, double timeLimit)
	Enumerates 3-separations for a 3-connected matrix. 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.

◆ CMRregularSearchThreeSeparation()

CMR_ERROR CMRregularSearchThreeSeparation	(	CMR *	cmr,
		CMR_DEC *	dec,
		CMR_CHRMAT *	transpose,
		bool	ternary,
		size_t	firstNonCoGraphicMinor,
		CMR_SUBMAT **	psubmatrix,
		CMR_REGULAR_STATISTICS *	stats,
		double	timeLimit
	)

Enumerates 3-separations for a 3-connected matrix.

Parameters

cmr	CMR environment.
dec	Decomposition node.
transpose	Transpose of nested-minors matrix of `dec`.
ternary	Whether to consider the signs of the matrix.
firstNonCoGraphicMinor	Index of first nested minor that is neither graphic nor cographic.
psubmatrix	Pointer for storing a violator matrix.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

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

◆ transformSeparationNested()

static CMR_ERROR transformSeparationNested	(	CMR *	cmr,
		CMR_DEC *	dec,
		CMR_SEPA *	separation
	)

static

Transforms a separation of the nested minors matrix to the matrix of dec.

The separation is assumed to be incomplete, i.e., only rowsToPart and columnsToPart are set.

Parameters

cmr	CMR environment.
dec	Decomposition node.
separation	3-separation.

Classes

Functions

Function Documentation

◆ assignRow()

◆ CMRregularSearchThreeSeparation()

◆ determineType()

◆ extendMinorSeparation()

◆ findRank1()

◆ findRank2()

◆ findRank3()

◆ transformSeparationNested()