/***************************************************************************//***                                                                     ***//***                  backtrack.c (Version 1.0)                          ***//***                                                                     ***//***       Ronny Fehling, Bernhard Nebel, Jochen Renz  - March 1988      ***//***                                                                     ***//***         fehling, nebel, renz@informatik.uni-freiburg.de             ***//***                                                                     ***//***          http://www.informatik.uni-freiburg.de/~sppraum             ***//***                                                                     ***//***                      Institut fuer Informatik                       ***//***                     Albert-Ludwigs-Universitaet                     ***//***                           Am Flughafen 17                           ***//***                       79110 Freiburg, Germany                       ***//***                                                                     ***//***************************************************************************//*  Heuristic for the choice of the next node while backtracking.  The next node is the one with minimum value of splitinfo[r][0] and   maximum value of FVAL(splitinfo[r][1]) (i.e. minimal restricting) */#include "rcc8.h"#include "rcc8op.h"/* should be in stdlib.h ! */long lrand48(void);#define tempset(r,i,j)          17*(splitinfo[r][0]) + FVAL(r);  #define tempenv(i,j)            10 * envcons(csp, maxnodeid, i,j)+temp;/* extern switches */   extern int swdebug;extern int swcomppath;extern int swverbose;extern int swquite;extern int swsummary;extern int swbrief;extern int swabrief;extern int swpositive;extern int swnegative;extern int swposneg;extern int swsplitinfo;extern int swrandomorder;extern int swwqueue;extern int swenvcons;extern int swfixed;extern int swtimeout;extern int swsolveonly;extern int swonlypathcons;extern int swmaxvisit;/* extern statistical info */extern unsigned int randomseed;extern int maxnodeid;extern char csptype[100];extern int consistent;extern int cntconsistent;extern int pathconsistent;extern int cntpathconsistent;extern int pcops;extern int pcits;extern int nodesvisited;extern int searchdepth;extern int maxdepth;extern double cputicks;extern double cpumicro;extern int trial;extern int rectrial;extern long int tpcops[MAXTRIAL];extern long int tpcits[MAXTRIAL];extern long int tnodesvisited[MAXTRIAL];extern int tmaxdepth[MAXTRIAL];extern double tcputicks[MAXTRIAL];extern double cumcputicks;extern double cumcpumicro;extern int cntsize;extern int size;RELTYPE splitinfo[MAXSET][9];#if defined(DYNAMIC)extern RELTYPE **csp;extern struct entry **entry;extern char **mark;extern int **consval;extern int prevmax;extern int path_cons(RELTYPE **csp,int maxnodeid, int node1, int node2);#else extern RELTYPE csp[MAXCSP][MAXCSP];extern struct entry entry[MAXWT][MAXCSP*MAXCSP];extern char mark[MAXCSP][MAXCSP];extern int consval[MAXCSP][MAXCSP];extern int path_cons(RELTYPE csp[MAXCSP][MAXCSP],int maxnodeid, int node1, int node2);#endifextern void initrand(unsigned int seed);/* compute the constrainedness of the environment of an edge */int envcons(csp, maxnodeid, i, j)     int    maxnodeid;     register int i,j;#if defined(DYNAMIC)     RELTYPE   **csp;#else      RELTYPE csp[MAXCSP][MAXCSP];#endif{  register int k;  register int w = 0;    for (k = 0; k <= maxnodeid; k++) {    if ((k != i) && (k != j)) {      if (k < i) w += FVAL(csp[k][i]);      else w += FVAL(FINV(csp[i][k]));      if (k < j) w += FVAL(csp[k][j]);      else w += FVAL(FINV(csp[j][k]));    }  }  return(w);}/*  check whether CSP is already solved,  if so return 1,  else return 0 and give a relation that can be split.*/int solved_csp(csp, maxnodeid, node1, node2)     int    maxnodeid, *node1, *node2;#if defined(DYNAMIC)     RELTYPE   **csp;#else     RELTYPE csp[MAXCSP][MAXCSP];#endif{  register int i,j;  register int temp, minval;  register RELTYPE r;  int defaultval = DEFAULTVAL;  minval = defaultval;  *node1 = -1;  *node2 = -1;  for (i=0; i <= maxnodeid; i++)    for (j=i+1; j <= maxnodeid; j++) {      if (csp[j][i]) {	r = csp[i][j];	if (swsplitinfo) {	  if (splitinfo[r][0] == 1) temp=0;	  else 	    temp = tempset(r,i,j);  	} else {	 	  if ((r == DC) || (r == EC) || (r == PO) || (r == TPP) || 	      (r == NTPP) || (r == TPPI) || (r == NTPPI) || (r == EQ) ||	      (r ==DALL))	    temp = 0; 	  else temp =  (FVAL(r));	}	if (temp == 0)	  csp[j][i] = 0;	else	  if (temp > 0) {	    if (swfixed) temp = consval[i][j];	    else if (swenvcons) temp = tempenv(i,j);	    if ((temp < minval) && (temp > 0)) {	      minval = temp;	      *node1 = i;	      *node2 = j;	    }	  }      }    }  if (swdebug) {    fprintf(stderr,"S(%d,%d->%d)  ",*node1,*node2,minval);    fflush(stderr);  }  if (minval == defaultval) return(1);  else     if (!swrandomorder || swfixed) return(0);    else {      if (randomseed == 0) 	initrand(0);      temp = abs(lrand48())%(maxnodeid*2);      do {	for (i=0; i <= maxnodeid; i++)	  for (j=i+1; j <= maxnodeid; j++) 	    if (csp[j][i]) 	      if (--temp <= 0) {		*node1 = i;		*node2 = j;		return(0);	      }      } while (1);    }}/* compute initial cons values */void init_consval(csp, maxnodeid)     int    maxnodeid;#if defined(DYNAMIC)     RELTYPE   **csp;#else      RELTYPE csp[MAXCSP][MAXCSP];#endif{  register RELTYPE r;  register int i,j, temp;  for (i=0; i <= maxnodeid; i++)    for (j=i+1; j <= maxnodeid; j++) {	r = csp[i][j];	if (swsplitinfo) {	  if (splitinfo[r][0] == 1) temp=0;	  else 	     temp = tempset(r,i,j);	} else {	 	  if ((r == DC) || (r == EC) || (r == PO) || (r == TPP) || 	      (r == NTPP) || (r == TPPI) || (r == NTPPI) || (r == EQ) ||	      (r ==DALL))	    temp = 0;	  else  temp = (FVAL(r));	}	if (temp <= 0) consval[i][j] = 0;	else {	  if (swenvcons) temp = tempenv(i,j);	  if (swrandomorder) temp = abs(abs(lrand48())%(temp*100));	  consval[i][j] = temp;	}      }}/* generate a "split" */void gen_split(RELTYPE r, RELTYPE split[8]){  int i;    if (swsplitinfo) {    for (i=1;i<=8;i++) split[i-1] = splitinfo[r][i];    } else {    i = 0;     if (r & PO) split[i++] = PO;    if (r & DC) split[i++] = DC;    if (r & EC) split[i++] = EC;      if (r & TPP) split[i++] = TPP;       if (r & TPPI) split[i++] = TPPI;    if (r & NTPP) split[i++] = NTPP;    if (r & NTPPI) split[i++] = NTPPI;    if (r & EQ) split[i++] = EQ;    split[i] = 0;  }}/* checks CSP for global consistency */int global_cons(csp, maxnodeid, node1, node2)     int    maxnodeid, node1, node2;#if defined(DYNAMIC)     RELTYPE   **csp;#else      RELTYPE csp[MAXCSP][MAXCSP];#endif{#if defined(DYNAMIC)  RELTYPE   **newcsp;#else   RELTYPE newcsp[MAXCSP][MAXCSP];#endif   RELTYPE split[8];  int splitnode1, splitnode2, s, cons=0;  register int i,j;  int node, cspsize=maxnodeid+1;     nodesvisited++;  node = nodesvisited;  if (node > swmaxvisit) return(-1);/*   if((node % NV_HEURISTIC_LIMIT) == 0) return(-1); */  if((++searchdepth) > maxdepth) maxdepth++;  if (swdebug) {    fprintf(stderr,"D%1d(%d,%d:%d)  ",searchdepth,node1,node2,csp[abs(node1)][abs(node2)]);    fflush(stderr);  }  #if defined(DYNAMIC)  newcsp = (RELTYPE **)malloc(cspsize*sizeof(RELTYPE *));  newcsp[0] = (RELTYPE *)malloc(cspsize*cspsize*sizeof(RELTYPE));  for(i=1;i<cspsize;i++)    newcsp[i] = newcsp[0] + i * cspsize;#endif  if (node1 < 0) {    for (i = 0; i <= maxnodeid; i++)      for (j = i+1; j <= maxnodeid; j++) {	newcsp[i][j] = csp[i][j];	newcsp[j][i] = 1;      }     if(!path_cons(newcsp,maxnodeid,node1,node2)) {#if defined(DYNAMIC)       free((void *) newcsp[0]); free((void *) newcsp); #endif      return(0);    }     pathconsistent = 1;    if (swonlypathcons) {#if defined(DYNAMIC)       free((void *) newcsp[0]); free((void *) newcsp); #endif      return(0);    }     if (swfixed) init_consval(newcsp,maxnodeid);    /* mark all nodes that don't have to be split */     if (solved_csp(newcsp,maxnodeid,&splitnode1,&splitnode2)) {#if defined(DYNAMIC)       free((void *) newcsp[0]); free((void *) newcsp); #endif         return(1);    }  }  else {    for (i = 0; i <= maxnodeid; i++)      for (j = 0; j <= maxnodeid; j++) {	newcsp[i][j] = csp[i][j];      }    if (!path_cons(newcsp,maxnodeid,node1,node2)) {      if (swdebug) {	fprintf(stderr,"u%1d  ",searchdepth);	fflush(stderr);      }      searchdepth--;#if defined(DYNAMIC)       free((void *) newcsp[0]); free((void *) newcsp); #endif        return(0);    }    if (solved_csp(newcsp,maxnodeid,&splitnode1,&splitnode2)) {      if (swdebug) {	fprintf(stderr,"U%1d  ",searchdepth);	fflush(stderr);      }      searchdepth--;#if defined(DYNAMIC)       free((void *) newcsp[0]); free((void *) newcsp); #endif             return(1);    }   }    /* splitting */  gen_split(newcsp[splitnode1][splitnode2],split);  for (s = 0; s < 8; s++) {    if (split[s] != 0) {      newcsp[splitnode1][splitnode2] = split[s];      cons=global_cons(newcsp,maxnodeid,splitnode1,splitnode2);      if (cons==1) {	if (swdebug) {	  fprintf(stderr,"U%1d  ",searchdepth);	  fflush(stderr);	}	searchdepth--; #if defined(DYNAMIC)       free((void *) newcsp[0]); free((void *) newcsp); #endif  	return(1);      }      else if (cons == -1) {	searchdepth--;#if defined(DYNAMIC) 	free((void *) newcsp[0]); free((void *) newcsp); #endif       return(-1);      }    } else break;  }  if (swdebug) {    fprintf(stderr,"u%1d  ",searchdepth);    fflush(stderr);  }  searchdepth--;#if defined(DYNAMIC)       free((void *) newcsp[0]); free((void *) newcsp); #endif       if(cons == -1) return(-1);      return(0);}