/* cddtypes.h: Header file for cddlib.c    written by Komei Fukuda, fukuda@ifor.math.ethz.ch   Version 0.94b, Aug. 24, 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  __CDDTYPES_H#define  __CDDTYPES_H#endif  /* __CDDTYPES_H */#define dd_COPYRIGHT   "Copyright (C) 1996, Komei Fukuda, fukuda@ifor.math.ethz.ch"#define dd_DDVERSION   "Version 0.94b (August 25, 2005)"#include <time.h>#define dd_wordlenmax     127#define dd_linelenmax     255#define dd_datawidth       10#define dd_filenamelen    255#define dd_FALSE 0#define dd_TRUE 1typedef int dd_boolean;typedef long dd_rowrange;typedef long dd_colrange;typedef long dd_bigrange;typedef set_type dd_rowset;typedef set_type dd_colset;typedef long *dd_rowindex;   typedef int *dd_rowflag;   typedef long *dd_colindex;typedef mytype **dd_Amatrix;typedef mytype *dd_Arow;typedef set_type *dd_SetVector;typedef mytype **dd_Bmatrix;typedef set_type *dd_Aincidence;/* typedef char dd_FilenameType[dd_filenamelen]; deleted 000505*/typedef char dd_DataFileType[dd_filenamelen];typedef char dd_LineType[dd_linelenmax];typedef char dd_WordType[dd_wordlenmax];typedef struct dd_raydata *dd_RayPtr;typedef struct dd_raydata {  mytype *Ray;  dd_rowset ZeroSet;  dd_rowrange FirstInfeasIndex;  /* the first inequality the ray violates */  dd_boolean feasible;  /* flag to store the feasibility */  mytype ARay;   /* temporary area to store some row of A*Ray */  dd_RayPtr Next;} dd_RayType;typedef struct dd_adjacencydata *dd_AdjacencyPtr;typedef struct dd_adjacencydata {  dd_RayPtr Ray1, Ray2;  dd_AdjacencyPtr Next;} dd_AdjacencyType;typedef enum {  dd_Combinatorial, dd_Algebraic} dd_AdjacencyTestType;typedef enum {  dd_MaxIndex, dd_MinIndex, dd_MinCutoff, dd_MaxCutoff, dd_MixCutoff,   dd_LexMin, dd_LexMax, dd_RandomRow} dd_RowOrderType;typedef enum {  dd_Unknown=0, dd_Real, dd_Rational, dd_Integer} dd_NumberType;typedef enum {  dd_Unspecified=0, dd_Inequality, dd_Generator} dd_RepresentationType;typedef enum {  dd_IneToGen, dd_GenToIne, dd_LPMax, dd_LPMin, dd_InteriorFind} dd_ConversionType;typedef enum {  dd_IncOff=0, dd_IncCardinality, dd_IncSet} dd_IncidenceOutputType;typedef enum {  dd_AdjOff=0, dd_AdjacencyList,  dd_AdjacencyDegree} dd_AdjacencyOutputType;typedef enum {  dd_Auto, dd_SemiAuto, dd_Manual} dd_FileInputModeType;      /* Auto if a input filename is specified by command arguments */typedef enum {  dd_DimensionTooLarge, dd_ImproperInputFormat,   dd_NegativeMatrixSize, dd_EmptyVrepresentation, dd_EmptyHrepresentation, dd_EmptyRepresentation,  dd_IFileNotFound, dd_OFileNotOpen, dd_NoLPObjective, dd_NoRealNumberSupport,  dd_NotAvailForH, dd_NotAvailForV, dd_CannotHandleLinearity,  dd_RowIndexOutOfRange, dd_ColIndexOutOfRange,  dd_LPCycling, dd_NumericallyInconsistent,  dd_NoError} dd_ErrorType;typedef enum {  dd_InProgress, dd_AllFound, dd_RegionEmpty} dd_CompStatusType;/* --- LP types ---- */typedef enum {  dd_LPnone=0, dd_LPmax, dd_LPmin} dd_LPObjectiveType;typedef enum {  dd_CrissCross, dd_DualSimplex} dd_LPSolverType;typedef enum {  dd_LPSundecided, dd_Optimal, dd_Inconsistent, dd_DualInconsistent,  dd_StrucInconsistent, dd_StrucDualInconsistent,  dd_Unbounded, dd_DualUnbounded} dd_LPStatusType;typedef struct dd_lpsolution *dd_LPSolutionPtr;typedef struct dd_lpsolution {  dd_DataFileType filename;  dd_LPObjectiveType objective;  dd_LPSolverType solver;   dd_rowrange m;  dd_colrange d;  dd_NumberType numbtype;  dd_LPStatusType LPS;  /* the current solution status */  mytype optvalue;  /* optimal value */  dd_Arow sol;   /* primal solution */  dd_Arow dsol;  /* dual solution */  dd_colindex nbindex;  /* current basis represented by nonbasic indices */  dd_rowrange re;  /* row index as a certificate in the case of inconsistency */  dd_colrange se;  /* col index as a certificate in the case of dual inconsistency */  long pivots[5];    /* pivots[0]=setup (to find a basis), pivots[1]=PhaseI or Criss-Cross,      pivots[2]=Phase II, pivots[3]=Anticycling, pivots[4]=GMP postopt. */  long total_pivots;} dd_LPSolutionType;typedef struct dd_lpdata *dd_LPPtr;typedef struct dd_lpdata {  dd_DataFileType filename;  dd_LPObjectiveType objective;  dd_LPSolverType solver;   dd_boolean Homogeneous;       /* The first column except for the obj row is all zeros. */  dd_rowrange m;  dd_colrange d;  dd_Amatrix A;  dd_Bmatrix B;  dd_rowrange objrow;  dd_colrange rhscol;  dd_NumberType numbtype;  dd_rowrange eqnumber;  /* the number of equalities */  dd_rowset equalityset;    dd_boolean redcheck_extensive;  /* Apply the extensive redundancy check. */  dd_rowrange ired; /* the row index for the redundancy checking */  dd_rowset redset_extra;  /* a set of rows that are newly recognized redundan by the extensive search. */  dd_rowset redset_accum;  /* the accumulated set of rows that are recognized redundant */  dd_rowset posset_extra;  /* a set of rows that are recognized non-linearity */  dd_boolean lexicopivot;  /* flag to use the lexicogrphic pivot rule (symbolic perturbation). */  dd_LPStatusType LPS;  /* the current solution status */  dd_rowrange m_alloc; /* the allocated row size of matrix A */  dd_colrange d_alloc; /* the allocated col size of matrix A */  mytype optvalue;  /* optimal value */  dd_Arow sol;   /* primal solution */  dd_Arow dsol;  /* dual solution */  dd_colindex nbindex;  /* current basis represented by nonbasic indices */  dd_rowrange re;  /* row index as a certificate in the case of inconsistency */  dd_colrange se;  /* col index as a certificate in the case of dual inconsistency */  long pivots[5];    /* pivots[0]=setup (to find a basis), pivots[1]=PhaseI or Criss-Cross,      pivots[2]=Phase II, pivots[3]=Anticycling, pivots[4]=GMP postopt. */  long total_pivots;  int use_given_basis;  /* switch to indicate the use of the given basis */  dd_colindex given_nbindex;  /* given basis represented by nonbasic indices */  time_t starttime;  time_t endtime;} dd_LPType;/*----  end of LP Types ----- */typedef struct  dd_matrixdata *dd_MatrixPtr;typedef struct  dd_matrixdata {  dd_rowrange rowsize;  dd_rowset linset;     /*  a subset of rows of linearity (ie, generators of        linearity space for V-representation, and equations        for H-representation. */  dd_colrange colsize;  dd_RepresentationType representation;  dd_NumberType numbtype;  dd_Amatrix matrix;  dd_LPObjectiveType objective;  dd_Arow rowvec;} dd_MatrixType;typedef struct dd_setfamily *dd_SetFamilyPtr;typedef struct dd_setfamily {  dd_bigrange famsize;  dd_bigrange setsize;  dd_SetVector set;  } dd_SetFamilyType;typedef struct dd_nodedata *dd_NodePtr;typedef struct dd_nodedata {dd_bigrange key; dd_NodePtr next;} dd_NodeType;typedef struct dd_graphdata *dd_GraphPtr;typedef struct dd_graphdata {  dd_bigrange vsize;  dd_NodePtr *adjlist;  /* should be initialized to have vsize components */} dd_GraphType;typedef struct dd_polyhedradata *dd_PolyhedraPtr;typedef struct dd_conedata *dd_ConePtr;typedef struct dd_polyhedradata {  dd_RepresentationType representation;  /* given representation */  dd_boolean homogeneous;  dd_colrange d;  dd_rowrange m;  dd_Amatrix A;   /* Inequality System:  m times d matrix */  dd_NumberType numbtype;  dd_ConePtr child;  /* pointing to the homogenized cone data */  dd_rowrange m_alloc; /* allocated row size of matrix A */  dd_colrange d_alloc; /* allocated col size of matrix A */  dd_Arow c;           /* cost vector */  dd_rowflag EqualityIndex;      /* ith component is 1 if it is equality, -1 if it is strict inequality, 0 otherwise. */  dd_boolean IsEmpty;  /* This is to tell whether the set is empty or not */    dd_boolean NondegAssumed;  dd_boolean InitBasisAtBottom;  dd_boolean RestrictedEnumeration;  dd_boolean RelaxedEnumeration;  dd_rowrange m1;     /* = m or m+1 (when representation=Inequality && !homogeneous)       This data is written after dd_ConeDataLoad is called.  This       determines the size of Ainc. */  dd_boolean AincGenerated;    /* Indicates whether Ainc, Ared, Adom are all computed.       All the variables below are valid only when this is TRUE */  dd_colrange ldim;   /* linearity dimension */  dd_bigrange n;     /* the size of output = total number of rays        in the computed cone + linearity dimension */  dd_Aincidence Ainc;    /* incidence of input and output */  dd_rowset Ared;      /* redundant set of rows whose removal results in a minimal system */  dd_rowset Adom;      /* dominant set of rows (those containing all rays). */} dd_PolyhedraType;typedef struct dd_conedata {  dd_RepresentationType representation;  dd_rowrange m;  dd_colrange d;  dd_Amatrix A;  dd_NumberType numbtype;  dd_PolyhedraPtr parent;  /* pointing to the original polyhedra data */  dd_rowrange m_alloc; /* allocated row size of matrix A */  dd_colrange d_alloc; /* allocated col size of matrix A *//* CONTROL: variables to control computation */  dd_rowrange Iteration;  dd_RowOrderType HalfspaceOrder;  dd_RayPtr FirstRay, LastRay, ArtificialRay; /* The second description: Generator */  dd_RayPtr PosHead, ZeroHead, NegHead, PosLast, ZeroLast, NegLast;  dd_AdjacencyType **Edges;  /* adjacency relation storage for iteration k */  unsigned int rseed;  /* random seed for random row permutation */  dd_boolean ColReduced;  /* flag to indicate that a column basis is computed and reduced */  dd_bigrange LinearityDim;              /*  the dimension of the linearity space (when input is H), and               the size of a minimal system of equations to determine the space (when V). */  dd_colrange d_orig;  /* the size d of the original matrix A */  dd_colindex newcol;  /* the size d of the original matrix A */    dd_colindex InitialRayIndex;   /* InitialRayIndex[s] (s>=1) stores the corr. row index */  dd_rowindex OrderVector;  dd_boolean RecomputeRowOrder;  dd_boolean PreOrderedRun;  dd_rowset GroundSet, EqualitySet, NonequalitySet,        AddedHalfspaces, WeaklyAddedHalfspaces, InitialHalfspaces;  long RayCount, FeasibleRayCount, WeaklyFeasibleRayCount,       TotalRayCount, ZeroRayCount;  long EdgeCount, TotalEdgeCount;  long count_int,count_int_good,count_int_bad; /* no. of intersection operations */  dd_Bmatrix B;  dd_Bmatrix Bsave;  /* a copy of the dual basis inverse used to reduce the matrix A *//* STATES: variables to represent current state. */  dd_ErrorType Error;  dd_CompStatusType CompStatus;  /* Computation Status */  time_t starttime, endtime;} dd_ConeType;/* Global Variables */extern dd_boolean dd_debug;extern dd_boolean dd_log;/* end of cddtypes.h */