gencsp.c

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

/***************************************************************************/
/***                                                                     ***/
/***                  gencsp.c   (Version 2.0)                           ***/
/***                                                                     ***/
/***       Jochen Renz, Bernhard Nebel, Ronny Fehling  - July 1999       ***/
/***                                                                     ***/
/***         fehling, nebel, [e-mail]             ***/
/***                                                                     ***/
/***          http://www.informatik.uni-freiburg.de/~sppraum             ***/
/***                                                                     ***/
/***                      Institut fuer Informatik                       ***/
/***                     Albert-Ludwigs-Universitaet                     ***/
/***                           Am Flughafen 17                           ***/
/***                       79110 Freiburg, Germany                       ***/
/***                                                                     ***/
/***************************************************************************/


/*
    gencsp [-ue] [-is number] [-cdlnCDLN min [max step]]  [-rx file] [-o name]

    Generates RCC8 CSPs. 
    options are:
       -u   uniform distribution of labels (50% probability for each label, 
            overwrites -l)
       -e   all possible relations are equally distributed (owerwrites -u 
            and -l)

       -i <number>  specifies number of instances to be generated (default 1)
       -s <number>  specifies the seed for the random function

      The following options expect either one value (particular value) or 
      three values (minimum value, maximum value and the stepwidth) which 
      specifies the range of the generated instances.
      Numbers in brackets specify the range of accepted values.
       -c   specifies the constraint density (default 0.0) [0.01 - 1.0]
       -d   specifies the average degree of a node (default 0) [0 - MAXCSP]
       -l   specifies the average labelsize (default 4.0) [1.0 - 8.0] 
       -n   specifies the number of nodes (default 3) [3 - MAXCSP]
      The following options restrict the output of the generated instances 
      to those within the given range; again either one value or three values 
      are expected. These options are by default unset. Do not set C without 
      setting c, D without d, L without l, and N without n. 
       -C   restricts the output constraint density [0.01 - 1.0]
       -D   restricts the output average degree of a node [0 - MAXCSP]
       -L   restricts the output labelsize [1.0 - 8.0]
       -N   restricts the output number of nodes [3 - MAXCSP]


       -r <file>  restricts all relations to be the ones mentioned in the file
       -x <file>  specifies the relations to be excluded

       -o <name>  specifies the prefix of the outputfile 
                  (default is none)

       The -c and -d options override each other.
*/


const char *usagestring = "\
usage: gencsp [-u] [-is number] [-cdlnCDLN min [max step]]  [-rx file] [-o name]

    Generates RCC8 CSPs. 
    options are:
       -u   uniform distribution of labels (50% probability for each label, 
            overwrites -l)
       -e   all possible relations are equally distributed (owerwrites -u 
            and -l)

       -i <number>  specifies number of instances to be generated (default 1)
       -s <number>  specifies the seed for the random function

      The following options expect at least one value or three indicating 
      minimum value, maximum value and the stepwidth.
      Numbers in brackets specify the range of accepted values.
       -c   specifies the constraint density (default 0.0) [0.01 - 1.0]
       -d   specifies the average degree of a node (default 0) [0 - MAXCSP]
       -l   specifies the labelsize (default 4.0) [1.0 - 8.0] 
       -n   specifies the number of nodes (default 3) [3 - MAXCSP]
      The following options restrict the output of the generated instances
      to those within the given range; again either one value or three values
      are expected. These options are by default unset. Do not set C without 
      setting c, D without d, L without l, and N without n. 
       -C   restricts the output constraint density [0.01 - 1.0]
       -D   restricts the output average degree of a node [0 - MAXCSP]
       -L   restricts the output average labelsize [1.0 - 8.0]
       -N   restricts the output number of nodes [3 - MAXCSP]      

       -r <file>  restricts all relations to be the ones mentioned in the file
       -x <file>  specifies the relations to be excluded

       -o <name>  specifies the prefix of the outputfile 
                  (default is none)

       The -c and -d options override each other.";



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

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/times.h>
#include <sys/types.h>
#include <sys/resource.h>

/* should be in stdlib.h ! */
void srand48(long seedval);
long lrand48(void);

/* switches for gencsp */ 
unsigned int   swseed = 0;
int swoutfile = 0;
int swinstances = 1;
int swminnodes  = 3;
int swmaxnodes = 3;
int swstepnodes = 1;
int swexclude = 0;
int swrestrict = 0;
int restrictsize;
int swuniform = 0;
int swequaldistribution = 0;
int swminsize =0;
int minsize = 0;
float swmindegree = 0.0;
float swmaxdegree = 0.0;
float swstepdegree = 1.0;
float swminlabsiz = 4.0;
float swmaxlabsiz = 4.0;
float swsteplabsiz = 1.0;
float swminconsdensity = 0.0;
float swmaxconsdensity = 0.0;
float swstepconsdensity = 0.1;

int swminnodesout  = 0;
int swmaxnodesout = 0;
int swstepnodesout = 1;
int swnodesout=0;
float swminlabsizout = 0.0;
float swmaxlabsizout = 0.0;
float swsteplabsizout = 1.0;
int swlabout = 0;
float swminconsdensityout = 0.0;
float swmaxconsdensityout = 0.0;
float swstepconsdensityout = 0.1;
int swconsdensout=0;
float swmindegreeout = 0.0;
float swmaxdegreeout = 0.0;
float swstepdegreeout = 1.0;
int swdegreeout=0;

char cstype[100]; 
char csptype[100];
char xalg[MAXSET];
char ralg[MAXSET];
RELTYPE posslabels;
RELTYPE equalalg[MAXSET];
RELTYPE ralglist[MAXSET];
RELTYPE splitinfo[MAXSET][9];

#if defined(DYNAMIC)
RELTYPE **csp;
#else 
RELTYPE csp[MAXCSP][MAXCSP];
#endif


/* files and filenames */
FILE *infile;
char infilename[200];
FILE *splitfile;
char splitfilename[200];
FILE *outfile;
char outfilename[200];
char ralgname[200];
char xalgname[200];



/* seed for random variable */
unsigned int randomseed = 0;

int equalnumber = 0;


/* Initalizes random seed */
void initrand(unsigned int seed)
{
  if (seed == 0)
    randomseed = time(NULL);
  else
    randomseed = seed;

  srand48(randomseed);
}

RELTYPE genlab(float avglabsiz, int uniform, int restrict, int exclude)
{
  long int thres;
  RELTYPE rel, shift;
  int onerelx;
  int i;
  int disjcnt;
  
  if (swequaldistribution) {
    shift = (RELTYPE) (abs(lrand48())%equalnumber);
    rel = equalalg[shift];
    return rel;
  }
    

  if (uniform) {
    thres = 4999;
    onerelx = -1;
  } 
  else {
    thres = ((int)((avglabsiz-1.0)*10000.0/7.0))-1;
    if(!swrestrict && !swexclude) onerelx = abs(lrand48())%8;
    else  
      do {
          shift = 1;
          onerelx = abs(lrand48())%8;
          shift = shift << onerelx;
         } while ((shift & posslabels) == 0);
   }
 
  do {
    shift = 1;
    i = 0;
    rel = 0;
    disjcnt = 1;

    do {
      if (i == onerelx) {
	rel |= shift;
	disjcnt++;
      }
      else
	if (abs(lrand48())%10000 <= thres) {
	  rel |= shift;
	  disjcnt++;
	}
      shift = shift << 1;
    } while (++i < 8);
  } while ((swexclude && xalg[rel] && (disjcnt > 1)) || 
	   (swrestrict && !ralg[rel]));
  return(rel);
}



void gennet(csp,typestring,instcnt,cspsize, seed,avglabsiz,avgcondense,avgdegree)
     char *typestring;
     int instcnt,cspsize; 
     unsigned int seed;
     float avglabsiz,avgcondense,avgdegree;
#if defined(DYNAMIC)
     RELTYPE   **csp;
#else 
     RELTYPE csp[MAXCSP][MAXCSP];
#endif
{
  register int i,j;
  long int thres;
  int incons;

  
  sprintf(typestring,"#%1d-N%1d-%c%1.2f-%c%1.2f-R:%s-X:%s-S%1u",
	  instcnt,cspsize,	 
	  (avgcondense != 0.0 ? 'C' : 'D'),
	  (avgcondense != 0.0 ? avgcondense : avgdegree),
	  (swuniform ? 'U' : 'L'),
	  avglabsiz,
	  (swrestrict ? ralgname : "-"), 
	  (swexclude ? xalgname : "-"), 
	  seed);
 
  
  if (avgcondense == 0.0) 
    avgcondense = (((avgdegree))/((float)(cspsize-1)));

  thres = ((int)(avgcondense*10000.0))-1;

  do {
    incons = 0;
    for (i = 0; i < cspsize; i++)
      for (j = i+1; j < cspsize; j++)
	if (abs(lrand48())%10000 <= thres) {
	  if (!(csp[i][j] = genlab(avglabsiz,swuniform,swrestrict,swexclude))) {
	    i = cspsize;
	    j = cspsize;
	    incons = 1;
	    break;
	  }
	} else
	  csp[i][j] = DALL;
  } while (incons);
}



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



int int_compare(long int *i1, long int *i2)
{
  return(((*i1 < *i2) ? -1 
	  : ((*i1 == *i2) ? 0 : 1)));
}