/* functions relating to the order defined on subcases */ void checkminiC(subcaseptr s, int row, int col, int c) /* are all choices after that of whether the number of common neighbours is c in position [row][col] the minimum possible? i.e. there should be no position after [row][col] where the number is decided to be greater than c and none before (inclusive) [row][col] where it is decided to be greater than c+1 */ { int i,j; for (i=1;i row || i==row&&j>col) Assert(s->mincommon[i][j]<=c,"too many common neighbours"); else Assert(s->mincommon[i][j]<=c+1,"too many common neighbours"); } } void checkmaxiC(subcaseptr s, int row, int col, int c) /* are all choices after that of whether the number of common neighbours is c in position [row][col] the maximum possible?*/ { int i,j,com; for (i=1;imincommon[i][j]; if (com==s->maxcommon[i][j] && (com>=c && (i> row || i==row&&j>col)||com>c)) /* a choice has been made to have exactly com common neighbours; so com must be the maximum possible number for this vertex pair */ Assert(com==s->theomaxcommon[i][j], "wrong number of common neighbours"); } } void checkminiD(subcaseptr s, int v) /* are all choices after that of the degree of vertex Bv the minimum possible?*/ { int i,min=Nhood?size:size-1; for (i=v+1;i<=size;i++) Assert(s->degree[i]==min || s->degree[i]==unknown,"degree too high"); checkminiC(s,1,1,0); } void checkmaxiD(subcaseptr s, int v) /* are all choices after that of the degree of vertex Bv the maximum possible?*/ { int i, max=Nhood&&size>=5?8:7; for (i=v+1;i<=size;i++) Assert(s->degree[i]==max || s->degree[i]==unknown,"degree too low"); checkmaxiC(s,1,1,0); } void checkminiE(subcaseptr s, int row, int col) /* are all choices after that of an edge in position [row][col] the minimum possible?*/ { int i,j; for (i=row;iadj[i][j]==0 || s->adj[i][j]==unknown,"there shouldn't be an edge here"); checkminiD(s, 0); } void checkmaxiE(subcaseptr s, int row, int col) /* are all choices after that of an edge in position [row][col] the maximum possible?*/ { int i,j; for (i=row;iadj[i][j]==1 || s->adj[i][j]==unknown,"there shouldn't be a non-edge here"); checkmaxiD(s, 0); } void checkinterval(subcaseptr I) /* does a subcase really correspond to an interval in the order defined by a common prefix of the labels? i.e. is it given by an initial segment of the choices having been made and all the remaining ones still open. (open choices being given by the value "unknown" for edges and degrees and by a range (i,theoretical max>i) for a choice as to whether the number of common neighbours of two vertices is exactly i) */ { int i,j,common; bool open, allopen=false; /* allopen if all questions from here on must be unanswered */ /* edges */ for (i=1;iadj[i][j]==unknown; if (allopen) if (!Assert(open,"edges don't give an interval")) return; else; else allopen=open; } /* degrees */ for (i=1;idegree[i]==unknown; if (allopen) if (!Assert(open,"degrees don't give an interval")) return; else; else allopen=open; } /* common neighbours */ for (common=0;commonmaxcommon[i][j]>=common) { open=I->mincommon[i][j]==common && I->maxcommon[i][j]>common; if (allopen) if (!Assert(open || I->maxcommon[i][j]==I->theomaxcommon[i][j], "common neighbours don't give an interval")) return; else; else allopen=open; } } /* in the following functions the parameter(s) are assumed to be intervals */ void checkinitial(subcaseptr first) /* does this interval start at the first possible subcase? (no edges, degrees minimum and no common neighbours) */ { checkminiE(first,1,1); } void checkfinal(subcaseptr last) /* does this interval finish at the last possible subcase? (all edges, degrees maximum and maximum possible common neighbours) */ { checkmaxiE(last,1,1); } void checkfollows(subcaseptr X, subcaseptr Y) /* does the second of two intervals start immediately after the end of the first? */ { int i,j,c,divi,divj; for (i=1;iadj[i][j]!=unknown && Y->adj[i][j]!=unknown, "overlapping intervals")) return; else if (X->adj[i][j]adj[i][j]) {checkmaxiE(X,i,j);checkminiE(Y,i,j);return;} else if (!Assert(X->adj[i][j]<=Y->adj[i][j], "intervals in wrong order")) return; for (i=1;i<=size;i++) if (!Assert(X->degree[i]!=unknown && Y->degree[i]!=unknown, "overlapping intervals")) return; else if (X->degree[i]degree[i]) { Assert(X->degree[i]+1==Y->degree[i],"gap in degrees"); checkmaxiD(X,i);checkminiD(Y,i);return; } else if (!Assert(X->degree[i]<=Y->degree[i], "intervals in wrong order")) return; /* look for first point where the two diverged in choosing common neighbour information */ c=maxsize; for (i=1;imincommon[i][j]!=Y->mincommon[i][j]) { int m=X->mincommon[i][j]; if (mmaxcommon[divi][divj]==c && Y->mincommon[divi][divj]==c+1,"range split wrong"); checkmaxiC(X,divi,divj,c); checkminiC(Y,divi,divj,c); }