rcc8io.c

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

/***************************************************************************/
/***                                                                     ***/
/***                     rcc8io.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"
#include <stdlib.h>


/* Print relation to string */
char *sprrel(char *s, RELTYPE r)
{

  *s = '\0';

  strcat(s,"( ");
  if (r&DC)
    strcat(s,"DC ");
  if (r&EC)
    strcat(s,"EC ");
  if (r&PO)
    strcat(s,"PO ");
  if (r&TPP)
    strcat(s,"TPP ");
  if (r&NTPP)
    strcat(s,"NTPP ");
  if (r&TPPI)
    strcat(s,"TPPI ");
  if (r&NTPPI)
    strcat(s,"NTPPI ");
  if (r&EQ)
    strcat(s,"EQ ");
  strcat(s,")");
  return(s);
}



/* Print constraint to string */
void sprcons(char *s, RELTYPE r, int node1, int node2)
{
  char relstr[100];

  sprintf(s,"%2d %2d ",node1,node2);
  sprrel(relstr,r);
  strcat(s,relstr);
}



/* Print an entire CSP to outfile */
#if defined(DYNAMIC)
void printcsp(FILE *outfile, int maxnodeid, char *typeid, RELTYPE **csp)
#else
void printcsp(FILE *outfile, int maxnodeid, char *typeid, RELTYPE csp[MAXCSP][MAXCSP])
#endif
{
  int i,j;
  char line[80];

  fprintf(outfile,"%d %s\n",maxnodeid,typeid);
  for (i = 0; i <= maxnodeid; i++) 
    for (j = i+1; j <= maxnodeid; j++) 
      if (csp[i][j] != DALL) {
	sprcons(line, csp[i][j], i, j);
	fprintf(outfile,"%s\n",line);
      }
  fprintf(outfile,".\n");
}
  


/* Parse relation from string */
int parserel(char *line, RELTYPE *r)
{
  RELTYPE result;
  char *oldline;
  
  oldline = line;
  result = 0;


  while ((*line != '\0') && (*line != '(')) line++;
  if (*(line++) != '(') {
    fprintf(stderr,"\n*** no '(' in rel spec: '%s'\n",oldline);
    return(0);
  }
  while (*line == ' ') line++;
  while ((*line != ')' ) && *line) {
    while (*line == ' ') line++;
    switch (*(line++)) {
    case 'D' : case 'd' :
      result |= DC; 
      line++; 
      break;
    case 'P' : case 'p' :
      result |= PO; 
      line++; 
      break;
    case 'E' : case 'e' :
      if (*line == 'C' || *line == 'c') result |= EC; 
      else result |= EQ;
      line++;
      break;
    case 'N' : case 'n':
      if (*(line=line+3) == 'I' || *line == 'i') result |= NTPPI;
      else result |= NTPP;
      line++;
      break;
    case 'T' : case 't':
      if (*(line=line+2) == 'I' || *line == 'i') result |= TPPI;
      else result |= TPP;
      line++;
      break;
    default : 
      fprintf(stderr,"\n*** Illegal rel spec: '%s'\n",oldline);
      return(0);
    }
    while (*line == ' ') line++;
  }
  if (*line != ')') {
    fprintf(stderr,"\n*** Missing ')' in rel spec in '%s'\n",oldline);
    return(0);
  }		
  *r = result;
  return(1);
}



/* Parse constraint from string */
int parsecons(char *line, RELTYPE *r, int *node1, int *node2)
{

  *node1 = -1;
  *node2 = -1;

  if (sscanf(line,"%d %d",node1,node2) != 2) {
    fprintf(stderr,"\n*** no node ids in rel spec: '%s'\n",line);
    return(0);
  }

  return(parserel(line, r));
}



/* Standard parsecsp for static allocation of CSP  */
int parsecsp(FILE *infile, int limit, int *maxnodeid, char *typeid, RELTYPE csp[MAXCSP][MAXCSP])
{
  char line[128];
  int i,j;
  RELTYPE r;

  if (feof(infile)) return(0);
  while (fgets(line,128,infile) && ((line[0] == '\n') || (line[0] == '\0')));
  if (feof(infile)) return(0);

  if (sscanf(line,"%d %s",maxnodeid,typeid) != 2) {
    fprintf(stderr,"\n*** Header line of CSP not found: '%s'\n",line);
    return(-1);
  }
  
  if (*maxnodeid > limit) {
    fprintf(stderr,"\n*** Maxnode too large: '%s'\n",line);
    return(-1);
  }
 
  for (i = 0; i <= *maxnodeid; i++)
    for (j = i+1; j <= *maxnodeid; j++)
      csp[i][j] = DALL;
     
  do {
    fgets(line,128,infile);
    if (line[0] == '.') return (1);
    if (parsecons(line, &r, &i, &j)) {
      if ((i > *maxnodeid) || (i < 0) || (j > *maxnodeid) || (j < 0) ||
	  (i == j)) {
	fprintf(stderr,"\n*** Illegal node id (parsecsp): '%s'\n",line);
	return(-1);
      }
      if (i > j) csp[j][i] &= inverse(r);
      else csp[i][j] &= r;
    } else return(-1);
  } while (1);
}



/* Parsecsp for fixed size dynamic allocation of CSP  */
int parsecsp_fsd(FILE *infile, int limit, int *maxnodeid, char *typeid, RELTYPE **csp)
{
  char line[128];
  int i,j;
  RELTYPE r;

  if (feof(infile)) return(0);
  while (fgets(line,128,infile) && ((line[0] == '\n') || (line[0] == '\0')));
  if (feof(infile)) return(0);

  if (sscanf(line,"%d %s",maxnodeid,typeid) != 2) {
    fprintf(stderr,"\n*** Header line of CSP not found: '%s'\n",line);
    return(-1);
  }
  
  if (*maxnodeid > limit) {
    fprintf(stderr,"\n*** Maxnode too large: '%s'\n",line);
    return(-1);
  }
 
  for (i = 0; i <= *maxnodeid; i++)
    for (j = i+1; j <= *maxnodeid; j++)
      csp[i][j] = DALL;
     
  do {
    fgets(line,128,infile);
    if (line[0] == '.') return (1);
    if (parsecons(line, &r, &i, &j)) {
      if ((i > *maxnodeid) || (i < 0) || (j > *maxnodeid) || (j < 0) ||
	  (i == j)) {
	fprintf(stderr,"\n*** Illegal node id (parescsp_fsd): '%s'\n",line);
	return(-1);
      }
      if (i > j) csp[j][i] &= inverse(r);
      else csp[i][j] &= r;
    } else return(-1);
  } while (1);
}



/* Parsecsp for variable sized dynamic allocation of CSP */
int parsecsp_vsd(FILE *infile, int limit, int prevmax, int *maxnodeid, char *typeid, RELTYPE ***csp)
{
  char line[128];
  int i,j,cspsize;
  RELTYPE r;

  if (feof(infile)) return(0);
  while (fgets(line,128,infile) && ((line[0] == '\n') || (line[0] == '\0')));
  if (feof(infile)) return(0);

  if (sscanf(line,"%d %s",maxnodeid,typeid) != 2) {
    fprintf(stderr,"\n*** Header line of CSP not found: '%s'\n",line);
    return(-1);
  }
  if (*maxnodeid > limit) {
    fprintf(stderr,"\n*** Maxnode too large: '%s'\n",line);
    return(-1);
  }

  if (*maxnodeid >= prevmax) {
    if(prevmax > 0){
      free((void *)(*csp)[0]);
      free((void *)(*csp));
    }
    cspsize=(*maxnodeid)+1;
    (*csp) = (RELTYPE **)malloc(cspsize*sizeof(RELTYPE *));
    (*csp)[0] = (RELTYPE *)malloc(cspsize*cspsize*sizeof(RELTYPE));
    for(i=1;i<cspsize;i++)
      (*csp)[i] = (*csp)[0] + i * cspsize;
  }
 
  for (i = 0; i <= *maxnodeid; i++)
    for (j = i+1; j <= *maxnodeid; j++)
      (*csp)[i][j] = DALL;
     
  do {
    fgets(line,128,infile);
    if (line[0] == '.') return (1);
    if (parsecons(line, &r, &i, &j)) {
      if ((i > *maxnodeid) || (i < 0) || (j > *maxnodeid) || (j < 0) ||
	  (i == j)) {
	fprintf(stderr,"\n*** Illegal node id (parsecsp_vsd): '%s' in %s,%d\n",line,typeid,*maxnodeid);
	return(-1);
      }
      if (i > j) (*csp)[j][i] &= inverse(r);
      else (*csp)[i][j] &= r;
    } else return(-1);
  } while (1);
}



/* Parse algfile and store it as array */
int parsealg(FILE *infile, char alg[MAXSET])
{ 
  char line[100];
  RELTYPE r;
  int size;

  
  size = 0;
  for (r=0; r<MAXSET; r++) alg[r] = 0;

  while (fgets(line,100,infile)) {
    if ((line[0] == '.') || (line[0] == '\0')) return(size);
    if (!parserel(line,&r)) return(0);
    alg[r] = 1;
    size++;
  }
  return(size);
}



/* Parse typeid from CSP */
int parse_type(char *csptype,int *newsize,float *newlabel,float *newdegree,float *newdensity)
{
  char *oldtype,crap[200];
  int change=0, oldsize;
  float oldlabel, olddegree, olddensity;

  
  oldsize=*newsize;
  oldlabel=*newlabel;
  olddegree=*newdegree;
  olddensity=*newdensity;

  oldtype=csptype;
  while ((*oldtype != '\0') && (*oldtype != 'N')) oldtype++;
  if (*(oldtype++) != 'N') {
    fprintf(stderr,"\n*** wrong statistical line: '%s'\n",oldtype);
    return(0);
  }

  sscanf(oldtype,"%d%s",newsize,crap);
  if(*newsize != oldsize) change=1;

  oldtype=csptype;
  while ((*oldtype != '\0') && (*oldtype != 'C') && (*oldtype != 'D')) oldtype++;
  if (*(oldtype) == 'D') {
    oldtype++;
    sscanf(oldtype,"%f%s",newdegree,crap);
    if(*newdegree != olddegree) change=1;
  }
  else if (*(oldtype) == 'C') {
    oldtype++;
    sscanf(oldtype,"%f%s",newdensity,crap);
    if(*newdensity != olddensity) change=1;
  }
  else {
    fprintf(stderr,"\n*** wrong statistical line: '%s'\n",oldtype);
    return(0);
  }
 
  oldtype=csptype;
  while ((*oldtype != '\0') && (*oldtype != 'L') && (*oldtype != 'U')) oldtype++;
  if (*(oldtype++) == '\0') {
    fprintf(stderr,"\n*** wrong statistical line: '%s'\n",oldtype);
    return(0);
  }
  sscanf(oldtype,"%f%s",newlabel,crap);
  if(*newlabel != oldlabel) change=1;

  return change;
}