Merge branch 'charm' of charmgit:charm into charm
[charm.git] / src / ck-ldb / tm_tree.c
1 #include <float.h>
2 #include "treematch.h"
3 #include <stdlib.h>
4 #include <stdio.h>
5 #include <math.h>
6 #include "treetimings.h"
7 #include "treebucket.h"
8 #include <assert.h>
9
10 #define MIN(a,b) ((a)<(b)?(a):(b))
11 #define MAX(a,b) ((a)>(b)?(a):(b))
12 #undef DEBUG
13
14
15 void free_list_child(tree_t *tree){
16   int i;
17   if(tree){
18     for(i=0;i<tree->arity;i++){
19       free_list_child(tree->child[i]);
20     }
21   }
22   free(tree->child);
23   if(tree->dumb)
24     free(tree);
25 }
26
27
28
29
30 void free_tab_child(tree_t *tree){
31   if(tree){
32     free_tab_child(tree->tab_child);
33     free(tree->tab_child);
34   }
35 }
36
37
38
39 void free_tree(tree_t *tree){
40
41   free_list_child(tree);
42   free_tab_child(tree);
43   free(tree);
44 }
45
46 long int choose (long n,long k){
47   // compute C_n_k
48   double res=1;
49   int i;
50   for(i=0;i<k;i++)
51     res*=(double)(n-i)/(double)(k-i);
52   
53   return (long int)res;
54 }
55
56 void set_node(tree_t *node,tree_t ** child, int arity,tree_t *parent,int id,double val,tree_t *tab_child){
57   static int uniq=0;
58   node->child=child;
59   node->arity=arity;
60   node->tab_child=NULL;
61   node->parent=parent;
62   node->id=id;
63   node->val=val;
64   node->uniq=uniq++;
65   node->dumb=0;
66 }
67
68 void display_node(tree_t *node){
69   printf("child : %p\narity : %d\nparent : %p\nid : %d\nval : %f\nuniq : %d\n\n" ,
70          node->child,node->arity,node->parent,node->id,node->val,node->uniq);
71 }
72 void clone_tree(tree_t *new,tree_t *old){
73   int i;
74   new->child=old->child;
75   new->arity=old->arity;
76   new->parent=old->parent;
77   //new->deb_tab_child=old->deb_tab_child;
78   new->id=old->id;
79   new->val=old->val;
80   new->uniq=old->uniq;
81   new->dumb=old->dumb;
82   for(i=0;i<new->arity;i++)
83     new->child[i]->parent=new;
84 }
85
86
87
88 double **aggregate_tab(tree_t *new_tab_node,double **tab,int N,int M){
89   int i,j,i1,j1,id1,id2;
90   double **res;
91     
92   res=(double**)malloc(M*sizeof(double*));
93   for(i=0;i<M;i++)
94     res[i]=(double*)malloc(M*sizeof(double));
95   
96   for(i=0;i<M;i++){
97     for(j=0;j<M;j++){
98       if(i==j)
99         res[i][j]=0;
100       else{
101         res[i][j]=0;
102         for(i1=0;i1<new_tab_node[i].arity;i1++){
103           id1=new_tab_node[i].child[i1]->id;
104           for(j1=0;j1<new_tab_node[j].arity;j1++){
105             id2=new_tab_node[j].child[j1]->id;
106             res[i][j]+=tab[id1][id2];
107             //printf("res[%d][%d]+=tab[%d][%d]=%f\n",i,j,id1,id2,tab[id1][id2]);
108           }
109         }
110       }
111     }
112   }
113   
114   return res;
115
116 }
117
118 void free_tab_double(double**tab,int N){
119   int i;
120   for(i=0;i<N;i++){
121     free(tab[i]);
122   }
123   free(tab);
124 }
125
126 void free_tab_int(int**tab,int N){
127   int i;
128   for(i=0;i<N;i++){
129     free(tab[i]);
130   }
131   free(tab);
132 }
133
134 void display_tab(double **tab,int N){
135   int i,j;
136   double line,total=0;;
137   for(i=0;i<N;i++){
138     line=0;
139     for(j=0;j<N;j++){
140       printf("%8.2f ",tab[i][j]);
141       line+=tab[i][j];
142     }
143     total+=line;
144     //printf(": %.2f",line);
145     printf("\n");
146   }
147   printf("Total: %.2f\n",total);
148 }
149
150
151 double eval_grouping(double **tab,tree_t **cur_group,int arity,int N){
152   double res=0;
153   int i,k,j,id,id1,id2;
154   //display_tab(tab,N);
155
156
157   for(i=0;i<arity;i++){
158     id=cur_group[i]->id;
159     //printf("%d ",id);
160     for(k=0;k<N;k++){
161       //printf("res+=tab[%d][%d]+tab[%d][%d]=%f+%f \n",k,id,id,k,tab[k][id],tab[id][k]);
162       res+=tab[k][id];
163     }
164   }
165   
166   for(i=0;i<arity;i++){
167     id1=cur_group[i]->id;
168     for(j=0;j<arity;j++){
169       id2=cur_group[j]->id;
170       //printf("res-=tab[%d][%d]=%f\n",id1,id2,tab[id1][id2]);
171       res-=tab[id1][id2];
172     }
173   }
174   //printf(" = %f\n",res);
175   return res;
176 }
177
178
179
180 group_list_t *new_group_list(tree_t **tab,double val,group_list_t *next){
181   group_list_t *res;
182   res=(group_list_t *)malloc(sizeof(group_list_t));
183   res->tab=tab;
184   res->val=val;
185   res->next=next;
186   res->sum_neighbour=0;
187   return res;
188 }
189
190
191 void add_to_list(group_list_t *list,tree_t **cur_group, int arity, double val){
192
193   group_list_t *elem;
194   int i;
195   tree_t **tab;
196   
197   tab=(tree_t **)malloc(sizeof(tree_t *)*arity);
198
199   for(i=0;i<arity;i++){
200     tab[i]=cur_group[i];
201     //printf("%d ",cur_group[i]->id);
202   }
203
204   //printf("\n");
205   elem=new_group_list(tab,val,list->next);
206   list->next=elem;
207   list->val++;
208 }
209
210
211
212 void  list_all_possible_groups(double **tab,tree_t *tab_node,int id,int arity, int depth,
213                                tree_t **cur_group,int N,group_list_t *list){
214   double val;
215   int i;
216
217
218
219   if(depth==arity){
220     val=eval_grouping(tab,cur_group,arity,N);
221     add_to_list(list,cur_group,arity,val);
222     return;
223     }else if(N+depth>=arity+id){
224     //}else if(1){
225     for(i=id;i<N;i++){
226       if(tab_node[i].parent)
227         continue;
228       cur_group[depth]=&tab_node[i];
229       //printf("%d<-%d\n",depth,i);
230       list_all_possible_groups(tab,tab_node,i+1,arity,depth+1,cur_group,N,list);
231     }
232   }
233 }
234
235
236 void update_val(double **tab,tree_t *parent,int N){
237   int i;
238
239   parent->val=eval_grouping(tab,parent->child,parent->arity,N);
240   //printf("connecting: ");
241   for(i=0;i<parent->arity;i++){
242     //printf("%d ",parent->child[i]->id);
243     /*  if(parent->child[i]->parent!=parent){
244       parent->child[i]->parent=parent;
245     }else{
246       fprintf(stderr,"redundant operation!\n");
247       exit(-1);
248       }*/
249   }
250
251
252   //printf(": %f\n",parent->val);
253 }
254
255
256 int independent_groups(group_list_t **selection,int d,group_list_t *elem,int arity){
257   int i,j,k;
258
259   if(d==0)
260     return 1;
261
262   for(i=0;i<arity;i++){
263     for(j=0;j<d;j++){
264       for(k=0;k<arity;k++){
265         if(elem->tab[i]->id==selection[j]->tab[k]->id)
266           return 0;
267       }
268     }
269   }
270   
271   return 1;
272
273
274 }
275
276 void display_selection (group_list_t** selection,int M,int arity,double val){
277   int i,j;
278   for(i=0;i<M;i++){
279     for(j=0;j<arity;j++)
280       printf("%d ",selection[i]->tab[j]->id);
281     printf("-- ");
282   }
283   printf(":%f\n",val); 
284
285 }
286
287 void display_grouping (tree_t *father,int M,int arity,double val){
288   int i,j;
289   for(i=0;i<M;i++){
290     for(j=0;j<arity;j++)
291       printf("%d ",father[i].child[j]->id);
292     printf("-- ");
293   }
294   printf(":%f\n",val); 
295
296 }
297
298
299 int recurs_select_independent_groups(group_list_t **tab,int i,int n,int arity,int d,int M,double val,double *best_val,group_list_t **selection,group_list_t **best_selection){
300   group_list_t *elem;
301
302   //if(val>=*best_val)
303   // return 0;
304
305   if(d==M){
306     //display_selection(selection,M,arity,val);
307     if(val<*best_val){
308       *best_val=val;
309       for(i=0;i<M;i++)
310         best_selection[i]=selection[i];
311       return 1;
312     }
313     return 0;
314   }
315   
316   while(i<n){
317     elem=tab[i];
318     if(independent_groups(selection,d,elem,arity)){
319       //printf("%d: %d\n",d,i);
320       selection[d]=elem;
321       val+=elem->val;
322       return recurs_select_independent_groups(tab,i+1,n,arity,d+1,M,val,best_val,selection,best_selection);
323     }
324     i++;
325   }
326   return 0;
327 }
328
329
330 int test_independent_groups(group_list_t **tab,int i,int n,int arity,int d,int M,double val,double *best_val,group_list_t **selection,group_list_t **best_selection){
331   group_list_t *elem;
332
333   if(d==M){
334     //display_selection(selection,M,arity,val);
335     return 1;
336   }
337   
338   while(i<n){
339     elem=tab[i];
340     if(independent_groups(selection,d,elem,arity)){
341       //printf("%d: %d\n",d,i);
342       selection[d]=elem;
343       val+=elem->val;
344       return recurs_select_independent_groups(tab,i+1,n,arity,d+1,M,val,best_val,selection,best_selection);
345     }
346     i++;
347   }
348   return 0;
349 }
350
351 void  delete_group_list(group_list_t *list){
352
353   if(list){
354     delete_group_list(list->next);
355     free(list->tab);
356     free(list);
357   }
358 }
359
360
361 int group_list_id(const void* x1,const void* x2){ 
362
363   group_list_t *e1,*e2;
364
365   e1=*((group_list_t**)x1);
366   e2=*((group_list_t**)x2);
367
368   
369   return e1->tab[0]->id<e2->tab[0]->id?-1:1;
370
371
372 int group_list_asc(const void* x1,const void* x2){ 
373
374   group_list_t *e1,*e2;
375
376   e1=*((group_list_t**)x1);
377   e2=*((group_list_t**)x2);
378
379   
380   return e1->val<e2->val?-1:1;
381
382
383
384 int group_list_dsc(const void* x1,const void* x2){ 
385
386   group_list_t *e1,*e2;
387
388   e1=*((group_list_t**)x1);
389   e2=*((group_list_t**)x2);
390
391   
392   return e1->val>e2->val?-1:1;
393
394
395
396 int weighted_degree_asc(const void* x1,const void* x2){ 
397
398   group_list_t *e1,*e2;
399
400   e1=*((group_list_t**)x1);
401   e2=*((group_list_t**)x2);
402
403   
404   return e1->wg>e2->wg?1:-1;
405
406
407
408 int weighted_degree_dsc(const void* x1,const void* x2){ 
409
410   group_list_t *e1,*e2;
411
412   e1=*((group_list_t**)x1);
413   e2=*((group_list_t**)x2);
414
415   
416   return e1->wg>e2->wg?-1:1;
417
418
419 int  select_independent_groups(group_list_t **tab_group,int n,int arity,int M,double *best_val,group_list_t **best_selection,int bound,double max_duration){
420   int i;
421   group_list_t **selection;
422   double val,duration;
423   CLOCK_T time1,time0;
424
425
426   selection=(group_list_t **)malloc(sizeof(group_list_t*)*M);
427   CLOCK(time0);
428   for(i=0;i<MIN(bound,n);i++){
429     selection[0]=tab_group[i];
430     val=tab_group[i]->val;
431     recurs_select_independent_groups(tab_group,i+1,n,arity,1,M,val,best_val,selection,best_selection);
432     if(i%5){
433       CLOCK(time1);
434       duration=CLOCK_DIFF(time1,time0);
435       if(duration>max_duration){
436         free(selection);
437         return 1;
438       }
439     }
440   }
441
442   free(selection);
443
444 #ifdef DEBUG
445   display_selection(best_selection,M,arity,*best_val);
446 #endif
447   return 0;
448 }
449
450 int  select_independent_groups_by_largest_index(group_list_t **tab_group,int n,int arity,int M,double *best_val,group_list_t **best_selection,int bound,double max_duration){
451   int i,nb_groups=0;
452   group_list_t **selection;
453   double val,duration;
454   int dec;
455   CLOCK_T time1,time0;
456
457   selection=(group_list_t **)malloc(sizeof(group_list_t*)*M);
458   CLOCK(time0);
459   
460   dec=MAX(n/10000,1);
461   for(i=n-1;i>=0;i-=dec*dec){
462     selection[0]=tab_group[i];
463     val=tab_group[i]->val;
464     nb_groups+=test_independent_groups(tab_group,i+1,n,arity,1,M,val,best_val,selection,best_selection);
465     //printf("%d:%d\n",i,nb_groups);
466     if(nb_groups>=bound){
467       free(selection);
468       return 0;
469     }
470     if(i%5){
471       CLOCK(time1);
472       duration=CLOCK_DIFF(time1,time0);
473       if(duration>max_duration){
474         free(selection);
475         return 1;
476       }
477     }
478   }
479
480   free(selection);
481   return 0;
482 }
483
484 void list_to_tab(group_list_t *list,group_list_t **tab,int n){
485   int i;
486   for(i=0;i<n;i++){
487     if(!list){
488       fprintf(stderr,"Error not enough elements. Only %d on %d\n",i,n);
489       exit(-1);
490     }
491     tab[n-i-1]=list;
492     list=list->next;
493   }
494   if(list){
495     fprintf(stderr,"Error too many elements\n");
496     exit(-1);
497   }
498 }
499
500 void display_tab_group(group_list_t **tab, int n,int arity){
501   int i,j;
502   for(i=0;i<n;i++){
503     for(j=0;j<arity;j++)
504       printf("%d ",tab[i]->tab[j]->id);
505     printf(": %.2f %.2f\n",tab[i]->val,tab[i]->wg);
506   }
507 }
508
509 int independent_tab(tree_t **tab1,tree_t **tab2,int n){
510   int i,j;
511   i=0;j=0;
512   while((i<n)&&(j<n)){
513     if(tab1[i]->id==tab2[j]->id)
514       return 0;
515     else if(tab1[i]->id>tab2[j]->id)
516       j++;
517     else
518       i++;
519   }
520   return 1;
521 }
522
523     
524
525 void compute_weighted_degree(group_list_t **tab, int n,int arity){
526   int i,j;
527   for(i=0;i<n;i++)
528     tab[i]->sum_neighbour=0;
529   for(i=0;i<n;i++){
530     //printf("%d/%d=%f%%\n",i,n,(100.0*i)/n);
531     for(j=i+1;j<n;j++){
532       //if(!independent_groups(&tab[i],1,tab[j],arity)){
533         if(!independent_tab(tab[i]->tab,tab[j]->tab,arity)){
534         tab[i]->sum_neighbour+=tab[j]->val;
535         tab[j]->sum_neighbour+=tab[i]->val;
536      }
537     }
538
539     tab[i]->wg=tab[i]->sum_neighbour/tab[i]->val;
540     if(tab[i]->sum_neighbour==0)
541       tab[i]->wg=0;
542     //printf("%d:%f/%f=%f\n",i,tab[i]->sum_neighbour,tab[i]->val,tab[i]->wg);
543   }
544 }
545
546
547 /*
548   Very slow: explore all possibilities
549   tab: comm_matrix at the considered level (used to evaluate a grouping)
550   tab_node: array of the node to group
551   parent: node to which attached the computed group
552   id: current considered node of tab_node
553   arity: number of children of parent (i.e.) size of the group to compute
554   best_val: current value of th grouping
555   cur_group: current grouping
556  */
557 void  group(double **tab,tree_t *tab_node,tree_t *parent,int id,int arity, int n,double *best_val,tree_t **cur_group,int N){
558   double val;
559   int i;
560
561
562   //if we have found enough noide in the group
563   if(n==arity){
564     // evaluate this group
565     val=eval_grouping(tab,cur_group,arity,N);
566     // If we improve compared to previous grouping: uodate the children of parent accordingly
567     if(val<*best_val){
568       *best_val=val;
569         for(i=0;i<arity;i++){
570           parent->child[i]=cur_group[i];
571         }
572       parent->arity=arity;
573     } 
574     return;
575   }
576   
577
578
579   // If we need more node in the group
580   // Continue to explore avilable nodes
581   for(i=id+1;i<N;i++){
582     // If this node is allready in a group: skip it
583     if(tab_node[i].parent)
584       continue;
585     //Otherwise, add it to the group at place n
586     cur_group[n]=&tab_node[i];
587     //printf("%d<-%d\n",n,i);
588     //recursively add the next element to this group
589     group(tab,tab_node,parent,i,arity,n+1,best_val,cur_group,N);
590   }
591 }
592
593 /*
594    tab: comm_matrix at the considered level (use to evaluate a grouping)
595   tab_node: array of the node to group
596   parent: node to which attached the computed group
597   id: current considered node of tab_node
598   arity: number of children of parent (i.e.) size of the group to compute
599   best_val: current value of th grouping
600   cur_group: current grouping
601   N: size of tab and tab_node. i.e. number of nodes at the considered level
602  */
603 void  fast_group(double **tab,tree_t *tab_node,tree_t *parent,int id,int arity, int n,
604                  double *best_val,tree_t **cur_group,int N, int *nb_groups,int max_groups){
605   double val;
606   int i;
607
608   //printf("Max groups=%d\n",max_groups);
609
610   //if we have found enough node in the group
611   if(n==arity){
612     (*nb_groups)++;
613     // evaluate this group
614     val=eval_grouping(tab,cur_group,arity,N);
615     // If we improve compared to previous grouping: uodate the children of parent accordingly
616     if(val<*best_val){
617       *best_val=val;
618         for(i=0;i<arity;i++){
619           parent->child[i]=cur_group[i];
620         }
621       parent->arity=arity;
622     } 
623     return;
624   }
625   
626
627
628   // If we need more node in the group
629   // Continue to explore avilable nodes
630   for(i=id+1;i<N;i++){
631     // If this node is allready in a group: skip it
632     if(tab_node[i].parent)
633       continue;
634     //Otherwise, add it to the group at place n
635     cur_group[n]=&tab_node[i];
636     //printf("%d<-%d %d/%d\n",n,i,*nb_groups,max_groups);
637     //exit(-1);
638     //recursively add the next element to this group
639     fast_group(tab,tab_node,parent,i,arity,n+1,best_val,cur_group,N,nb_groups,max_groups);
640     if(*nb_groups>max_groups)
641       return;
642   }
643 }
644
645
646
647
648 void fast_grouping(double **tab,tree_t *tab_node, tree_t *new_tab_node, int arity,int N, int M,long int k){
649   tree_t **cur_group;
650   int l,i;
651   double best_val,val=0;
652   int nb_groups;
653
654   cur_group=(tree_t**)malloc(sizeof(tree_t*)*arity);
655   for(l=0;l<M;l++){
656     best_val=DBL_MAX;
657     nb_groups=0;
658     //printf("k%d/%d, k=%ld\n",l,M,k);
659     /* select the best greedy grouping among the 10 first one*/
660     //fast_group(tab,tab_node,&new_tab_node[l],-1,arity,0,&best_val,cur_group,N,&nb_groups,MAX(2,(int)(50-log2(k))-M/10));
661     fast_group(tab,tab_node,&new_tab_node[l],-1,arity,0,&best_val,cur_group,N,&nb_groups,MAX(1,(int)(50-log2(k))-M/10));
662     val+=best_val;
663     for(i=0;i<new_tab_node[l].arity;i++){
664       new_tab_node[l].child[i]->parent=&new_tab_node[l];
665     }
666     update_val(tab,&new_tab_node[l],N);
667   }
668
669   free(cur_group);  
670
671   printf("val=%f\n",val);
672   //exit(-1);
673
674 #ifdef DEBUG
675   display_grouping(new_tab_node,M,arity,val);
676 #endif
677 }
678
679
680
681
682 int adjacency_asc(const void* x1,const void* x2){ 
683
684   adjacency_t *e1,*e2;
685
686   e1=((adjacency_t*)x1);
687   e2=((adjacency_t*)x2);
688
689   
690   return e1->val<e2->val?-1:1;
691
692
693
694 int adjacency_dsc(const void* x1,const void* x2){ 
695
696   adjacency_t *e1,*e2;
697
698   e1=((adjacency_t*)x1);
699   e2=((adjacency_t*)x2);
700
701   
702   return e1->val>e2->val?-1:1;
703
704 void super_fast_grouping(double **tab,tree_t *tab_node, tree_t *new_tab_node, int arity,int N, int M,int k){
705   double val=0;
706   adjacency_t *graph;
707   int i,j,e,l,nb_groups;
708   double duration;
709
710   assert(arity==2);
711
712   TIC;
713   graph=(adjacency_t*)malloc(sizeof(adjacency_t)*((N*N-N)/2));
714   e=0;
715   for(i=0;i<N;i++){
716     for(j=i+1;j<N;j++){
717       graph[e].i=i;
718       graph[e].j=j;
719       graph[e].val=tab[i][j];
720       e++;
721     }
722   }
723   duration=TOC;
724   printf("linearization=%fs\n",duration);
725   
726
727   assert(e==(N*N-N)/2);
728   TIC;  
729   qsort(graph,e,sizeof(adjacency_t),adjacency_dsc);
730   duration=TOC;
731   
732   printf("sorting=%fs\n",duration);
733
734   TIC;
735
736 TIC;
737   l=0;
738   nb_groups=0;
739   for(i=0;i<e&&l<M;i++){
740     if(try_add_edge(tab,tab_node,&new_tab_node[l],arity,graph[i].i,graph[i].j,N,&nb_groups)){
741       l++;
742     }
743   }
744
745   for(l=0;l<M;l++){
746     update_val(tab,&new_tab_node[l],N);      
747     val+=new_tab_node[l].val;
748   }
749
750   duration=TOC;
751   printf("Grouping=%fs\n",duration);
752
753   printf("val=%f\n",val);
754
755 #ifdef DEBUG
756   display_grouping(new_tab_node,M,arity,val);
757 #endif
758 }
759
760
761
762
763 /*
764   tab: comm_matrix at the considered level (use to evaluate a grouping)
765   tab_node: array of the node to group
766   new_tab_node: array of nodes at the next level (the parents of the node in tab_node once the grouping will be done). 
767   arity: number of children of parent (i.e.) size of the group to compute
768   N: size of tab and tab_node. i.e. number of nodes at the considered level
769   M: size of new_tab_node (i.e) the number of parents
770   Hence we have: M*arity=N
771  */void group_nodes(double **tab,tree_t *tab_node, tree_t *new_tab_node, int arity,int N, int M){
772   tree_t **cur_group;
773   int j,l,n;
774   group_list_t list,**best_selection,**tab_group;
775   double best_val,last_best;
776   int timeout;
777
778
779   long int k=choose(N,arity);
780   printf("Number of groups:%ld\n",k);
781   
782   if(k>30000){
783 #ifdef DEBUG
784     printf("Fast Grouping...\n");
785 #endif
786
787     double duration;
788     
789     TIC;
790     if(arity<=2){
791       bucket_grouping(tab,tab_node,new_tab_node,arity,N,M,k);
792     }else{
793       fast_grouping(tab,tab_node,new_tab_node,arity,N,M,k);
794     }
795     duration=TOC;
796
797     printf("Fast grouping duration=%f\n",duration);
798     
799     //exit(-1);
800   }else{
801 #ifdef DEBUG
802     printf("Grouping nodes...\n");
803 #endif
804     list.next=NULL;
805     list.val=0;//number of elements in the list
806     cur_group=(tree_t**)malloc(sizeof(tree_t*)*arity);
807     best_selection=(group_list_t **)malloc(sizeof(group_list_t*)*M);
808   
809     list_all_possible_groups(tab,tab_node,0,arity,0,cur_group,N,&list);
810     n=(int)list.val;
811     assert(n==k);
812     tab_group=(group_list_t**)malloc(sizeof(group_list_t)*n);
813     list_to_tab(list.next,tab_group,n);
814 #ifdef DEBUG
815     printf("List to tab done\n");
816 #endif
817     best_val=DBL_MAX;
818   
819     // perform the pack mapping fist
820     timeout=select_independent_groups(tab_group,n,arity,M,&best_val,best_selection,1,0.1);
821 #ifdef DEBUG
822     if(timeout){
823       printf("Packed mapping timeout!\n");
824     }
825 #endif
826     // give this mapping an exra credit (in general MPI application are made such that neighbour process communicates more than distant ones)
827     best_val/=1.001;
828 #ifdef DEBUG
829     printf("Packing computed\n");
830 #endif
831     // perform a mapping trying to use group that cost less first
832     qsort(tab_group,n,sizeof(group_list_t*),group_list_asc);
833     last_best=best_val;
834     timeout=select_independent_groups(tab_group,n,arity,M,&best_val,best_selection,10,0.1);
835 #ifdef DEBUG
836     if(timeout){
837       printf("Cost less first timeout!\n");
838     }else if(last_best>best_val){
839       printf("Cost less first Impoved solution\n");
840     }
841     printf("----\n");
842 #endif
843     // perform a mapping trying to minimize the use of groups that cost a lot 
844     qsort(tab_group,n,sizeof(group_list_t*),group_list_dsc);
845     last_best=best_val;
846     timeout=select_independent_groups_by_largest_index(tab_group,n,arity,M,&best_val,best_selection,10,0.1);
847 #ifdef DEBUG
848     if(timeout){
849       printf("Cost most last timeout!\n");
850     }else if(last_best>best_val){
851       printf("Cost most last impoved solution\n");
852     }
853 #endif
854     if(n<10000){
855       // perform a mapping in the weighted degree order 
856 #ifdef DEBUG
857       printf("----WG----\n");
858 #endif
859       compute_weighted_degree(tab_group,n,arity);
860 #ifdef DEBUG
861       printf("Weigted degree computed\n");
862 #endif
863       qsort(tab_group,n,sizeof(group_list_t*),weighted_degree_dsc);
864       //display_tab_group(tab_group,n,arity);
865       last_best=best_val;
866       timeout=select_independent_groups(tab_group,n,arity,M,&best_val,best_selection,10,0.1);
867 #ifdef DEBUG
868       if(timeout){
869         printf("WG timeout!\n");
870       }else if(last_best>best_val){
871         printf("WG impoved solution\n");
872       }
873 #endif
874     }
875     
876     qsort(best_selection,M,sizeof(group_list_t*),group_list_id);
877
878     for(l=0;l<M;l++){
879       for(j=0;j<arity;j++){
880         new_tab_node[l].child[j]=best_selection[l]->tab[j];
881         new_tab_node[l].child[j]->parent=&new_tab_node[l];
882       }
883       new_tab_node[l].arity=arity;
884     
885       //printf("arity=%d\n",new_tab_node[l].arity);
886       update_val(tab,&new_tab_node[l],N);
887     }
888     
889     delete_group_list((&list)->next);
890     free(best_selection);
891     free(tab_group);
892     free(cur_group);  
893   }
894
895   printf("Grouping done!\n");
896 }
897
898
899
900
901
902 void complete_tab(double ***tab,int N, int K){
903   double **old_tab,**new_tab;
904   int M,i,j;
905   if(K==0)
906     return;
907
908   old_tab=*tab;
909   
910   M=N+K;
911   new_tab=(double**)malloc(M*sizeof(double*));
912   for(i=0;i<M;i++)
913     new_tab[i]=(double*)malloc(M*sizeof(double));
914   
915   *tab=new_tab;
916   for(i=0;i<M;i++){
917     for(j=0;j<M;j++){
918       if((i<N)&&(j<N)){
919         new_tab[i][j]=old_tab[i][j];
920       }else{
921         new_tab[i][j]=0;
922       }
923     }
924   }
925 }
926
927 void create_dumb_tree(tree_t *node,int depth,tm_topology_t *topology){
928   tree_t **list_child;
929   int arity,i;
930
931   
932   if(depth==topology->nb_levels-1){
933     set_node(node,NULL,0,NULL,-1,0,NULL);  
934     return;
935   }
936
937   arity=topology->arity[depth];
938   assert(arity>0);
939   list_child=(tree_t**)calloc(arity,sizeof(tree_t*));
940   for(i=0;i<arity;i++){
941     list_child[i]=(tree_t*)malloc(sizeof(tree_t));
942     create_dumb_tree(list_child[i],depth+1,topology);
943     list_child[i]->parent=node;
944     list_child[i]->dumb=1;
945   }
946
947   set_node(node,list_child,arity,NULL,-1,0,list_child[0]);
948   
949 }
950
951 void complete_tab_node(tree_t **tab,int N, int K,int depth,tm_topology_t *topology){
952   tree_t *old_tab,*new_tab;
953   int M,i;
954   if(K==0)
955     return;
956
957   old_tab=*tab;
958   
959   M=N+K;
960   new_tab=(tree_t*)malloc(M*sizeof(tree_t));
961   
962   *tab=new_tab;
963   for(i=0;i<M;i++){
964     if((i<N)){
965       clone_tree(&new_tab[i],&old_tab[i]);
966     }else{
967       create_dumb_tree(&new_tab[i],depth,topology);
968       new_tab[i].id=i;
969     }
970   }
971
972   //do not suppress tab if you are at the depth-most level it will be used at the mapping stage
973   free(old_tab);  
974 }
975
976
977 void set_deb_tab_child(tree_t *tree, tree_t *child,int depth){
978   //printf("depth=%d\t%p\t%p\n",depth,child,tree);
979   if(depth>0)
980     set_deb_tab_child(tree->tab_child,child,depth-1);
981   else
982     tree->tab_child=child;
983 }
984
985
986
987 /* 
988 Build the tree of the matching. It is a bottom up algorithm: it starts from the bottom of the tree on proceed by decreasing the depth 
989 It groups nodes of the matrix tab and link these groups to the nodes of the under level. 
990 Then it calls recursivcely the function to prefrom the grouping at the above level. 
991
992 tab_node: array of nodes of the under level. 
993 tab: local communication matrix 
994 N: number of nodes.
995 arity: arity of the nodes of the above level.
996 depth: current depth of the algorithm
997 toplogy: description of the hardware topology.  
998 */
999 tree_t *build_level_topology(tree_t *tab_node,double **com_mat,int N,int arity,int depth,tm_topology_t *topology){
1000   int M; /*N/Arity: number the groups*/
1001   int K=0,i;
1002   tree_t *new_tab_node; /*array of node for this level (of size M): there will be linked to the nodes of tab_nodes*/
1003   double **new_com_mat; /*New communication matrix (after grouyping nodes together)*/
1004   tree_t *res; /*resulting tree*/
1005   int completed=0;
1006
1007   if((depth==0)){
1008     if((N==1)&&(depth==0))
1009       return &tab_node[0];
1010     else{
1011       fprintf(stderr,"Error: matrix size: %d and depth:%d (should be 1 and -1 respectively)\n",N,depth);
1012       exit(-1);
1013     }
1014   }
1015
1016   
1017   /* If the number of nodes does not devide teh aruty: we add K nodes  */
1018   if(N%arity!=0){
1019     K=arity*((N/arity)+1)-N;
1020     //printf("****N=%d arity=%d K=%d\n",N,arity,K);  
1021     //display_tab(tab,N);
1022     /* add K rows and columns to tab*/
1023     complete_tab(&com_mat,N,K);
1024     //display_tab(tab,N+K);
1025     /* add a dumb tree to the K new "virtual nodes"*/
1026     complete_tab_node(&tab_node,N,K,depth,topology);
1027     completed=1; /*flag this addition*/
1028     N+=K; /*increase the number of nodes accordingly*/
1029   } //display_tab(tab,N);
1030
1031
1032   M=N/arity;
1033   printf("Depth=%d\tnb_nodes=%d\tnb_groups=%d\tsize of groups(arity)=%d\n",depth,N,M,arity);
1034
1035   /*create the new nodes*/
1036   new_tab_node=(tree_t*)malloc(sizeof(tree_t)*M);
1037   /*intitialize each node*/
1038   for(i=0;i<M;i++){
1039     tree_t **list_child;
1040     list_child=(tree_t**)calloc(arity,sizeof(tree_t*));
1041     set_node(&new_tab_node[i],list_child,arity,NULL,i,0,tab_node);
1042   }
1043
1044   /*Core of the algorithm: perfrom the grouping*/
1045   group_nodes(com_mat,tab_node,new_tab_node,arity,N,M);
1046  
1047   /*based on that grouping aggregate the communication matrix*/
1048   new_com_mat=aggregate_tab(new_tab_node,com_mat,N,M);
1049
1050   /* set ID of virtual nodes to -1*/
1051   for(i=N-K;i<N;i++)
1052     tab_node[i].id=-1;
1053
1054   //for(i=0;i<N;i++)
1055   //  display_node(&tab_node[i]);
1056
1057   //display_tab(new_com_mat,M);
1058
1059   /* decrease depth and compute arity of the above level*/
1060   depth--;
1061   if(depth>0)
1062     arity = topology->arity[depth-1];
1063   else
1064     arity=1;
1065   // assume all objects have the same arity
1066   res = build_level_topology(new_tab_node,new_com_mat,M,arity,depth,topology);  
1067
1068   set_deb_tab_child(res,tab_node,depth);
1069
1070
1071   if(completed){
1072     free_tab_double(com_mat,N);
1073   }
1074   free_tab_double(new_com_mat,M);
1075
1076
1077   return res;
1078 }
1079
1080
1081
1082 double speed(int depth){
1083   // Bertha values
1084   //double tab[5]={21,9,4.5,2.5,0.001};
1085   //double tab[5]={1,1,1,1,1};
1086   //double tab[6]={100000,10000,1000,500,100,10};
1087   double tab[5]={100000,10000,1000,500,10};
1088     
1089   return 1.0/tab[depth];
1090   //return 10*log(depth+2);
1091   //return (depth+1);
1092   //return (long int)pow(100,depth);
1093 }
1094
1095 tree_t * build_tree_from_topology(tm_topology_t *topology,double **tab,int N){
1096   int depth,i; 
1097   tree_t *res,*tab_node;
1098
1099
1100   tab_node=(tree_t*)malloc(sizeof(tree_t)*N);
1101   for(i=0;i<N;i++)
1102     set_node(&tab_node[i],NULL,0,NULL,i,0,NULL); 
1103  
1104
1105   depth = topology->nb_levels -1;
1106   printf("nb_levels=%d\n",depth+1);
1107   // assume all objects have the same arity
1108   res = build_level_topology(tab_node,tab,N,topology->arity[depth-1],depth,topology);
1109   printf("Build tree done!\n");
1110   return res;
1111 }