18 #ifndef ORDERTREE_SLEP
19 #define ORDERTREE_SLEP
21 #define IGNORE_IN_CLASSLIST
52 #ifndef DOXYGEN_SHOULD_SKIP_THIS
76 struct NodeNum *firstNode;
77 struct NodeNum *lastNode;
118 void readFromFile(
char * FileName,
struct ChildrenNum ** TreeInfo,
int n){
120 struct ChildrenNum * treeInfo;
121 int i, j, num, nodeId;
124 fp=fopen(FileName,
"r");
127 printf(
"\n\n Fatal Error!!!");
128 printf(
"\n\n Failure in reading the file:%s!", FileName);
129 printf(
"\n\n The program does not check the correctness of the tree provided in the file: %s!", FileName);
133 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
136 printf(
"\n Allocation of treeInfo failure!");
141 treeInfo[i].children_num=0;
142 treeInfo[i].children=NULL;
149 if ( fscanf(fp,
"%d %d", &i, &num)!=2){
155 printf(
"\n For each row, it should has at least two numbers: nodeNum and number of children");
160 printf(
"\n The node number should be between [1, %d]!",n);
167 treeInfo[i].children_num=num;
169 treeInfo[i].children=(
int *)malloc(
sizeof(
int)*num);
171 if(!treeInfo[i].children){
172 printf(
"\n Allocation of treeInfo failure!");
177 if(!fscanf(fp,
"%d", &nodeId) ){
178 printf(
"\n This row should have %d children nodes!", num);
182 if (nodeId>n || nodeId<1){
183 printf(
"\n The node number should be between [1, %d]!", n);
187 treeInfo[i].children[j]=nodeId-1;
218 void buildTree(
struct Node* root,
struct ChildrenNum * treeInfo,
double *u){
221 struct Node * newNode;
222 struct NodeNum * currentNode;
223 int currentRoot=root->firstNode->node_num;
224 int numberOfChildren=treeInfo[currentRoot].children_num;
229 for(i=0;i<numberOfChildren;i++){
232 newNode=(
struct Node *)malloc(
sizeof(
struct Node));
233 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
236 printf(
"\n Allocation in buildTree failure!");
241 printf(
"\n Allocation in buildTree failure!");
247 newNode->m=u[treeInfo[currentRoot].children[i]];
251 currentNode->node_num=treeInfo[currentRoot].children[i];
252 currentNode->next=NULL;
253 newNode->firstNode=newNode->lastNode=currentNode;
259 newNode->brother=root->child;
267 buildTree(newNode, treeInfo, u);
278 void initializeRoot(
struct Node ** Root,
char * FileName,
double *u,
int rootNum,
int n){
280 struct NodeNum * currentNode;
282 struct ChildrenNum * treeInfo;
286 readFromFile(FileName, &treeInfo, n);
288 if(rootNum>n || rootNum <1){
289 printf(
"\n The node number of the root should be between [1, %d]!", n);
296 root=(
struct Node *)malloc(
sizeof(
struct Node));
297 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
300 printf(
"\n Allocation in computeGroups failure!");
305 printf(
"\n Allocation in computeGroups failure!");
313 root->brother=root->child=NULL;
315 currentNode->node_num=rootNum;
316 currentNode->next=NULL;
317 root->firstNode=root->lastNode=currentNode;
320 buildTree(root, treeInfo, u);
324 if (treeInfo[i].children_num)
325 free(treeInfo[i].children);
340 void initializeRootBinary(
struct Node ** Root,
double *u,
int n){
342 struct NodeNum * currentNode;
344 struct ChildrenNum * treeInfo;
358 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
360 printf(
"\n Allocation of treeInfo failure!");
365 treeInfo[i].children_num=2;
366 treeInfo[i].children=(
int *)malloc(
sizeof(
int)*2);
367 treeInfo[i].children[0]=2*i+1;
368 treeInfo[i].children[1]=2*i+2;
372 treeInfo[i].children_num=0;
373 treeInfo[i].children=NULL;
380 root=(
struct Node *)malloc(
sizeof(
struct Node));
381 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
384 printf(
"\n Allocation in computeGroups failure!");
389 printf(
"\n Allocation in computeGroups failure!");
397 root->brother=root->child=NULL;
399 currentNode->node_num=rootNum;
400 currentNode->next=NULL;
401 root->firstNode=root->lastNode=currentNode;
404 buildTree(root, treeInfo, u);
408 free(treeInfo[i].children);
422 void initializeRootDepth1(
struct Node ** Root,
double *u,
int n){
424 struct NodeNum * currentNode;
426 struct ChildrenNum * treeInfo;
437 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
439 printf(
"\n Allocation of treeInfo failure!");
444 treeInfo[i].children_num=0;
445 treeInfo[i].children=NULL;
450 treeInfo[0].children_num=n-1;
451 treeInfo[0].children=(
int *)malloc(
sizeof(
int)*(n-1));
453 treeInfo[0].children[i-1]=i;
459 root=(
struct Node *)malloc(
sizeof(
struct Node));
460 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
463 printf(
"\n Allocation in computeGroups failure!");
468 printf(
"\n Allocation in computeGroups failure!");
476 root->brother=root->child=NULL;
478 currentNode->node_num=rootNum;
479 currentNode->next=NULL;
480 root->firstNode=root->lastNode=currentNode;
483 buildTree(root, treeInfo, u);
487 free(treeInfo[0].children);
498 void merge(
struct Node * root,
struct Node * maxNode ){
499 struct Node * childrenNode, *maxNodeChild;
501 root->m= (root->m* root->num + maxNode->m *maxNode->num)/(root->num + maxNode->num);
502 root->num+=maxNode->num;
503 root->lastNode->next=maxNode->firstNode;
504 root->lastNode=maxNode->lastNode;
510 if (root->child==maxNode){
511 root->child=maxNode->brother;
514 childrenNode=root->child;
516 while(childrenNode->brother!=maxNode){
517 childrenNode=childrenNode->brother;
520 childrenNode->brother=maxNode->brother;
527 maxNodeChild=maxNode->child;
531 while(maxNodeChild->brother)
532 maxNodeChild=maxNodeChild->brother;
535 maxNodeChild->brother=root->child;
536 root->child=maxNode->child;
553 void computeMaximalMean(
struct Node * root){
554 struct Node * childrenNode, *maxNode;
571 childrenNode=root->child;
589 if (!childrenNode->flag)
590 computeMaximalMean(childrenNode);
592 if (childrenNode->m >= mean){
593 mean=childrenNode->m;
594 maxNode=childrenNode;
597 childrenNode=childrenNode->brother;
600 if ( (root->m <= 0) && (mean==0) ){
605 childrenNode=root->child;
607 merge(root, childrenNode);
608 childrenNode=root->child;
636 void computeMaximalMean_without_nonnegative(
struct Node * root){
637 struct Node * childrenNode, *maxNode;
660 childrenNode=root->child;
686 if (!childrenNode->flag)
687 computeMaximalMean_without_nonnegative(childrenNode);
691 mean=childrenNode->m;
695 if (childrenNode->m >= mean){
696 mean=childrenNode->m;
697 maxNode=childrenNode;
700 childrenNode=childrenNode->brother;
721 void computeSolution(
double *x,
struct Node *root){
723 struct NodeNum *currentNode;
735 currentNode=root->firstNode;
737 x[currentNode->node_num]=mean;
738 currentNode=currentNode->next;
744 computeSolution(x, child);
746 child=child->brother;
756 void traversalTree(
struct Node *root){
758 struct NodeNum *currentNode;
761 printf(
"\n\n root->m =%2.5f, num:%d \n Nodes:",root->m,root->num);
763 currentNode=root->firstNode;
765 printf(
" %d ", currentNode->node_num);
766 currentNode=currentNode->next;
769 printf(
"\n root: %d, child:", root->m);
774 printf(
" %d", child->m);
775 child=child->brother;
781 traversalTree(child);
783 child=child->brother;
796 void deleteTree(
struct Node *root){
797 struct Node *child, *temp;
798 struct NodeNum *currentNode;
821 currentNode=root->firstNode;
823 root->firstNode=currentNode->next;
826 currentNode=root->firstNode;
838 void orderTree(
double *x,
char * FileName,
double *u,
int rootNum,
int n){
844 initializeRoot(&root, FileName, u, rootNum, n);
856 computeMaximalMean(root);
861 computeSolution(x, root);
881 void orderTree_without_nonnegative(
double *x,
char * FileName,
double *u,
int rootNum,
int n){
887 initializeRoot(&root, FileName, u, rootNum, n);
899 computeMaximalMean_without_nonnegative(root);
904 computeSolution(x, root);
925 void orderTreeBinary(
double *x,
double *u,
int n){
935 initializeRootBinary(&root, u, n);
947 computeMaximalMean(root);
952 computeSolution(x, root);
972 void orderTreeDepth1(
double *x,
double *u,
int n){
980 initializeRootDepth1(&root, u, n);
992 computeMaximalMean(root);
997 computeSolution(x, root);
1010 #endif //USE_GPL_SHOGUN
#define IGNORE_IN_CLASSLIST