| 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){ | |
| 42 | do{ | |
| 43 | n--; | |
| 44 | } while(cstlist->cluster[n]==NULL && n>i); | |
| 14779b | 45 | if(i<=n) break; |
| b4c13e | 46 | cstlist->cluster[i]=cstlist->cluster[n]; |
| SP | 47 | cstlist->cluster[n]=NULL; |
| 48 | } | |
| 49 | } | |
| 50 | cstlist->cluster=(ts_cluster **)realloc(cstlist->cluster,n*sizeof(ts_cluster *)); | |
| c37ddc | 51 | cstlist->n=n; |
| b4c13e | 52 | return TS_SUCCESS; |
| SP | 53 | } |
| 54 | ||
| 55 | ||
| 56 | ts_bool cluster_join(ts_cluster *cluster1, ts_cluster *cluster2){ | |
| 57 | ts_cluster *master_cluster,*slave_cluster; | |
| 58 | ts_uint i; | |
| 59 | if(cluster1->idx<cluster2->idx){ | |
| 60 | master_cluster=cluster1; | |
| 61 | slave_cluster=cluster2; | |
| 62 | } else { | |
| 63 | master_cluster=cluster2; | |
| 64 | slave_cluster=cluster1; | |
| 65 | } | |
| 66 | for(i=0;i<slave_cluster->nvtx;i++){ | |
| 67 | cluster_add_vertex(master_cluster,slave_cluster->vtx[i]); | |
| 68 | } | |
| 69 | cluster_free(slave_cluster); | |
| 70 | slave_cluster=NULL; | |
| 71 | return TS_SUCCESS; | |
| 72 | } | |
| 73 | ||
| 92b76b | 74 | ts_bool cluster_free(ts_cluster *cluster){ |
| SP | 75 | if(cluster!=NULL){ |
| 76 | if(cluster->vtx!=NULL) | |
| 77 | free(cluster->vtx); | |
| 78 | free(cluster); | |
| 79 | } | |
| 80 | return TS_SUCCESS; | |
| 81 | } | |
| 82 | ||
| 83 | ts_bool cluster_list_free(ts_cluster_list *cstlist){ | |
| 84 | ts_uint i; | |
| 85 | if(cstlist!=NULL){ | |
| 86 | for(i=0;i<cstlist->n;i++){ | |
| 87 | cluster_free(cstlist->cluster[i]); | |
| 88 | } | |
| b4c13e | 89 | free(cstlist->cluster); |
| 92b76b | 90 | free(cstlist); |
| SP | 91 | } |
| 92 | return TS_SUCCESS; | |
| 93 | } | |
| 94 | ||
| b4c13e | 95 | |
| SP | 96 | /* This is a stub function. User should check whether the vertex is clustering or not. */ |
| 97 | ts_bool is_clusterable(ts_vertex *vtx){ | |
| 98 | ||
| 99 | return 1; | |
| 100 | } | |
| 101 | ||
| 102 | ||
| 103 | ts_cluster *cluster_vertex_neighbor(ts_vertex *vtx){ | |
| 104 | int j; | |
| 105 | for(j=0;j<vtx->neigh_no;j++){ | |
| 106 | if(vtx->neigh[j]->cluster!=NULL) | |
| 107 | return vtx->neigh[j]->cluster; | |
| 108 | } | |
| 109 | return NULL; | |
| 110 | } | |
| 111 | ||
| 112 | ts_bool cluster_vertex_neighbor_check(ts_vertex *vtx){ | |
| 113 | ||
| 114 | int j; | |
| 115 | for(j=0;j<vtx->neigh_no;j++){ | |
| 116 | if(vtx->neigh[j]->cluster!=NULL){ | |
| 117 | if(vtx->neigh[j]->cluster!=vtx->cluster){ | |
| 118 | cluster_join(vtx->cluster, vtx->neigh[j]->cluster); | |
| 119 | } | |
| 120 | } | |
| 121 | } | |
| 122 | return TS_SUCCESS; | |
| 123 | } | |
| 124 | ||
| 125 | ||
| 126 | ts_bool clusterize_vesicle(ts_vesicle *vesicle, ts_cluster_list *cstlist){ | |
| 127 | ||
| 128 | int i; | |
| 129 | ts_vertex *vtx; | |
| 130 | ts_cluster *cst; | |
| 131 | for(i=0;i<vesicle->vlist->n;i++){ | |
| 132 | //for each vertex | |
| 133 | vtx=vesicle->vlist->vtx[i]; | |
| 134 | if(is_clusterable(vtx)){ | |
| 135 | if(vtx->cluster!=NULL){ | |
| 136 | //find first neigbor with cluster index | |
| 137 | cst=cluster_vertex_neighbor(vtx); | |
| 138 | if(cst==NULL){ | |
| 139 | //no clusters are around us, vo we are probably lonely vertex or no surronding vertex has been mapped yet. | |
| 140 | cst=new_cluster(cstlist); | |
| 141 | cluster_add_vertex(cst,vtx); | |
| 142 | } else { | |
| 143 | //we are added to the first cluster found | |
| 144 | cluster_add_vertex(cst,vtx); | |
| 145 | cluster_vertex_neighbor_check(vtx); | |
| 146 | cluster_list_compact(cstlist); | |
| 147 | } | |
| 148 | ||
| 149 | } | |
| 150 | } | |
| 151 | } | |
| 152 | ||
| 153 | ||
| 154 | return TS_SUCCESS; | |
| 155 | } | |
