pcwq.c

利用空间表示的rcc8模型进行空间推理

/***************************************************************************/
/***                                                                     ***/
/***                    pcwq.c (Version 1.0)                             ***/
/***                                                                     ***/
/***       Ronny Fehling, Bernhard Nebel, Jochen Renz  - March 1998      ***/
/***                                                                     ***/
/***         fehling, nebel, [e-mail]             ***/
/***                                                                     ***/
/***          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;
#else
extern struct entry entry[MAXWT][MAXCSP*MAXCSP];
extern char mark[MAXCSP][MAXCSP];
#endif

extern 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);
}