pc1.c

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

/***************************************************************************/
/***                                                                     ***/
/***                     pc1.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"
 
#define FCOMP1(rel1,rel2) fcomp[rel1][rel2]

extern int swdebug;
extern int pcops;
extern int pcits;

#if defined(DYNAMIC)
extern char **mark;
#else
extern char mark[MAXCSP][MAXCSP];
#endif



/*
  Apply path-consistency to CSP.
  If node1,node2 > -1 then use only this as initial "queue".
  Return 0 if inconsistent.
*/
int path_cons1 (csp, maxnodeid, node1, node2)
     int       maxnodeid, node1, node2;
#if defined(DYNAMIC) 
     RELTYPE   **csp;
#else
     RELTYPE csp[MAXCSP][MAXCSP];
#endif
{
  register int i, j, k;
  register RELTYPE temp;
  int changed;

  if (swdebug) {
    putc('.',stderr);
    fflush(stderr);
  }

  if (node1 < 0) {
    for (i=0; i <= maxnodeid; i++)
      for (j=i+1; j <=maxnodeid; j++) 
	mark[i][j] = 1;
  } else {
    for (i=0; i <= maxnodeid; i++)
      for (j=i+1; j <= maxnodeid; j++) 
	mark[i][j] = 0;
    mark[node1][node2] = 1;
  }

  do {
    changed = 0;
    pcits++;
    for (i=0; i <= maxnodeid; i++)
      for (j=i+1; j <=maxnodeid; j++) 
	if (mark[i][j]) {
	  mark[i][j] = 0;
	  for (k = 0; k <= maxnodeid; k++) {
	    if ((k != i) && (k != j)) {
	      pcops++; /* constrain k,i,j */
	      if (k < i) 
		temp = FCOMP1(csp[k][i],csp[i][j]);
	      else 
		temp = FCOMP1(FINV(csp[i][k]),csp[i][j]);
	      if (temp != DALL) {
		if (k < j) {
		  temp = (temp&csp[k][j]);
		  if (temp == 0) {
		    if (swdebug) {
		      putc('-',stderr);
		      fflush(stderr);
		    }
		    return(0);
		  }
		  if (temp != csp[k][j]) {
		    changed = 1;
		    mark[k][j] = 1;
		    csp[k][j] = temp;
		  }
		} else {
		  temp = (FINV(temp)&csp[j][k]);
		  if (temp == 0) {
		    if (swdebug) {
		      putc('-',stderr);
		      fflush(stderr);
		    }
		    return(0);
		  }
		  if (temp != csp[j][k]) {
		    changed = 1;
		    mark[j][k] = 1;
		    csp[j][k] = temp;
		  }
		}
	      }
	      pcops++; /* constrain i,j,k */
	      if (j < k)
		temp = FCOMP1(csp[i][j],csp[j][k]);
	      else
		temp = FCOMP1(csp[i][j],FINV(csp[k][j]));
	      if (temp != DALL) {
		if (i < k) {
		  temp = (temp&csp[i][k]);
		  if (temp == 0) {
		    if (swdebug) {
		      putc('-',stderr);
		      fflush(stderr);
		    }
		    return(0);
		  }
		  if (temp != csp[i][k]) {
		    changed = 1;
		    mark[i][k] = 1;
		    csp[i][k] = temp;
		  } 
		} else {
		  temp = (FINV(temp)&(csp[k][i]));
		  if (temp == 0) {
		    if (swdebug) {
		      putc('-',stderr);
		      fflush(stderr);
		    }
		    return(0);
		  }
		  if (temp != csp[k][i]) {
		    changed = 1;
		    mark[k][i] = 1;
		    csp[k][i] = temp;
		  }
		}
	      }
	    }
	  }
	}		  
  } while (changed);
  if (swdebug) {
    putc('+',stderr);
    fflush(stderr);
  }
  return(1);
}