#include <time.h>
#include "densematrix.h"
#include <cmr/matroid.h>
#include <cmr/seymour.h>
#include <cmr/series_parallel.h>

Classes
struct	_CMR_SEYMOUR_NODE

struct	DecompositionTask

struct	DecompositionQueue

Typedefs
typedef struct DecompositionTask	DecompositionTask

typedef struct DecompositionQueue	DecompositionQueue

Functions
char *	CMRseymourConsistency (CMR_SEYMOUR_NODE *node, bool recurse)
	Checks a Seymour decomposition node for consistency. More...

CMR_EXPORT CMR_ERROR	CMRseymourPrintChild (CMR cmr, CMR_SEYMOUR_NODE child, CMR_SEYMOUR_NODE parent, size_t childIndex, FILE stream, size_t indent, bool printChildren, bool printParentElements, bool printMatrices, bool printGraphs, bool printReductions, bool printPivots)
	Prints the decomposition `child` to `stream`. More...

CMR_ERROR	CMRseymourAddMinor (CMR cmr, CMR_SEYMOUR_NODE node, CMR_MINOR *minor)
	Adds a minor to a Seymour decomposition node. More...

CMR_ERROR	CMRseymourSetNumChildren (CMR cmr, CMR_SEYMOUR_NODE node, size_t numChildren)
	Sets the number of children and allocates memory accordingly. More...

CMR_ERROR	CMRseymourUpdateOneSum (CMR cmr, CMR_SEYMOUR_NODE node, size_t numChildren)
	Initialize an existing unknown decomposition node as a 1-sum with `numChildren` children. More...

CMR_ERROR	CMRseymourCreateChildFromMatrices (CMR cmr, CMR_SEYMOUR_NODE parent, size_t childIndex, CMR_CHRMAT matrix, CMR_CHRMAT transpose, CMR_ELEMENT rowsToParent, CMR_ELEMENT columnsToParent)
	Creates a decomposition node as a child. More...

CMR_ERROR	CMRseymourUpdateViolator (CMR cmr, CMR_SEYMOUR_NODE node, CMR_SUBMAT *violator)
	Initialize an existing unknown decomposition node to be irregular with a violator submatrix. More...

CMR_ERROR	CMRseymourUpdateSeriesParallel (CMR cmr, CMR_SEYMOUR_NODE node, CMR_SUBMAT *reducedSubmatrix)
	Updates an existing unknown Seymour decomposition node to be a series-parallel node. More...

CMR_ERROR	CMRseymourUpdateTwoSum (CMR cmr, CMR_SEYMOUR_NODE node, CMR_SEPA *separation)
	Initialize an existing unknown decomposition node as a 2-separation node according to the given `separation`. More...

CMR_ERROR	CMRseymourUpdatePivots (CMR cmr, CMR_SEYMOUR_NODE node, size_t numPivots, size_t pivotRows, size_t pivotColumns, CMR_CHRMAT matrix, CMR_CHRMAT transpose)
	Initialize an existing unknown decomposition node as a pivot node according to the given arrays of pivots. More...

CMR_ERROR	CMRseymourUpdateThreeSumInit (CMR cmr, CMR_SEYMOUR_NODE node)
	Initialize an existing unknown decomposition node as a 3-sum node. More...

CMR_ERROR	CMRseymourUpdateThreeSumCreateWideFirstChild (CMR cmr, CMR_SEYMOUR_NODE node, size_t rowsToChild, size_t columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraRow, size_t extraColumn1, size_t extraColumn2, int8_t extraEntry)
	Creates wide first child of an initialized 3-sum node. More...

CMR_ERROR	CMRseymourUpdateThreeSumCreateWideSecondChild (CMR cmr, CMR_SEYMOUR_NODE node, size_t rowsToChild, size_t columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraRow, size_t extraColumn1, size_t extraColumn2, int8_t extraEntry)
	Creates wide second child of an initialized 3-sum node. More...

CMR_ERROR	CMRseymourUpdateThreeSumCreateMixedFirstChild (CMR cmr, CMR_SEYMOUR_NODE node, size_t rowsToChild, size_t columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraRow1, size_t extraRow2, int8_t extraEntry)
	Creates mixed first child of an initialized 3-sum node. More...

CMR_ERROR	CMRseymourUpdateThreeSumCreateMixedSecondChild (CMR cmr, CMR_SEYMOUR_NODE node, size_t rowsToChild, size_t columnsToChild, size_t numChildBaseRows, size_t numChildBaseColumns, size_t extraColumn1, size_t extraColumn2, int8_t extraEntry)
	Creates mixed second child of an initialized 3-sum node. More...

CMR_ERROR	CMRseymourSetAttributes (CMR_SEYMOUR_NODE *node)
	Set regularity and (co)graphicness attributes of a decomposition tree. More...

CMR_ERROR	CMRregularityTaskCreateRoot (CMR cmr, CMR_SEYMOUR_NODE dec, DecompositionTask *ptask, CMR_SEYMOUR_PARAMS params, CMR_SEYMOUR_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	CMRseymourDecompose (CMR cmr, CMR_CHRMAT matrix, bool ternary, CMR_SEYMOUR_NODE *proot, CMR_SEYMOUR_PARAMS params, CMR_SEYMOUR_STATS *stats, double timeLimit)
	Tests ternary or binary linear matroid for regularity. More...

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

CMR_ERROR	CMRregularityRefineDecomposition (CMR cmr, size_t numNodes, CMR_SEYMOUR_NODE nodes, CMR_SEYMOUR_PARAMS params, CMR_SEYMOUR_STATS *stats, double timeLimit)
	Replaces the subtrees of several nodes of a matroid decomposition tree by new ones. More...

Typedef Documentation

◆ DecompositionQueue

typedef struct DecompositionQueue DecompositionQueue

◆ DecompositionTask

typedef struct DecompositionTask DecompositionTask

Function Documentation

◆ CMRregularityCompleteDecomposition()

CMR_ERROR CMRregularityCompleteDecomposition	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	subtree,
		CMR_SEYMOUR_PARAMS *	params,
		CMR_SEYMOUR_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 Matrices, 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.

◆ CMRregularityRefineDecomposition()

CMR_ERROR CMRregularityRefineDecomposition	(	CMR *	cmr,
		size_t	numNodes,
		CMR_SEYMOUR_NODE **	nodes,
		CMR_SEYMOUR_PARAMS *	params,
		CMR_SEYMOUR_STATS *	stats,
		double	timeLimit
	)

Replaces the subtrees of several nodes of a matroid decomposition tree by new ones.

Parameters

cmr	CMR environment.
numNodes	Number of nodes to refine.
nodes	Array of decomposition nodes to refine.
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ 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_SEYMOUR_NODE_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_SEYMOUR_NODE *	dec,
		DecompositionTask **	ptask,
		CMR_SEYMOUR_PARAMS *	params,
		CMR_SEYMOUR_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.

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

◆ CMRseymourAddMinor()

CMR_ERROR CMRseymourAddMinor	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		CMR_MINOR *	minor
	)

Adds a minor to a Seymour decomposition node.

Does not copy the minor.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
minor	Minor to be added.

◆ CMRseymourConsistency()

char* CMRseymourConsistency	(	CMR_SEYMOUR_NODE *	node,
		bool	recurse
	)

Checks a Seymour decomposition node for consistency.

Checks all requirements defined in Representation of Matroids.

Returns: NULL if consistent. Otherwise, an explanation string is returned, which must freed with free().

See also: CMRdbgConsistencyAssert() for checking the returned string and aborting in case of inconsistency.

Parameters

node	Seymour decomposition node.
recurse	Whether all (grand-)children shall be checked, too.

◆ CMRseymourCreateChildFromMatrices()

CMR_ERROR CMRseymourCreateChildFromMatrices	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	parent,
		size_t	childIndex,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		CMR_ELEMENT *	rowsToParent,
		CMR_ELEMENT *	columnsToParent
	)

Creates a decomposition node as a child.

Copies matrix and transpose into the node.

Parameters

cmr	CMR environment.
parent	Seymour decomposition parent node.
childIndex	Child index of parent.
matrix	The matrix corresponding to this node.
transpose	The transpose matrix corresponding to this node.
rowsToParent	Array for mapping rows to elements of parent.
columnsToParent	Array for mapping columns to elements of parent.

◆ CMRseymourDecompose()

CMR_ERROR CMRseymourDecompose	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool	ternary,
		CMR_SEYMOUR_NODE **	proot,
		CMR_SEYMOUR_PARAMS *	params,
		CMR_SEYMOUR_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.
proot	Pointer for storing the root of the Seymour decomposition.
params	Parameters for the computation.
stats	Statistics for the computation (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRseymourPrintChild()

CMR_EXPORT CMR_ERROR CMRseymourPrintChild	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	child,
		CMR_SEYMOUR_NODE *	parent,
		size_t	childIndex,
		FILE *	stream,
		size_t	indent,
		bool	printChildren,
		bool	printParentElements,
		bool	printMatrices,
		bool	printGraphs,
		bool	printReductions,
		bool	printPivots
	)

Prints the decomposition child to stream.

Parameters

cmr	CMR environment.
child	Seymour decomposition child node.
parent	Seymour decomposition parent node.
childIndex	Index of `child` as a child of `parent`.
stream	Stream to write to.
indent	Indentation of this node.
printChildren	Whether to recurse.
printParentElements	Whether to print mapping of rows/columns to parent elements (if `parent` is not `NULL`).
printMatrices	Whether to print matrices.
printGraphs	Whether to print graphs.
printReductions	Whether to print series-parallel reductions.
printPivots	Whether to print pivots.

◆ CMRseymourSetAttributes()

CMR_ERROR CMRseymourSetAttributes ( CMR_SEYMOUR_NODE * node )

Set regularity and (co)graphicness attributes of a decomposition tree.

Parameters

node	Seymour decomposition node.

◆ CMRseymourSetNumChildren()

CMR_ERROR CMRseymourSetNumChildren	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		size_t	numChildren
	)

Sets the number of children and allocates memory accordingly.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
numChildren	Number of children.

◆ CMRseymourUpdateOneSum()

CMR_ERROR CMRseymourUpdateOneSum	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		size_t	numChildren
	)

Initialize an existing unknown decomposition node as a 1-sum with numChildren children.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
numChildren	Number of child nodes.

◆ CMRseymourUpdatePivots()

CMR_ERROR CMRseymourUpdatePivots	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		size_t	numPivots,
		size_t *	pivotRows,
		size_t *	pivotColumns,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose
	)

Initialize an existing unknown decomposition node as a pivot node according to the given arrays of pivots.

The unique child node will be of type CMR_SEYMOUR_NODE_TYPE_UNKNOWN.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
numPivots	Number of pivots.
pivotRows	Array with pivot rows.
pivotColumns	Array with pivot columns.
matrix	New matrix.
transpose	Transpose of `matrix`.

◆ CMRseymourUpdateSeriesParallel()

CMR_ERROR CMRseymourUpdateSeriesParallel	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		CMR_SUBMAT *	reducedSubmatrix
	)

Updates an existing unknown Seymour decomposition node to be a series-parallel node.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
reducedSubmatrix	SP-reduced submatrix.

◆ CMRseymourUpdateThreeSumCreateMixedFirstChild()

CMR_ERROR CMRseymourUpdateThreeSumCreateMixedFirstChild	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraRow1,
		size_t	extraRow2,
		int8_t	extraEntry
	)

Creates mixed first child of an initialized 3-sum node.

A nonzero extraEntry indicates the bottom-right nonzero entry.

Parameters

cmr	CMR environment.
node	Seymour decomposition node (initialized with CMRseymourUpdateThreeSumInit).
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraRow1	Index of the first extra row.
extraRow2	Index of the second extra row.
extraEntry	Sign of the extra entry.

◆ CMRseymourUpdateThreeSumCreateMixedSecondChild()

CMR_ERROR CMRseymourUpdateThreeSumCreateMixedSecondChild	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraColumn1,
		size_t	extraColumn2,
		int8_t	extraEntry
	)

Creates mixed second child of an initialized 3-sum node.

A nonzero extraEntry indicates the top-left nonzero entry.

Parameters

cmr	CMR environment.
node	Seymour decomposition node (initialized with CMRseymourUpdateThreeSumInit).
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraColumn1	Index of the first extra column.
extraColumn2	Index of the second extra column.
extraEntry	Sign of the extra entry.

◆ CMRseymourUpdateThreeSumCreateWideFirstChild()

CMR_ERROR CMRseymourUpdateThreeSumCreateWideFirstChild	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraRow,
		size_t	extraColumn1,
		size_t	extraColumn2,
		int8_t	extraEntry
	)

Creates wide first child of an initialized 3-sum node.

A nonzero extraEntry indicates the bottom-right nonzero entry.

Parameters

cmr	CMR environment.
node	Seymour decomposition node (initialized with CMRseymourUpdateThreeSumInit).
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraRow	Index of the extra row.
extraColumn1	Index of 1st extra column.
extraColumn2	Index of 2nd extra column, parallel to `extraColumn1`; equality is allowed.
extraEntry	Sign of the extra entry.

◆ CMRseymourUpdateThreeSumCreateWideSecondChild()

CMR_ERROR CMRseymourUpdateThreeSumCreateWideSecondChild	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		size_t *	rowsToChild,
		size_t *	columnsToChild,
		size_t	numChildBaseRows,
		size_t	numChildBaseColumns,
		size_t	extraRow,
		size_t	extraColumn1,
		size_t	extraColumn2,
		int8_t	extraEntry
	)

Creates wide second child of an initialized 3-sum node.

A nonzero extraEntry indicates the bottom-right nonzero entry.

Parameters

cmr	CMR environment.
node	Seymour decomposition node (initialized with CMRseymourUpdateThreeSumInit).
rowsToChild	Array mapping rows to child rows.
columnsToChild	Array mapping columns to child columns.
numChildBaseRows	Number of base rows of this child.
numChildBaseColumns	Number of base rows of this child.
extraRow	Index of the extra row.
extraColumn1	Index of 1st extra column.
extraColumn2	Index of 2nd extra column, parallel to `extraColumn1`; equality is allowed.
extraEntry	Sign of the extra entry, if known.

◆ CMRseymourUpdateThreeSumInit()

CMR_ERROR CMRseymourUpdateThreeSumInit	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node
	)

Initialize an existing unknown decomposition node as a 3-sum node.

The two child nodes remain uninitialized.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.

◆ CMRseymourUpdateTwoSum()

CMR_ERROR CMRseymourUpdateTwoSum	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		CMR_SEPA *	separation
	)

Initialize an existing unknown decomposition node as a 2-separation node according to the given separation.

The two child nodes will be of type CMR_SEYMOUR_NODE_TYPE_UNKNOWN.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
separation	2-separation.

◆ CMRseymourUpdateViolator()

CMR_ERROR CMRseymourUpdateViolator	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		CMR_SUBMAT *	violator
	)

Initialize an existing unknown decomposition node to be irregular with a violator submatrix.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
violator	Submatrix. Is not copied.

Classes

Typedefs

Functions

Typedef Documentation

◆ DecompositionQueue

◆ DecompositionTask

Function Documentation

◆ CMRregularityCompleteDecomposition()

◆ CMRregularityDecomposeSeriesParallel()

◆ CMRregularityDecomposeThreeSum()

◆ CMRregularityExtendNestedMinorSequence()

◆ CMRregularityInitNestedMinorSequence()

◆ CMRregularityNestedMinorSequenceCographicness()

◆ CMRregularityNestedMinorSequenceGraphicness()

◆ CMRregularityNestedMinorSequenceSearchThreeSeparation()

◆ CMRregularityQueueAdd()

◆ CMRregularityQueueCreate()

◆ CMRregularityQueueEmpty()

◆ CMRregularityQueueFree()

◆ CMRregularityQueueRemove()

◆ CMRregularityRefineDecomposition()

◆ CMRregularitySearchOneSum()

◆ CMRregularityTaskCreateRoot()

◆ CMRregularityTaskFree()

◆ CMRregularityTestCographicness()

◆ CMRregularityTestGraphicness()

◆ CMRregularityTestR10()

◆ CMRseymourAddMinor()

◆ CMRseymourConsistency()

◆ CMRseymourCreateChildFromMatrices()

◆ CMRseymourDecompose()

◆ CMRseymourPrintChild()

◆ CMRseymourSetAttributes()

◆ CMRseymourSetNumChildren()

◆ CMRseymourUpdateOneSum()

◆ CMRseymourUpdatePivots()

◆ CMRseymourUpdateSeriesParallel()

◆ CMRseymourUpdateThreeSumCreateMixedFirstChild()

◆ CMRseymourUpdateThreeSumCreateMixedSecondChild()

◆ CMRseymourUpdateThreeSumCreateWideFirstChild()

◆ CMRseymourUpdateThreeSumCreateWideSecondChild()

◆ CMRseymourUpdateThreeSumInit()

◆ CMRseymourUpdateTwoSum()

◆ CMRseymourUpdateViolator()