/***************************************************************************//***                                                                     ***//***                    pcvb.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];#endif/* Weighting of the RCC8 basisrelations */int wt [8] = {4, 3, 5, 2, 2, 2, 2, 1};#define push(x, y)	{\			if (mark[x][y] == 0) {\				weight = 0;\				if (x < y) label = csp [x][y];\				else label = FINV(csp[y][x]);\				for (m = 0, mask = 1; m < 8; m++, mask*=2)\					if (label & mask) weight += wt [m];\				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 < 34; 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_entries_vb2 (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;	for (weight = 1; weight <= 21; weight++)		maxentry[weight] = 0;	/* determine the weight of the label */	weight = 0;	label = csp [r1][r2];	for (m = 0, mask = 1; m < 8; m++, mask*=2)		if (label & mask) weight += wt [m];	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_vb (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;	int	i, j;	for (weight = 1; weight <= 21; 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 = 0;		label = csp[i][j];		for (m = 0, mask = 1; m < 8; m++, mask*=2)			if (label & mask) weight += wt [m];		(*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 van Beek's scheme of a weighted queue.  If node1,node2 > -1 then use only this as initial queue.  Return 0 if inconsistent.*/int path_cons_vb (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	        m, mask, 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_entries_vb2(csp,maxnodeid,maxentry,node1,node2);    q = 1;  } else sort_entries_vb (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);}