source: trunk/greenstone3-extensions/vishnu/src/cluster/clustering.c@ 8189

/* Related word hierarchical clustering using a given triangle similarity matrix */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

//#include <sys/times.h>
//#ifndef CLK_TCK
#include <time.h> 
//#endif

#include "clustering.h"
#include "create_trisim.h"
#include "simfuncs.h"
#include "iterative.h"
#include "linkfuncs.h"
#include "hierarchical.h"
#include "procresults.h"
#include "mysammon.h"


void *myrealloc(void *p, int n) {
    void *ret = p? realloc(p, n): mymalloc(n);
    
    if(!ret)
        fprintf(stderr, "clustering.c: no memory for realloc(p,%d)\n", n), exit(1);
    
    return ret;
}

void *mycalloc(int n, int m) {
    void *ret = calloc(n, m);
    
    if(!ret)
        fprintf(stderr, "clustering.c: no memory for calloc(%d,%d)\n", n, m), exit(1);
    
    return ret;
}

void *mymalloc(int n) {
    void *ret = malloc(n);
    
    if(!ret)
        fprintf(stderr, "clustering.c: no memory for malloc(%d,%d)\n", n), exit(1);
    
    return ret;
}

void myfree(void *p) {
    if(p)
        free(p);
}

void free_vector_array(double **d,int n)
{
    int i;
    for(i=0;i<n;i++)
        free(d[i]);
    free(d);
}

int VECTOR_SIZE;

/*
*  Main
*/
/* 0 vectors_3333 15 1 10 20 */

int
do_clustering (int linkage, double **vectors, int num_of_vectors, int arraySize, int min_c_items, 
               int target_clusters, int limit, int *coding, double ***centroidsPtr, char * buffer, int 
*cursize, int * curptr)
{
//    char * buffer = (char *) malloc (256);
//    int cursize = 256;
//    int curptr = 0;
    char bbuf[20];
    int n;

    double *sim_matrix, **centroids;
    double (*linkage_func)(double, double);
    
    //struct tms *timer = (struct tms *) mymalloc(sizeof (struct tms));
    
    Cluster *toplevel_cluster;
    Cluster **splitclusters = NULL;
    int clusters = 0, zeros=0;
 
    double threshold;
    double (*sim_func)(double *, double *, int) = cosine_distance;
    
    double *heights;

    int i, j;
    
    VECTOR_SIZE = arraySize;
     switch (linkage) {
    case COMPLETE_LINKAGE:
        linkage_func = maxlink;
        break;
    case AVERAGE_LINKAGE:
        linkage_func = avelink;
        break;
    case SINGLE_LINKAGE:
        linkage_func = minlink;
        break;
    default:
        printf ("clustering.c: main(): linkage type %d not defined.\n", linkage);
        exit(0);
    }
    
    if(limit > num_of_vectors) limit = num_of_vectors;
    
    sim_matrix = create_sim_matrix (vectors, limit, sim_func);
    
    
    /* an array of heights sorted by descending disim */
    heights = (double *) mycalloc ((limit - 1), sizeof (double));
    
    toplevel_cluster = hierarchical_clustering (sim_matrix, limit, heights, linkage_func);
   
    
    threshold = split_clusters (toplevel_cluster, &splitclusters, heights, limit, target_clusters-zeros, min_c_items, &clusters);
    
    iterative_clustering (splitclusters, clusters, vectors, limit, num_of_vectors, sim_func);
    
    centroids = malloc(sizeof(double **)*clusters);
    assert(centroids);
    
    n = sprintf(bbuf,"%d\n",clusters);  
    buffer = appendString(buffer,cursize,curptr,bbuf,strlen(bbuf));

    for (i = 0; i < clusters; i++)
    {
        centroids[i] = calloc(VECTOR_SIZE,sizeof(double));
        assert(centroids[i]);
        print_cluster_children (splitclusters[i], coding, buffer, cursize,curptr); 
    for (j = 0; j < splitclusters[i]->iter_items_num; j++)
      { 
        if( j<splitclusters[i]->iter_items_num-1 )
          {
        n = sprintf(bbuf,"%d%s",coding[splitclusters[i]->iter_items[j]],",");
        buffer = appendString(buffer,cursize,curptr,bbuf,strlen(bbuf));
          }
        else
          {
        n = sprintf(bbuf,"%d%s",coding[splitclusters[i]->iter_items[j]],"");
        buffer = appendString(buffer,cursize,curptr,bbuf,strlen(bbuf));
        
          }
      }
    
        for (j = 0; j < VECTOR_SIZE; j++) 
    {
            centroids[i][j]=splitclusters[i]->centroid[j];
    }

    buffer = appendString(buffer,cursize,curptr,"\n",1);
     }

    free (sim_matrix);
    free_cluster (toplevel_cluster);
    free (heights);

    *centroidsPtr = centroids;
    return clusters;
}

int clustering (int linkage, MatrixNodePtr *matrix, int num_of_vectors, int arraySize, int min_c_items, 
int target_clusters, int limit, char *buffer, int *cursize, int *curptr)
{
    int *coding, *newcoding, clusterCount, groupCount, i;
    double **vectors, **centroids, **newCentroids;
    vectors     = read_vectors (matrix, num_of_vectors, arraySize, &coding);
    
    clusterCount = do_clustering (linkage, vectors, num_of_vectors, arraySize, min_c_items, 
                target_clusters, limit, coding, &centroids, buffer, cursize, curptr);

    mysammon( centroids,  clusterCount, arraySize, buffer, cursize, curptr);

    free_vector_array(vectors,num_of_vectors);
    free_vector_array(centroids,clusterCount);

    
    free(coding);
    return 0;

}