CMR  1.3.0
series_parallel.h
Go to the documentation of this file.
1 #ifndef CMR_SERIES_PARALLEL_H
2 #define CMR_SERIES_PARALLEL_H
3 
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15 
16 #include <cmr/element.h>
17 #include <cmr/matrix.h>
18 #include <cmr/separation.h>
19 
24 typedef struct
25 {
26  uint32_t totalCount;
27  double totalTime;
28  uint32_t reduceCount;
29  double reduceTime;
30  uint32_t wheelCount;
31  double wheelTime;
32  uint32_t nonbinaryCount;
33  double nonbinaryTime;
35 
40 CMR_EXPORT
42  CMR_SP_STATISTICS* stats
43 );
44 
49 CMR_EXPORT
51  FILE* stream,
52  CMR_SP_STATISTICS* stats,
53  const char* prefix
54 );
55 
60 typedef struct
61 {
65 
70 CMR_EXPORT
72  CMR_SP_REDUCTION reduction,
73  char* buffer
77 );
78 
83 static inline
85  CMR_SP_REDUCTION reduction
86 )
87 {
88  return reduction.element < 0;
89 }
90 
95 static inline
97  CMR_SP_REDUCTION reduction
98 )
99 {
100  return reduction.element > 0;
101 }
102 
107 static inline
109  CMR_SP_REDUCTION reduction
110 )
111 {
112  return reduction.mate == 0;
113 }
114 
119 static inline
121  CMR_SP_REDUCTION reduction
122 )
123 {
124  return reduction.element * reduction.mate < 0;
125 }
126 
131 static inline
133  CMR_SP_REDUCTION reduction
134 )
135 {
136  return reduction.element * reduction.mate > 0;
137 }
138 
143 static inline
145  CMR_SP_REDUCTION reduction
146 )
147 {
148  return reduction.element != 0;
149 }
150 
165 CMR_EXPORT
167  CMR* cmr,
168  CMR_CHRMAT* matrix,
169  bool* pisSeriesParallel,
170  CMR_SP_REDUCTION* reductions,
172  size_t* pnumReductions,
173  CMR_SUBMAT** preducedSubmatrix,
174  CMR_SUBMAT** pviolatorSubmatrix,
175  CMR_SP_STATISTICS* stats,
176  double timeLimit
177 );
178 
193 CMR_EXPORT
195  CMR* cmr,
196  CMR_CHRMAT* matrix,
197  bool* pisSeriesParallel,
198  CMR_SP_REDUCTION* reductions,
200  size_t* pnumReductions,
201  CMR_SUBMAT** preducedSubmatrix,
202  CMR_SUBMAT** pviolatorSubmatrix,
203  CMR_SP_STATISTICS* stats,
204  double timeLimit
205 );
206 
225 CMR_EXPORT
227  CMR* cmr,
228  CMR_CHRMAT* matrix,
229  bool* pisSeriesParallel,
230  CMR_SP_REDUCTION* reductions,
232  size_t maxNumReductions,
233  size_t* pnumReductions,
235  CMR_SUBMAT** preducedSubmatrix,
236  CMR_SUBMAT** pviolatorSubmatrix,
237  CMR_SEPA** pseparation,
238  CMR_SP_STATISTICS* stats,
239  double timeLimit
240 );
241 
242 
265 CMR_EXPORT
267  CMR* cmr,
268  CMR_CHRMAT* matrix,
269  bool* pisSeriesParallel,
270  CMR_SP_REDUCTION* reductions,
272  size_t maxNumReductions,
273  size_t* pnumReductions,
275  CMR_SUBMAT** preducedSubmatrix,
276  CMR_SUBMAT** pviolatorSubmatrix,
278  CMR_SEPA** pseparation,
279  CMR_SP_STATISTICS* stats,
280  double timeLimit
281 );
282 
283 #ifdef __cplusplus
284 }
285 #endif
286 
287 #endif /* CMR_SERIES_PARALLEL_H */
Functionality for the row and column elements of a matrix.
int CMR_ELEMENT
Definition: element.h:20
CMR_ERROR
Type for return codes of library functions.
Definition: env.h:32
Functionality for sparse matrices.
Data structures for k-separations and k-sums.
CMR_EXPORT CMR_ERROR CMRspStatsInit(CMR_SP_STATISTICS *stats)
Initializes all statistics for series-parallel computations.
Definition: series_parallel.c:37
CMR_EXPORT CMR_ERROR CMRdecomposeBinarySeriesParallel(CMR *cmr, CMR_CHRMAT *matrix, bool *pisSeriesParallel, CMR_SP_REDUCTION *reductions, size_t maxNumReductions, size_t *pnumReductions, CMR_SUBMAT **preducedSubmatrix, CMR_SUBMAT **pviolatorSubmatrix, CMR_SEPA **pseparation, CMR_SP_STATISTICS *stats, double timeLimit)
Finds all series-parallel reductions for the binary matrix .
Definition: series_parallel.c:1686
CMR_EXPORT CMR_ERROR CMRtestTernarySeriesParallel(CMR *cmr, CMR_CHRMAT *matrix, bool *pisSeriesParallel, CMR_SP_REDUCTION *reductions, size_t *pnumReductions, CMR_SUBMAT **preducedSubmatrix, CMR_SUBMAT **pviolatorSubmatrix, CMR_SP_STATISTICS *stats, double timeLimit)
Finds all series-parallel reductions for the ternary matrix .
Definition: series_parallel.c:1942
static bool CMRspIsCopy(CMR_SP_REDUCTION reduction)
Returns true if the series-parallel reduction removes a vector that is a copy of another vector.
Definition: series_parallel.h:132
static bool CMRspIsColumn(CMR_SP_REDUCTION reduction)
Returns true if the series-parallel reduction removes a column, i.e., is parallel.
Definition: series_parallel.h:96
CMR_EXPORT CMR_ERROR CMRdecomposeTernarySeriesParallel(CMR *cmr, CMR_CHRMAT *matrix, bool *pisSeriesParallel, CMR_SP_REDUCTION *reductions, size_t maxNumReductions, size_t *pnumReductions, CMR_SUBMAT **preducedSubmatrix, CMR_SUBMAT **pviolatorSubmatrix, CMR_SEPA **pseparation, CMR_SP_STATISTICS *stats, double timeLimit)
Finds all series-parallel reductions for the ternary matrix .
Definition: series_parallel.c:1969
static bool CMRspIsZero(CMR_SP_REDUCTION reduction)
Returns true if the series-parallel reduction removes a zero vector.
Definition: series_parallel.h:108
CMR_EXPORT char * CMRspReductionString(CMR_SP_REDUCTION reduction, char *buffer)
Definition: series_parallel.c:73
CMR_EXPORT CMR_ERROR CMRtestBinarySeriesParallel(CMR *cmr, CMR_CHRMAT *matrix, bool *pisSeriesParallel, CMR_SP_REDUCTION *reductions, size_t *pnumReductions, CMR_SUBMAT **preducedSubmatrix, CMR_SUBMAT **pviolatorSubmatrix, CMR_SP_STATISTICS *stats, double timeLimit)
Finds all series-parallel reductions for the binary matrix .
Definition: series_parallel.c:1658
static bool CMRspIsRow(CMR_SP_REDUCTION reduction)
Returns true if the series-parallel reduction removes a row, i.e., is series.
Definition: series_parallel.h:84
static bool CMRspIsUnit(CMR_SP_REDUCTION reduction)
Returns true if the series-parallel reduction removes a unit vector.
Definition: series_parallel.h:120
static bool CMRspIsValid(CMR_SP_REDUCTION reduction)
Returns true if the series-parallel reduction is valid.
Definition: series_parallel.h:144
CMR_EXPORT CMR_ERROR CMRspStatsPrint(FILE *stream, CMR_SP_STATISTICS *stats, const char *prefix)
Prints statistics for series-parallel computations.
Definition: series_parallel.c:53
Row-wise representation of sparse char matrix.
Definition: matrix.h:204
Definition: env_internal.h:45
Definition: separation.h:52
Represents a series-parallel reduction.
Definition: series_parallel.h:61
CMR_ELEMENT mate
Definition: series_parallel.h:63
CMR_ELEMENT element
Definition: series_parallel.h:62
Statistics for series-parallel recognition algorithm.
Definition: series_parallel.h:25
double wheelTime
Definition: series_parallel.h:31
double totalTime
Definition: series_parallel.h:27
uint32_t totalCount
Definition: series_parallel.h:26
uint32_t reduceCount
Definition: series_parallel.h:28
uint32_t wheelCount
Definition: series_parallel.h:30
double reduceTime
Definition: series_parallel.h:29
uint32_t nonbinaryCount
Definition: series_parallel.h:32
double nonbinaryTime
Definition: series_parallel.h:33
Row and column indices for a submatrix.
Definition: matrix.h:28