17 #ifndef ORDERTREE_SLEP
18 #define ORDERTREE_SLEP
20 #define IGNORE_IN_CLASSLIST
50 #ifndef DOXYGEN_SHOULD_SKIP_THIS
74 struct NodeNum *firstNode;
75 struct NodeNum *lastNode;
116 void readFromFile(
char * FileName,
struct ChildrenNum ** TreeInfo,
int n){
118 struct ChildrenNum * treeInfo;
119 int i, j, num, nodeId;
122 fp=fopen(FileName,
"r");
125 printf(
"\n\n Fatal Error!!!");
126 printf(
"\n\n Failure in reading the file:%s!", FileName);
127 printf(
"\n\n The program does not check the correctness of the tree provided in the file: %s!", FileName);
131 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
134 printf(
"\n Allocation of treeInfo failure!");
139 treeInfo[i].children_num=0;
140 treeInfo[i].children=NULL;
147 if ( fscanf(fp,
"%d %d", &i, &num)!=2){
153 printf(
"\n For each row, it should has at least two numbers: nodeNum and number of children");
158 printf(
"\n The node number should be between [1, %d]!",n);
165 treeInfo[i].children_num=num;
167 treeInfo[i].children=(
int *)malloc(
sizeof(
int)*num);
169 if(!treeInfo[i].children){
170 printf(
"\n Allocation of treeInfo failure!");
175 if(!fscanf(fp,
"%d", &nodeId) ){
176 printf(
"\n This row should have %d children nodes!", num);
180 if (nodeId>n || nodeId<1){
181 printf(
"\n The node number should be between [1, %d]!", n);
185 treeInfo[i].children[j]=nodeId-1;
216 void buildTree(
struct Node* root,
struct ChildrenNum * treeInfo,
double *u){
219 struct Node * newNode;
220 struct NodeNum * currentNode;
221 int currentRoot=root->firstNode->node_num;
222 int numberOfChildren=treeInfo[currentRoot].children_num;
227 for(i=0;i<numberOfChildren;i++){
230 newNode=(
struct Node *)malloc(
sizeof(
struct Node));
231 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
234 printf(
"\n Allocation in buildTree failure!");
239 printf(
"\n Allocation in buildTree failure!");
245 newNode->m=u[treeInfo[currentRoot].children[i]];
249 currentNode->node_num=treeInfo[currentRoot].children[i];
250 currentNode->next=NULL;
251 newNode->firstNode=newNode->lastNode=currentNode;
257 newNode->brother=root->child;
276 void initializeRoot(
struct Node ** Root,
char * FileName,
double *u,
int rootNum,
int n){
278 struct NodeNum * currentNode;
280 struct ChildrenNum * treeInfo;
286 if(rootNum>n || rootNum <1){
287 printf(
"\n The node number of the root should be between [1, %d]!", n);
294 root=(
struct Node *)malloc(
sizeof(
struct Node));
295 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
298 printf(
"\n Allocation in computeGroups failure!");
303 printf(
"\n Allocation in computeGroups failure!");
311 root->brother=root->child=NULL;
313 currentNode->node_num=rootNum;
314 currentNode->next=NULL;
315 root->firstNode=root->lastNode=currentNode;
322 if (treeInfo[i].children_num)
323 free(treeInfo[i].children);
340 struct NodeNum * currentNode;
342 struct ChildrenNum * treeInfo;
356 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
358 printf(
"\n Allocation of treeInfo failure!");
363 treeInfo[i].children_num=2;
364 treeInfo[i].children=(
int *)malloc(
sizeof(
int)*2);
365 treeInfo[i].children[0]=2*i+1;
366 treeInfo[i].children[1]=2*i+2;
370 treeInfo[i].children_num=0;
371 treeInfo[i].children=NULL;
378 root=(
struct Node *)malloc(
sizeof(
struct Node));
379 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
382 printf(
"\n Allocation in computeGroups failure!");
387 printf(
"\n Allocation in computeGroups failure!");
395 root->brother=root->child=NULL;
397 currentNode->node_num=rootNum;
398 currentNode->next=NULL;
399 root->firstNode=root->lastNode=currentNode;
406 free(treeInfo[i].children);
422 struct NodeNum * currentNode;
424 struct ChildrenNum * treeInfo;
435 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
437 printf(
"\n Allocation of treeInfo failure!");
442 treeInfo[i].children_num=0;
443 treeInfo[i].children=NULL;
448 treeInfo[0].children_num=n-1;
449 treeInfo[0].children=(
int *)malloc(
sizeof(
int)*(n-1));
451 treeInfo[0].children[i-1]=i;
457 root=(
struct Node *)malloc(
sizeof(
struct Node));
458 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
461 printf(
"\n Allocation in computeGroups failure!");
466 printf(
"\n Allocation in computeGroups failure!");
474 root->brother=root->child=NULL;
476 currentNode->node_num=rootNum;
477 currentNode->next=NULL;
478 root->firstNode=root->lastNode=currentNode;
485 free(treeInfo[0].children);
496 void merge(
struct Node * root,
struct Node * maxNode ){
497 struct Node * childrenNode, *maxNodeChild;
499 root->m= (root->m* root->num + maxNode->m *maxNode->num)/(root->num + maxNode->num);
500 root->num+=maxNode->num;
501 root->lastNode->next=maxNode->firstNode;
502 root->lastNode=maxNode->lastNode;
508 if (root->child==maxNode){
509 root->child=maxNode->brother;
512 childrenNode=root->child;
514 while(childrenNode->brother!=maxNode){
515 childrenNode=childrenNode->brother;
518 childrenNode->brother=maxNode->brother;
525 maxNodeChild=maxNode->child;
529 while(maxNodeChild->brother)
530 maxNodeChild=maxNodeChild->brother;
533 maxNodeChild->brother=root->child;
534 root->child=maxNode->child;
552 struct Node * childrenNode, *maxNode;
569 childrenNode=root->child;
587 if (!childrenNode->flag)
590 if (childrenNode->m >= mean){
591 mean=childrenNode->m;
592 maxNode=childrenNode;
595 childrenNode=childrenNode->brother;
598 if ( (root->m <= 0) && (mean==0) ){
603 childrenNode=root->child;
605 merge(root, childrenNode);
606 childrenNode=root->child;
635 struct Node * childrenNode, *maxNode;
658 childrenNode=root->child;
684 if (!childrenNode->flag)
689 mean=childrenNode->m;
693 if (childrenNode->m >= mean){
694 mean=childrenNode->m;
695 maxNode=childrenNode;
698 childrenNode=childrenNode->brother;
721 struct NodeNum *currentNode;
733 currentNode=root->firstNode;
735 x[currentNode->node_num]=mean;
736 currentNode=currentNode->next;
744 child=child->brother;
756 struct NodeNum *currentNode;
759 printf(
"\n\n root->m =%2.5f, num:%d \n Nodes:",root->m,root->num);
761 currentNode=root->firstNode;
763 printf(
" %d ", currentNode->node_num);
764 currentNode=currentNode->next;
767 printf(
"\n root: %d, child:", root->m);
772 printf(
" %d", child->m);
773 child=child->brother;
781 child=child->brother;
795 struct Node *child, *temp;
796 struct NodeNum *currentNode;
819 currentNode=root->firstNode;
821 root->firstNode=currentNode->next;
824 currentNode=root->firstNode;
836 void orderTree(
double *x,
char * FileName,
double *u,
int rootNum,
int n){
void computeMaximalMean(struct Node *root)
void orderTree_without_nonnegative(double *x, char *FileName, double *u, int rootNum, int n)
void orderTreeBinary(double *x, double *u, int n)
void traversalTree(struct Node *root)
void orderTreeDepth1(double *x, double *u, int n)
void readFromFile(char *FileName, struct ChildrenNum **TreeInfo, int n)
#define IGNORE_IN_CLASSLIST
void initializeRoot(struct Node **Root, char *FileName, double *u, int rootNum, int n)
void initializeRootBinary(struct Node **Root, double *u, int n)
void computeMaximalMean_without_nonnegative(struct Node *root)
void orderTree(double *x, char *FileName, double *u, int rootNum, int n)
void buildTree(struct Node *root, struct ChildrenNum *treeInfo, double *u)
void merge(struct Node *root, struct Node *maxNode)
void initializeRootDepth1(struct Node **Root, double *u, int n)
void deleteTree(struct Node *root)
void computeSolution(double *x, struct Node *root)