narray.c

Entropy-based CLIQUE算法改进

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include "Param.h"
#include "NPoint.h"
#include "NArray.h"

// Constructor
NArray::NArray(int d, const Param& prm)
:dim(d), val_min(prm.min_val), val_max(prm.max_val),
 int_size(prm.int_size), no_data(0)
{
  float temp_int_no;
  
  // First determine int_no
  temp_int_no = (float)(val_max-val_min)/int_size;
  int_no = int(temp_int_no);
  if (temp_int_no - int_no > 0.00001) int_no++;
  
  // Then calculate total no of cells needed
  total_int_no = ipower(int_no,dim);

  // Allocate and initialize the cells
  data = new int[int(total_int_no)];
  memset(data, 0, int(total_int_no)*sizeof(int));
}

NArray::NArray(int d, float mi, float ma, float s)
:dim(d), val_min(mi), val_max(ma), int_size(s), no_data(0)
{
  float temp_int_no;

  // First determine int_no
  temp_int_no = (float)(ma-mi)/s;
  int_no = int(temp_int_no);
  if (temp_int_no - int_no > 0.00001) int_no++;
  
  // Then calculate total no of cells needed
  total_int_no = ipower(int_no,dim);

  // Allocate and initialize the cells
  data = new int[total_int_no];
  memset(data, total_int_no*sizeof(int), 0);
}

// Destructor
NArray::~NArray()
{
  delete[] data;
}

// Set a value of the array
void NArray::set_value(NPoint& np, int value)
{
  data[cal_index(np)] = value;
}

// Get a value from the array
int NArray::get_value(NPoint& np)
{
  return data[cal_index(np)];
}

// Increment the value
void NArray::inc_value(NPoint& np)
{
  data[cal_index(np)]++;
  no_data++;
}

// Calculate the power of integer
int NArray::ipower(int x, int n)
{
  int result, i;

  assert(n>=0);

  // For n=0,
  if (n==0) return 1;
  
  // For n>0,
  result = x;
  for (i=0; i<n-1; i++) {
    result *= x;
  }
  
  return result;
}

// Calculate the index of the array from the co-ordinate
int NArray::cal_index(NPoint& np)
{
  int i;
  int pos;  
  
  pos = 0;
  for (i=0; i<dim; i++) {
    pos += ( int((np[i]-val_min)/int_size)*ipower(int_no,i) );
  }

  // The following code is for debug
  if (pos>total_int_no) {
    // That is likely to cause segmentation fault
    printf("Warning: pos>total_int_no at NArray::cal_index()\n ");
    printf("np = ");
    np.show();
    printf("\n");
  }

  return pos;
}

// Calculate the co-ordinate from the index of the array
void NArray::cal_coord(int index, NPoint& np)
{
  int i;

  if (np.get_dim()!=dim) {
    printf("NArray::cal_coord(): Warning: Dimensions do not match\n");
  }
  
  for (i=0; i<dim; i++) {
    np[i] = index % int_no;
    index = index / int_no;
  }
  
  for (i=0; i<dim; i++)
    np[i] = (np[i]+0.5)*int_size + val_min;
}

// Calculate the entropy
float NArray::cal_entropy()
{
  float density;
  float entropy = 0;
  int i;

  for (i=0; i<total_int_no; i++) {
    density = (float)data[i]/no_data;

    if (density > 1e-10) {
      entropy += -density*log(density);
    }
  }

  return entropy;  
}

// Clear the content of NArray
void NArray::clear()
{
  memset(data, 0, int(total_int_no)*sizeof(int));
  no_data = 0;
}

// Write the content of NArray to file
void NArray::writefile(char* filename)
{
  FILE* fout;
  NPoint np(dim);
  int i;
  float density;

  fout = fopen(filename,"wt");
  if (fout==NULL) {
    printf("NArray::writefile(): Cannot open '%s'\n",filename);
    exit(3);
  }

  for (i=0; i<total_int_no; i++) {
    cal_coord(i,np);
    density = (float)data[i]/no_data;

    if (density > 1e-10) {
      np.show(fout);
      fprintf(fout,"%f\n", density);
    }
  }
  
  fclose(fout);
}