#define YYSTYPE struct yystruct #define maxsize 8 #define bool int #define true 1 #define false 0 #define epsilon 0.0000000005 #define unknown (-1) /*Types*/ typedef struct subcase { int degree[maxsize], extdegree[maxsize]; int adj[maxsize][maxsize]; int mincommon[maxsize][maxsize]; int maxcommon[maxsize][maxsize]; int theomaxcommon[maxsize][maxsize]; /* maximum possible based on degree and adj */ } subcase, *subcaseptr; typedef struct vertexset { bool Av, /* true if A in set */ Bv[maxsize]; /* Bv[i]=true if B[i] in set */ int neighbourinmis[maxsize], neighbournotinmis[maxsize], /* neighbourinmis[i]=the number of external neighbours of Bv[i] in this vertex set because they are in the independent set; similarly for neighbournotinmis */ commonneighbour[maxsize][maxsize], /* number of common external neighbours of B[i] and B[j] in the set */ jointneighbour[maxsize][maxsize]; /* and in union of external neighbours of B[i] and B[j] */ } vertexset, *vertexsetptr; typedef struct constant { int sort, /* degree<=X (1) or 1<=degree<=X (4) or choose i out of j conditions (2) or choose 1 out of 3 (not a triangle) (3) */ n, /* the degree or the number (at most 2) of conditions */ take[3], outof[3]; /* The "i" and "j" of the conditions (numbered 1..n) */ } *constantptr; constantptr constc2, constc3, constc4, constc5, constc6,constc7, consta1, consta1y, consta2, consta2x, consta2y, consta3, consta3z, consta4, consta4x, consta4y, consta5, const1, constd1, constle2, constant=(constantptr)0; typedef int vector[maxsize]; typedef vector *permptr; struct yystruct {int ival; double rval; subcaseptr subcase; permptr permutation; vector Bset; vertexsetptr vertexset; constantptr constant;}; /* non-terminals have up to two of these attributes defined */ /* Global variables */ double poweralpha[50]; /* powers of alpha^-1 */ int line=0, /* line number in input file */ errorcount=0; /* number of semantic errors found */ vertexsetptr Chosen, Neighbours, Rejected, ForcedIn, ForcedOut; int size, /* the number of B vertices */ indx, columnindx, rowindx, /* used while reading a subcase */ Bi, Bj; /* the two chosen B vertices in a recursive call (if they exist) */ bool Nhood, /* is the subcase a neighbourhood (as opposed to a choose 2) */ Achosen, Bichosen, Bjchosen, /* are these vertices chosen in current recursive call? */ first, /* is current recursive call the first in its list? */ Acovered, Bcovered[maxsize][maxsize]; /* have there been recursive calls covering independent sets containing A or containing Bi,Bj */ double bound; /* the claimed upper bound on time for this constant */ subcaseptr pointer; /* the last subcase structure created */ vector Degree, /* apparent degree of B[i] in G-Neighbours-Rejected assuming minimum number of common external neighbours */ mindegree; /* minimum allowing for possible common external neighbours */