/usr/include/cdd/cdd.h is in libcdd-dev 094b.dfsg-4.2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 | /* cdd.h: Header file for cddlib.c
written by Komei Fukuda, fukuda@ifor.math.ethz.ch
Version 0.94, Aug. 4, 2005
*/
/* cddlib.c : C-Implementation of the double description method for
computing all vertices and extreme rays of the polyhedron
P= {x : b - A x >= 0}.
Please read COPYING (GNU General Public Licence) and
the manual cddlibman.tex for detail.
*/
#ifndef __CDD_H
#define __CDD_H
#endif /* __CDD_H */
#ifndef __CDDMP_H
#include "cddmp.h"
#endif /* __CDDMP_H */
#ifndef __CDDTYPES_H
#include "cddtypes.h"
#endif /* __CDDTYPES_H */
#ifdef GMPRATIONAL
#ifndef __CDD_HF
#include "cdd_f.h"
#endif
#endif
/* GLOBAL CONSTANTS and STATISTICS VARIABLES (to be set by dd_set_global_constants() */
extern mytype dd_zero;
extern mytype dd_one;
extern mytype dd_purezero;
extern mytype dd_minuszero;
extern mytype dd_minusone;
extern time_t dd_statStartTime; /* cddlib starting time */
extern long dd_statBApivots; /* basis finding pivots */
extern long dd_statCCpivots; /* criss-cross pivots */
extern long dd_statDS1pivots; /* phase 1 pivots */
extern long dd_statDS2pivots; /* phase 2 pivots */
extern long dd_statACpivots; /* anticycling (cc) pivots */
#ifdef GMPRATIONAL
extern long dd_statBSpivots; /* basis status checking pivots */
#endif
extern dd_LPSolverType dd_choiceLPSolverDefault; /* Default LP solver Algorithm */
extern dd_LPSolverType dd_choiceRedcheckAlgorithm; /* Redundancy Checking Algorithm */
extern dd_boolean dd_choiceLexicoPivotQ; /* whether to use the lexicographic pivot */
/* to be used to avoid creating temporary spaces for mytype */
#define dd_almostzero 1.0E-7
/* ---------- FUNCTIONS MEANT TO BE PUBLIC ---------- */
/* basic matrix manipulations */
void dd_InitializeArow(dd_colrange,dd_Arow *);
void dd_InitializeAmatrix(dd_rowrange,dd_colrange,dd_Amatrix *);
void dd_InitializeBmatrix(dd_colrange, dd_Bmatrix *);
dd_SetFamilyPtr dd_CreateSetFamily(dd_bigrange,dd_bigrange);
void dd_FreeSetFamily(dd_SetFamilyPtr);
dd_MatrixPtr dd_CreateMatrix(dd_rowrange,dd_colrange);
void dd_FreeAmatrix(dd_rowrange,dd_colrange,dd_Amatrix);
void dd_FreeArow(dd_colrange, dd_Arow);
void dd_FreeBmatrix(dd_colrange,dd_Bmatrix);
void dd_FreeDDMemory(dd_PolyhedraPtr);
void dd_FreePolyhedra(dd_PolyhedraPtr);
void dd_FreeMatrix(dd_MatrixPtr);
void dd_SetToIdentity(dd_colrange, dd_Bmatrix);
/* sign recognitions */
dd_boolean dd_Nonnegative(mytype);
dd_boolean dd_Nonpositive(mytype);
dd_boolean dd_Positive(mytype);
dd_boolean dd_Negative(mytype);
dd_boolean dd_EqualToZero(mytype);
dd_boolean dd_Nonzero(mytype);
dd_boolean dd_Equal(mytype,mytype);
dd_boolean dd_Larger(mytype,mytype);
dd_boolean dd_Smaller(mytype,mytype);
void dd_abs(mytype, mytype);
void dd_LinearComb(mytype, mytype, mytype, mytype, mytype);
void dd_InnerProduct(mytype, dd_colrange, dd_Arow, dd_Arow);
/* major cddlib operations */
dd_MatrixPtr dd_CopyInput(dd_PolyhedraPtr);
dd_MatrixPtr dd_CopyOutput(dd_PolyhedraPtr);
dd_MatrixPtr dd_CopyInequalities(dd_PolyhedraPtr);
dd_MatrixPtr dd_CopyGenerators(dd_PolyhedraPtr);
dd_SetFamilyPtr dd_CopyIncidence(dd_PolyhedraPtr);
dd_SetFamilyPtr dd_CopyAdjacency(dd_PolyhedraPtr);
dd_SetFamilyPtr dd_CopyInputIncidence(dd_PolyhedraPtr);
dd_SetFamilyPtr dd_CopyInputAdjacency(dd_PolyhedraPtr);
dd_boolean dd_DDFile2File(char *ifile, char *ofile, dd_ErrorType *err);
dd_boolean dd_DDInputAppend(dd_PolyhedraPtr*, dd_MatrixPtr, dd_ErrorType*);
dd_MatrixPtr dd_PolyFile2Matrix(FILE *f, dd_ErrorType *);
dd_PolyhedraPtr dd_DDMatrix2Poly(dd_MatrixPtr, dd_ErrorType *);
dd_PolyhedraPtr dd_DDMatrix2Poly2(dd_MatrixPtr, dd_RowOrderType, dd_ErrorType *);
dd_boolean dd_Redundant(dd_MatrixPtr, dd_rowrange, dd_Arow, dd_ErrorType *); /* 092 */
dd_rowset dd_RedundantRows(dd_MatrixPtr, dd_ErrorType *); /* 092 */
dd_boolean dd_SRedundant(dd_MatrixPtr, dd_rowrange, dd_Arow, dd_ErrorType *); /* 093a */
dd_rowset dd_SRedundantRows(dd_MatrixPtr, dd_ErrorType *); /* 093a */
dd_rowset dd_RedundantRowsViaShooting(dd_MatrixPtr, dd_ErrorType *); /* 092 */
dd_rowrange dd_RayShooting(dd_MatrixPtr, dd_Arow intpt, dd_Arow direction); /* 092 */
/* 092, find the first inequality "hit" by a ray from an intpt. */
dd_boolean dd_ImplicitLinearity(dd_MatrixPtr, dd_rowrange, dd_Arow, dd_ErrorType *); /* 092 */
dd_rowset dd_ImplicitLinearityRows(dd_MatrixPtr, dd_ErrorType *); /* 092 */
int dd_FreeOfImplicitLinearity(dd_MatrixPtr, dd_Arow, dd_rowset *, dd_ErrorType *) ; /* 094 */
dd_boolean dd_MatrixCanonicalizeLinearity(dd_MatrixPtr *, dd_rowset *,dd_rowindex *, dd_ErrorType *); /* 094 */
dd_boolean dd_MatrixCanonicalize(dd_MatrixPtr *, dd_rowset *, dd_rowset *, dd_rowindex *, dd_ErrorType *); /* 094 */
dd_boolean dd_MatrixRedundancyRemove(dd_MatrixPtr *M, dd_rowset *redset,dd_rowindex *newpos, dd_ErrorType *); /* 094 */
dd_boolean dd_FindRelativeInterior(dd_MatrixPtr, dd_rowset *, dd_rowset *, dd_LPSolutionPtr *, dd_ErrorType *); /* 094 */
dd_boolean dd_ExistsRestrictedFace(dd_MatrixPtr, dd_rowset, dd_rowset, dd_ErrorType *); /* 0.94 */
dd_boolean dd_ExistsRestrictedFace2(dd_MatrixPtr, dd_rowset, dd_rowset, dd_LPSolutionPtr *, dd_ErrorType *); /* 0.94 */
dd_SetFamilyPtr dd_Matrix2Adjacency(dd_MatrixPtr, dd_ErrorType *); /* 093 */
dd_SetFamilyPtr dd_Matrix2WeakAdjacency(dd_MatrixPtr, dd_ErrorType *); /* 093a */
long dd_MatrixRank(dd_MatrixPtr, dd_rowset, dd_colset, dd_rowset *, dd_colset *);
/* Matrix Basic Operations */
dd_MatrixPtr dd_MatrixCopy(dd_MatrixPtr); /* a new name for dd_CopyMatrix */
dd_MatrixPtr dd_CopyMatrix(dd_MatrixPtr); /* 090c, kept for compatibility */
dd_MatrixPtr dd_MatrixNormalizedCopy(dd_MatrixPtr); /* 094 */
dd_MatrixPtr dd_MatrixNormalizedSortedCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
dd_MatrixPtr dd_MatrixUniqueCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
dd_MatrixPtr dd_MatrixNormalizedSortedUniqueCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
dd_MatrixPtr dd_MatrixSortedUniqueCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
dd_MatrixPtr dd_MatrixAppend(dd_MatrixPtr, dd_MatrixPtr); /* a name for dd_AppendMatrix */
dd_MatrixPtr dd_AppendMatrix(dd_MatrixPtr, dd_MatrixPtr); /* 090c, kept for compatibility */
int dd_MatrixAppendTo(dd_MatrixPtr*, dd_MatrixPtr); /* 092 */
int dd_Remove(dd_MatrixPtr*, dd_rowrange); /* 092 */
dd_MatrixPtr dd_MatrixSubmatrix(dd_MatrixPtr, dd_rowset delset); /* 092 */
dd_MatrixPtr dd_MatrixSubmatrix2(dd_MatrixPtr, dd_rowset delset,dd_rowindex*); /* 094. It returns new row positions. */
dd_MatrixPtr dd_MatrixSubmatrix2L(dd_MatrixPtr, dd_rowset delset,dd_rowindex*); /* 094. Linearity shifted up. */
int dd_MatrixShiftupLinearity(dd_MatrixPtr *,dd_rowindex *); /* 094 */
int dd_MatrixRowRemove(dd_MatrixPtr *M, dd_rowrange r); /* 092 */
int dd_MatrixRowRemove2(dd_MatrixPtr *M, dd_rowrange r,dd_rowindex*); /* 094*/
int dd_MatrixRowsRemove(dd_MatrixPtr *M, dd_rowset delset); /* 094 */
int dd_MatrixRowsRemove2(dd_MatrixPtr *M, dd_rowset delset,dd_rowindex*); /* 094 */
/* input/output */
void dd_SetInputFile(FILE **f,dd_DataFileType inputfile, dd_ErrorType *);
void dd_SetWriteFileName(dd_DataFileType, dd_DataFileType, char, dd_RepresentationType);
void dd_WriteAmatrix(FILE *, dd_Amatrix, dd_rowrange, dd_colrange);
void dd_WriteArow(FILE *f, dd_Arow a, dd_colrange);
void dd_WriteBmatrix(FILE *, dd_colrange, dd_Bmatrix T);
void dd_WriteMatrix(FILE *, dd_MatrixPtr);
void dd_MatrixIntegerFilter(dd_MatrixPtr);
void dd_WriteReal(FILE *, mytype);
void dd_WriteNumber(FILE *f, mytype x);
/* write a number depending on the arithmetic used. */
void dd_WritePolyFile(FILE *, dd_PolyhedraPtr);
void dd_WriteRunningMode(FILE *, dd_PolyhedraPtr);
void dd_WriteErrorMessages(FILE *, dd_ErrorType);
void dd_WriteSetFamily(FILE *, dd_SetFamilyPtr);
void dd_WriteSetFamilyCompressed(FILE *, dd_SetFamilyPtr);
void dd_WriteProgramDescription(FILE *);
void dd_WriteDDTimes(FILE *, dd_PolyhedraPtr);
void dd_WriteTimes(FILE *, time_t, time_t);
void dd_WriteIncidence(FILE *, dd_PolyhedraPtr);
void dd_WriteAdjacency(FILE *, dd_PolyhedraPtr);
void dd_WriteInputAdjacency(FILE *, dd_PolyhedraPtr);
void dd_WriteInputIncidence(FILE *, dd_PolyhedraPtr);
/* functions and types for LP solving */
dd_LPPtr dd_Matrix2LP(dd_MatrixPtr, dd_ErrorType *);
/* Load a matrix to create an LP object. */
dd_LPPtr dd_Matrix2Feasibility(dd_MatrixPtr, dd_ErrorType *);
/* Load a matrix to create an LP object for feasibility (obj == 0) .*/ /* 094 */
dd_LPPtr dd_Matrix2Feasibility2(dd_MatrixPtr, dd_rowset, dd_rowset, dd_ErrorType *);
/* Load a matrix to create an LP object for feasibility with additional equality and
strict inequality constraints. */ /* 094 */
dd_boolean dd_LPSolve(dd_LPPtr,dd_LPSolverType,dd_ErrorType *);
dd_boolean dd_LPSolve0(dd_LPPtr,dd_LPSolverType,dd_ErrorType *);
void dd_CrissCrossSolve(dd_LPPtr lp,dd_ErrorType *);
void dd_DualSimplexSolve(dd_LPPtr lp,dd_ErrorType *);
dd_LPPtr dd_MakeLPforInteriorFinding(dd_LPPtr);
dd_LPSolutionPtr dd_CopyLPSolution(dd_LPPtr); /* 0.90c */
void dd_WriteLP(FILE *, dd_LPPtr); /* 092 */
dd_LPPtr dd_CreateLPData(dd_LPObjectiveType,dd_NumberType,dd_rowrange,dd_colrange);
int dd_LPReverseRow(dd_LPPtr, dd_rowrange);
/* reverse the i-th row (1 <= i <= no. of rows) */
int dd_LPReplaceRow(dd_LPPtr, dd_rowrange, dd_Arow);
/* replace the i-th row (1 <= i <= no. of rows) */
dd_Arow dd_LPCopyRow(dd_LPPtr, dd_rowrange);
/* copy the i-th row (1 <= i <= no. of rows) */
void dd_FreeLPData(dd_LPPtr);
void dd_FreeLPSolution(dd_LPSolutionPtr);
void dd_WriteLPResult(FILE *, dd_LPPtr, dd_ErrorType);
void dd_WriteLPErrorMessages(FILE *, dd_ErrorType);
void dd_WriteLPTimes(FILE *, dd_LPPtr);
void dd_WriteLPStats(FILE *f);
void dd_WriteLPMode(FILE *f);
dd_MatrixPtr dd_FourierElimination(dd_MatrixPtr,dd_ErrorType *);
dd_MatrixPtr dd_BlockElimination(dd_MatrixPtr, dd_colset, dd_ErrorType *);
/* ---------- FUNCTIONS MEANT TO BE NON-PUBLIC ---------- */
void dd_QuickSort(dd_rowindex, long, long, dd_Amatrix, long);
void dd_RandomPermutation(dd_rowindex, long, unsigned int seed);
void dd_UniqueRows(dd_rowindex, long, long, dd_Amatrix, long, dd_rowset, long *);
dd_boolean dd_DoubleDescription(dd_PolyhedraPtr, dd_ErrorType*);
dd_boolean dd_DoubleDescription2(dd_PolyhedraPtr, dd_RowOrderType, dd_ErrorType *);
void dd_FreeDDMemory0(dd_ConePtr);
void dd_fread_rational_value (FILE *f, mytype value);
void dd_sread_rational_value (char *s, mytype value);
void dd_AddNewHalfspace1(dd_ConePtr, dd_rowrange);
void dd_AddNewHalfspace2(dd_ConePtr, dd_rowrange);
void dd_AddRay(dd_ConePtr, mytype *);
void dd_AddArtificialRay(dd_ConePtr);
void dd_AValue(mytype*,dd_colrange, dd_Amatrix, mytype *, dd_rowrange);
void dd_CheckAdjacency(dd_ConePtr, dd_RayPtr*, dd_RayPtr*, dd_boolean *);
void dd_CheckEquality(dd_colrange, dd_RayPtr *, dd_RayPtr *, dd_boolean *);
void dd_ComputeRowOrderVector(dd_ConePtr);
void dd_ConditionalAddEdge(dd_ConePtr,dd_RayPtr, dd_RayPtr, dd_RayPtr);
void dd_CopyArow(mytype *, mytype *, dd_colrange);
void dd_CopyNormalizedAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange);
void dd_CopyNormalizedArow(mytype *, mytype *, dd_colrange);
void dd_CopyAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange);
void dd_PermuteCopyAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange, dd_rowindex);
void dd_PermutePartialCopyAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange, dd_rowindex,dd_rowrange, dd_rowrange);
void dd_CopyBmatrix(dd_colrange, dd_Bmatrix T, dd_Bmatrix TCOPY);
void dd_CopyRay(mytype *, dd_colrange, dd_RayPtr,
dd_RepresentationType, dd_colindex);
void dd_CreateInitialEdges(dd_ConePtr);
void dd_CreateNewRay(dd_ConePtr, dd_RayPtr, dd_RayPtr, dd_rowrange);
void dd_Eliminate(dd_ConePtr, dd_RayPtr*);
void dd_EvaluateARay1(dd_rowrange, dd_ConePtr);
void dd_EvaluateARay2(dd_rowrange, dd_ConePtr);
void dd_FeasibilityIndices(long *, long *, dd_rowrange, dd_ConePtr);
void dd_FindBasis(dd_ConePtr, long *rank);
void dd_FindInitialRays(dd_ConePtr, dd_boolean *);
void dd_ColumnReduce(dd_ConePtr);
void dd_GaussianColumnPivot(dd_rowrange, dd_colrange, dd_Amatrix, dd_Bmatrix, dd_rowrange, dd_colrange);
dd_boolean dd_LexSmaller(mytype *, mytype *, long);
dd_boolean dd_LexLarger(mytype *, mytype *, long);
dd_boolean dd_LexEqual(mytype *, mytype *, long);
void dd_Normalize(dd_colrange, mytype *);
void dd_MatrixIntegerFilter(dd_MatrixPtr);
void dd_ProcessCommandLine(FILE*,dd_MatrixPtr, char *);
void dd_SelectNextHalfspace(dd_ConePtr, dd_rowset, dd_rowrange *);
void dd_SelectPivot2(dd_rowrange,dd_colrange,dd_Amatrix,
dd_Bmatrix,dd_RowOrderType,dd_rowindex, dd_rowset,dd_rowrange,dd_rowset,
dd_colset,dd_rowrange *,dd_colrange *,dd_boolean *);
void dd_SelectPreorderedNext(dd_ConePtr, dd_rowset, dd_rowrange *);
void dd_SetInequalitySets(dd_ConePtr);
void dd_SnapToInteger(mytype, mytype);
void dd_StoreRay1(dd_ConePtr, mytype *, dd_boolean *);
void dd_StoreRay2(dd_ConePtr, mytype *, dd_boolean *, dd_boolean *);
void dd_TableauEntry(mytype *, dd_rowrange, dd_colrange, dd_Amatrix, dd_Bmatrix T, dd_rowrange, dd_colrange);
void dd_UpdateEdges(dd_ConePtr, dd_RayPtr, dd_RayPtr);
void dd_UpdateRowOrderVector(dd_ConePtr, dd_rowset PriorityRows);
void dd_WriteRay(FILE *, dd_colrange, dd_RayPtr,
dd_RepresentationType, dd_colindex);
void dd_ZeroIndexSet(dd_rowrange, dd_colrange, dd_Amatrix, mytype *, dd_rowset);
/* New functions to handle data loading, NON-PUBLIC */
dd_NumberType dd_GetNumberType(char *);
dd_ConePtr dd_ConeDataLoad(dd_PolyhedraPtr);
dd_PolyhedraPtr dd_CreatePolyhedraData(dd_rowrange, dd_colrange);
dd_boolean dd_InitializeConeData(dd_rowrange, dd_colrange, dd_ConePtr*);
dd_boolean dd_AppendMatrix2Poly(dd_PolyhedraPtr*, dd_MatrixPtr);
/* end of cddlib.h */
|