![]() |
CMR
1.3.0
|
#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... | |
#define MIN_IF_EXISTS | ( | currentValue, | |
child, | |||
childValue | |||
) |
|
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.
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 . |
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 | 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. |
void CMRregularityQueueAdd | ( | DecompositionQueue * | queue, |
DecompositionTask * | task | ||
) |
Adds a task to a decomposition queue.
queue | Queue. |
task | Task. |
CMR_ERROR CMRregularityQueueCreate | ( | CMR * | cmr, |
DecompositionQueue ** | pqueue | ||
) |
Initializes a decomposition queue.
cmr | CMR environment. |
pqueue | Pointer for storing the queue. |
bool CMRregularityQueueEmpty | ( | DecompositionQueue * | queue | ) |
Returns whether a queue is empty.
queue | Queue. |
CMR_ERROR CMRregularityQueueFree | ( | CMR * | cmr, |
DecompositionQueue ** | pqueue | ||
) |
Frees the decomposition queue.
cmr | CMR environment. |
pqueue | Pointer to queue. |
DecompositionTask* CMRregularityQueueRemove | ( | DecompositionQueue * | queue | ) |
Removes a task from a decomposition queue.
queue | Queue. |
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.
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. |
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 | 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. |
CMR_ERROR CMRregularityTaskFree | ( | CMR * | cmr, |
DecompositionTask ** | ptask | ||
) |
Frees a decomposition task.
cmr | CMR environment. |
ptask | Pointer to task. |
|
static |
Runs a task for processing the associated decomposition node.
cmr | CMR environment. |
task | Task to be processed; already removed from the list of unprocessed tasks. |
queue | Queue of unprocessed tasks. |
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.
cmr | CMR environment. |
node | Seymour decomposition node. |
minor | Minor to be added. |
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.
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. |
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!
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. |
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 | 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. |
CMR_ERROR CMRseymourSetAttributes | ( | CMR_SEYMOUR_NODE * | node | ) |
Set regularity and (co)graphicness attributes of a decomposition tree.
node | 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 | CMR environment. |
node | Seymour decomposition node. |
numChildren | Number of children. |
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 | CMR environment. |
node | Seymour decomposition node. |
numChildren | Number of child nodes. |
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.
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 . |
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 | CMR environment. |
node | Seymour decomposition node. |
reducedSubmatrix | SP-reduced submatrix. |
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.
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. |
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.
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. |
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.
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. |
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.
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. |
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.
cmr | CMR environment. |
node | Seymour decomposition 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
.
The two child nodes will be of type CMR_SEYMOUR_NODE_TYPE_UNKNOWN.
cmr | CMR environment. |
node | Seymour decomposition node. |
separation | 2-separation. |
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 | CMR environment. |
node | Seymour decomposition node. |
violator | Submatrix. Is not copied. |
|
static |
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. |
|
static |
Updates matrix of dec
from parent using rowsParent and columnsParent arrays.
cmr | CMR environment. |
parent | Parent node in Seymour decomposition. |
childIndex | Index of child to update. |
|
static |
Updates rowsToChild and columnsToChild of the parent.
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. |
|
static |
Allocates and sets childRowsToParent and childColumnsToParent of the child of parent
indicated by childIndex
.
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. |