Sandia Home Sandia Home
Main Page | Publications | Downloads | Configuration | Running the Code | Solver Parameters | FAQ | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

cdd.h

Go to the documentation of this file.
00001 
00043 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00044 
00045 /* cdd.h: Header file for cddlib.c 
00046    written by Komei Fukuda, fukuda@ifor.math.ethz.ch
00047    Version 0.94, Aug. 4, 2005
00048 */
00049 
00050 /* cddlib.c : C-Implementation of the double description method for
00051    computing all vertices and extreme rays of the polyhedron 
00052    P= {x :  b - A x >= 0}.  
00053    Please read COPYING (GNU General Public Licence) and
00054    the manual cddlibman.tex for detail.
00055 */
00056 
00057 #ifndef  __CDD_H
00058 #define  __CDD_H
00059 #endif  /* __CDD_H */
00060 
00061 #ifndef  __CDDMP_H
00062 #include "cddmp.h"
00063 #endif  /* __CDDMP_H */
00064 
00065 #ifndef  __CDDTYPES_H
00066 #include "cddtypes.h"
00067 #endif  /* __CDDTYPES_H */
00068 
00069 #ifdef GMPRATIONAL
00070 #ifndef __CDD_HF
00071 #include "cdd_f.h"
00072 #endif
00073 #endif
00074 
00075 /* GLOBAL CONSTANTS and STATISTICS VARIABLES (to be set by dd_set_global_constants() */
00076 extern mytype dd_zero;
00077 extern mytype dd_one;
00078 extern mytype dd_purezero;
00079 extern mytype dd_minuszero;
00080 extern mytype dd_minusone;
00081 
00082 extern time_t dd_statStartTime; /* cddlib starting time */
00083 extern long dd_statBApivots;  /* basis finding pivots */
00084 extern long dd_statCCpivots;  /* criss-cross pivots */
00085 extern long dd_statDS1pivots; /* phase 1 pivots */
00086 extern long dd_statDS2pivots; /* phase 2 pivots */
00087 extern long dd_statACpivots;  /* anticycling (cc) pivots */
00088 #ifdef GMPRATIONAL
00089 extern long dd_statBSpivots;  /* basis status checking pivots */
00090 #endif
00091 extern dd_LPSolverType dd_choiceLPSolverDefault;  /* Default LP solver Algorithm */
00092 extern dd_LPSolverType dd_choiceRedcheckAlgorithm;  /* Redundancy Checking Algorithm */
00093 extern dd_boolean dd_choiceLexicoPivotQ;    /* whether to use the lexicographic pivot */
00094 
00095    /* to be used to avoid creating temporary spaces for mytype */
00096 #define dd_almostzero  1.0E-7
00097 
00098 /* ---------- FUNCTIONS MEANT TO BE PUBLIC ---------- */
00099 
00100 /* basic matrix manipulations */
00101 void dd_InitializeArow(dd_colrange,dd_Arow *);
00102 void dd_InitializeAmatrix(dd_rowrange,dd_colrange,dd_Amatrix *);
00103 void dd_InitializeBmatrix(dd_colrange, dd_Bmatrix *);
00104 dd_SetFamilyPtr dd_CreateSetFamily(dd_bigrange,dd_bigrange);
00105 void dd_FreeSetFamily(dd_SetFamilyPtr);
00106 dd_MatrixPtr dd_CreateMatrix(dd_rowrange,dd_colrange);
00107 void dd_FreeAmatrix(dd_rowrange,dd_colrange,dd_Amatrix);
00108 void dd_FreeArow(dd_colrange, dd_Arow);
00109 void dd_FreeBmatrix(dd_colrange,dd_Bmatrix);
00110 void dd_FreeDDMemory(dd_PolyhedraPtr);
00111 void dd_FreePolyhedra(dd_PolyhedraPtr);
00112 void dd_FreeMatrix(dd_MatrixPtr);
00113 void dd_SetToIdentity(dd_colrange, dd_Bmatrix);
00114 
00115 /* sign recognitions */
00116 dd_boolean dd_Nonnegative(mytype);
00117 dd_boolean dd_Nonpositive(mytype);
00118 dd_boolean dd_Positive(mytype);
00119 dd_boolean dd_Negative(mytype);
00120 dd_boolean dd_EqualToZero(mytype);
00121 dd_boolean dd_Nonzero(mytype);
00122 dd_boolean dd_Equal(mytype,mytype);
00123 dd_boolean dd_Larger(mytype,mytype);
00124 dd_boolean dd_Smaller(mytype,mytype);
00125 void dd_abs(mytype, mytype);
00126 void dd_LinearComb(mytype, mytype, mytype, mytype, mytype);
00127 void dd_InnerProduct(mytype, dd_colrange, dd_Arow, dd_Arow);
00128 
00129 /* major cddlib operations */
00130 dd_MatrixPtr dd_CopyInput(dd_PolyhedraPtr);
00131 dd_MatrixPtr dd_CopyOutput(dd_PolyhedraPtr);
00132 dd_MatrixPtr dd_CopyInequalities(dd_PolyhedraPtr);
00133 dd_MatrixPtr dd_CopyGenerators(dd_PolyhedraPtr);
00134 dd_SetFamilyPtr dd_CopyIncidence(dd_PolyhedraPtr);
00135 dd_SetFamilyPtr dd_CopyAdjacency(dd_PolyhedraPtr);
00136 dd_SetFamilyPtr dd_CopyInputIncidence(dd_PolyhedraPtr);
00137 dd_SetFamilyPtr dd_CopyInputAdjacency(dd_PolyhedraPtr);
00138 dd_boolean dd_DDFile2File(char *ifile, char *ofile, dd_ErrorType *err);
00139 dd_boolean dd_DDInputAppend(dd_PolyhedraPtr*, dd_MatrixPtr, dd_ErrorType*);
00140 dd_MatrixPtr dd_PolyFile2Matrix(FILE *f, dd_ErrorType *);
00141 
00142 dd_PolyhedraPtr dd_DDMatrix2Poly(dd_MatrixPtr, dd_ErrorType *);
00143 dd_PolyhedraPtr dd_DDMatrix2Poly2(dd_MatrixPtr, dd_RowOrderType, dd_ErrorType *);
00144 dd_boolean dd_Redundant(dd_MatrixPtr, dd_rowrange, dd_Arow, dd_ErrorType *);  /* 092 */
00145 dd_rowset dd_RedundantRows(dd_MatrixPtr, dd_ErrorType *);  /* 092 */
00146 dd_boolean dd_SRedundant(dd_MatrixPtr, dd_rowrange, dd_Arow, dd_ErrorType *);  /* 093a */
00147 dd_rowset dd_SRedundantRows(dd_MatrixPtr, dd_ErrorType *);  /* 093a */
00148 dd_rowset dd_RedundantRowsViaShooting(dd_MatrixPtr, dd_ErrorType *); /* 092 */
00149 dd_rowrange dd_RayShooting(dd_MatrixPtr, dd_Arow intpt, dd_Arow direction);  /* 092 */ 
00150  /* 092, find the first inequality "hit" by a ray from an intpt.  */
00151 dd_boolean dd_ImplicitLinearity(dd_MatrixPtr, dd_rowrange, dd_Arow, dd_ErrorType *);  /* 092 */
00152 dd_rowset dd_ImplicitLinearityRows(dd_MatrixPtr, dd_ErrorType *);  /* 092  */
00153 int dd_FreeOfImplicitLinearity(dd_MatrixPtr, dd_Arow, dd_rowset *, dd_ErrorType *) ; /* 094 */
00154 dd_boolean dd_MatrixCanonicalizeLinearity(dd_MatrixPtr *, dd_rowset *,dd_rowindex *, dd_ErrorType *); /* 094 */
00155 dd_boolean dd_MatrixCanonicalize(dd_MatrixPtr *, dd_rowset *, dd_rowset *, dd_rowindex *, dd_ErrorType *); /* 094 */
00156 dd_boolean dd_MatrixRedundancyRemove(dd_MatrixPtr *M, dd_rowset *redset,dd_rowindex *newpos, dd_ErrorType *); /* 094 */
00157 dd_boolean dd_FindRelativeInterior(dd_MatrixPtr, dd_rowset *, dd_rowset *, dd_LPSolutionPtr *, dd_ErrorType *);  /* 094 */
00158 dd_boolean dd_ExistsRestrictedFace(dd_MatrixPtr, dd_rowset, dd_rowset, dd_ErrorType *);  /* 0.94 */
00159 dd_boolean dd_ExistsRestrictedFace2(dd_MatrixPtr, dd_rowset, dd_rowset, dd_LPSolutionPtr *, dd_ErrorType *); /* 0.94 */
00160 
00161 dd_SetFamilyPtr dd_Matrix2Adjacency(dd_MatrixPtr, dd_ErrorType *);  /* 093 */
00162 dd_SetFamilyPtr dd_Matrix2WeakAdjacency(dd_MatrixPtr, dd_ErrorType *);  /* 093a */
00163 long dd_MatrixRank(dd_MatrixPtr, dd_rowset, dd_colset, dd_rowset *, dd_colset *);
00164 
00165 /* Matrix Basic Operations */
00166 dd_MatrixPtr dd_MatrixCopy(dd_MatrixPtr); /* a new name for dd_CopyMatrix */
00167 dd_MatrixPtr dd_CopyMatrix(dd_MatrixPtr); /* 090c, kept for compatibility */
00168 dd_MatrixPtr dd_MatrixNormalizedCopy(dd_MatrixPtr); /* 094 */
00169 dd_MatrixPtr dd_MatrixNormalizedSortedCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
00170 dd_MatrixPtr dd_MatrixUniqueCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
00171 dd_MatrixPtr dd_MatrixNormalizedSortedUniqueCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
00172 dd_MatrixPtr dd_MatrixSortedUniqueCopy(dd_MatrixPtr,dd_rowindex*); /* 094 */
00173 
00174 dd_MatrixPtr dd_MatrixAppend(dd_MatrixPtr, dd_MatrixPtr);  /* a name for dd_AppendMatrix */
00175 dd_MatrixPtr dd_AppendMatrix(dd_MatrixPtr, dd_MatrixPtr);  /* 090c, kept for compatibility */
00176 
00177 int dd_MatrixAppendTo(dd_MatrixPtr*, dd_MatrixPtr);  /* 092 */
00178 int dd_Remove(dd_MatrixPtr*, dd_rowrange);  /* 092 */
00179 dd_MatrixPtr dd_MatrixSubmatrix(dd_MatrixPtr, dd_rowset delset); /* 092 */
00180 dd_MatrixPtr dd_MatrixSubmatrix2(dd_MatrixPtr, dd_rowset delset,dd_rowindex*); /* 094.  It returns new row positions. */
00181 dd_MatrixPtr dd_MatrixSubmatrix2L(dd_MatrixPtr, dd_rowset delset,dd_rowindex*); /* 094.  Linearity shifted up. */
00182 int dd_MatrixShiftupLinearity(dd_MatrixPtr *,dd_rowindex *); /* 094 */
00183 int dd_MatrixRowRemove(dd_MatrixPtr *M, dd_rowrange r); /* 092 */
00184 int dd_MatrixRowRemove2(dd_MatrixPtr *M, dd_rowrange r,dd_rowindex*); /* 094*/
00185 int dd_MatrixRowsRemove(dd_MatrixPtr *M, dd_rowset delset); /* 094 */
00186 int dd_MatrixRowsRemove2(dd_MatrixPtr *M, dd_rowset delset,dd_rowindex*); /* 094 */
00187 
00188 /* input/output */
00189 void dd_SetInputFile(FILE **f,dd_DataFileType inputfile, dd_ErrorType *);
00190 void dd_SetWriteFileName(dd_DataFileType, dd_DataFileType, char, dd_RepresentationType);
00191 
00192 void dd_WriteAmatrix(FILE *, dd_Amatrix, dd_rowrange, dd_colrange);
00193 void dd_WriteArow(FILE *f, dd_Arow a, dd_colrange);
00194 void dd_WriteBmatrix(FILE *, dd_colrange, dd_Bmatrix T);
00195 void dd_WriteMatrix(FILE *, dd_MatrixPtr);
00196 void dd_MatrixIntegerFilter(dd_MatrixPtr);
00197 void dd_WriteReal(FILE *, mytype);
00198 void dd_WriteNumber(FILE *f, mytype x); 
00199     /* write a number depending on the arithmetic used.  */
00200 void dd_WritePolyFile(FILE *, dd_PolyhedraPtr);
00201 void dd_WriteRunningMode(FILE *, dd_PolyhedraPtr);
00202 void dd_WriteErrorMessages(FILE *, dd_ErrorType);
00203 void dd_WriteSetFamily(FILE *, dd_SetFamilyPtr);
00204 void dd_WriteSetFamilyCompressed(FILE *, dd_SetFamilyPtr);
00205 void dd_WriteProgramDescription(FILE *);
00206 void dd_WriteDDTimes(FILE *, dd_PolyhedraPtr);
00207 void dd_WriteTimes(FILE *, time_t, time_t);
00208 void dd_WriteIncidence(FILE *, dd_PolyhedraPtr);
00209 void dd_WriteAdjacency(FILE *, dd_PolyhedraPtr);
00210 void dd_WriteInputAdjacency(FILE *, dd_PolyhedraPtr);
00211 void dd_WriteInputIncidence(FILE *, dd_PolyhedraPtr);
00212 
00213 /* functions and types for LP solving */
00214 
00215 dd_LPPtr dd_Matrix2LP(dd_MatrixPtr, dd_ErrorType *);
00216   /* Load a matrix to create an LP object. */
00217   
00218 dd_LPPtr dd_Matrix2Feasibility(dd_MatrixPtr, dd_ErrorType *);
00219   /* Load a matrix to create an LP object for feasibility (obj == 0) .*/  /*  094 */
00220   
00221 dd_LPPtr dd_Matrix2Feasibility2(dd_MatrixPtr, dd_rowset, dd_rowset, dd_ErrorType *);
00222   /* Load a matrix to create an LP object for feasibility with additional equality and
00223    strict inequality constraints. */  /*  094 */
00224 
00225 dd_boolean dd_LPSolve(dd_LPPtr,dd_LPSolverType,dd_ErrorType *);
00226 dd_boolean dd_LPSolve0(dd_LPPtr,dd_LPSolverType,dd_ErrorType *);
00227 void dd_CrissCrossSolve(dd_LPPtr lp,dd_ErrorType *);
00228 void dd_DualSimplexSolve(dd_LPPtr lp,dd_ErrorType *);
00229 
00230 dd_LPPtr dd_MakeLPforInteriorFinding(dd_LPPtr);  
00231 dd_LPSolutionPtr dd_CopyLPSolution(dd_LPPtr);  /* 0.90c */
00232 void dd_WriteLP(FILE *, dd_LPPtr); /* 092 */
00233 
00234 dd_LPPtr dd_CreateLPData(dd_LPObjectiveType,dd_NumberType,dd_rowrange,dd_colrange);
00235 int dd_LPReverseRow(dd_LPPtr, dd_rowrange);
00236     /* reverse the i-th row (1 <= i <= no. of rows) */
00237 int dd_LPReplaceRow(dd_LPPtr, dd_rowrange, dd_Arow);
00238     /* replace the i-th row (1 <= i <= no. of rows) */
00239 dd_Arow dd_LPCopyRow(dd_LPPtr, dd_rowrange);
00240     /* copy the i-th row (1 <= i <= no. of rows) */
00241 
00242 void dd_FreeLPData(dd_LPPtr);
00243 void dd_FreeLPSolution(dd_LPSolutionPtr);
00244 
00245 void dd_WriteLPResult(FILE *, dd_LPPtr, dd_ErrorType);
00246 void dd_WriteLPErrorMessages(FILE *, dd_ErrorType);
00247 void dd_WriteLPTimes(FILE *, dd_LPPtr);
00248 void dd_WriteLPStats(FILE *f);
00249 void dd_WriteLPMode(FILE *f);
00250 
00251 dd_MatrixPtr dd_FourierElimination(dd_MatrixPtr,dd_ErrorType *);
00252 dd_MatrixPtr dd_BlockElimination(dd_MatrixPtr, dd_colset, dd_ErrorType *);
00253 
00254 /* ---------- FUNCTIONS MEANT TO BE NON-PUBLIC ---------- */
00255 void dd_QuickSort(dd_rowindex, long, long, dd_Amatrix, long);
00256 void dd_RandomPermutation(dd_rowindex, long, unsigned int seed);
00257 void dd_UniqueRows(dd_rowindex, long, long, dd_Amatrix, long, dd_rowset, long *);
00258 
00259 dd_boolean dd_DoubleDescription(dd_PolyhedraPtr, dd_ErrorType*);
00260 dd_boolean dd_DoubleDescription2(dd_PolyhedraPtr, dd_RowOrderType, dd_ErrorType *);
00261 
00262 void dd_FreeDDMemory0(dd_ConePtr);
00263 void dd_fread_rational_value (FILE *f, mytype value);
00264 void dd_sread_rational_value (char *s, mytype value);
00265 void dd_AddNewHalfspace1(dd_ConePtr, dd_rowrange);
00266 void dd_AddNewHalfspace2(dd_ConePtr, dd_rowrange);
00267 void dd_AddRay(dd_ConePtr, mytype *);
00268 void dd_AddArtificialRay(dd_ConePtr);
00269 void dd_AValue(mytype*,dd_colrange, dd_Amatrix, mytype *, dd_rowrange);
00270 void dd_CheckAdjacency(dd_ConePtr, dd_RayPtr*, dd_RayPtr*, dd_boolean *);
00271 void dd_CheckEquality(dd_colrange, dd_RayPtr *, dd_RayPtr *, dd_boolean *);
00272 void dd_ComputeRowOrderVector(dd_ConePtr);
00273 void dd_ConditionalAddEdge(dd_ConePtr,dd_RayPtr, dd_RayPtr, dd_RayPtr);
00274 void dd_CopyArow(mytype *, mytype *, dd_colrange);
00275 void dd_CopyNormalizedAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange);
00276 void dd_CopyNormalizedArow(mytype *, mytype *, dd_colrange);
00277 void dd_CopyAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange);
00278 void dd_PermuteCopyAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange, dd_rowindex);
00279 void dd_PermutePartialCopyAmatrix(mytype **, mytype **, dd_rowrange, dd_colrange, dd_rowindex,dd_rowrange, dd_rowrange);
00280 void dd_CopyBmatrix(dd_colrange, dd_Bmatrix T, dd_Bmatrix TCOPY);
00281 void dd_CopyRay(mytype *, dd_colrange, dd_RayPtr,
00282    dd_RepresentationType, dd_colindex);
00283 void dd_CreateInitialEdges(dd_ConePtr);
00284 void dd_CreateNewRay(dd_ConePtr, dd_RayPtr, dd_RayPtr, dd_rowrange);
00285 void dd_Eliminate(dd_ConePtr, dd_RayPtr*);
00286 void dd_EvaluateARay1(dd_rowrange, dd_ConePtr);
00287 void dd_EvaluateARay2(dd_rowrange, dd_ConePtr);
00288 void dd_FeasibilityIndices(long *, long *, dd_rowrange, dd_ConePtr);
00289 void dd_FindBasis(dd_ConePtr, long *rank);
00290 void dd_FindInitialRays(dd_ConePtr, dd_boolean *);
00291 void dd_ColumnReduce(dd_ConePtr);
00292 void dd_GaussianColumnPivot(dd_rowrange, dd_colrange, dd_Amatrix, dd_Bmatrix,  dd_rowrange, dd_colrange);
00293 dd_boolean dd_LexSmaller(mytype *, mytype *, long);
00294 dd_boolean dd_LexLarger(mytype *, mytype *, long);
00295 dd_boolean dd_LexEqual(mytype *, mytype *, long);
00296 void dd_Normalize(dd_colrange, mytype *);
00297 void dd_MatrixIntegerFilter(dd_MatrixPtr);
00298 void dd_ProcessCommandLine(FILE*,dd_MatrixPtr, char *);
00299 void dd_SelectNextHalfspace(dd_ConePtr, dd_rowset, dd_rowrange *);
00300 void dd_SelectPivot2(dd_rowrange,dd_colrange,dd_Amatrix,
00301 dd_Bmatrix,dd_RowOrderType,dd_rowindex, dd_rowset,dd_rowrange,dd_rowset,
00302 dd_colset,dd_rowrange *,dd_colrange *,dd_boolean *);
00303 void dd_SelectPreorderedNext(dd_ConePtr, dd_rowset, dd_rowrange *);
00304 void dd_SetInequalitySets(dd_ConePtr);
00305 void dd_SnapToInteger(mytype, mytype);
00306 void dd_StoreRay1(dd_ConePtr, mytype *, dd_boolean *);
00307 void dd_StoreRay2(dd_ConePtr, mytype *, dd_boolean *, dd_boolean *);
00308 void dd_TableauEntry(mytype *, dd_rowrange, dd_colrange, dd_Amatrix, dd_Bmatrix T, dd_rowrange, dd_colrange);
00309 void dd_UpdateEdges(dd_ConePtr, dd_RayPtr, dd_RayPtr);
00310 void dd_UpdateRowOrderVector(dd_ConePtr, dd_rowset PriorityRows);
00311 void dd_WriteRay(FILE *, dd_colrange, dd_RayPtr,
00312    dd_RepresentationType, dd_colindex);
00313 void dd_ZeroIndexSet(dd_rowrange, dd_colrange, dd_Amatrix, mytype *, dd_rowset);
00314 
00315 /* New functions to handle data loading, NON-PUBLIC */
00316 dd_NumberType dd_GetNumberType(char *);
00317 dd_ConePtr dd_ConeDataLoad(dd_PolyhedraPtr);
00318 dd_PolyhedraPtr dd_CreatePolyhedraData(dd_rowrange, dd_colrange);
00319 dd_boolean dd_InitializeConeData(dd_rowrange, dd_colrange, dd_ConePtr*);
00320 dd_boolean dd_AppendMatrix2Poly(dd_PolyhedraPtr*, dd_MatrixPtr);
00321 
00322 
00323 
00324 
00325 
00326 /* end of cddlib.h */
00327 
00328 #endif

 

© Sandia Corporation | Site Contact | Privacy and Security

Generated on Fri Feb 16 10:33:35 2007 for APPSPACK 5.0.1 by doxygen 1.3.9.1 written by Dimitri van Heesch, © 1997-2002