util.c

多层权核k均值算法

/*
 * Copyright 1997, Regents of the University of Minnesota
 *
 * util.c
 *
 * This function contains various utility routines
 *
 * Started 9/28/95
 * George
 *
 * $Id: util.c,v 1.1 1998/11/27 17:59:32 karypis Exp $
 */

#include <metis.h>

/************************************************************************
 when command line fails, print out help info
************************************************************************/
void print_help(char *program_name){
  printf("\nHelp\nTo cluster a graph into a given number of clusters:\n %s [options] graph_file number_of_clusters\n", program_name);
  printf(" options: -o ncut|rassoc\n");
  printf(" \t\t ncut --- normalized cut (default)\n\t\t rassoc --- ratio association\n");
  printf("          -l number_of_local_search_steps (default is 0)\n");
  printf("          -b use only boundary points (default is to use all points)\n");
  printf("\nTo compute objective function value for a given clustering:\n %s [options] -e clustering_file graph_file\n\n", program_name);
}


/************************************************************************
 find out the cluster size
************************************************************************/
void clusterSize(GraphType * graph, int *clustersize){
  int *where, i, nvtxs;
  where = graph->where;
  nvtxs = graph->nvtxs;

  for (i=0; i<nvtxs; i++)
    clustersize[where[i]] ++;
}

/*************************************************************************
* This function transform Metis graph matrix into a dense matrix,
* which is represented as an array initialized to be 0
**************************************************************************/
void sparse2dense(GraphType * graph, double * dense, float *m_adjwgt)
{
  int nvtxs, i, j;
  idxtype *adjwgt, *adjncy, *xadj;

  nvtxs = graph->nvtxs;
  xadj = graph->xadj;
  adjncy = graph->adjncy;
  adjwgt = graph->adjwgt;

  for (i=0; i<nvtxs; i++)
    for (j=0; j<nvtxs; j++)
      dense[i*nvtxs+j] =0;

  if (adjwgt == NULL)
    for (i=0; i<nvtxs; i++)
      for (j=xadj[i]; j<xadj[i+1]; j++) 
	dense[i* nvtxs+adjncy[j]] = 1;
  else
    for (i=0; i<nvtxs; i++)
      for (j=xadj[i]; j<xadj[i+1]; j++) 
	dense[i* nvtxs+adjncy[j]] = m_adjwgt[j];
}

/*************************************************************************
* This function extracts file name from a path
**************************************************************************/
void extractfilename(char *path, char *name)
{
  int length, i, j;
  length = strlen(path);
  for(i= length-1; i>=0; i--)
    if ((path[i] == '/') || (path[i] == '\\'))
      {
	i++;
	for (j=i; j<length; j++)
	  name[j-i]=path[j];
	name[j-i] = '\0';
	break;
      }
    else if (i==0)
      {
	for (j=i; j<length; j++)
	  name[j-i]=path[j];
	name[j] = '\0';
	break;
      }
}

/*************************************************************************
* This function prints an error message and exits
**************************************************************************/
void errexit(char *f_str,...)
{
  va_list argp;
  char out1[256], out2[256];

  va_start(argp, f_str);
  vsprintf(out1, f_str, argp);
  va_end(argp);

  sprintf(out2, "Error! %s", out1);

  fprintf(stdout, out2);
  fflush(stdout);

  abort();
}



#ifndef DMALLOC
/*************************************************************************
* The following function allocates an array of Chains
**************************************************************************/
Chains *chainmalloc(int n, char *msg)
{
  if (n == 0)
    return NULL;

  return (Chains *)GKmalloc(sizeof(Chains)*n, msg);
}

/*************************************************************************
* The following function allocates an 2-D array of floats
**************************************************************************/
float **f2malloc(int n, int m, char *msg)
{
  float ** temp;
  int i;
  if ((n == 0) || (m==0))
    return NULL;

  temp = (float **)GKmalloc(sizeof(float *)*n, msg);
  for (i=0; i<n; i++)
    temp[i] = (float *)GKmalloc(sizeof(float)*m, msg);
  return temp;
}

/*************************************************************************
* The following function allocates an 2-D array of ints
**************************************************************************/
int **i2malloc(int n, int m, char *msg)
{
  int ** temp;
  int i;
  if ((n == 0) || (m==0))
    return NULL;

  temp = (int **)GKmalloc(sizeof(int *)*n, msg);
  for (i=0; i<n; i++)
    temp[i] = (int *)GKmalloc(sizeof(int)*m, msg);
  return temp;
}

/*************************************************************************
* The following function allocates an array of integers
**************************************************************************/
int *imalloc(int n, char *msg)
{
  if (n == 0)
    return NULL;

  return (int *)GKmalloc(sizeof(int)*n, msg);
}


/*************************************************************************
* The following function allocates an array of integers
**************************************************************************/
idxtype *idxmalloc(int n, char *msg)
{
  if (n == 0)
    return NULL;

  return (idxtype *)GKmalloc(sizeof(idxtype)*n, msg);
}


/*************************************************************************
* The following function allocates an array of float 
**************************************************************************/
float *fmalloc(int n, char *msg)
{
  if (n == 0)
    return NULL;

  return (float *)GKmalloc(sizeof(float)*n, msg);
}


/*************************************************************************
* The follwoing function allocates an array of integers
**************************************************************************/
int *ismalloc(int n, int ival, char *msg)
{
  if (n == 0)
    return NULL;

  return iset(n, ival, (int *)GKmalloc(sizeof(int)*n, msg));
}



/*************************************************************************
* The follwoing function allocates an array of integers
**************************************************************************/
idxtype *idxsmalloc(int n, idxtype ival, char *msg)
{
  if (n == 0)
    return NULL;

  return idxset(n, ival, (idxtype *)GKmalloc(sizeof(idxtype)*n, msg));
}


/*************************************************************************
* This function is my wrapper around malloc
**************************************************************************/
void *GKmalloc(int nbytes, char *msg)
{
  void *ptr;

  if (nbytes == 0)
    return NULL;

  ptr = (void *)malloc(nbytes);
  if (ptr == NULL) 
    errexit("***Memory allocation failed for %s. Requested size: %d bytes", msg, nbytes);

  return ptr;
}
#endif

/*************************************************************************
* This function is my wrapper around free, allows multiple pointers    
**************************************************************************/
void GKfree(void **ptr1,...)
{
  va_list plist;
  void **ptr;

  if (*ptr1 != NULL)
    free(*ptr1);
  *ptr1 = NULL;

  va_start(plist, ptr1);

  /* while ((int)(ptr = va_arg(plist, void **)) != -1) { */
  while ((ptr = va_arg(plist, void **)) != LTERM) {
    if (*ptr != NULL)
      free(*ptr);
    *ptr = NULL;
  }

  va_end(plist);
}            


/*************************************************************************
* These functions set the values of a vector
**************************************************************************/
int *iset(int n, int val, int *x)
{
  int i;

  for (i=0; i<n; i++)
    x[i] = val;

  return x;
}


/*************************************************************************
* These functions set the values of a vector
**************************************************************************/
idxtype *idxset(int n, idxtype val, idxtype *x)
{
  int i;

  for (i=0; i<n; i++)
    x[i] = val;

  return x;
}


/*************************************************************************
* These functions set the values of a vector
**************************************************************************/
float *sset(int n, float val, float *x)
{
  int i;

  for (i=0; i<n; i++)
    x[i] = val;

  return x;
}



/*************************************************************************
* These functions return the index of the maximum element in a vector
**************************************************************************/
int iamax(int n, int *x)
{
  int i, max=0;

  for (i=1; i<n; i++)
    max = (x[i] > x[max] ? i : max);

  return max;
}


/*************************************************************************
* These functions return the index of the maximum element in a vector
**************************************************************************/
int idxamax(int n, idxtype *x)
{
  int i, max=0;

  for (i=1; i<n; i++)
    max = (x[i] > x[max] ? i : max);

  return max;