seymour.c File Reference

#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.
CMR_ERROR	CMRseymourStatsInit (CMR_SEYMOUR_STATS *stats)
	Initializes all statistics for Seymour decomposition computations.
CMR_ERROR	CMRseymourStatsPrint (FILE *stream, CMR_SEYMOUR_STATS *stats, const char *prefix)
	Prints statistics for Seymour decomposition computations.
bool	CMRseymourIsTernary (CMR_SEYMOUR_NODE *node)
	Returns true iff the decomposition is over \( \mathbb{F}_3 \).
CMR_CHRMAT *	CMRseymourGetMatrix (CMR_SEYMOUR_NODE *node)
	Returns the matrix of the decomposition node dec (or NULL if it is not stored).
bool	CMRseymourHasTranspose (CMR_SEYMOUR_NODE *node)
	Returns true iff the transposed matrix of the decomposition node dec is stored.
CMR_CHRMAT *	CMRseymourGetTranspose (CMR_SEYMOUR_NODE *node)
	Returns the transposed matrix of the decomposition node dec (or NULL if it is not stored).
size_t	CMRseymourNumChildren (CMR_SEYMOUR_NODE *node)
	Returns the number of children of the decomposition node dec.
CMR_SEYMOUR_NODE *	CMRseymourChild (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns a child of the decomposition node dec.
CMR_SEYMOUR_NODE_TYPE	CMRseymourType (CMR_SEYMOUR_NODE *node)
	Returns the type of a decomposition node dec.
int8_t	CMRseymourGraphicness (CMR_SEYMOUR_NODE *node)
	Indicates graphicness/being network.
int8_t	CMRseymourCographicness (CMR_SEYMOUR_NODE *node)
	Indicates cographicness/being conetwork.
int8_t	CMRseymourRegularity (CMR_SEYMOUR_NODE *node)
	Indicates regularity/total unimodularity.
size_t	CMRseymourNumRows (CMR_SEYMOUR_NODE *node)
	Returns the number of rows.
CMR_ELEMENT *	CMRseymourChildRowsToParent (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the mapping of rows of child childIndex to this node's elements.
CMR_ELEMENT *	CMRseymourChildColumnsToParent (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the mapping of columns of child childIndex to this node's elements.
size_t *	CMRseymourChildSpecialRows (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the array of special rows of child childIndex.
size_t *	CMRseymourChildSpecialColumns (CMR_SEYMOUR_NODE *node, size_t childIndex)
	Returns the array of special columns of child childIndex.
size_t	CMRseymourNumColumns (CMR_SEYMOUR_NODE *node)
	Returns the number of columns.
CMR_GRAPH *	CMRseymourGraph (CMR_SEYMOUR_NODE *node)
	Returns the graph (if available).
CMR_GRAPH_EDGE *	CMRseymourGraphForest (CMR_SEYMOUR_NODE *node)
	Returns the forest of the graph (if available).
size_t	CMRseymourGraphSizeForest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the graph's forest (if available).
CMR_GRAPH_EDGE *	CMRseymourGraphCoforest (CMR_SEYMOUR_NODE *node)
	Returns the coforest of the graph (if available).
size_t	CMRseymourGraphSizeCoforest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the graph's coforest (if available).
bool *	CMRseymourGraphArcsReversed (CMR_SEYMOUR_NODE *node)
	Returns an array that indicates for the graph's edges whether they must be reversed (if available).
CMR_GRAPH *	CMRseymourCograph (CMR_SEYMOUR_NODE *node)
	Returns the cograph (if available).
size_t	CMRseymourCographSizeForest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the cograph's forest (if available).
CMR_GRAPH_EDGE *	CMRseymourCographForest (CMR_SEYMOUR_NODE *node)
	Returns the forest of the cograph (if available).
size_t	CMRseymourCographSizeCoforest (CMR_SEYMOUR_NODE *node)
	Returns the number of edges of the cograph's coforest (if available).
CMR_GRAPH_EDGE *	CMRseymourCographCoforest (CMR_SEYMOUR_NODE *node)
	Returns the coforest of the cograph (if available).
bool *	CMRseymourCographArcsReversed (CMR_SEYMOUR_NODE *node)
	Returns an array that indicates for the cograph's edges whether they must be reversed (if available).
size_t	CMRseymourNumPivots (CMR_SEYMOUR_NODE *node)
	Returns the number of pivots (if available).
size_t *	CMRseymourPivotRows (CMR_SEYMOUR_NODE *node)
	Returns the array with the pivot rows (if available).
size_t *	CMRseymourPivotColumns (CMR_SEYMOUR_NODE *node)
	Returns the array with the pivot columns (if available).
size_t	CMRseymourGetUsed (CMR_SEYMOUR_NODE *node)
	Returns node's reference counter.
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	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.
CMR_ERROR	CMRseymourCapture (CMR *cmr, CMR_SEYMOUR_NODE *node)
	Increases the reference counter by 1.
CMR_ERROR	CMRseymourRelease (CMR *cmr, CMR_SEYMOUR_NODE **pnode)
	Releases a decomposition node, freeing it if this was the last reference.
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.
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.
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.
static CMR_ERROR	updateChildMatrix (CMR *cmr, CMR_SEYMOUR_NODE *parent, size_t childIndex)
	Updates matrix of dec from parent using rowsParent and columnsParent arrays.
CMR_ERROR	CMRseymourCreate (CMR *cmr, CMR_SEYMOUR_NODE **pnode, bool isTernary, CMR_CHRMAT *matrix, bool copyMatrix)
	Creates an unknown decomposition node as a root.
CMR_ERROR	CMRseymourAddMinor (CMR *cmr, CMR_SEYMOUR_NODE *node, CMR_MINOR *minor)
	Adds a minor to a Seymour decomposition node.
size_t	CMRseymourNumMinors (CMR_SEYMOUR_NODE *node)
	Returns the number of minors of the decomposition node.
CMR_MINOR *	CMRseymourMinor (CMR_SEYMOUR_NODE *node, size_t minorIndex)
	Returns a minor of the 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	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	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	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.
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.
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.
CMR_ERROR	CMRregularityTaskCreateRoot (CMR *cmr, CMR_SEYMOUR_NODE *node, 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.
static CMR_ERROR	CMRregularityTaskRun (CMR *cmr, DecompositionTask *task, DecompositionQueue *queue)
	Runs a task for processing the associated decomposition node.
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.

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 *	node,
		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.
node	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.

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.

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.