#include <time.h>
#include <cmr/regular.h>
#include "matroid_internal.h"

Classes
struct	DecompositionTask

struct	DecompositionQueue

Typedefs
typedef struct DecompositionTask	DecompositionTask

typedef struct DecompositionQueue	DecompositionQueue

Functions
CMR_ERROR	CMRregularityTaskCreateRoot (CMR cmr, CMR_MATROID_DEC dec, DecompositionTask *ptask, CMR_REGULAR_PARAMS params, CMR_REGULAR_STATS *stats, clock_t startClock, double timeLimit)
	Creates a decomposition task for the root of the decomposition. More...

CMR_ERROR	CMRregularityTaskFree (CMR cmr, DecompositionTask *ptask)
	Frees a decomposition task. More...

CMR_ERROR	CMRregularityQueueCreate (CMR cmr, DecompositionQueue *pqueue)
	Initializes a decomposition queue. More...

CMR_ERROR	CMRregularityQueueFree (CMR cmr, DecompositionQueue *pqueue)
	Frees the decomposition queue. More...

bool	CMRregularityQueueEmpty (DecompositionQueue *queue)
	Returns whether a queue is empty. More...

DecompositionTask *	CMRregularityQueueRemove (DecompositionQueue *queue)
	Removes a task from a decomposition queue. More...

void	CMRregularityQueueAdd (DecompositionQueue queue, DecompositionTask task)
	Adds a task to a decomposition queue. More...

CMR_ERROR	CMRregularityDecomposeThreeSum (CMR cmr, DecompositionTask task, DecompositionQueue queue, CMR_SEPA separation)
	Applies a 3-sum decomposition. More...

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

CMR_ERROR	CMRregularityNestedMinorSequenceGraphicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests each minor of the sequence of nested 3-connected minors for graphicness. More...

CMR_ERROR	CMRregularityNestedMinorSequenceCographicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests each minor of the sequence of nested 3-connected minors for graphicness. More...

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

CMR_ERROR	CMRregularityTestR10 (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests `matrix` for representing \( R_{10} \). More...

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

CMR_ERROR	CMRregularityDecomposeSeriesParallel (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Splits off series-parallel elements from the matrix of the decomposition node. More...

CMR_ERROR	CMRregularityTestGraphicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests `matrix` for graphicness/network and stores it in `dec`. More...

CMR_ERROR	CMRregularityTestCographicness (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Tests `matrix` for cographicness/conetwork and stores it in `dec`. More...

CMR_ERROR	CMRregularitySearchOneSum (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Performs a 1-sum decomposition of `matrix` and stores it in `dec`. More...

CMR_ERROR	CMRregularityTest (CMR cmr, CMR_CHRMAT matrix, bool ternary, bool pisRegular, CMR_MATROID_DEC pdec, CMR_MINOR pminor, CMR_REGULAR_PARAMS params, CMR_REGULAR_STATS *stats, double timeLimit)
	Tests ternary or binary linear matroid for regularity. More...

CMR_ERROR	CMRregularityCompleteDecomposition (CMR cmr, CMR_MATROID_DEC subtree, CMR_REGULAR_PARAMS params, CMR_REGULAR_STATS stats, double timeLimit)
	Replaces the subtree of a matroid decomposition tree by a new one. More...

Typedef Documentation

◆ DecompositionQueue

typedef struct DecompositionQueue DecompositionQueue

◆ DecompositionTask

typedef struct DecompositionTask DecompositionTask

Function Documentation

◆ CMRregularityCompleteDecomposition()

CMR_ERROR CMRregularityCompleteDecomposition	(	CMR *	cmr,
		CMR_MATROID_DEC *	subtree,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		double	timeLimit
	)

Replaces the subtree of a matroid decomposition tree by a new one.

Parameters

cmr	CMR environment.
subtree	Decomposition node of the subtree root.
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularityDecomposeSeriesParallel()

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

Splits off series-parallel elements from the matrix of the decomposition node.

In case the matrix is Series-Parallel Matroids, then the node is declared to be planar.

In case the matrix does not admit series-parallel reductions, then the node remains remain unchanged. Otherwise, a child node is created whose matrix is the series-parallel-reduced one. For that child node, a 2-separation may be found, and corresponding children will be created.

Parameters

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

◆ CMRregularityDecomposeThreeSum()

CMR_ERROR CMRregularityDecomposeThreeSum	(	CMR *	cmr,
		DecompositionTask *	task,
		DecompositionQueue *	queue,
		CMR_SEPA *	separation
	)

Applies a 3-sum decomposition.

Parameters

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

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

◆ CMRregularityNestedMinorSequenceCographicness()

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

Tests each minor of the sequence of nested 3-connected minors for graphicness.

Sets task->dec->CMRregularityNestedMinorSequenceCographicness accordingly.

Parameters

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

◆ CMRregularityNestedMinorSequenceGraphicness()

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

Tests each minor of the sequence of nested 3-connected minors for graphicness.

Sets task->dec->CMRregularityNestedMinorSequenceGraphicness accordingly.

Parameters

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

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

◆ CMRregularityQueueAdd()

void CMRregularityQueueAdd	(	DecompositionQueue *	queue,
		DecompositionTask *	task
	)

Adds a task to a decomposition queue.

Parameters

queue	Queue.
task	Task.

◆ CMRregularityQueueCreate()

CMR_ERROR CMRregularityQueueCreate	(	CMR *	cmr,
		DecompositionQueue **	pqueue
	)

Initializes a decomposition queue.

Parameters

cmr	CMR environment.
pqueue	Pointer for storing the queue.

◆ CMRregularityQueueEmpty()

bool CMRregularityQueueEmpty ( DecompositionQueue * queue )

Returns whether a queue is empty.

Parameters

queue Queue.

◆ CMRregularityQueueFree()

CMR_ERROR CMRregularityQueueFree	(	CMR *	cmr,
		DecompositionQueue **	pqueue
	)

Frees the decomposition queue.

Parameters

cmr	CMR environment.
pqueue	Pointer to queue.

◆ CMRregularityQueueRemove()

DecompositionTask* CMRregularityQueueRemove ( DecompositionQueue * queue )

Removes a task from a decomposition queue.

Parameters

queue Queue.

◆ CMRregularitySearchOneSum()

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

Performs a 1-sum decomposition of matrix and stores it in dec.

If matrix is 1-connected, then dec remains unchanged. Otherwise, dec will become a CMR_MATROID_DEC_TYPE_ONE_SUM node with children that are initialized to the 1-connected components. In this case, the matrix and transpose members of the child nodes are set.

Parameters

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

◆ CMRregularityTaskCreateRoot()

CMR_ERROR CMRregularityTaskCreateRoot	(	CMR *	cmr,
		CMR_MATROID_DEC *	dec,
		DecompositionTask **	ptask,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		clock_t	startClock,
		double	timeLimit
	)

Creates a decomposition task for the root of the decomposition.

Parameters

cmr	CMR environment.
dec	Decomposition node.
ptask	Pointer for storing the new task.
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
startClock	Clock for the start time.
timeLimit	Time limit to impose.

◆ CMRregularityTaskFree()

CMR_ERROR CMRregularityTaskFree	(	CMR *	cmr,
		DecompositionTask **	ptask
	)

Frees a decomposition task.

Parameters

cmr	CMR environment.
ptask	Pointer to task.

◆ CMRregularityTest()

CMR_ERROR CMRregularityTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool	ternary,
		bool *	pisRegular,
		CMR_MATROID_DEC **	pdec,
		CMR_MINOR **	pminor,
		CMR_REGULAR_PARAMS *	params,
		CMR_REGULAR_STATS *	stats,
		double	timeLimit
	)

Tests ternary or binary linear matroid for regularity.

If pdec is not NULL, *pdec will be a (partial) decomposition tree.

If pminor is not NULL and matrix is not regular, then an \( F_7 \) or \( F_7^\star \) minor or a submatrix with non-ternary determinant is searched. This causes additional computational effort!

Parameters

cmr	CMR environment.
matrix	Input matrix.
ternary	Whether the matrix shall be considered ternary.
pisRegular	Pointer for storing whether `matrix` is regular.
pdec	Pointer for storing the decomposition tree (may be `NULL`).
pminor	Pointer for storing an \( F_7 \) or \( F_7^\star \) minor.
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRregularityTestCographicness()

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

Tests matrix for cographicness/conetwork and stores it in dec.

Parameters

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

◆ CMRregularityTestGraphicness()

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

Tests matrix for graphicness/network and stores it in dec.

Parameters

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

◆ CMRregularityTestR10()

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

Tests matrix for representing \( R_{10} \).

Parameters

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

Classes

Typedefs

Functions

Typedef Documentation

◆ DecompositionQueue

◆ DecompositionTask

Function Documentation

◆ CMRregularityCompleteDecomposition()

◆ CMRregularityDecomposeSeriesParallel()

◆ CMRregularityDecomposeThreeSum()

◆ CMRregularityExtendNestedMinorSequence()

◆ CMRregularityInitNestedMinorSequence()

◆ CMRregularityNestedMinorSequenceCographicness()

◆ CMRregularityNestedMinorSequenceGraphicness()

◆ CMRregularityNestedMinorSequenceSearchThreeSeparation()

◆ CMRregularityQueueAdd()

◆ CMRregularityQueueCreate()

◆ CMRregularityQueueEmpty()

◆ CMRregularityQueueFree()

◆ CMRregularityQueueRemove()

◆ CMRregularitySearchOneSum()

◆ CMRregularityTaskCreateRoot()

◆ CMRregularityTaskFree()

◆ CMRregularityTest()

◆ CMRregularityTestCographicness()

◆ CMRregularityTestGraphicness()

◆ CMRregularityTestR10()