/***************************************************************************//***                                                                     ***//***                    pcwq.c (Version 1.0)                             ***//***                                                                     ***//***       Ronny Fehling, Bernhard Nebel, Jochen Renz  - March 1998      ***//***                                                                     ***//***         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                       ***//***                                                                     ***//***************************************************************************/#include "rcc8.h"#include "rcc8op.h"extern int swdebug;extern int pcops;extern int pcits;#if defined(DYNAMIC)extern struct entry **entry;extern char **mark;#elseextern struct entry entry[MAXWT][MAXCSP*MAXCSP];extern char mark[MAXCSP][MAXCSP];#endifextern int vtab[256];#define push(x, y)	{\			if (mark[x][y] == 0) {\				weight = 0;\				if (x < y) label = csp [x][y];\				else label = FINV(csp[y][x]);\			        weight = vtab [label];\				maxentry[weight]++;\				if (weight < index) index = weight;\				if (x < y) {\				  entry [weight][maxentry[weight]].row = x;\				  entry [weight][maxentry[weight]].col = y;\				} else {\				  entry [weight][maxentry[weight]].row = y;\				  entry [weight][maxentry[weight]].col = x;\				}\				mark[x][y] = 1;\				mark[y][x] = 1;\				q++;\			}\			}#define pop(x, y)	{\			for( ; maxentry[index] == 0 && index < 16; index++)\				;\			x = entry[index][maxentry[index]].row;\			y = entry[index][maxentry[index]].col;\			maxentry[index]--;\			mark[x][y] = 0;\			mark[y][x] = 0;\			q--;\			}void sort_entries2 (csp, maxnodeid, maxentry, r1, r2)     int		maxnodeid, r1, r2;     int		maxentry [MAXWT];#if defined(DYNAMIC)     RELTYPE   **csp;#else      RELTYPE csp[MAXCSP][MAXCSP];#endif{  /* register int m, label, weight, mask; */  register int weight;    for (weight = 1; weight <= 16; weight++)    maxentry[weight] = 0;  /* determine the weight of the label */  weight = vtab[csp [r1][r2]];    maxentry[weight]++;  entry [weight][maxentry[weight]].row = r1;  entry [weight][maxentry[weight]].col = r2;  mark[r1][r2] = 1;  mark[r2][r1] = 1;	}void sort_entries (csp, maxnodeid, maxentry, q)     int		maxnodeid, *q;     int		maxentry [MAXWT];#if defined(DYNAMIC)     RELTYPE   **csp;#else     RELTYPE csp[MAXCSP][MAXCSP];#endif{  /* register int m, label, weight, mask; */  register int weight;  int	i, j;      for (weight = 1; weight <= 16; weight++)    maxentry[weight] = 0;    for (i = 0; i < maxnodeid; i++)    for (j = i+1; j <=  maxnodeid; j++) {            if (csp [i][j] == DALL)	continue;            /* determine the weight of the label */      weight = vtab [csp [i][j]];            (*q)++;      maxentry[weight]++;      entry [weight][maxentry[weight]].row = i;      entry [weight][maxentry[weight]].col = j;      mark[i][j] = 1;      mark[j][i] = 1;    }  }/*    Apply path-consistency to CSP using a weighted queue.   If node1,node2 > -1 then use only this as initial queue.   Return 0 if inconsistent. */int path_cons_wq (csp, maxnodeid, node1, node2)     int       maxnodeid, node1, node2;#if defined(DYNAMIC)     RELTYPE   **csp;#else     RELTYPE csp[MAXCSP][MAXCSP];#endif{  register RELTYPE La, Lb, Lc, Lnc;  register int	i, j, k, temp;  int		q;  int	        label, weight;  int		maxentry [MAXWT], index;    if (swdebug) {    putc('.',stderr);    fflush(stderr);  }  for (i = 0; i <= maxnodeid; i++)    for (j = 0; j <= maxnodeid; j++)      mark [i][j] = 0;    q = 0;  if  ((node1 > -1) && (node2 > -1)) {    sort_entries2(csp,maxnodeid,maxentry,node1,node2);    q = 1;  } else sort_entries (csp,maxnodeid,maxentry,&q);    index=1;  while (q != 0) {       pop (i, j);    for (k = 0; k <= maxnodeid; k++) if (k != i && k != j) {      if (k < i) La = csp[k][i];      else La = FINV(csp[i][k]);      Lb = csp[i][j];      Lnc = FCOMP(La,Lb);      if (Lnc == DALL)	goto skip_3a;      pcops++;      if (k < j) Lc = csp[k][j];      else Lc = FINV(csp[j][k]);      temp = Lc & Lnc;      if (temp != Lc) {	if (temp == 0) {	  if (swdebug) {	    putc('-',stderr);	    fflush(stderr);	  }	  return (0);	}	if (k < j) {	  csp[k][j] = temp;	  push (k, j);	} else {	  csp[j][k] =  FINV(temp);	  push(j, k);	}      }    skip_3a:      ;      La = csp[i][j];      if (j < k) Lb = csp[j][k];      else Lb = FINV(csp[k][j]);      Lnc = FCOMP(La,Lb);      if (Lnc == DALL)  	goto skip_3b;      pcops++;      if (i < k) Lc = csp[i][k];      else Lc = FINV(csp[k][i]);      temp = Lc & Lnc;      if (temp != Lc) {	if (temp == 0) {	  if (swdebug) {	    putc('-',stderr);	    fflush(stderr);	  }	  return (0);	}	if ( i< k) {	  csp[i][k] = temp;	  push (i, k);	} else {	  csp[k][i] = FINV(temp);	  push(k,i);	}      }    skip_3b:      ;    }  }  if (swdebug) {    putc('+',stderr);    fflush(stderr);  }  return (1);}