CMR  1.3.0
dec_internal.h
Go to the documentation of this file.
1 #ifndef CMR_DEC_INTERNAL_H
2 #define CMR_DEC_INTERNAL_H
3 
4 #include <cmr/dec.h>
5 #include <cmr/matroid.h>
6 #include <cmr/series_parallel.h>
7 
8 struct _CMR_DEC
9 {
14  struct _CMR_DEC* parent;
15  size_t numChildren;
16  struct _CMR_DEC** children;
18  size_t numRows;
19  size_t* rowsParent;
21  size_t numColumns;
22  size_t* columnsParent;
35  size_t numReductions;
47 };
48 
54  CMR* cmr,
55  CMR_DEC* parent,
56  size_t numRows,
57  size_t* rowsParent,
58  size_t numColumns,
59  size_t* columnsParent,
60  CMR_DEC** pdec
61 );
62 
68  CMR* cmr,
69  CMR_DEC* node
70 );
71 
77  CMR* cmr,
78  CMR_DEC* node,
79  size_t numChildren
80 );
81 
87  CMR_DEC* node
88 );
89 
95  CMR_DEC* node,
96  CMR_MINOR* minor
97 );
98 
106  CMR* cmr,
107  CMR_DEC* dec,
108  CMR_SEPA* sepa
109 );
110 
116  CMR* cmr,
117  CMR_DEC* dec,
118  FILE* stream
119 );
120 
121 #endif /* CMR_DEC_INTERNAL_H */
Data structures for a decomposition tree for a matrix.
CMR_ERROR CMRdecInheritMatrices(CMR *cmr, CMR_DEC *node)
Construct matrix and tranpose based on rowsParent and columnsParent.
Definition: dec.c:405
CMR_ERROR CMRdecTranslateMinorToParent(CMR_DEC *node, CMR_MINOR *minor)
Translate the rows/columns of minor to the parent of node.
Definition: dec.c:505
CMR_ERROR CMRdecComputeRegularity(CMR_DEC *node)
Traverses decomposition tree to decide if node is regular, graphic or cographic.
Definition: dec.c:448
CMR_ERROR CMRdecPrintSequenceNested3ConnectedMinors(CMR *cmr, CMR_DEC *dec, FILE *stream)
Prints the sequence of nested 3-connected minors for the matrix of a decomposition node.
Definition: dec.c:911
CMR_ERROR CMRdecSetNumChildren(CMR *cmr, CMR_DEC *node, size_t numChildren)
Sets the number of child nodes and allocates memory.
Definition: dec.c:435
CMR_ERROR CMRdecCreate(CMR *cmr, CMR_DEC *parent, size_t numRows, size_t *rowsParent, size_t numColumns, size_t *columnsParent, CMR_DEC **pdec)
Creates a decomposition node.
Definition: dec.c:355
CMR_ERROR CMRdecApplySeparation(CMR *cmr, CMR_DEC *dec, CMR_SEPA *sepa)
Turns the given node into one for the given separation.
Definition: dec.c:583
int CMR_ELEMENT
Definition: element.h:20
CMR_ERROR
Type for return codes of library functions.
Definition: env.h:31
int CMR_GRAPH_EDGE
Reference to an edge of CMR_GRAPH.
Definition: graph.h:31
CMR_DEC_TYPE
Definition: dec.h:34
CMR_DEC_FLAGS
Definition: dec.h:55
Functionality for matroids.
Recognition of series-parallel matrices.
Row-wise representation of sparse char matrix.
Definition: matrix.h:204
Definition: env_internal.h:45
Definition: graph.h:49
A minor of a matroid.
Definition: matroid.h:28
Definition: separation.h:24
Represents a series-parallel reduction.
Definition: series_parallel.h:61
Definition: dec_internal.h:9
CMR_ELEMENT * nestedMinorsRowsOriginal
Maps rows of nestedMinorsMatrix to elements of matrix.
Definition: dec_internal.h:44
struct _CMR_DEC * parent
Parent node (NULL for decomposition root).
Definition: dec_internal.h:14
CMR_DEC_TYPE type
Type of this node.
Definition: dec_internal.h:10
CMR_SEPA * separation
Separation data.
Definition: dec_internal.h:37
size_t numChildren
Number of child nodes.
Definition: dec_internal.h:15
CMR_GRAPH_EDGE * cographForest
Spanning forest of cograph.
Definition: dec_internal.h:30
struct _CMR_DEC ** children
Array of child nodes.
Definition: dec_internal.h:16
CMR_SP_REDUCTION * reductions
Array of series-parallel reductions.
Definition: dec_internal.h:34
CMR_DEC_FLAGS flags
Flags for this node.
Definition: dec_internal.h:11
size_t numColumns
Length of columnsParent.
Definition: dec_internal.h:21
CMR_GRAPH * cograph
Graph represented by the transpose of this matrix.
Definition: dec_internal.h:29
bool * graphArcsReversed
Array indicating which arcs of the graph are reversed.
Definition: dec_internal.h:27
size_t numReductions
Length of reductions.
Definition: dec_internal.h:35
CMR_CHRMAT * nestedMinorsMatrix
Equivalent binary matrix that displays the sequence of nested minors.
Definition: dec_internal.h:39
size_t * nestedMinorsSequenceNumColumns
Number of columns of sequence of nested minors.
Definition: dec_internal.h:42
size_t * rowsParent
Array for mapping rows to rows of parent.
Definition: dec_internal.h:19
size_t numRows
Length of rowsParent.
Definition: dec_internal.h:18
CMR_GRAPH_EDGE * graphCoforest
Coforest of graph.
Definition: dec_internal.h:26
CMR_GRAPH * graph
Graph represented by this matrix.
Definition: dec_internal.h:24
size_t * columnsParent
Array for mapping columns to columns of parent.
Definition: dec_internal.h:22
CMR_CHRMAT * transpose
Tranpose of matrix representing this node.
Definition: dec_internal.h:13
size_t nestedMinorsLength
Length of sequence of nested minors.
Definition: dec_internal.h:43
CMR_GRAPH_EDGE * graphForest
Spanning forest of graph.
Definition: dec_internal.h:25
CMR_ELEMENT * nestedMinorsColumnsOriginal
Maps columns of nestedMinorsMatrix to elements of matrix.
Definition: dec_internal.h:45
size_t * nestedMinorsSequenceNumRows
Number of rows of sequence of nested minors.
Definition: dec_internal.h:41
CMR_CHRMAT * matrix
Matrix representing this node.
Definition: dec_internal.h:12
CMR_GRAPH_EDGE * cographCoforest
Coforest of cograph.
Definition: dec_internal.h:31
bool * cographArcsReversed
Array indicating which arcs of the cograph are reversed.
Definition: dec_internal.h:32