cover.c

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

/***************************************************************************/
/***                                                                     ***/
/***               cover.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                       ***/
/***                                                                     ***/
/***************************************************************************/


/*
       cover < relation-file > coverfile

    reads in a set of relations from stdin and outputs to stdout a table 
    consisting of coverages of each relation in numerical form, 
    i.e., a table with 256 entries. Each entry has 9 numbers, standing 
    for size and the 8 base relations that cover the relation. 
    Prints statistics to stderr. 
*/

const char *usagestring = "\
usage: cover < relation-file > coverfile
    
    computes the table of all 256 RCC8 relations covered by the 
    relations in the relation-file.";
     

#include "rcc8.h"
#include "rcc8io.h"
#include "rcc8op.h"

#include <stdlib.h>
#include <stdio.h>

#define MAXCOVER 8

char coverset[MAXSET];
int coversize;
int coverstat[MAXSET];

int try(RELTYPE rel, 
	int trycomb, 
	int candcount, 
	RELTYPE cand[MAXSET], 
	RELTYPE res[MAXCOVER])
{
  register int i;

  for (i = trycomb-1; i >= 0 ; i--)
    res[i] = 0;

  if (trycomb == 1) {
    for (i=0; i<candcount; i++) 
      if ((~cand[i] & rel) == 0)  {
	res[0] = cand[i];
	return(1);
      }
  } else {
    for (i=0; i<candcount; i++) 
      if (cand[i] & rel)  {
	res[trycomb-1] = cand[i];
	if (try((~cand[i] & rel), trycomb-1, candcount, cand, res))
	  return(1);
      }
  }
  return(0);
}

int cand_compare(const void*p1, const void *p2){
  const RELTYPE *r1=p1,*r2=p2;
  register int v1, v2;

  v1 = FVAL(*r1);
  v2 = FVAL(*r2);
  return(((v1 < v2) ? -1 : ((v1 == v2) ? 0 : 1)));
}

int printcover(FILE *outfile, RELTYPE rel, int csize, char cset[MAXSET])
{
  static RELTYPE cand[MAXSET];
  RELTYPE ccand;
  register RELTYPE i;
  RELTYPE c[MAXCOVER] = {0,0,0,0,0,0,0,0};
  int cc;


  if (rel == 0) {
    fprintf(outfile,"1 0 0 0 0 0 0 0 0\n");
    return(1);
  }

  ccand = 0;
  /* select candidates: only those relations that are included in rel */
  for (i=1; i<MAXSET; i++)
    if ((cset[i]) && (((~rel) & i) == 0)) 
      cand[ccand++] = i;

  /* now sort candidates such that least constraining relations appear first */
  qsort(cand,ccand,sizeof(RELTYPE),&cand_compare);
  
  for (cc = 1; cc <= MAXCOVER; cc++) 
    if (try(rel, cc, ccand, cand, c)) {
      fprintf(outfile,"%d %d %d %d %d %d %d %d %d\n",
	      cc, c[0],c[1],c[2],c[3],c[4],c[5],c[6],c[7]);
      return(cc);
    }
  fprintf(stderr,"***More than %d relations for coverage needed!\n",MAXCOVER);
  exit(-1);
}

	
  


void printstat(FILE *outfile, int cstat[MAXSET])
{
  register int i;
  int ccount[MAXCOVER] = {0,0,0,0,0,0,0,0};

  for (i = 0; i<MAXSET; i++)
    if ((cstat[i] < 1) || (cstat[i] > MAXCOVER)) {
      fprintf(stderr, "***Illegal coverage value for '%d': '%d'\n",i,cstat[i]);
      exit(-1);
    } else ccount[cstat[i]-1]++;
  
  fprintf(outfile,"Coverage:\n");
  fprintf(outfile,"  1: %4d\n  2: %4d\n  3: %4d\n  4: %4d\n  5: %4d\n  6: %4d\n  7: %4d\n  8: %4d\n",
	  ccount[0],ccount[1],ccount[2],ccount[3],ccount[4],
	  ccount[5],ccount[6],ccount[7]);
  fprintf(outfile,"  average branching: %8.3f\n",((double)(ccount[0]*1+
							   ccount[1]*2+
							   ccount[2]*3+
							   ccount[3]*4+
							   ccount[4]*5+
							   ccount[5]*6+
							   ccount[6]*7+
							   ccount[7]*8)/
						  (double)MAXSET));
}


void usage()
{
  fprintf(stderr,"%s\n",usagestring);
  exit(-1);
}


void main(int argc, char **argv)
{

  int r;


  if (argc != 1) usage();

  initfop();

  coversize = parsealg(stdin, coverset);
  for (r=0;r<MAXSET;r++) 
    coverstat[r] = printcover(stdout, r, coversize, coverset);
  printstat(stderr, coverstat);
  exit(0);
}