#include <cmr/seymour.h>
#include "env_internal.h"
#include "seymour_internal.h"
#include "matrix_internal.h"
#include "listmatrix.h"
#include <assert.h>
#include <string.h>
#include <time.h>

Classes
struct	ClonePair
	Pair of a given Seymour decomposition node and its clone. More...

Macros
#define	MIN_IF_EXISTS(currentValue, child, childValue)

Functions
CMR_ERROR	CMRseymourParamsInit (CMR_SEYMOUR_PARAMS *params)
	Initializes the default parameters for regularity testing. More...

CMR_ERROR	CMRseymourStatsInit (CMR_SEYMOUR_STATS *stats)
	Initializes all statistics for Seymour decomposition computations. More...

CMR_ERROR	CMRseymourStatsPrint (FILE stream, CMR_SEYMOUR_STATS stats, const char *prefix)
	Prints statistics for Seymour decomposition computations. More...

bool	CMRseymourIsTernary (CMR_SEYMOUR_NODE *node)
	Returns `true` iff the decomposition is over \( \mathbb{F}_3 \). More...

bool	CMRseymourThreeSumDistributedRanks (CMR_SEYMOUR_NODE *node)
	Returns `true` iff the 3-sum decomposition node has \( 3 \)-separation with two rank-1 matrices. More...

bool	CMRseymourThreeSumConcentratedRank (CMR_SEYMOUR_NODE *node)
	Returns `true` iff the 3-sum decomposition node has \( 3 \)-separation with one rank-2 matrix. More...

CMR_CHRMAT *	CMRseymourGetMatrix (CMR_SEYMOUR_NODE *node)
	Returns the matrix of the decomposition node `dec` (or `NULL` if it is not stored). More...

bool	CMRseymourHasTranspose (CMR_SEYMOUR_NODE *node)
	Returns `true` iff the transposed matrix of the decomposition node `dec` is stored. More...

CMR_CHRMAT *	CMRseymourGetTranspose (CMR_SEYMOUR_NODE *node)
	Returns the transposed matrix of the decomposition node `dec` (or `NULL` if it is not stored). More...

size_t	CMRseymourNumChildren (CMR_SEYMOUR_NODE *node)
	Returns the number of children of the decomposition node `dec`. More...

CMR_SEYMOUR_NODE *	CMRseymourChild (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns a child of the decomposition node `dec`. More...

CMR_SEYMOUR_NODE_TYPE	CMRseymourType (CMR_SEYMOUR_NODE *node)
	Returns the type of a decomposition node `dec`. More...

int8_t	CMRseymourGraphicness (CMR_SEYMOUR_NODE *node)
	Indicates graphicness/being network. More...

int8_t	CMRseymourCographicness (CMR_SEYMOUR_NODE *node)
	Indicates cographicness/being conetwork. More...

int8_t	CMRseymourRegularity (CMR_SEYMOUR_NODE *node)
	Indicates regularity/total unimodularity. More...

size_t	CMRseymourNumRows (CMR_SEYMOUR_NODE *node)
	Returns the number of rows. More...

CMR_ELEMENT *	CMRseymourChildRowsToParent (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the mapping of rows of child `childIndex` to this node's elements. More...

CMR_ELEMENT *	CMRseymourChildColumnsToParent (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the mapping of columns of child `childIndex` to this node's elements. More...

size_t	CMRseymourNumColumns (CMR_SEYMOUR_NODE *node)
	Returns the number of columns. More...

CMR_GRAPH *	CMRseymourGraph (CMR_SEYMOUR_NODE *node)
	Returns the graph (if available). More...

CMR_GRAPH_EDGE *	CMRseymourGraphForest (CMR_SEYMOUR_NODE *node)
	Returns the forest of the graph (if available). More...

size_t	CMRseymourGraphSizeForest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the graph's forest (if available). More...

CMR_GRAPH_EDGE *	CMRseymourGraphCoforest (CMR_SEYMOUR_NODE *node)
	Returns the coforest of the graph (if available). More...

size_t	CMRseymourGraphSizeCoforest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the graph's coforest (if available). More...

bool *	CMRseymourGraphArcsReversed (CMR_SEYMOUR_NODE *node)
	Returns an array that indicates for the graph's edges whether they must be reversed (if available). More...

CMR_GRAPH *	CMRseymourCograph (CMR_SEYMOUR_NODE *node)
	Returns the cograph (if available). More...

size_t	CMRseymourCographSizeForest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the cograph's forest (if available). More...

CMR_GRAPH_EDGE *	CMRseymourCographForest (CMR_SEYMOUR_NODE *node)
	Returns the forest of the cograph (if available). More...

size_t	CMRseymourCographSizeCoforest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the cograph's coforest (if available). More...

CMR_GRAPH_EDGE *	CMRseymourCographCoforest (CMR_SEYMOUR_NODE *node)
	Returns the coforest of the cograph (if available). More...

bool *	CMRseymourCographArcsReversed (CMR_SEYMOUR_NODE *node)
	Returns an array that indicates for the cograph's edges whether they must be reversed (if available). More...

size_t	CMRseymourNumPivots (CMR_SEYMOUR_NODE *node)
	Returns the number of pivots (if available). More...

size_t *	CMRseymourPivotRows (CMR_SEYMOUR_NODE *node)
	Returns the array with the pivot rows (if available). More...

size_t *	CMRseymourPivotColumns (CMR_SEYMOUR_NODE *node)
	Returns the array with the pivot columns (if available). More...

size_t	CMRseymourGetUsed (CMR_SEYMOUR_NODE *node)
	Returns node's reference counter. More...

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	CMRseymourPrint (CMR cmr, CMR_SEYMOUR_NODE node, FILE *stream, bool printChildren, bool printParentElements, bool printMatrices, bool printGraphs, bool printReductions, bool printPivots)
	Prints the decomposition `dec` to `stream`. More...

CMR_ERROR	CMRseymourCapture (CMR cmr, CMR_SEYMOUR_NODE node)
	Increases the reference counter by 1. More...

CMR_ERROR	CMRseymourRelease (CMR cmr, CMR_SEYMOUR_NODE *pnode)
	Releases a decomposition node, freeing it if this was the last reference. More...

static CMR_ERROR	createNode (CMR cmr, CMR_SEYMOUR_NODE *pnode, bool isTernary, CMR_SEYMOUR_NODE_TYPE type, size_t numRows, size_t numColumns)

CMR_ERROR	CMRseymourCloneUnknown (CMR cmr, CMR_SEYMOUR_NODE node, CMR_SEYMOUR_NODE **pclone)
	Clones a decomposition node `node` into `*pclone` which represents the same matrix but has type CMR_SEYMOUR_NODE_TYPE_UNKNOWN type and no child nodes. More...

static CMR_ERROR	updateRowsColumnsToParent (CMR cmr, CMR_SEYMOUR_NODE parent, size_t childIndex, size_t parentRows, size_t parentColumns)
	Allocates and sets childRowsToParent and childColumnsToParent of the child of `parent` indicated by `childIndex`. More...

static CMR_ERROR	updateRowsColumnsToChild (CMR_SEYMOUR_NODE parent, size_t childIndex, size_t parentRows, size_t firstRow, size_t beyondRow, size_t *parentColumns, size_t firstColumn, size_t beyondColumn)
	Updates rowsToChild and columnsToChild of the parent. More...

static CMR_ERROR	updateChildMatrix (CMR cmr, CMR_SEYMOUR_NODE parent, size_t childIndex)
	Updates matrix of `dec` from parent using rowsParent and columnsParent arrays. More...

CMR_ERROR	CMRseymourCreate (CMR cmr, CMR_SEYMOUR_NODE pnode, bool isTernary, CMR_CHRMAT matrix)
	Creates an unknown decomposition node as a root. More...

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

size_t	CMRseymourNumMinors (CMR_SEYMOUR_NODE *node)
	Returns the number of minors of the decomposition node. More...

CMR_MINOR *	CMRseymourMinor (CMR_SEYMOUR_NODE *node, size_t minorIndex)
	Returns a minor of the 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	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	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	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...

static CMR_ERROR	cloneRecursively (CMR cmr, CMR_SEYMOUR_NODE node, CMR_SEYMOUR_NODE *pclone, CMR_LISTHASHTABLE nodesToClonesHashtable, ClonePair *pclonePairs, size_t pmemClonePairs, size_t *pnumClonePairs)
	Clones `node` to `*pclone`, updates cloning data structures and calls itself recursively. More...

CMR_ERROR	CMRseymourCloneSubtrees (CMR cmr, size_t numSubtrees, CMR_SEYMOUR_NODE subtreeRoots, CMR_SEYMOUR_NODE *clonedSubtrees)
	Clones the union of subtrees of a Seymour decomposition, returning the copies. 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...

static CMR_ERROR	CMRregularityTaskRun (CMR cmr, DecompositionTask task, DecompositionQueue *queue)
	Runs a task for processing the associated decomposition node. 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...

Macro Definition Documentation

◆ MIN_IF_EXISTS

#define MIN_IF_EXISTS	(	currentValue,
		child,
		childValue
	)

Value:

  ( (child != NULL) \
    ? ( ((childValue) < (currentValue)) ? (childValue) : (currentValue) ) \
    : ( (0 < (currentValue)) ? 0 : (currentValue) ) \
  )

Function Documentation

◆ cloneRecursively()

static CMR_ERROR cloneRecursively	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	node,
		CMR_SEYMOUR_NODE **	pclone,
		CMR_LISTHASHTABLE *	nodesToClonesHashtable,
		ClonePair **	pclonePairs,
		size_t *	pmemClonePairs,
		size_t *	pnumClonePairs
	)

static

Clones node to *pclone, updates cloning data structures and calls itself recursively.

Inserts it into nodesToClonesHashtable, and updates the array *pclonePairs with the cloned pairs.

Parameters

cmr	CMR environment.
node	Seymour decomposition node.
pclone	Pointer for storing the cloned Seymour decomposition node.
nodesToClonesHashtable	Hashtable for the mapping from nodes to cloned nodes.
pclonePairs	Pointer to array of cloned pairs.
pmemClonePairs	Allocated size of `*pclonePairs`.
pnumClonePairs	Length of `*pclonePairs`.

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

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

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

◆ CMRregularityTaskRun()

static CMR_ERROR CMRregularityTaskRun	(	CMR *	cmr,
		DecompositionTask *	task,
		DecompositionQueue *	queue
	)

static

Runs a task for processing the associated decomposition node.

Parameters

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

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

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

◆ createNode()

static CMR_ERROR createNode	(	CMR *	cmr,
		CMR_SEYMOUR_NODE **	pnode,
		bool	isTernary,
		CMR_SEYMOUR_NODE_TYPE	type,
		size_t	numRows,
		size_t	numColumns
	)

static

Parameters

cmr	CMR environment.
pnode	Pointer for storing the new Seymour decomposition node.
isTernary	Whether the node is ternary.
type	Type of the new node.
numRows	Number of rows.
numColumns	Number of columns.

◆ updateChildMatrix()

static CMR_ERROR updateChildMatrix	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	parent,
		size_t	childIndex
	)

static

Updates matrix of dec from parent using rowsParent and columnsParent arrays.

Parameters

cmr	CMR environment.
parent	Parent node in Seymour decomposition.
childIndex	Index of child to update.

◆ updateRowsColumnsToChild()

static CMR_ERROR updateRowsColumnsToChild	(	CMR_SEYMOUR_NODE *	parent,
		size_t	childIndex,
		size_t *	parentRows,
		size_t	firstRow,
		size_t	beyondRow,
		size_t *	parentColumns,
		size_t	firstColumn,
		size_t	beyondColumn
	)

static

Updates rowsToChild and columnsToChild of the parent.

Parameters

parent	Seymour decomposition node of parent.
childIndex	An index of a child of `parent`.
parentRows	Array indicating parent row of each row of the child.
firstRow	First index of `parentRows` to consider.
beyondRow	Beyond index of `parentRows` to consider.
parentColumns	Array indicating parent column of each column of the child.
firstColumn	First index of `parentColumns` to consider.
beyondColumn	Beyond index of `parentColumns` to consider.

◆ updateRowsColumnsToParent()

static CMR_ERROR updateRowsColumnsToParent	(	CMR *	cmr,
		CMR_SEYMOUR_NODE *	parent,
		size_t	childIndex,
		size_t *	parentRows,
		size_t *	parentColumns
	)

static

Allocates and sets childRowsToParent and childColumnsToParent of the child of parent indicated by childIndex.

Parameters

cmr	CMR environment.
parent	Seymour decomposition parent node.
childIndex	Child index.
parentRows	Array indicating parent row of each row of the child.
parentColumns	Array indicating parent column of each column of the child.

Classes

Macros

Functions

Macro Definition Documentation

◆ MIN_IF_EXISTS

Function Documentation

◆ cloneRecursively()

◆ CMRregularityCompleteDecomposition()

◆ CMRregularityQueueAdd()

◆ CMRregularityQueueCreate()

◆ CMRregularityQueueEmpty()

◆ CMRregularityQueueFree()

◆ CMRregularityQueueRemove()

◆ CMRregularityRefineDecomposition()

◆ CMRregularityTaskCreateRoot()

◆ CMRregularityTaskFree()

◆ CMRregularityTaskRun()

◆ CMRseymourAddMinor()

◆ CMRseymourCreateChildFromMatrices()

◆ CMRseymourDecompose()

◆ CMRseymourPrintChild()

◆ CMRseymourSetAttributes()

◆ CMRseymourSetNumChildren()

◆ CMRseymourUpdateOneSum()

◆ CMRseymourUpdatePivots()

◆ CMRseymourUpdateSeriesParallel()

◆ CMRseymourUpdateThreeSumCreateMixedFirstChild()

◆ CMRseymourUpdateThreeSumCreateMixedSecondChild()

◆ CMRseymourUpdateThreeSumCreateWideFirstChild()

◆ CMRseymourUpdateThreeSumCreateWideSecondChild()

◆ CMRseymourUpdateThreeSumInit()

◆ CMRseymourUpdateTwoSum()

◆ CMRseymourUpdateViolator()

◆ createNode()

◆ updateChildMatrix()

◆ updateRowsColumnsToChild()

◆ updateRowsColumnsToParent()