SHOGUN
v2.0.0
|
00001 /* This program is free software: you can redistribute it and/or modify 00002 * it under the terms of the GNU General Public License as published by 00003 * the Free Software Foundation, either version 3 of the License, or 00004 * (at your option) any later version. 00005 * 00006 * This program is distributed in the hope that it will be useful, 00007 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00008 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00009 * GNU General Public License for more details. 00010 * 00011 * You should have received a copy of the GNU General Public License 00012 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00013 * 00014 * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye 00015 */ 00016 00017 #ifndef ORDERTREE_SLEP 00018 #define ORDERTREE_SLEP 00019 00020 #define IGNORE_IN_CLASSLIST 00021 00022 #include <stdlib.h> 00023 #include <stdio.h> 00024 #include <time.h> 00025 #include <math.h> 00026 00027 00028 /* 00029 * In this file, we propose an O(n^2) algorithm for solving the problem: 00030 * 00031 * min 1/2 \|x - u\|^2 00032 * s.t. x_i \ge x_j \ge 0, (i,j) \in I, 00033 * 00034 * where I is the edge set of the tree 00035 * 00036 * 00037 */ 00038 00039 /* 00040 * Last updated on January, 21, 2011 00041 * 00042 * 1) the function merge is a non-recursive process for merging one tree with the other 00043 * 00044 * 2) we follow the writeup to revise the function computeMaximalMean 00045 * 00046 */ 00047 00048 #ifndef DOXYGEN_SHOULD_SKIP_THIS 00049 IGNORE_IN_CLASSLIST struct NodeNum 00050 { 00051 int node_num; 00052 struct NodeNum *next; 00053 }; 00054 00055 IGNORE_IN_CLASSLIST struct ChildrenNum 00056 { 00057 int children_num; 00058 int *children; 00059 }; 00060 00061 IGNORE_IN_CLASSLIST struct Node 00062 { 00063 int flag; /*if the maximal root-tree of the subtree rooted at this node has been computed, flag=1, otherwise 0*/ 00064 double m; /*During the computation, it stores the maximal mean from this node to (grandson) child node 00065 *The number of nodes on this path is stored in num 00066 * 00067 *It is intialized with the value of u(node_num) 00068 */ 00069 int num; /*the number of nodes, whose avarage gives the maximal mean---x*/ 00070 struct Node *brother; /*the pointer to the brother node(s)*/ 00071 struct Node *child; /*the pointer to the child node(s)*/ 00072 struct NodeNum *firstNode; /*the first node in the "maximal mean" group*/ 00073 struct NodeNum *lastNode; /*the last node in the "maximal mean" group*/ 00074 }; 00075 #endif 00076 00077 /* 00078 * We build a tree with the input from a file 00079 * 00080 * The file has n rows represented in the following format 00081 * 00082 | parent | number of children | children 00083 18 3 10 13 17 00084 10 3 5 8 9 00085 13 2 11 12 00086 17 3 13 14 15 00087 5 2 1 4 00088 8 2 6 7 00089 9 0 00090 11 0 00091 12 0 00092 14 0 00093 15 0 00094 16 0 00095 1 0 00096 4 2 2 3 00097 6 0 00098 7 0 00099 2 0 00100 3 0 00101 * 00102 * 00103 * Each row provides the information of one parent node and its children 00104 * 00105 * If a parent node is not included in any row, it is regarded that it is the leaf node. 00106 * For example, it is valid that the rows with zero children can be deleted. 00107 * 00108 * Node number is numbered from 1 to n, where n denotes the number of nodes. 00109 * 00110 * In the program, we deduct the number by 1, as C starts from 0, instead of 1. 00111 * 00112 */ 00113 00114 void readFromFile(char * FileName, struct ChildrenNum ** TreeInfo, int n){ 00115 FILE *fp; 00116 struct ChildrenNum * treeInfo; 00117 int i, j, num, nodeId; 00118 00119 00120 fp=fopen(FileName, "r"); 00121 00122 if(!fp){ 00123 printf("\n\n Fatal Error!!!"); 00124 printf("\n\n Failure in reading the file:%s!", FileName); 00125 printf("\n\n The program does not check the correctness of the tree provided in the file: %s!", FileName); 00126 return; 00127 } 00128 00129 treeInfo=(struct ChildrenNum *)malloc(sizeof(struct ChildrenNum)*n); 00130 00131 if(!treeInfo){ 00132 printf("\n Allocation of treeInfo failure!"); 00133 return; 00134 } 00135 00136 for(i=0;i<n;i++){ 00137 treeInfo[i].children_num=0; 00138 treeInfo[i].children=NULL; 00139 } 00140 00141 00142 while (!feof(fp)) { 00143 00144 i=-1;num=-1; 00145 if ( fscanf(fp, "%d %d", &i, &num)!=2){ 00146 00147 /*if this is due to extra spaces/breaks etc., we terminate reading the file */ 00148 if(feof(fp)) 00149 break; 00150 00151 printf("\n For each row, it should has at least two numbers: nodeNum and number of children"); 00152 return; 00153 } 00154 00155 if (i>n || i<1){ 00156 printf("\n The node number should be between [1, %d]!",n); 00157 return; 00158 } 00159 00160 i=i-1; 00161 /*i=i-1, as C starts from 0 instead of 1*/ 00162 if (num>0){ 00163 treeInfo[i].children_num=num; 00164 00165 treeInfo[i].children=(int *)malloc(sizeof(int)*num); 00166 00167 if(!treeInfo[i].children){ 00168 printf("\n Allocation of treeInfo failure!"); 00169 return; 00170 } 00171 00172 for(j=0;j<num;j++){ 00173 if(!fscanf(fp, "%d", &nodeId) ){ 00174 printf("\n This row should have %d children nodes!", num); 00175 return; 00176 } 00177 else{ 00178 if (nodeId>n || nodeId<1){ 00179 printf("\n The node number should be between [1, %d]!", n); 00180 return; 00181 } 00182 00183 treeInfo[i].children[j]=nodeId-1; 00184 /*add -1, as C starts from 0 instead of 1*/ 00185 } 00186 00187 } 00188 } 00189 } 00190 00191 fclose(fp); 00192 00193 /* 00194 printf("\n In readFromFile!"); 00195 for(i=0;i<n;i++){ 00196 printf("\n %d: %d:",i, treeInfo[i].children_num); 00197 00198 for(j=0;j<treeInfo[i].children_num;j++) 00199 printf(" %d", treeInfo[i].children[j]); 00200 } 00201 printf("\n Out of readFromFile!"); 00202 */ 00203 00204 00205 *TreeInfo=treeInfo;/*set value for TreeInfo*/ 00206 } 00207 00208 00209 /* 00210 * 00211 * We build the tree in a recursive manner 00212 * 00213 */ 00214 void buildTree(struct Node* root, struct ChildrenNum * treeInfo, double *u){ 00215 00216 00217 struct Node * newNode; 00218 struct NodeNum * currentNode; 00219 int currentRoot=root->firstNode->node_num; 00220 int numberOfChildren=treeInfo[currentRoot].children_num; 00221 int i; 00222 00223 /* insert the children nodes of the current root 00224 */ 00225 for(i=0;i<numberOfChildren;i++){ 00226 00227 00228 newNode=(struct Node *)malloc(sizeof(struct Node)); 00229 currentNode=(struct NodeNum *)malloc(sizeof(struct NodeNum)); 00230 00231 if(!newNode){ 00232 printf("\n Allocation in buildTree failure!"); 00233 return; 00234 } 00235 00236 if(!currentNode){ 00237 printf("\n Allocation in buildTree failure!"); 00238 return; 00239 } 00240 00241 00242 newNode->flag=0; 00243 newNode->m=u[treeInfo[currentRoot].children[i]]; 00244 newNode->num=1; 00245 newNode->child=NULL; 00246 00247 currentNode->node_num=treeInfo[currentRoot].children[i]; 00248 currentNode->next=NULL; 00249 newNode->firstNode=newNode->lastNode=currentNode; 00250 00251 /* 00252 * insert newnode to be the children nodes of root 00253 * 00254 */ 00255 newNode->brother=root->child; 00256 root->child=newNode; 00257 00258 /* 00259 * treat newNode as the root, and add its children 00260 * 00261 */ 00262 00263 buildTree(newNode, treeInfo, u); 00264 } 00265 } 00266 00267 /* 00268 * initilize the root, which means that the tree is built by this function. 00269 * as the root is the starting point of a tree 00270 * 00271 * we use the input file for building the tree 00272 */ 00273 00274 void initializeRoot(struct Node ** Root, char * FileName, double *u, int rootNum, int n){ 00275 00276 struct NodeNum * currentNode; 00277 struct Node *root; 00278 struct ChildrenNum * treeInfo; 00279 int i; 00280 00281 /*read the from the file to construct treeInfo*/ 00282 readFromFile(FileName, &treeInfo, n); 00283 00284 if(rootNum>n || rootNum <1){ 00285 printf("\n The node number of the root should be between [1, %d]!", n); 00286 return; 00287 } 00288 00289 rootNum=rootNum-1; 00290 /*add -1, as C starts from 0 instead of 1*/ 00291 00292 root=(struct Node *)malloc(sizeof(struct Node)); 00293 currentNode=(struct NodeNum *)malloc(sizeof(struct NodeNum)); 00294 00295 if(!root){ 00296 printf("\n Allocation in computeGroups failure!"); 00297 return; 00298 } 00299 00300 if(!currentNode){ 00301 printf("\n Allocation in computeGroups failure!"); 00302 return; 00303 } 00304 00305 00306 root->flag=0; 00307 root->m=u[rootNum]; 00308 root->num=1; 00309 root->brother=root->child=NULL; 00310 00311 currentNode->node_num=rootNum; 00312 currentNode->next=NULL; 00313 root->firstNode=root->lastNode=currentNode; 00314 00315 /*build the tree using buildTree*/ 00316 buildTree(root, treeInfo, u); 00317 00318 /*free treeInfo*/ 00319 for(i=0;i<n;i++){ 00320 if (treeInfo[i].children_num) 00321 free(treeInfo[i].children); 00322 } 00323 free(treeInfo); 00324 00325 *Root=root; 00326 } 00327 00328 00329 00330 /* 00331 * initilize the root for the full binary tree 00332 * 00333 * We do not need to give the input file, as binary tree is very special 00334 */ 00335 00336 void initializeRootBinary(struct Node ** Root, double *u, int n){ 00337 00338 struct NodeNum * currentNode; 00339 struct Node *root; 00340 struct ChildrenNum * treeInfo; 00341 int rootNum=1; 00342 int i, half=n/2; 00343 00344 /* 00345 * 00346 * readFromFile(FileName, &treeInfo, n); 00347 * 00348 * Replace the above function. 00349 * 00350 * we build treeInfo here directly using the special structure 00351 * 00352 */ 00353 00354 treeInfo=(struct ChildrenNum *)malloc(sizeof(struct ChildrenNum)*n); 00355 if(!treeInfo){ 00356 printf("\n Allocation of treeInfo failure!"); 00357 return; 00358 } 00359 00360 for(i=0;i<half;i++){ 00361 treeInfo[i].children_num=2; 00362 treeInfo[i].children=(int *)malloc(sizeof(int)*2); 00363 treeInfo[i].children[0]=2*i+1; 00364 treeInfo[i].children[1]=2*i+2; 00365 } 00366 00367 for(i=half;i<n;i++){ 00368 treeInfo[i].children_num=0; 00369 treeInfo[i].children=NULL; 00370 } 00371 00372 00373 rootNum=rootNum-1; 00374 /*add -1, as C starts from 0 instead of 1*/ 00375 00376 root=(struct Node *)malloc(sizeof(struct Node)); 00377 currentNode=(struct NodeNum *)malloc(sizeof(struct NodeNum)); 00378 00379 if(!root){ 00380 printf("\n Allocation in computeGroups failure!"); 00381 return; 00382 } 00383 00384 if(!currentNode){ 00385 printf("\n Allocation in computeGroups failure!"); 00386 return; 00387 } 00388 00389 00390 root->flag=0; 00391 root->m=u[rootNum]; 00392 root->num=1; 00393 root->brother=root->child=NULL; 00394 00395 currentNode->node_num=rootNum; 00396 currentNode->next=NULL; 00397 root->firstNode=root->lastNode=currentNode; 00398 00399 /*build the tree using buildTree*/ 00400 buildTree(root, treeInfo, u); 00401 00402 /*free treeInfo*/ 00403 for(i=0;i<half;i++){ 00404 free(treeInfo[i].children); 00405 } 00406 free(treeInfo); 00407 00408 *Root=root; 00409 } 00410 00411 00412 /* 00413 * initilize the root for the full binary tree 00414 * 00415 * We do not need to give the input file, as tree of depth 1 is very special 00416 */ 00417 00418 void initializeRootDepth1(struct Node ** Root, double *u, int n){ 00419 00420 struct NodeNum * currentNode; 00421 struct Node *root; 00422 struct ChildrenNum * treeInfo; 00423 int rootNum=1; 00424 int i; 00425 00426 /* 00427 * readFromFile(FileName, &treeInfo, n); 00428 * 00429 * we build treeInfo here, using the special structure of the tree with depth 1 00430 * 00431 */ 00432 00433 treeInfo=(struct ChildrenNum *)malloc(sizeof(struct ChildrenNum)*n); 00434 if(!treeInfo){ 00435 printf("\n Allocation of treeInfo failure!"); 00436 return; 00437 } 00438 00439 for(i=0;i<n;i++){ 00440 treeInfo[i].children_num=0; 00441 treeInfo[i].children=NULL; 00442 } 00443 00444 /*process the root*/ 00445 if (n>1){ 00446 treeInfo[0].children_num=n-1; 00447 treeInfo[0].children=(int *)malloc(sizeof(int)*(n-1)); 00448 for(i=1;i<n;i++) 00449 treeInfo[0].children[i-1]=i; 00450 } 00451 00452 rootNum=rootNum-1; 00453 /*add -1, as C starts from 0 instead of 1*/ 00454 00455 root=(struct Node *)malloc(sizeof(struct Node)); 00456 currentNode=(struct NodeNum *)malloc(sizeof(struct NodeNum)); 00457 00458 if(!root){ 00459 printf("\n Allocation in computeGroups failure!"); 00460 return; 00461 } 00462 00463 if(!currentNode){ 00464 printf("\n Allocation in computeGroups failure!"); 00465 return; 00466 } 00467 00468 00469 root->flag=0; 00470 root->m=u[rootNum]; 00471 root->num=1; 00472 root->brother=root->child=NULL; 00473 00474 currentNode->node_num=rootNum; 00475 currentNode->next=NULL; 00476 root->firstNode=root->lastNode=currentNode; 00477 00478 /*build the tree using buildTree*/ 00479 buildTree(root, treeInfo, u); 00480 00481 /*free treeInfo*/ 00482 if(n>1) 00483 free(treeInfo[0].children); 00484 free(treeInfo); 00485 00486 *Root=root; 00487 } 00488 00489 00490 00491 /* 00492 * merge root with maxNode 00493 */ 00494 void merge(struct Node * root, struct Node * maxNode ){ 00495 struct Node * childrenNode, *maxNodeChild; 00496 00497 root->m= (root->m* root->num + maxNode->m *maxNode->num)/(root->num + maxNode->num); 00498 root->num+=maxNode->num; 00499 root->lastNode->next=maxNode->firstNode; 00500 root->lastNode=maxNode->lastNode; 00501 00502 /* 00503 * update the brother list of maxNode (when removing maxNode) 00504 * 00505 */ 00506 if (root->child==maxNode){ 00507 root->child=maxNode->brother; 00508 } 00509 else{ 00510 childrenNode=root->child; 00511 00512 while(childrenNode->brother!=maxNode){ 00513 childrenNode=childrenNode->brother; 00514 } 00515 /*childrenNode's brother is maxNode*/ 00516 childrenNode->brother=maxNode->brother; 00517 } 00518 00519 00520 /* 00521 * change the children of maxNode to the children of root 00522 */ 00523 maxNodeChild=maxNode->child; 00524 if (maxNodeChild){ 00525 /*if maxNode has at least a child*/ 00526 00527 while(maxNodeChild->brother) 00528 maxNodeChild=maxNodeChild->brother; 00529 /*maxNodeChild points to the last child of maxNode*/ 00530 00531 maxNodeChild->brother=root->child; 00532 root->child=maxNode->child; 00533 } 00534 00535 /* 00536 * remove maxNode from the children list of root 00537 */ 00538 free(maxNode); 00539 00540 } 00541 00542 00543 00544 /* 00545 * compute the maximal mean for each node 00546 * 00547 */ 00548 00549 void computeMaximalMean(struct Node * root){ 00550 struct Node * childrenNode, *maxNode; 00551 double mean; 00552 00553 /*if root already points to a leaf node, we do nothing*/ 00554 if(!root->child){ 00555 00556 /*the value of a maximal root-tree is non-negative*/ 00557 if (root->m <0) 00558 root->m =0; 00559 00560 root->flag=1; 00561 return; 00562 } 00563 00564 /*the following loop corresponds to line 5-20 of the algorithm*/ 00565 while(1){ 00566 00567 childrenNode=root->child; 00568 if(!childrenNode){ 00569 00570 if (root->m <0) 00571 root->m =0; 00572 00573 root->flag=1; 00574 return; 00575 } 00576 00577 /*we note that, childrenNode->m >=0*/ 00578 00579 mean=0; 00580 00581 /*visit all its children nodes, to get the maximal "mean" and corresponding maxNode*/ 00582 while(childrenNode){ 00583 00584 /*if the maximal root-tree at childrenNode is not computed, we compute it*/ 00585 if (!childrenNode->flag) 00586 computeMaximalMean(childrenNode); 00587 00588 if (childrenNode->m >= mean){ 00589 mean=childrenNode->m; 00590 maxNode=childrenNode; 00591 } 00592 00593 childrenNode=childrenNode->brother; 00594 } 00595 00596 if ( (root->m <= 0) && (mean==0) ){ 00597 /* merge root with all its children, in this case, 00598 * its children is a super-node 00599 * (thus does not has any other children, due to merge)*/ 00600 00601 childrenNode=root->child; 00602 while(childrenNode){ 00603 merge(root, childrenNode); 00604 childrenNode=root->child; 00605 } 00606 00607 root->m =0; 00608 root->flag=1; 00609 return; 00610 } 00611 00612 if (root->m > mean){ 00613 00614 root->flag=1; 00615 return; 00616 } 00617 00618 merge(root,maxNode); 00619 } 00620 00621 } 00622 00623 00624 00625 /* 00626 * compute the maximal mean for each node, without the non-negative constraint 00627 * 00628 * Composed on November 23, 2011. 00629 * 00630 */ 00631 00632 void computeMaximalMean_without_nonnegative(struct Node * root){ 00633 struct Node * childrenNode, *maxNode; 00634 double mean; 00635 int mean_flag; 00636 00637 /*if root already points to a leaf node, we do nothing*/ 00638 if(!root->child){ 00639 00640 /*the value of a maximal root-tree is not necessarily non-negative, when the non-negative constraint is not imposed*/ 00641 00642 /* 00643 The following is removed 00644 if (root->m <0) 00645 root->m =0; 00646 */ 00647 00648 00649 root->flag=1; 00650 return; 00651 } 00652 00653 /*the following loop corresponds to line 5-20 of the algorithm */ 00654 while(1){ 00655 00656 childrenNode=root->child; 00657 if(!childrenNode){ 00658 00659 /*the value of a maximal root-tree is not necessarily non-negative, when the non-negative constraint is not imposed*/ 00660 00661 /* 00662 The following is removed 00663 00664 if (root->m <0) 00665 root->m =0; 00666 */ 00667 00668 root->flag=1; 00669 return; 00670 } 00671 00672 /*we note that, childrenNode->m >=0 does not necesarily hold. 00673 Therefore, for mean, we need to initialize with a small value. We initialize it with the value of its first child node 00674 */ 00675 00676 mean_flag=0; /*0 denotes that "mean" has not been really specified*/ 00677 00678 /*visit all its children nodes, to get the maximal "mean" and corresponding maxNode*/ 00679 while(childrenNode){ 00680 00681 /*if the maximal root-tree at childrenNode is not computed, we compute it*/ 00682 if (!childrenNode->flag) 00683 computeMaximalMean_without_nonnegative(childrenNode); 00684 00685 /*if mean has not been specified, let us specify it, and set mean_flag to 1*/ 00686 if (!mean_flag){ 00687 mean=childrenNode->m; 00688 mean_flag=1; 00689 } 00690 00691 if (childrenNode->m >= mean){ 00692 mean=childrenNode->m; 00693 maxNode=childrenNode; 00694 } 00695 00696 childrenNode=childrenNode->brother; 00697 } 00698 00699 if (root->m > mean){ 00700 00701 root->flag=1; 00702 return; 00703 } 00704 00705 merge(root,maxNode); 00706 } 00707 00708 } 00709 00710 00711 /* 00712 * computeSolution 00713 * 00714 */ 00715 00716 00717 void computeSolution(double *x, struct Node *root){ 00718 struct Node * child; 00719 struct NodeNum *currentNode; 00720 double mean; 00721 00722 if (root){ 00723 /* 00724 * process the root 00725 * 00726 * set the value for x 00727 */ 00728 00729 mean=root->m; 00730 00731 currentNode=root->firstNode; 00732 while(currentNode){ 00733 x[currentNode->node_num]=mean; 00734 currentNode=currentNode->next; 00735 } 00736 00737 /*process the children of root*/ 00738 child=root->child; 00739 while(child){ 00740 computeSolution(x, child); 00741 00742 child=child->brother; 00743 } 00744 } 00745 } 00746 00747 /* 00748 * traverse the tree 00749 * used for debugging the correctness of the code 00750 */ 00751 00752 void traversalTree(struct Node *root){ 00753 struct Node * child; 00754 struct NodeNum *currentNode; 00755 00756 if (root){ 00757 printf("\n\n root->m =%2.5f, num:%d \n Nodes:",root->m,root->num); 00758 00759 currentNode=root->firstNode; 00760 while(currentNode){ 00761 printf(" %d ", currentNode->node_num); 00762 currentNode=currentNode->next; 00763 } 00764 00765 printf("\n root: %d, child:", root->m); 00766 00767 /*print out the children of root*/ 00768 child=root->child; 00769 while(child){ 00770 printf(" %d", child->m); 00771 child=child->brother; 00772 } 00773 00774 /*print out the children of children*/ 00775 child=root->child; 00776 while(child){ 00777 traversalTree(child); 00778 00779 child=child->brother; 00780 } 00781 } 00782 } 00783 00784 00785 00786 00787 00788 /* 00789 * free the dynamic space generated by alloc 00790 */ 00791 00792 void deleteTree(struct Node *root){ 00793 struct Node *child, *temp; 00794 struct NodeNum *currentNode; 00795 00796 if (root){ 00797 00798 child=root->child; 00799 00800 while(child){ 00801 00802 temp=child->brother; 00803 /*point to its brother*/ 00804 00805 deleteTree(child); 00806 /*free its chlidren*/ 00807 00808 child=temp; 00809 } 00810 00811 /* 00812 * free root 00813 * 00814 * 1. free NodeNum pointed by firstNode and lastNode 00815 * 2. free Node 00816 */ 00817 currentNode=root->firstNode; 00818 while(currentNode){ 00819 root->firstNode=currentNode->next; 00820 free(currentNode); 00821 00822 currentNode=root->firstNode; 00823 } 00824 root->lastNode=NULL; 00825 free(root); 00826 } 00827 } 00828 00829 /* 00830 * This is the main function for the general tree 00831 * 00832 */ 00833 00834 void orderTree(double *x, char * FileName, double *u, int rootNum, int n){ 00835 struct Node * root; 00836 00837 /* 00838 * build the tree using initializeRoot 00839 */ 00840 initializeRoot(&root, FileName, u, rootNum, n); 00841 00842 /* 00843 printf("\n\n Before computation"); 00844 traversalTree(root); 00845 */ 00846 00847 00848 /* 00849 * compute the maximal average for each node 00850 */ 00851 00852 computeMaximalMean(root); 00853 00854 00855 /*compute the solution from the tree*/ 00856 00857 computeSolution(x, root); 00858 00859 00860 /* 00861 printf("\n\n After computation"); 00862 traversalTree(root); 00863 */ 00864 00865 00866 /* delete the tree 00867 */ 00868 deleteTree(root); 00869 } 00870 00871 00872 /* 00873 * This is the main function for the general tree, without the non-negative constraint 00874 * 00875 */ 00876 00877 void orderTree_without_nonnegative(double *x, char * FileName, double *u, int rootNum, int n){ 00878 struct Node * root; 00879 00880 /* 00881 * build the tree using initializeRoot 00882 */ 00883 initializeRoot(&root, FileName, u, rootNum, n); 00884 00885 /* 00886 printf("\n\n Before computation"); 00887 traversalTree(root); 00888 */ 00889 00890 00891 /* 00892 * compute the maximal average for each node 00893 */ 00894 00895 computeMaximalMean_without_nonnegative(root); 00896 00897 00898 /*compute the solution from the tree*/ 00899 00900 computeSolution(x, root); 00901 00902 00903 /* 00904 printf("\n\n After computation"); 00905 traversalTree(root); 00906 */ 00907 00908 00909 /* delete the tree 00910 */ 00911 deleteTree(root); 00912 } 00913 00914 00915 00916 /* 00917 * This is the main function for the full binary tree 00918 * 00919 */ 00920 00921 void orderTreeBinary(double *x, double *u, int n){ 00922 struct Node * root; 00923 00924 /* 00925 * build the tree using initializeRootBinary for the binary tree 00926 * 00927 * please make sure that n=2^{depth +1} -1 00928 * 00929 */ 00930 00931 initializeRootBinary(&root, u, n); 00932 00933 /* 00934 printf("\n\n Before computation"); 00935 traversalTree(root); 00936 */ 00937 00938 00939 /* 00940 * compute the maximal average for each node 00941 */ 00942 00943 computeMaximalMean(root); 00944 00945 00946 /*compute the solution from the tree*/ 00947 00948 computeSolution(x, root); 00949 00950 00951 /* 00952 printf("\n\n After computation"); 00953 traversalTree(root); 00954 */ 00955 00956 00957 /* delete the tree 00958 */ 00959 deleteTree(root); 00960 } 00961 00962 00963 /* 00964 * This is the main function for the tree with depth 1 00965 * 00966 */ 00967 00968 void orderTreeDepth1(double *x, double *u, int n){ 00969 struct Node * root; 00970 00971 /* 00972 * build the tree using initializeRootDepth1 for the tree with depth 1 00973 * 00974 */ 00975 00976 initializeRootDepth1(&root, u, n); 00977 00978 /* 00979 printf("\n\n Before computation"); 00980 traversalTree(root); 00981 */ 00982 00983 00984 /* 00985 * compute the maximal average for each node 00986 */ 00987 00988 computeMaximalMean(root); 00989 00990 00991 /*compute the solution from the tree*/ 00992 00993 computeSolution(x, root); 00994 00995 00996 /* 00997 printf("\n\n After computation"); 00998 traversalTree(root); 00999 */ 01000 01001 01002 /* delete the tree 01003 */ 01004 deleteTree(root); 01005 } 01006 #endif /* ----- #ifndef ORDERTREE_SLEP ----- */