CMR  1.3.0
Typedefs | Enumerations | Functions
Representation matrices of matroids

Typedefs

typedef struct _CMR_DEC CMR_DEC
 

Enumerations

enum  CMR_DEC_TYPE {
  CMR_DEC_IRREGULAR = -1, CMR_DEC_UNKNOWN = 0, CMR_DEC_ONE_SUM = 1, CMR_DEC_TWO_SUM = 2,
  CMR_DEC_THREE_SUM = 3, CMR_DEC_GRAPHIC = 4, CMR_DEC_COGRAPHIC = 5, CMR_DEC_PLANAR = 6,
  CMR_DEC_SERIES_PARALLEL = 7, CMR_DEC_SPECIAL_R10 = 16, CMR_DEC_SPECIAL_FANO = 17, CMR_DEC_SPECIAL_FANO_DUAL = 18,
  CMR_DEC_SPECIAL_K_5 = 19, CMR_DEC_SPECIAL_K_5_DUAL = 20, CMR_DEC_SPECIAL_K_3_3 = 21, CMR_DEC_SPECIAL_K_3_3_DUAL = 22
}
 
enum  CMR_DEC_FLAGS {
  CMR_DEC_MASK_REPRESENTATION = 3, CMR_DEC_IS_GRAPHIC = 4, CMR_DEC_IS_COGRAPHIC = 8, CMR_DEC_IS_REGULAR = 16,
  CMR_DEC_HAS_LOWER_LEFT_NONZEROS = 32, CMR_DEC_HAS_UPPER_RIGHT_NONZEROS = 64
}
 

Functions

CMR_EXPORT CMR_ERROR CMRdecFree (CMR *cmr, CMR_DEC **pdec)
 
CMR_EXPORT bool CMRdecHasMatrix (CMR_DEC *dec)
 Returns true iff the matrix of the decomposition node is stored. More...
 
CMR_EXPORT bool CMRdecHasTranspose (CMR_DEC *dec)
 Returns true iff the transposed matrix of the decomposition node is stored. More...
 
CMR_EXPORT CMR_CHRMATCMRdecGetMatrix (CMR_DEC *dec)
 Returns the matrix of the decomposition node (or NULL if it is not stored). More...
 
CMR_EXPORT CMR_CHRMATCMRdecGetTranspose (CMR_DEC *dec)
 Returns the transposed matrix of the decomposition node (or NULL if it is not stored). More...
 
CMR_EXPORT size_t CMRdecNumChildren (CMR_DEC *dec)
 Returns the number of children of the decomposition node. More...
 
CMR_EXPORT CMR_DECCMRdecChild (CMR_DEC *dec, size_t childIndex)
 
CMR_EXPORT int CMRdecIsSum (CMR_DEC *dec, bool *plowerLeftNonzeros, bool *pupperRightNonzeros)
 Returns k if dec is a k-sum node and 0 otherwise. More...
 
CMR_EXPORT CMR_DEC_TYPE CMRdecIsSpecialLeaf (CMR_DEC *dec, int *prepresentationMatrix)
 Returns the corresponding flag if dec is a special matrix node and 0 otherwise. More...
 
CMR_EXPORT bool CMRdecIsGraphicLeaf (CMR_DEC *dec)
 Returns true if and only if dec is a graphic leaf node. More...
 
CMR_EXPORT bool CMRdecIsCographicLeaf (CMR_DEC *dec)
 Returns true if and only if dec is a cographic leaf node. More...
 
CMR_EXPORT bool CMRdecIsGraphic (CMR_DEC *dec)
 Returns true if and only if dec is graphic. More...
 
CMR_EXPORT bool CMRdecIsCographic (CMR_DEC *dec)
 Returns true if and only if dec is cographic. More...
 
CMR_EXPORT bool CMRdecIsRegular (CMR_DEC *dec)
 Returns true if and only if dec is regular. More...
 
CMR_EXPORT bool CMRdecNumRows (CMR_DEC *dec)
 Returns the number of rows. More...
 
CMR_EXPORT CMR_ELEMENTCMRdecRowElements (CMR_DEC *dec)
 Returns the row elements. More...
 
CMR_EXPORT size_t * CMRdecRowsParent (CMR_DEC *dec)
 Returns the mapping of rows to rows of parent. More...
 
CMR_EXPORT bool CMRdecNumColumns (CMR_DEC *dec)
 Returns the number of columns. More...
 
CMR_EXPORT CMR_ELEMENTCMRdecColumnElements (CMR_DEC *dec)
 Returns the column elements. More...
 
CMR_EXPORT size_t * CMRdecColumnsParent (CMR_DEC *dec)
 Returns the mapping of columns to columns of parent. More...
 
CMR_EXPORT CMR_ERROR CMRdecPrint (CMR *cmr, CMR_DEC *dec, FILE *stream, size_t indent, bool printMatrices, bool printGraphs, bool printReductions)
 Prints the decomposition dec to stream. More...
 
CMR_EXPORT char * CMRdecConsistency (CMR_DEC *dec, bool recurse)
 Checks a decomposition for consistency. More...
 
CMR_EXPORT CMR_GRAPHCMRdecGraph (CMR_DEC *dec)
 Returns the graph (if available). More...
 
CMR_EXPORT CMR_GRAPH_EDGECMRdecGraphForest (CMR_DEC *dec)
 Returns the forest of the graph (if available). More...
 
CMR_EXPORT size_t CMRdecGraphSizeForest (CMR_DEC *dec)
 Returns the number of edges of the graph's forest (if available). More...
 
CMR_EXPORT CMR_GRAPH_EDGECMRdecGraphCoforest (CMR_DEC *dec)
 Returns the coforest of the graph (if available). More...
 
CMR_EXPORT size_t CMRdecGraphSizeCoforest (CMR_DEC *dec)
 Returns the number of edges of the graph's coforest (if available). More...
 
CMR_EXPORT bool * CMRdecGraphArcsReversed (CMR_DEC *dec)
 Returns an array that indicates for the graph's edges whether they must be reversed (if available). More...
 
CMR_EXPORT CMR_GRAPHCMRdecCograph (CMR_DEC *dec)
 Returns the cograph (if available). More...
 
CMR_EXPORT CMR_GRAPH_EDGECMRdecCographForest (CMR_DEC *dec)
 Returns the forest of the cograph (if available). More...
 
CMR_EXPORT CMR_GRAPH_EDGECMRdecCographCoforest (CMR_DEC *dec)
 Returns the coforest of the cograph (if available). More...
 
CMR_EXPORT bool * CMRdecCographArcsReversed (CMR_DEC *dec)
 Returns an array that indicates for the cograph's edges whether they must be reversed (if available). More...
 

Detailed Description

Typedef Documentation

typedef struct _CMR_DEC CMR_DEC

Enumeration Type Documentation

Enumerator
CMR_DEC_MASK_REPRESENTATION 

Bit mask for a specific representation matrix of a minor.

CMR_DEC_IS_GRAPHIC 

Minor is graphic.

CMR_DEC_IS_COGRAPHIC 

Minor is cographic.

CMR_DEC_IS_REGULAR 

Minor is regular.

CMR_DEC_HAS_LOWER_LEFT_NONZEROS 

The 2- or 3-sum has nonzeros in lower-left.

CMR_DEC_HAS_UPPER_RIGHT_NONZEROS 

The 2- or 3-sum has nonzeros in upper-right.

Enumerator
CMR_DEC_IRREGULAR 

Node represents 3-connected irregular minor.

CMR_DEC_UNKNOWN 

Type of node is not yet determined.

CMR_DEC_ONE_SUM 

Node represents a 1-sum of minors; arbitrary number of child nodes.

CMR_DEC_TWO_SUM 

Node represents a 2-sum of minors; two child nodes.

CMR_DEC_THREE_SUM 

Node represents a 3-sum of minors; two child nodes.

CMR_DEC_GRAPHIC 

Node represents a graphic leaf minor; no child nodes.

CMR_DEC_COGRAPHIC 

Node represents a cographic leaf minor; no child nodes.

CMR_DEC_PLANAR 

Node represents a planar (graphic and cographic) leaf minor; no child nodes.

CMR_DEC_SERIES_PARALLEL 

Node represents a series-parallel reduction; one child node.

CMR_DEC_SPECIAL_R10 

Node represents a minor isomorphic to \( R_{10} \).

CMR_DEC_SPECIAL_FANO 

Node represents a minor isomorphic to \( F_7 \).

CMR_DEC_SPECIAL_FANO_DUAL 

Node represents a minor isomorphic to \( F_7^\star \).

CMR_DEC_SPECIAL_K_5 

Node represents a minor isomorphic to \( M(K_5) \).

CMR_DEC_SPECIAL_K_5_DUAL 

Node represents a minor isomorphic to \( M(K_5)^\star \).

CMR_DEC_SPECIAL_K_3_3 

Node represents a minor isomorphic to \( M(K_{3,3}) \).

CMR_DEC_SPECIAL_K_3_3_DUAL 

Node represents a minor isomorphic to \( M(K_{3,3})^\star \).

Function Documentation

CMR_EXPORT CMR_DEC* CMRdecChild ( CMR_DEC dec,
size_t  childIndex 
)
Parameters
decDecomposition node.
childIndexIndex of child.
CMR_EXPORT CMR_GRAPH* CMRdecCograph ( CMR_DEC dec)

Returns the cograph (if available).

Parameters
decDecomposition.
CMR_EXPORT bool* CMRdecCographArcsReversed ( CMR_DEC dec)

Returns an array that indicates for the cograph's edges whether they must be reversed (if available).

Parameters
decDecomposition.
CMR_EXPORT CMR_GRAPH_EDGE* CMRdecCographCoforest ( CMR_DEC dec)

Returns the coforest of the cograph (if available).

Parameters
decDecomposition.
CMR_EXPORT CMR_GRAPH_EDGE* CMRdecCographForest ( CMR_DEC dec)

Returns the forest of the cograph (if available).

Parameters
decDecomposition.
CMR_EXPORT CMR_ELEMENT* CMRdecColumnElements ( CMR_DEC dec)

Returns the column elements.

Parameters
decDecomposition.
CMR_EXPORT size_t* CMRdecColumnsParent ( CMR_DEC dec)

Returns the mapping of columns to columns of parent.

Parameters
decDecomposition.
CMR_EXPORT char* CMRdecConsistency ( CMR_DEC dec,
bool  recurse 
)

Checks a decomposition for consistency.

Checks whether a potentially stored alternative matrix (exhibiting a sequence of nested 3-connected minors) correctly corresponds to the stored matrix.

Returns
NULL if consistent. Otherwise, an explanation string is returned, which must free'd with free().
See also
CMRconsistencyAssert() for checking the returned string and aborting in case of inconsistency.
Parameters
decDecomposition.
recurseWhether all (grand-)children shall be checked, too.
CMR_EXPORT CMR_ERROR CMRdecFree ( CMR cmr,
CMR_DEC **  pdec 
)
Parameters
cmrCMR environment.
pdecPointer to the decomposition node.
CMR_EXPORT CMR_CHRMAT* CMRdecGetMatrix ( CMR_DEC dec)

Returns the matrix of the decomposition node (or NULL if it is not stored).

Parameters
decDecomposition node.
CMR_EXPORT CMR_CHRMAT* CMRdecGetTranspose ( CMR_DEC dec)

Returns the transposed matrix of the decomposition node (or NULL if it is not stored).

Parameters
decDecomposition node.
CMR_EXPORT CMR_GRAPH* CMRdecGraph ( CMR_DEC dec)

Returns the graph (if available).

Parameters
decDecomposition.
CMR_EXPORT bool* CMRdecGraphArcsReversed ( CMR_DEC dec)

Returns an array that indicates for the graph's edges whether they must be reversed (if available).

Parameters
decDecomposition.
CMR_EXPORT CMR_GRAPH_EDGE* CMRdecGraphCoforest ( CMR_DEC dec)

Returns the coforest of the graph (if available).

Parameters
decDecomposition.
CMR_EXPORT CMR_GRAPH_EDGE* CMRdecGraphForest ( CMR_DEC dec)

Returns the forest of the graph (if available).

Parameters
decDecomposition.
CMR_EXPORT size_t CMRdecGraphSizeCoforest ( CMR_DEC dec)

Returns the number of edges of the graph's coforest (if available).

Parameters
decDecomposition.
CMR_EXPORT size_t CMRdecGraphSizeForest ( CMR_DEC dec)

Returns the number of edges of the graph's forest (if available).

Parameters
decDecomposition.
CMR_EXPORT bool CMRdecHasMatrix ( CMR_DEC dec)

Returns true iff the matrix of the decomposition node is stored.

Parameters
decDecomposition node.
CMR_EXPORT bool CMRdecHasTranspose ( CMR_DEC dec)

Returns true iff the transposed matrix of the decomposition node is stored.

Parameters
decDecomposition node.
CMR_EXPORT bool CMRdecIsCographic ( CMR_DEC dec)

Returns true if and only if dec is cographic.

Parameters
decDecomposition.
CMR_EXPORT bool CMRdecIsCographicLeaf ( CMR_DEC dec)

Returns true if and only if dec is a cographic leaf node.

Parameters
decDecomposition.
CMR_EXPORT bool CMRdecIsGraphic ( CMR_DEC dec)

Returns true if and only if dec is graphic.

Parameters
decDecomposition.
CMR_EXPORT bool CMRdecIsGraphicLeaf ( CMR_DEC dec)

Returns true if and only if dec is a graphic leaf node.

Parameters
decDecomposition.
CMR_EXPORT bool CMRdecIsRegular ( CMR_DEC dec)

Returns true if and only if dec is regular.

Parameters
decDecomposition.
CMR_EXPORT CMR_DEC_TYPE CMRdecIsSpecialLeaf ( CMR_DEC dec,
int *  prepresentationMatrix 
)

Returns the corresponding flag if dec is a special matrix node and 0 otherwise.

Parameters
decDecomposition.
prepresentationMatrixPointer for storing the id of the actual representation matrix (may be NULL).
CMR_EXPORT int CMRdecIsSum ( CMR_DEC dec,
bool *  plowerLeftNonzeros,
bool *  pupperRightNonzeros 
)

Returns k if dec is a k-sum node and 0 otherwise.

Parameters
decDecomposition node.
plowerLeftNonzerosPointer for storing the lower-left submatrix of a 2- or 3-sum contains a nonzero (may be NULL).
pupperRightNonzerosPointer for storing the lower-left submatrix of a 2- or 3-sum contains a nonzero (may be NULL).
CMR_EXPORT size_t CMRdecNumChildren ( CMR_DEC dec)

Returns the number of children of the decomposition node.

Parameters
decDecomposition node.
CMR_EXPORT bool CMRdecNumColumns ( CMR_DEC dec)

Returns the number of columns.

Parameters
decDecomposition.
CMR_EXPORT bool CMRdecNumRows ( CMR_DEC dec)

Returns the number of rows.

Parameters
decDecomposition.
CMR_EXPORT CMR_ERROR CMRdecPrint ( CMR cmr,
CMR_DEC dec,
FILE *  stream,
size_t  indent,
bool  printMatrices,
bool  printGraphs,
bool  printReductions 
)

Prints the decomposition dec to stream.

Parameters
cmrCMR environment.
decDecomposition node.
streamStream to write to.
indentIndentation of this node.
printMatricesWhether to print matrices.
printGraphsWhether to print graphs.
printReductionsWhether to print series-parallel reductions.
CMR_EXPORT CMR_ELEMENT* CMRdecRowElements ( CMR_DEC dec)

Returns the row elements.

Parameters
decDecomposition.
CMR_EXPORT size_t* CMRdecRowsParent ( CMR_DEC dec)

Returns the mapping of rows to rows of parent.

Parameters
decDecomposition.