seymour_internal.h File Reference

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

Go to the source code of this file.

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.
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.
CMR_ERROR	CMRseymourAddMinor (CMR *cmr, CMR_SEYMOUR_NODE *node, CMR_MINOR *minor)
	Adds a minor to a Seymour decomposition node.
CMR_ERROR	CMRseymourSetNumChildren (CMR *cmr, CMR_SEYMOUR_NODE *node, size_t numChildren)
	Sets the number of children and allocates memory accordingly.
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.
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.
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.
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.
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.
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.
CMR_ERROR	CMRseymourSetAttributes (CMR_SEYMOUR_NODE *node)
	Set regularity and (co)graphicness attributes of a decomposition tree.
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.
CMR_ERROR	CMRregularityTaskFree (CMR *cmr, DecompositionTask **ptask)
	Frees a decomposition task.
CMR_ERROR	CMRregularityQueueCreate (CMR *cmr, DecompositionQueue **pqueue)
	Initializes a decomposition queue.
CMR_ERROR	CMRregularityQueueFree (CMR *cmr, DecompositionQueue **pqueue)
	Frees the decomposition queue.
bool	CMRregularityQueueEmpty (DecompositionQueue *queue)
	Returns whether a queue is empty.
DecompositionTask *	CMRregularityQueueRemove (DecompositionQueue *queue)
	Removes a task from a decomposition queue.
void	CMRregularityQueueAdd (DecompositionQueue *queue, DecompositionTask *task)
	Adds a task to a decomposition queue.
CMR_ERROR	CMRregularityDecomposeThreeSum (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue, CMR_SEPA *separation)
	Applies a 3-sum decomposition.
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.
CMR_ERROR	CMRregularityNestedMinorSequenceGraphicness (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Tests each minor of the sequence of nested 3-connected minors for graphicness.
CMR_ERROR	CMRregularityNestedMinorSequenceCographicness (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Tests each minor of the sequence of nested 3-connected minors for graphicness.
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	CMRregularityTestR10 (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Tests matrix for representing \( R_{10} \).
CMR_ERROR	CMRregularityInitNestedMinorSequence (CMR *cmr, DecompositionTask *task, CMR_SUBMAT *wheelSubmatrix)
	Initializes a sequence of nested minors with one minor, for a given wheelSubmatrix.
CMR_ERROR	CMRregularityDecomposeSeriesParallel (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Splits off series-parallel elements from the matrix of the decomposition node.
CMR_ERROR	CMRregularityTestGraphicness (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Tests matrix for graphicness/network and stores it in dec.
CMR_ERROR	CMRregularityTestCographicness (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Tests matrix for cographicness/conetwork and stores it in dec.
CMR_ERROR	CMRregularitySearchOnesum (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Performs a 1-sum decomposition of matrix and stores it in dec.
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.
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.
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.

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

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.

Takes ownership of violator.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
violator	Violating submatrix; ownership is taken.