bool Assert(bool condition, char *message) /* check that condition is true and flag a semantic error if not */ { if (!condition) { printf("error %s at line number %i\n",message,line); errorcount++; return false; } return true; } void CopyVertexset(vertexsetptr source, vertexsetptr destination) { int i,j; destination->Av=source->Av; for (i=1;i<=size;i++) { destination->Bv[i]=source->Bv[i]; destination->neighbourinmis[i]=source->neighbourinmis[i]; destination->neighbournotinmis[i]=source->neighbournotinmis[i]; for (j=1;j<=size;j++) { destination->commonneighbour[i][j]=source->commonneighbour[i][j]; destination->jointneighbour[i][j]=source->jointneighbour[i][j]; } } } bool TwoB() { /* Is the independent set required to contain 2 B vertices? */ return !(Nhood && (first || Achosen)); } bool approx(double x, double y) /* equal to within rounding error */ {return fabs(x-y)=1 && i<=size;} void validperm(permptr p) { int i; vector inverse; for (i=1;i<=size;i++) if (Assert(inrange((*p)[i]),"permutation invalid")) inverse[(*p)[i]]=i; else return; for (i=1;i<=size;i++) Assert(inverse[(*p)[i]]==i,"function is not a permutation"); } void nextcell() /* increment pair (rowindex,columnindex) to next values with columnindex in range and not on diagonal */ { columnindx++; if (columnindx==rowindx) columnindx++; if (columnindx==size+1) {columnindx=1;rowindx++;} } void initpowers() /* store powers of alpha^-1 in poweralpha[] */ { int i; double p=1; for (i=0;i<50;i++) {poweralpha[i]=p;p/=alpha;} } void checkregdom(subcaseptr Sub) { int i, j, mindegree=99, maxdegree=0, intdeg, maxintdeg=0; for (i=1;i<=size;i++) { if (Sub->degree[i]>maxdegree) maxdegree=Sub->degree[i]; if (Sub->degree[i]degree[i]; intdeg=0; for (j=1;j<=size;j++) if (i!=j && Sub->adj[i][j]) intdeg++; if (intdeg>maxintdeg) maxintdeg=intdeg; } Assert(maxdegree==size && mindegree==size && Nhood /*regularity*/|| maxintdeg>=size-1-Nhood /*(sub)dominance*/, "regularity or (sub)dominance test failed"); } void checkperm(subcaseptr X, permptr P, subcaseptr Y) { int i,j; for (i=1;i<=size;i++) { Assert(X->degree[i]==Y->degree[(*P)[i]],"degree wrongly permuted"); Assert(X->extdegree[i]==Y->extdegree[(*P)[i]],"extdegree wrongly permuted"); for (j=1;j<=size;j++) Assert(X->adj[i][j]==Y->adj[(*P)[i]][(*P)[j]],"adj wrongly permed"); for (j=1;j<=size;j++) Assert(X->mincommon[i][j]==Y->mincommon[(*P)[i]][(*P)[j]], "mincommon wrongly permed"); for (j=1;j<=size;j++) { Assert(X->maxcommon[i][j]==Y->maxcommon[(*P)[i]][(*P)[j]], "maxcommon wrongly permed"); Assert(X->theomaxcommon[i][j]==Y->theomaxcommon[(*P)[i]][(*P)[j]], "theomaxcommon wrongly permed"); } } } void checknotcanon(subcaseptr sub, permptr P, int basis) { int i,j,c, Pinverse[maxsize]; for (i=1;i<=size;i++) Pinverse[(*P)[i]]=i; /* check edges */ for (i=1;iadj[Pinverse[i]][Pinverse[j]]!=unknown && sub->adj[Pinverse[i]][Pinverse[j]]adj[i][j]) return; if (!Assert(sub->adj[Pinverse[i]][Pinverse[j]]<=sub->adj[i][j], "canon check fails in edges")) return; } if (Assert(basis!=1,"canon check found no edge difference")) return; /* check degrees */ for (i=1;idegree[Pinverse[i]]!=unknown && sub->degree[Pinverse[i]]degree[i]) return; if (!Assert(sub->degree[Pinverse[i]]<=sub->degree[i], "canon check fails in degrees")) return; } if (!Assert(basis!=2,"canon check found no edge or degree difference")) return; /* check common neighbour information */ for (c=0;c<=maxsize;c++) for (i=1;i<=size;i++) for (j=i+1;j<=size;j++) { int min1=sub->mincommon[i][j],max1=sub->maxcommon[i][j], min2=sub->mincommon[Pinverse[i]][Pinverse[j]], max2=sub->maxcommon[Pinverse[i]][Pinverse[j]]; if (min2>c) Assert(min1>c,"canon check fails in common"); else if (min1>c) { Assert(max2==c,"overlapping common ranges"); return; } if (max1==c) Assert(max2==c,"canon check fails in common"); else if (max2==c) return; } Assert(false,"checkcanon found no difference"); } void clearvertexset(vertexsetptr VS) {int i,j; VS->Av=false; for (i=1;i<=size;i++) { VS->Bv[i]=false; VS->neighbourinmis[i]=0; VS->neighbournotinmis[i]=0; for (j=1;j<=size;j++) VS->commonneighbour[i][j]=VS->jointneighbour[i][j]=0; } } void merge(vertexsetptr VS1, vertexsetptr VS2, subcaseptr P) { int i,j; if (!VS2) return; if (VS2->Av) { Assert(!VS1->Av,"merge of non-disjoint sets (Av)"); VS1->Av=true; } for (i=1;i<=size;i++) { if (VS2->Bv[i]) { Assert(!VS1->Bv[i],"merge of non-disjoint sets (Bv)"); VS1->Bv[i]=true; } if (VS2->neighbourinmis[i]) { Assert(!VS1->neighbourinmis[i],"merge of non-disjoint sets (neighbours)"); VS1->neighbourinmis[i]=VS2->neighbourinmis[i]; } if (VS2->neighbournotinmis[i]) { Assert(!VS1->neighbournotinmis[i], "merge of non-disjoint sets (non-neighbours)"); VS1->neighbournotinmis[i]=VS2->neighbournotinmis[i]; } for (j=1;j<=size;j++) { if (VS2->commonneighbour[i][j]) { Assert(!VS1->commonneighbour[i][j], "merge of non-disjoint sets (common neighbours)"); VS1->commonneighbour[i][j]=VS2->commonneighbour[i][j]; } if (VS2->jointneighbour[i][j]) { Assert(!VS1->jointneighbour[i][j], "merge of non-disjoint sets (joint neighbours)"); VS1->jointneighbour[i][j]=VS2->jointneighbour[i][j]; } } } } int order(vertexsetptr VS) { int i, j, s=0; if (!VS) return 0; if (VS->Av) s++; for (i=1;i<=size;i++) { if (VS->Bv[i]) s++; s+=VS->neighbourinmis[i]; s+=VS->neighbournotinmis[i]; for (j=1;j<=size;j++) { s+=VS->commonneighbour[i][j]; s+=VS->jointneighbour[i][j]; } } return s; } void checkconsistent(vertexsetptr VS, subcaseptr sub) {/* check that the vertex set has not counted a vertex twice */ int i,j; for (i=1;i<=size;i++) { for (j=1;j<=size;j++) if (i!=j) { if (VS->commonneighbour[i][j]) { int k; Assert(!(VS->neighbournotinmis[i]||VS->neighbournotinmis[j]), "vertex counted as neighbour and common neighbour"); for (k=1;k<=size;k++) if (k!=j && VS->commonneighbour[i][k]) Assert(sub->maxcommon[j][k]==0, "triple common neighbour possible (could be counted twice)"); } if (VS->neighbourinmis[i]&&VS->neighbourinmis[j]) Assert(VS->neighbourinmis[i]+VS->neighbourinmis[j]<= sub->extdegree[i]+sub->extdegree[j]-sub->maxcommon[i][j], "possible common neighbour counted twice"); } } } void checkchosen(vertexsetptr Choose, subcaseptr Sub) { int i, j; Achosen=false; Bichosen=Bjchosen=false; if (Choose->Av) { Achosen=true; Acovered=true; Assert(order(Choose)==1,"extra chosen vertices (A)"); return; } for (i=1;i<=size && !Choose->Bv[i];i++) ; if (i<=size) { Bichosen=true; Bi=i; for (j=i+1;j<=size && !Choose->Bv[j];j++) ; if (j<=size) { Bjchosen=true; Bcovered[i][j]=Bcovered[j][i]=true; Bj=j; } else for (j=i+1;j<=size;j++) Bcovered[i][j]=Bcovered[j][i]=true; Assert(order(Choose)==Bichosen+Bjchosen,"extra chosen vertices (B)"); } else /* call with no chosen A or B vertices */ { Assert(order(Choose)==0,"extra chosen vertices ({})"); for (i=size-2;i<=size;i++) for (j=i+1;j<=size;j++) Bcovered[i][j]=Bcovered[j][i]=true; } } void checkneighbours(vertexsetptr Choose, vertexsetptr Neigh, subcaseptr Sub) { int i,j, k, numb=0;; struct vertexset ok; /* the types of vertex which can legitimately be in the neighbour set */ if (!Neigh) return; clearvertexset(&ok); if (Choose->Av) { for (i=1;i<=size;i++) ok.Bv[i]=true; } else { if (Bichosen) ok.Av=true; ok.neighbournotinmis[Bi]=true; for (j=1;j<=size;j++) if (Sub->adj[Bi][j]) ok.Bv[j]=true; if (Bjchosen) ok.neighbournotinmis[Bj]=true; for (k=1;k<=size;k++) if (Sub->adj[Bj][k]) ok.Bv[k]=true; } /* ok is now set up; check Neigh contains only correct vertex types and correct numbers of external neighbours */ if (Neigh->Av) Assert(ok.Av,"A wrongly in neighbours"); for (i=1;i<=size;i++) { if (Neigh->Bv[i]) Assert(ok.Bv[i],"B wrongly in neighbours"); Assert(Neigh->neighbourinmis[i]==0,"wrong type vertex in neighbours"); if (Neigh->neighbournotinmis[i]) { Assert(ok.neighbournotinmis[i],"external vertices wrongly in neighbours"); Assert(Neigh->neighbournotinmis[i]<=Sub->extdegree[i],"too many neighbours"); for (j=i+1;j<=size;j++) if (Neigh->neighbournotinmis[j]) Assert(Neigh->neighbournotinmis[i]+Neigh->neighbournotinmis[j]<= Sub->extdegree[i]+Sub->extdegree[j] -Sub->maxcommon[i][j],"common neighbours overlooked"); } for (j=1;j<=size;j++) Assert(!(Neigh->commonneighbour[i][j]||Neigh->jointneighbour[i][j]), "common/joint neighbours should not be in neighbours"); } } void checkreject(vertexsetptr Choose, vertexsetptr Rej, subcaseptr Sub) { int i,j,k, maxpending=0; if (!Rej) return; for (i=1;i<=size && !Choose->Bv[i];i++) if (Rej->Bv[i]) maxpending=i; if (i>size) /* Choose contained no B vertices */ { Assert(maxpendingAv || maxpending==0,"rejected vertex with A chosen"); } else { for (j=i+1;j<=size && !Choose->Bv[j];j++) if (Rej->Bv[j]) maxpending=j; if (j>size) /* only one B vertex */ Assert(maxpendingBv[k],"wrong rejected vertex (3)"); } for (i=1;i<=size;i++) { Assert(!Rej->neighbourinmis[i],"rejected external vertex"); Assert(!Rej->neighbournotinmis[i],"rejected external vertex"); for (j=1;j<=size;j++) Assert(!(Rej->commonneighbour[i][j]||Rej->jointneighbour[i][j]), "rejected external vertex (2)"); } } void checkforcedin(vertexsetptr Choose, vertexsetptr Force, vertexsetptr Neigh, vertexsetptr Rej, subcaseptr Sub) { int i,j; bool last[maxsize]; /*either two vertices from which one must be taken or three from which two must be taken */ int nred=0, /* number of vertices with degree reduced to 2*/ reduced[maxsize], /* and which they are */ neighbours=0, /* and how many neighbours they must have */ claimed=0; /* and the number according to the analysis read */ bool nonadj=true; /* and are they all pairwise non-adjacent? */ if (!Force) return; for (i=1;i<=size;i++) last[i]=false; if (order(Choose)==0) last[size-2]=last[size-1]=last[size]=true; if (order(Choose)==1 && !Choose->Av) { /* last will contain the two surviving B vertices if there are just 2*/ int numlast=0; for (i=1;i<=size;i++) if (!(Choose->Bv[i]||Neigh->Bv[i]||Rej->Bv[i])) { last[i]=true; numlast++; } if (numlast>2) for (i=1;i<=size;i++) last[i]=false; } Assert(!Force->Av,"A in forced [in/ex]clusions"); for (i=1;i<=size;i++) { int deg=Sub->extdegree[i]; Assert(!Force->Bv[i],"B in forced [in/ex]clusions"); for (j=1;j<=size;j++) if (Force->commonneighbour[i][j]) { int k; Assert(last[i]&&last[j],"incorrect forced common neighbour"); Assert(Force->commonneighbour[i][j]<=Sub->mincommon[i][j], "too many common neighbours"); for (k=1;k<=size;k++) if (k!=j && Force->commonneighbour[i][k]) Assert(Sub->maxcommon[j][k]==0,"common neighbour counted twice?"); } claimed+=Force->neighbourinmis[i]; if (Force->neighbourinmis[i]) reduced[++nred]=i; for (j=i+1;j<=size;j++) if (Sub->adj[i][j] && !Neigh->Bv[j] && !Rej->Bv[j]) deg++; /* reduce degree by common neighbours with Bi or Bj or both */ if (!Bjchosen) deg-=Sub->mincommon[i][Bi]; else {int common=Sub->maxcommon[Bi][Bj]; if (size==4 && !Nhood) common=0; if (common<=Sub->mincommon[i][Bi] && common<=Sub->mincommon[i][Bj]) deg-=(Sub->mincommon[i][Bi]+Sub->mincommon[i][Bj]-common); else if (Sub->mincommon[i][Bi]>Sub->mincommon[i][Bj]) deg-=Sub->mincommon[i][Bi]; else deg-=Sub->mincommon[i][Bj]; } if (Force->neighbourinmis[i]) {/* i should be a rejected vertex with only two neighbours remaining */ Assert(Rej->Bv[i] || Bichosen && iadj[Bi][i], "vertex wrongly considered rejected"); Assert(deg<=2,"rejected vertex not certain to have degree <=2"); } Degree[i]=deg; } /* now check correct number of vertices in Force->neighbourinmis[i] */ neighbours=2*nred; /* reduced vertex must have 2 neighbours in independent set*/ for (i=1;i<=nred;i++) /* but don't count same vertex twice */ for (j=1;jmaxcommon[reduced[i]][reduced[j]]; for (k=1;k<=size;k++) if (!(Choose->Bv[k]||Neigh->Bv[k]||Rej->Bv[k]) && Sub->adj[reduced[i]][k] && Sub->adj[reduced[j]][k]) neighbours--; nonadj&=!Sub->adj[reduced[i]][reduced[j]]; } if (nonadj && neighbours<=nred && nred>0) neighbours=nred+1; /* alternative: x non adjacent reduced vertices have x+1 neighbours in indep set*/ for (i=1;i<=nred;i++) /* but Bi and Bj may be the required neighbours */ neighbours-=(Bichosen && Sub->adj[reduced[i]][Bi]) +(Bjchosen && Sub->adj[reduced[i]][Bj]); if (neighbours<2) /* can we do better by considering just 1 vertex? */ for (i=1;i<=nred;i++) if ((Bichosen && Sub->adj[reduced[i]][Bi]) +(Bjchosen && Sub->adj[reduced[i]][Bj])==0) { neighbours=2; break; } Assert(neighbours==claimed, "wrong number of neighbours in forced inclusion"); } void checkxoutofycondition(constantptr constant, subcaseptr Sub, vertexsetptr Rej, int vertex, int cond) { int already=Achosen+(Bichosen && Sub->adj[vertex][Bi]) +(Bjchosen && Sub->adj[vertex][Bj]); /* number of neighbours of Bvertex already in indep. set */ /* but we must also check that no neighbours of Bvertex have been forcibly included */ Assert(!ForcedIn,"potential clash between forced inclusions and coefficient"); Assert( Rej->Bv[vertex] || Bichosen && vertexadj[Bi][vertex] || Achosen && !first && vertex==1, "vertex not rejected"); Assert(constant->sort==2,"wrong justification type"); Assert(constant->take[cond]+already==2,"wrong number to take"); Assert(constant->outof[cond]+already==Degree[vertex], "wrong number out of"); } void checkomitclaim(subcaseptr Sub, int vertex, vertexsetptr Rej) { int Degreereduction=0; Assert(!ForcedIn,"potential clash between forced inclusions and omit claim"); Assert( Rej->Bv[vertex] || Bichosen && vertexadj[Bi][vertex] || Achosen && !first && vertex==1, "vertex in omit claim not rejected"); if (size==4 && !Nhood && !(Achosen || Bichosen)) { /* independent set will contain 2 of B[2], B[3], B[4] so Degree of B[1] will be reduced by common neighbours; moreover, there are no triple common neighbours of B[1],B[i],B[j] */ int sumcommon=0, maxcommon=0, i; for (i=2;i<=4;i++) { sumcommon+=Sub->mincommon[1][i]; if (Sub->mincommon[1][i]>maxcommon) maxcommon=Sub->mincommon[1][i]; } Degreereduction=sumcommon-maxcommon; /* sum of two smallest */ } Assert(Degree[vertex]-Degreereduction<2, "vertex in omit claim could have 2 neighbours in set"); } void checkexplicit(int n, int Bi, int Bj, int Bk, constantptr constant, vertexsetptr choose, vertexsetptr neigh, vertexsetptr rej) /* condition should be 1-out-of-2 (n=2) or (1||2)-out-of-3 (n=3) (i.e. that the independent set must contain vertices out of the remaining B to make up the number to at least 2 */ { int j; Assert(!(Achosen||Bjchosen),"explicit condition can have at most Bi chosen"); Assert(constant->sort==2 || constant->sort==3,"wrong justification type"); Assert(constant->outof[1]==n,"set sizes mismatch"); Assert(constant->take[1]+order(choose)==2,"wrong number to take"); /* every vertex except Bi, Bj, (Bk) is chosen, neighbour or rejected*/ for (j=1;j<=size;j++) if (j!=Bi && j!=Bj && (n==2 || j!=Bk)) Assert(choose->Bv[j] || neigh->Bv[j] || rej->Bv[j], "a B vertex is not accounted for"); } void checkunion(int i, int j, constantptr constant, subcaseptr Sub, vertexsetptr choose, vertexsetptr neigh, vertexsetptr rej) /* Condition should be that the independent set must contain at least one vertex from the external neighbours of B[i} and B[j]; B[i] and B[j] must both be rejected and not adjacent to each other; The number of external neighbours must match the coefficient and B[i] and B[j] must have no internal neighbours remaining. */ { int k; Assert(constant->sort==2 && constant->n==1 && constant->take[1]==1, "wrong constant for a union type justification"); Assert(Bichosen && iadj[i][j],"vertices adjacent in union"); Assert(constant->outof[1]==Sub->extdegree[i]+Sub->extdegree[j], "out-of value in union condition should be sum of external degrees"); for (k=1;k<=size;k++) if (Sub->adj[i][k] || Sub->adj[j][k]) Assert(choose->Bv[k] || neigh->Bv[k] || rej->Bv[k], "vertex in union condition has surviving internal neighbour"); } void checklast(int n, int i, int j, int k, vertexsetptr Choose, vertexsetptr Neigh, vertexsetptr Rej) { /*There are at most n B vertices left and i,j,k (if>0) are amongst them*/ int count=0, v; Assert(!(Choose->Bv[i] || Neigh->Bv[i] || Rej->Bv[i]), "not one of remaining vertices"); Assert(!(Choose->Bv[j] || Neigh->Bv[j] || Rej->Bv[j]), "not one of remaining vertices"); if (k>0) Assert(!(Choose->Bv[k] || Neigh->Bv[k] || Rej->Bv[k]), "not one of remaining vertices"); for (v=1;v<=size;v++) if (!(Choose->Bv[v] || Neigh->Bv[v] || Rej->Bv[v])) count++; Assert(count<=n,"too many vertices left"); } void CalcDegrees(vertexsetptr Choose, vertexsetptr Neigh, vertexsetptr Rej, subcaseptr Sub, vector degree) { int i,j; for (i=1;i<=size;i++) /* find the number of neighbours of B[i] which might be (or are already) in the independent set; store the maximum possible number in degree[i] and the minimum in mindegree[i] */ { int deg=Sub->extdegree[i]; if (Achosen) {mindegree[i]=degree[i]=deg+1; break;} for (j=1;j<=size;j++) if (Sub->adj[i][j] && !Neigh->Bv[j] && !Rej->Bv[j]) deg++; if (order(Choose)==0) { int sumcommon=0, maxcommon=0; /*if (size==4 && !Nhood && i==1) { int i; for (i=2;i<=4;i++) { sumcommon+=Sub->mincommon[1][i]; if (Sub->mincommon[1][i]>maxcommon) maxcommon=Sub->mincommon[1][i]; } } these are all disjoint because no triple common neighbours in choose-2-out-of-4 */ /* else??*/ mindegree[i]=deg-sumcommon; deg=mindegree[i]+maxcommon; } else if (!Bjchosen) { mindegree[i]=deg-Sub->maxcommon[i][Bi]; deg-=Sub->mincommon[i][Bi]; } else {int common=Sub->maxcommon[Bi][Bj]; if (size==4 && !Nhood) common=0; if (common<=Sub->mincommon[i][Bi] && common<=Sub->mincommon[i][Bj]) deg-=(Sub->mincommon[i][Bi]+Sub->mincommon[i][Bj]-common); else if (Sub->mincommon[i][Bi]>Sub->mincommon[i][Bj]) deg-=Sub->mincommon[i][Bi]; else deg-=Sub->mincommon[i][Bj]; mindegree[i]=deg-Sub->maxcommon[i][Bi]-Sub->maxcommon[i][Bj]; } degree[i]=deg; } } void clearcoverage() /* set all elements of Acovered and Bcovered to false */ { int i,j; Acovered=false; for (i=1;i<=size;i++) for (j=1;j<=size;j++) Bcovered[i][j]=false; } void checkcoverage(subcaseptr Sub) /* check all elements of Acovered (if subcase is a neighbourhood) and all above diagonal elements of Bcovered except those corresponding to edges (B[i],B[j]) are true */ {int i,j; if (Nhood) Assert(Acovered,"no recursive call for A"); for (i=1;i<=size;i++) for (j=i+1;j<=size;j++) Assert(Sub->adj[i][j] || Bcovered[i][j],"missing recursive call"); } void checkgraph(subcaseptr Sub) {int i,j; /* internal consistency checks */ for (i=1;i<=size;i++) { int internal=Nhood; /* number of neighbours of B[i] amongst A and B[j] */ /* check external degrees */ if (Sub->degree[i]==unknown) Assert(Sub->extdegree[i]==unknown,"external degree should be unknown"); else { for (j=1;j<=size;j++) if (i!=j && Sub->adj[i][j]) internal++; Assert(Sub->degree[i]==Sub->extdegree[i]+internal,"wrong external degree"); } for (j=i+1;j<=size;j++) { /* check symmetry */ int minext=Sub->extdegree[i]extdegree[j]? Sub->extdegree[i]:Sub->extdegree[j]; Assert(Sub->adj[i][j]==Sub->adj[j][i],"Asymmetric adjacency matrix"); Assert(Sub->mincommon[i][j]==Sub->mincommon[j][i],"Asymmetric mincommon matrix"); Assert(Sub->maxcommon[i][j]==Sub->maxcommon[j][i],"Asymmetric maxcommon matrix"); if (Sub->mincommon[i][j]==unknown) break; /* non canonical: following check irrelevant */ /* check theoretical max common */ if (Nhood) { if (Sub->theomaxcommon[i][j]degree[i]degree[j]?Sub->degree[i]:Sub->degree[j]; for (k=1;k<=size;k++) if (k!=i && k!=j && Sub->adj[k][i] && Sub->adj[k][j]) commoninternal++; /* common neighbours of Bi, Bj amongst A and other B */ Assert(Sub->theomaxcommon[i][j]==mindeg-2-commoninternal, "wrong theoretical max common in a neighbourhood subcase"); /* because of (sub)dominance argument in paper */ } else Assert(Sub->theomaxcommon[i][j]==minext, "wrong theoretical max common in a neighbourhood subcase"); } else Assert(Sub->theomaxcommon[i][j]==minext, "wrong theoretical max common in a choose-2-out-of subcase"); } } } void checkspecial(subcaseptr P) /* Does P point to a graph of the type referred to in paper section c4c, namely a neighbourhood of a degree 4 vertex A where all neighbours of A have degree 5 and have no edges between them or other common neighbours? */ { int i,j; if (!Assert(Nhood && size==4, "wrong sort of subcase for special case claim")) return; for (i=1;i<=4;i++) { if (!Assert(P->degree[i]==5,"degree must be 5 in special case claim")) return; for (j=i+1;j<=4;j++) { if (!Assert(P->adj[i][j]==0,"subgraph induced on B should have no edges")) return; if (!Assert(P->maxcommon[i][j]==0, "subgraph induced on B should have no common neighbours")) return; } } } void setup(constantptr *ptr, int sort, int n, int t1, int o1, int t2, int o2) { *ptr=(constantptr)malloc(sizeof(constant)); (*ptr)->sort=sort; (*ptr)->n=n; (*ptr)->take[1]=t1; (*ptr)->outof[1]=o1; (*ptr)->take[2]=t2; (*ptr)->outof[2]=o2; (*ptr)->sort=sort; } void setupconstants() { setup(&constc2,4,2,0,0,0,0); /*sort=4; degree in range 1..n */ setup(&constc3,1,3,0,0,0,0); setup(&constc4,1,4,0,0,0,0); setup(&constc5,1,5,0,0,0,0); setup(&constc6,1,6,0,0,0,0); setup(&constc7,1,7,0,0,0,0); setup(&consta1,2,1,1,2,0,0); setup(&consta1y,2,2,1,2,1,2); setup(&consta2,2,1,1,3,0,0); setup(&consta2x,2,2,1,3,1,3); setup(&consta2y,3,1,1,3,0,0); /* sort=3; not a triangle */ setup(&consta3,2,1,2,3,0,0); setup(&consta3z,2,2,2,3,2,3); setup(&consta4,2,1,2,4,0,0); setup(&consta4x,2,2,2,4,2,4); setup(&consta4y,2,2,2,4,2,5); setup(&consta5,2,1,2,5,0,0); setup(&constd1,4,1,0,0,0,0); setup(&constle2,1,2,0,0,0,0); }