| commit | author | age | ||
| 92b76b | 1 | /* vim: set ts=4 sts=4 sw=4 noet : */ |
| SP | 2 | #include<stdlib.h> |
| 3 | #include "general.h" | |
| 4 | #include "cluster.h" | |
| 5 | #include <math.h> | |
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 | ts_cluster_list *init_cluster_list(){ | |
| 11 | ts_cluster_list *cstlist=(ts_cluster_list *)malloc(sizeof(ts_cluster_list)); | |
| 12 | cstlist->n=0; | |
| 13 | cstlist->cluster=NULL; | |
| 14 | return cstlist; | |
| 15 | } | |
| 16 | ||
| 17 | ts_cluster *new_cluster(ts_cluster_list *cstlist){ | |
| 18 | ||
| 19 | cstlist->n++; | |
| 20 | cstlist->cluster=(ts_cluster **)realloc(cstlist->cluster,cstlist->n*sizeof(ts_cluster *)); | |
| 21 | if(cstlist->cluster==NULL) fatal("Cannot reallocate memory for additional **ts_cluster.",100); | |
| 22 | cstlist->cluster[cstlist->n-1]=(ts_cluster *)calloc(1,sizeof(ts_cluster)); | |
| 23 | if(cstlist->cluster[cstlist->n-1]==NULL) fatal("Cannot allocate memory for additional *ts_cluster.",100); | |
| 24 | return cstlist->cluster[cstlist->n-1]; | |
| 25 | } | |
| 26 | ||
| 27 | ts_bool cluster_add_vertex(ts_cluster *cluster, ts_vertex *vtx){ | |
| 28 | cluster->nvtx++; | |
| 29 | cluster->vtx=(ts_vertex **)realloc(cluster->vtx, cluster->nvtx*sizeof(ts_vertex *)); | |
| 30 | cluster->vtx[cluster->nvtx-1]=vtx; | |
| 31 | vtx->cluster=cluster; | |
| 32 | return TS_SUCCESS; | |
| 33 | } | |
| 34 | ||
| b4c13e | 35 | ts_bool cluster_list_compact(ts_cluster_list *cstlist){ |
| SP | 36 | |
| 37 | ||
| 38 | ts_uint i,n=cstlist->n; | |
| 39 | ||
| 40 | for(i=0;i<cstlist->n;i++){ | |
| 41 | if(cstlist->cluster[i]==NULL){ | |
| 8c91d2 | 42 | if(i>=n) break; |
| SP | 43 | //printf("Have to do compacting n=%d\n ",n); |
| b4c13e | 44 | do{ |
| SP | 45 | n--; |
| 46 | } while(cstlist->cluster[n]==NULL && n>i); | |
| 47 | cstlist->cluster[i]=cstlist->cluster[n]; | |
| 48 | cstlist->cluster[n]=NULL; | |
| 8c91d2 | 49 | //printf("After compacting n=%d\n",n); |
| b4c13e | 50 | } |
| SP | 51 | } |
| 52 | cstlist->cluster=(ts_cluster **)realloc(cstlist->cluster,n*sizeof(ts_cluster *)); | |
| c37ddc | 53 | cstlist->n=n; |
| b4c13e | 54 | return TS_SUCCESS; |
| SP | 55 | } |
| 56 | ||
| 57 | ||
| 8c91d2 | 58 | ts_bool cluster_join(ts_cluster_list *cstlist, ts_cluster *cluster1, ts_cluster *cluster2){ |
| b4c13e | 59 | ts_cluster *master_cluster,*slave_cluster; |
| SP | 60 | ts_uint i; |
| 61 | if(cluster1->idx<cluster2->idx){ | |
| 62 | master_cluster=cluster1; | |
| 63 | slave_cluster=cluster2; | |
| 64 | } else { | |
| 65 | master_cluster=cluster2; | |
| 66 | slave_cluster=cluster1; | |
| 67 | } | |
| 68 | for(i=0;i<slave_cluster->nvtx;i++){ | |
| 69 | cluster_add_vertex(master_cluster,slave_cluster->vtx[i]); | |
| 70 | } | |
| 8c91d2 | 71 | //find cluster in the list and free the location of the cluster |
| SP | 72 | for(i=0;i<cstlist->n;i++){ |
| 73 | if(cstlist->cluster[i]==slave_cluster){ | |
| 74 | cluster_free(slave_cluster); | |
| 75 | cstlist->cluster[i]=NULL; | |
| 76 | } | |
| 77 | } | |
| b4c13e | 78 | return TS_SUCCESS; |
| SP | 79 | } |
| 80 | ||
| 92b76b | 81 | ts_bool cluster_free(ts_cluster *cluster){ |
| SP | 82 | if(cluster!=NULL){ |
| 83 | if(cluster->vtx!=NULL) | |
| 84 | free(cluster->vtx); | |
| 85 | free(cluster); | |
| 86 | } | |
| 87 | return TS_SUCCESS; | |
| 88 | } | |
| 89 | ||
| 90 | ts_bool cluster_list_free(ts_cluster_list *cstlist){ | |
| 91 | ts_uint i; | |
| 92 | if(cstlist!=NULL){ | |
| 93 | for(i=0;i<cstlist->n;i++){ | |
| 94 | cluster_free(cstlist->cluster[i]); | |
| 95 | } | |
| b4c13e | 96 | free(cstlist->cluster); |
| 92b76b | 97 | free(cstlist); |
| SP | 98 | } |
| 99 | return TS_SUCCESS; | |
| 100 | } | |
| 101 | ||
| b4c13e | 102 | |
| SP | 103 | /* This is a stub function. User should check whether the vertex is clustering or not. */ |
| 104 | ts_bool is_clusterable(ts_vertex *vtx){ | |
| 62b11d | 105 | if(fabs(vtx->c)>1e-6){ |
| SP | 106 | return 1; |
| 107 | } | |
| 108 | else { | |
| 109 | return 0; | |
| 110 | } | |
| b4c13e | 111 | } |
| SP | 112 | |
| 113 | ||
| 114 | ts_cluster *cluster_vertex_neighbor(ts_vertex *vtx){ | |
| 115 | int j; | |
| 116 | for(j=0;j<vtx->neigh_no;j++){ | |
| 117 | if(vtx->neigh[j]->cluster!=NULL) | |
| 118 | return vtx->neigh[j]->cluster; | |
| 119 | } | |
| 120 | return NULL; | |
| 121 | } | |
| 122 | ||
| 8c91d2 | 123 | ts_bool cluster_vertex_neighbor_check(ts_cluster_list *cstlist, ts_vertex *vtx){ |
| b4c13e | 124 | |
| SP | 125 | int j; |
| 126 | for(j=0;j<vtx->neigh_no;j++){ | |
| 127 | if(vtx->neigh[j]->cluster!=NULL){ | |
| 128 | if(vtx->neigh[j]->cluster!=vtx->cluster){ | |
| 8c91d2 | 129 | cluster_join(cstlist, vtx->cluster, vtx->neigh[j]->cluster); |
| b4c13e | 130 | } |
| SP | 131 | } |
| 132 | } | |
| 133 | return TS_SUCCESS; | |
| 134 | } | |
| 135 | ||
| 136 | ||
| 137 | ts_bool clusterize_vesicle(ts_vesicle *vesicle, ts_cluster_list *cstlist){ | |
| 138 | ||
| 139 | int i; | |
| 140 | ts_vertex *vtx; | |
| 141 | ts_cluster *cst; | |
| 142 | for(i=0;i<vesicle->vlist->n;i++){ | |
| 143 | //for each vertex | |
| 144 | vtx=vesicle->vlist->vtx[i]; | |
| 145 | if(is_clusterable(vtx)){ | |
| 8c91d2 | 146 | if(vtx->cluster==NULL){ |
| b4c13e | 147 | //find first neigbor with cluster index |
| SP | 148 | cst=cluster_vertex_neighbor(vtx); |
| 149 | if(cst==NULL){ | |
| 150 | //no clusters are around us, vo we are probably lonely vertex or no surronding vertex has been mapped yet. | |
| 151 | cst=new_cluster(cstlist); | |
| 152 | cluster_add_vertex(cst,vtx); | |
| 153 | } else { | |
| 154 | //we are added to the first cluster found | |
| 155 | cluster_add_vertex(cst,vtx); | |
| 8c91d2 | 156 | cluster_vertex_neighbor_check(cstlist, vtx); |
| b4c13e | 157 | cluster_list_compact(cstlist); |
| SP | 158 | } |
| 159 | ||
| 160 | } | |
| 161 | } | |
| 162 | } | |
| 163 | ||
| 164 | ||
| 165 | return TS_SUCCESS; | |
| 166 | } | |
