chameleon.c

变色龙层次聚类算法

      printf("cannot allocate memory for right->points \n");
      return -1;
    }
  left->left = NULL;
  left->right = NULL;
  right->left = NULL;
  right->right = NULL;

  index0 = 0;
  index1 = 0;
  for(i=0; i<nvtxs; i++){
    if(part[i] == 0)
      {
	left->points[index0] = checkTable[i];
	index0++;
      }
    else if(part[i] == 1)
     {
	right->points[index1] = checkTable[i];
	index1++;
      }
    else
      {
	printf("something wrong with part. \n");
	return -1;
      }/* end if..else...*/
  }/* end for */
  if(index0!=group0 || index1!=group1)
    {
      printf("some thing wrong with index0-1. \n");
      return -1;
    }

  free(vwgts);
  free(eptr);
  free(eind);
  free(hewgts);
  free(options);
  free(part);
  free(edgecut);

  free(checkTable);

  return 1;

}/* end cutNode */


/****************************************************************
 * Name    : partition                                          *
 * Function: partition the graph recursively.                   *
 * Input   : void                                               *
 * Output  :  int                                               *
 ****************************************************************/
static int partition(struct node * source, struct node * left, struct node * right){
  struct node * l_left;
  struct node * l_right;
  struct node * r_left;
  struct node * r_right;
  int i;

  /* cut the source node into left node and right node */
  if(cutNode(source, left, right, BC)<0){
    printf("cutNode error! \n");
    return -1;
  }
  /* link the two sub-trees to the root */
  source->left = left;
  source->right = right;

  /* if left sub-tree is still bigger than threshold */
  if(left->numberPoints > threshold) {
    l_left = (struct node *)calloc(1, sizeof(struct node));
    if(l_left == NULL)
      {
	printf("cannot allocate memory for left! \n");
	return -1;
      }
    l_right = (struct node *)calloc(1, sizeof(struct node));
    if(l_right == NULL)
      {
	printf("cannot allocate memory for right! \n");
	return -1;
      }

    if(partition(left, l_left, l_right)<0)
      return -1;

  }else{
    groupLength[groupIndex] = left->numberPoints;
    groups[groupIndex] =  (int *)calloc(left->numberPoints, sizeof(int));
    if(groups[groupIndex] == NULL)
      {
	printf("cannot allocate memory for groups! \n");
	return -1;
      }
    for(i=0;  i<left->numberPoints; i++){
      groups[groupIndex][i] = left->points[i];
    }/* end for */
    groupIndex++;
    printf("groupIndex = %d \n", groupIndex);
    if(groupIndex >= MAXGROUPS)
      {
	printf("groupIndex is now bigger than MAXGROUPS \n");
	return -1;
      }

    /*following part is for output matlab file after first phase */
    /*
      printf("%Points in this group include: \n c%d = [", index_matlab);
      index_matlab++;
      for(i=0; i<left->numberPoints; i++)
      {
      printf("%f %f \n ", points[left->points[i]].x, points[left->points[i]].y);
      }
      printf("];\n\n");
    */
  }/* end if...else... */
  
  if(right->numberPoints > threshold){
    r_left = (struct node *)calloc(1, sizeof(struct node));
    if(r_left == NULL)
      {
	printf("cannot allocate memory for left! \n");
	return -1;
      }
    r_right = (struct node *)calloc(1, sizeof(struct node));
    if(r_right == NULL)
      {
	printf("cannot allocate memory for right! \n");
	return -1;
      }

    if(partition(right, r_left, r_right)<0)
      return -1;
  }else{
    groupLength[groupIndex] = right->numberPoints;
    groups[groupIndex] =  (int *)calloc(right->numberPoints, sizeof(int));
    if(groups[groupIndex] == NULL)
      {
	printf("cannot allocate memory for groups! \n");
	return -1;
      }
    for(i=0;  i<right->numberPoints; i++){
      groups[groupIndex][i] = right->points[i];
    }/* end for */
    groupIndex++;
    printf("groupIndex = %d \n", groupIndex);
    if(groupIndex >= MAXGROUPS)
      {
	printf("groupIndex is now bigger than MAXGROUPS \n");
	return -1;
      }


    /*following part is for output matlab file after first phase */
    /*
      printf("%Points in this group include: \n c%d =[", index_matlab);
      index_matlab++;
      for(i=0; i<right->numberPoints; i++)
      {
      printf("%f %f \n ", points[right->points[i]].x, points[right->points[i]].y);
      }
      printf("];\n\n");
    */
  }/* end if...else... */
  
  return 1;
}/* end partition */


/****************************************************************
 * Name    : computeSimilarity                                  *
 * Function: compute similarity between point i and point j     *
 * Input   :  int i -- index of point i                         *
 *            int j -- index of point j                         *
 * Output  :  double -- similarity in (DIAG-distance)/DIAG.     *
 ****************************************************************/
static double computeSimilarity(int i, int j) {
  float i_x, i_y, j_x, j_y;
  double simi;

  i_x = points[i].x;
  i_y = points[i].y;
  j_x = points[j].x;
  j_y = points[j].y;

  simi = (DIAG - sqrt((double)(i_x-j_x)*(i_x-j_x)+(double)(i_y-j_y)*(i_y-j_y)) )/DIAG;

  /*printf("simi is %f !!!", simi);*/

  return simi;
}/* end computeSimilarity */


/****************************************************************
 * Name    : establish_hyperGraph                               *
 * Function: establish hyperGraph based on the points           *
 *           information.                                       *
 * Input   :  void                                              *
 * Output  : int                                                *
 ****************************************************************/
static int establish_hyperGraph() {
  int i, j, k, l;
  double *similarity = NULL;
  double bestSimi;
  int indexBestSimi;
  int flag = 0;

  similarity = (double *)calloc(sizeof(double), N);
  if(similarity == NULL)
    return -1;

  /* find the k_nearest points for each of the N point */
  for (i=0; i<N; i++){
    /* compute similarity of point i with each point j */
    for (j =0; j<N; j++){
       similarity[j] = computeSimilarity(i,j);
    }/* end for j */

    /* find the K_nearest points around point i */
    for (k=0; k<K_nearest; k++){

      bestSimi = 0.0;
      indexBestSimi = 0;

      for (j=0; j<N; j++){
	if(j != i){
	  if (similarity[j]>bestSimi){
	    indexBestSimi = j;
	    bestSimi = similarity[j];
	  }/* end if */
	}/* end if */
      }/* end for j */
      
      /* add a new edge to one of the two points */
      if(i<indexBestSimi){
	points[i].edges[points[i].length].pointNO = indexBestSimi;
	points[i].edges[points[i].length].similarity = bestSimi;
	points[i].length += 1;
	if(points[i].length > K5_nearest)
	  {
	    printf("length of the edges exceeds K5_nearest! bestSimi is %f \n", 
		   bestSimi);
	    return -1;
	  }
      }
      else {
	/* check whether this edge has already been added from the
	 * other point.
	 */
	flag = 0;
	for(l=0; l<points[indexBestSimi].length; l++){
	  if(points[indexBestSimi].edges[l].pointNO == i){
	    flag = 1;
	    break;
	  }/* end if */
	}/* end for l */
	
	if(flag == 0){
	  points[indexBestSimi].edges[points[indexBestSimi].length].pointNO = i;
	  points[indexBestSimi].edges[points[indexBestSimi].length].similarity = bestSimi;
	  points[indexBestSimi].length += 1;
	  if(points[indexBestSimi].length > K5_nearest)
	  {
	    printf("length of the edges exceeds K5_nearest!bestSimi is %f \n", 
		   bestSimi);
	    return -1;
	  }
	}/* end if */
      }/* end else */

      similarity[indexBestSimi] = 0.0;

    }/* end for k */
    
  }/* end for i */

#ifdef Debug_establish_hyperGraph
  j =0;
  printf("hyper edge for point %d is: \n", j);
  for(i=0; i<points[j].length; i++){
    printf("%d  %f \n", points[j].edges[i].pointNO,  points[j].edges[i].similarity);
  }/* end for */
  j = 36;
  printf("hyper edge for point %d is: \n", j);
  for(i=0; i<points[j].length; i++){
    printf("%d  %f \n", points[j].edges[i].pointNO,  points[j].edges[i].similarity);
  }/* end for */
  j = 49;
  printf("hyper edge for point %d is: \n", j);
  for(i=0; i<points[j].length; i++){
    printf("%d  %f \n", points[j].edges[i].pointNO,  points[j].edges[i].similarity);
  }/* end for */
#endif 

  free(similarity);
  similarity = NULL;
  return 1;

}/* end establish_hyperGraph */


/****************************************************************
 * Name    : initialize                                         *
 * Function: initialize data                                    *
 * Input   :  void                                              *
 * Output  : int                                                *
 ****************************************************************/
static int initialize() {
  int i;

  bestGoodness = 0.0;

  groupIndex = 0;

  index_matlab = 0;

  for(i=0; i<MAXGROUPS; i++){
    groups[i]=NULL;
    groupLength[i]=0;
  }

  /* this is the threshold of size of node to stop partition */
  threshold = (int)(N*MINSIZE);
  if(threshold < 1)
    {
      printf("threshold less than 1, error! \n");
      return -1;
    }

  root = (struct node *)calloc(1, sizeof(struct node));
  if(root == NULL)
    {
      printf("cannot allocate memory for root! \n");
      return -1;
    }

  root->numberPoints = N;
  root->points = (int *)calloc(N, sizeof(int));
  if(root->points == NULL)
    {
      printf("cannot allocate memory for root->points! \n");
      return -1;
    }
  /* for the root node, all the points belong to it */
  for(i=0; i<N; i++)
    {
      (root->points)[i]=i;
    }

#ifdef Debug_initialize
  for(i=0; i<N; i++)
    {
      printf("(root->points)[%d]=%d \n", i, (root->points)[i]);
    }
#endif

  /* initialize points */
  for(i=0; i<N; i++) 
    {
      points[i].length = 0;
    }/* end for i */

  return 1;
}/* end initialize */



/****************************************************************
 * Name    : readData                                         *
 * Function: read in Data from the data file                    *
 * Input   :  void                                              *
 * Output  : void                                               *
 ****************************************************************/
/* 
 * May 23th, 2001. Weinan: readData() has been tested
 * being right.
 */
static int readData() {

  int i;

 /* open the data file */
  if ((fp = fopen(fileName, "r")) == NULL )
    {
      printf("cannot open input file correctly! \n");
      return -1;
    }

  /* Now start reading data */
  for (i=0; i<N; i++)
    {
      fscanf(fp, "%f%f", &points[i].x, &points[i].y);
    }/* end for i */

  return 1;

}/*end readData */


/****************************************************************
 * Name    : parsingInput                                       *
 * Function: parsing input command line                         *
 * Input   : argc, argv                                         *
 * Output  : void                                               *
 ****************************************************************/
/* 
 * May 23th, 2001. Weinan: parsingInput() has been tested
 * being right.
 */
static int parsingInput(int argc, char *argv[]) {

  if(argc == 4)
    {
      sscanf(argv[1], "%d", &N);
      if(N>MAXSIZE)
	{
	  printf("The size of the data set is bigger than MAXSIZE! \n");
	  return -1;
	}

      if ((int)strlen(argv[2]) >= MAX_fileName)
	{
	  printf("the name of the file is too long. "
		 "It should be within %d characters \n", 
		 MAX_fileName);
	  return -1;
	}
      else
	{
	  sscanf(argv[2], "%s", fileName);
	}

      sscanf(argv[3], "%d", &stopClusterNO);
      if(stopClusterNO>N)
	{
	  printf("stopClusterNO is now bigger than N, impossible! \n");
	  return -1;
	}
    } /* end if */
  else
    {
      printf("argument error \n");
      printf(" Usage of the program should be of the form: \n");
      printf(" chameleon N fileName stopClusterNO \n");
      return -1;
    }/* end else */

#ifdef Debug_parsingInput
  printf("Input data is: \n ");
  printf("N = %d \n", N);
  printf("fileName = %s \n", fileName);
  printf("stopClusterNO = %d \n", stopClusterNO);
#endif

  return 1;

}/* end parsingInput */