CMR  1.3.0
tu.h
Go to the documentation of this file.
1 #ifndef CMR_TU_H
2 #define CMR_TU_H
3 
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15 
16 #include <cmr/env.h>
17 #include <cmr/regular.h>
18 #include <cmr/matrix.h>
19 #include <cmr/camion.h>
20 
21 typedef enum
22 {
23  CMR_TU_ALGORITHM_DECOMPOSITION = 0,
24  CMR_TU_ALGORITHM_EULERIAN = 1,
25  CMR_TU_ALGORITHM_PARTITION = 2
26 } CMR_TU_ALGORITHM;
27 
28 typedef struct
29 {
30  CMR_TU_ALGORITHM algorithm;
31  CMR_SEYMOUR_PARAMS seymour;
32  bool ternary;
33  bool camionFirst;
34  bool naiveSubmatrix;
36 } CMR_TU_PARAMS;
37 
44 CMR_EXPORT
45 CMR_ERROR CMRtuParamsInit(
46  CMR_TU_PARAMS* params
47 );
48 
53 typedef struct
54 {
55  CMR_SEYMOUR_STATS seymour;
56  CMR_CAMION_STATISTICS camion;
58  uint32_t enumerationRowSubsets;
59  uint32_t enumerationColumnSubsets;
60  double enumerationTime;
62  uint32_t partitionRowSubsets;
63  uint32_t partitionColumnSubsets;
64  double partitionTime;
65 } CMR_TU_STATS;
66 
71 CMR_EXPORT
72 CMR_ERROR CMRtuStatsInit(
73  CMR_TU_STATS* stats
74 );
75 
80 CMR_EXPORT
81 CMR_ERROR CMRtuStatsPrint(
82  FILE* stream,
83  CMR_TU_STATS* stats,
84  const char* prefix
85 );
86 
99 CMR_EXPORT
100 CMR_ERROR CMRtuTest(
101  CMR* cmr,
102  CMR_CHRMAT* matrix,
103  bool* pisTotallyUnimodular,
104  CMR_SEYMOUR_NODE** proot,
105  CMR_SUBMAT** psubmatrix,
106  CMR_TU_PARAMS* params,
107  CMR_TU_STATS* stats,
108  double timeLimit
109 );
110 
120 CMR_EXPORT
121 CMR_ERROR CMRtuCompleteDecomposition(
122  CMR* cmr,
123  CMR_SEYMOUR_NODE* dec,
124  CMR_TU_PARAMS* params,
125  CMR_TU_STATS* stats,
126  double timeLimit
127 );
128 
129 #ifdef __cplusplus
130 }
131 #endif
132 
133 #endif /* CMR_TU_H */
camion.h
Testing whether a matrix is Camion-signed.
env.h
Basic functionality of the software library.
CMR_ERROR
CMR_ERROR
Type for return codes of library functions.
Definition: env.h:32
matrix.h
Functionality for sparse matrices.
regular.h
Recognition of binary regular matrices.
CMR_CAMION_STATISTICS
Statistics for Camion-signing algorithm.
Definition: camion.h:26
CMR_CHRMAT
Row-wise representation of sparse char matrix.
Definition: matrix.h:220
CMR_ENVIRONMENT
Definition: env_internal.h:45
CMR_SEYMOUR_PARAMS
Parameters for Seymour decomposition algorithm.
Definition: seymour.h:93
CMR_SEYMOUR_STATS
Statistics for Seymour decomposition algorithm.
Definition: seymour.h:169
CMR_SUBMAT
Row and column indices for a submatrix.
Definition: matrix.h:28
CMR_TU_PARAMS
Definition: tu.h:29
CMR_TU_PARAMS::naiveSubmatrix
bool naiveSubmatrix
Whether to use the naive submatrix search instead of a greedy algorithm (default: false).
Definition: tu.h:34
CMR_TU_PARAMS::camionFirst
bool camionFirst
If ternary is false, then whether to run the Camion test first.
Definition: tu.h:33
CMR_TU_PARAMS::seymour
CMR_SEYMOUR_PARAMS seymour
Parameters for testing via Seymour decomposition.
Definition: tu.h:31
CMR_TU_PARAMS::algorithm
CMR_TU_ALGORITHM algorithm
Algorithm to use.
Definition: tu.h:30
CMR_TU_PARAMS::ternary
bool ternary
Whether to create a ternary Seymour decomposition tree (default: true).
Definition: tu.h:32
CMR_TU_STATS
Statistics for recognition algorithm for totally unimodular matrices.
Definition: tu.h:54
CMR_TU_STATS::enumerationColumnSubsets
uint32_t enumerationColumnSubsets
Definition: tu.h:59
CMR_TU_STATS::seymour
CMR_SEYMOUR_STATS seymour
Definition: tu.h:55
CMR_TU_STATS::camion
CMR_CAMION_STATISTICS camion
Definition: tu.h:56
CMR_TU_STATS::partitionTime
double partitionTime
Definition: tu.h:64
CMR_TU_STATS::partitionRowSubsets
uint32_t partitionRowSubsets
Definition: tu.h:62
CMR_TU_STATS::enumerationTime
double enumerationTime
Definition: tu.h:60
CMR_TU_STATS::enumerationRowSubsets
uint32_t enumerationRowSubsets
Definition: tu.h:58
CMR_TU_STATS::partitionColumnSubsets
uint32_t partitionColumnSubsets
Definition: tu.h:63
_CMR_SEYMOUR_NODE
Definition: seymour_internal.h:18
CMRtuParamsInit
CMR_EXPORT CMR_ERROR CMRtuParamsInit(CMR_TU_PARAMS *params)
Initializes the default parameters for recognition of totally unimodular matrices.
Definition: tu.c:15
CMRtuCompleteDecomposition
CMR_EXPORT CMR_ERROR CMRtuCompleteDecomposition(CMR *cmr, CMR_SEYMOUR_NODE *dec, CMR_TU_PARAMS *params, CMR_TU_STATS *stats, double timeLimit)
Completes a subtree of an existing decomposition tree.
Definition: tu.c:725
CMR_TU_ALGORITHM
CMR_TU_ALGORITHM
Definition: tu.h:22
CMR_TU_ALGORITHM_PARTITION
@ CMR_TU_ALGORITHM_PARTITION
Enumeration algorithm based on criterion of Ghouila-Houri.
Definition: tu.h:25
CMR_TU_ALGORITHM_EULERIAN
@ CMR_TU_ALGORITHM_EULERIAN
Enumeration algorithm based on Eulerian submatrices.
Definition: tu.h:24
CMR_TU_ALGORITHM_DECOMPOSITION
@ CMR_TU_ALGORITHM_DECOMPOSITION
Algorithm based on Seymour's decomposition of regular matroids.
Definition: tu.h:23
CMRtuStatsInit
CMR_EXPORT CMR_ERROR CMRtuStatsInit(CMR_TU_STATS *stats)
Initializes all statistics for recognition algorithm for totally unimodular matrices.
Definition: tu.c:28
CMRtuTest
CMR_EXPORT CMR_ERROR CMRtuTest(CMR *cmr, CMR_CHRMAT *matrix, bool *pisTotallyUnimodular, CMR_SEYMOUR_NODE **proot, CMR_SUBMAT **psubmatrix, CMR_TU_PARAMS *params, CMR_TU_STATS *stats, double timeLimit)
Tests a matrix for being totally unimodular.
Definition: tu.c:624
CMRtuStatsPrint
CMR_EXPORT CMR_ERROR CMRtuStatsPrint(FILE *stream, CMR_TU_STATS *stats, const char *prefix)
Prints statistics for recognition algorithm for totally unimodular matrices.
Definition: tu.c:46
Generated by doxygen 1.9.1