17 #ifndef ORDERTREE_SLEP
18 #define ORDERTREE_SLEP
20 #define IGNORE_IN_CLASSLIST
48 #ifndef DOXYGEN_SHOULD_SKIP_THIS
72 struct NodeNum *firstNode;
73 struct NodeNum *lastNode;
114 void readFromFile(
char * FileName,
struct ChildrenNum ** TreeInfo,
int n){
116 struct ChildrenNum * treeInfo;
117 int i, j, num, nodeId;
120 fp=fopen(FileName,
"r");
123 printf(
"\n\n Fatal Error!!!");
124 printf(
"\n\n Failure in reading the file:%s!", FileName);
125 printf(
"\n\n The program does not check the correctness of the tree provided in the file: %s!", FileName);
129 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
132 printf(
"\n Allocation of treeInfo failure!");
137 treeInfo[i].children_num=0;
138 treeInfo[i].children=NULL;
145 if ( fscanf(fp,
"%d %d", &i, &num)!=2){
151 printf(
"\n For each row, it should has at least two numbers: nodeNum and number of children");
156 printf(
"\n The node number should be between [1, %d]!",n);
163 treeInfo[i].children_num=num;
165 treeInfo[i].children=(
int *)malloc(
sizeof(
int)*num);
167 if(!treeInfo[i].children){
168 printf(
"\n Allocation of treeInfo failure!");
173 if(!fscanf(fp,
"%d", &nodeId) ){
174 printf(
"\n This row should have %d children nodes!", num);
178 if (nodeId>n || nodeId<1){
179 printf(
"\n The node number should be between [1, %d]!", n);
183 treeInfo[i].children[j]=nodeId-1;
214 void buildTree(
struct Node* root,
struct ChildrenNum * treeInfo,
double *u){
217 struct Node * newNode;
218 struct NodeNum * currentNode;
219 int currentRoot=root->firstNode->node_num;
220 int numberOfChildren=treeInfo[currentRoot].children_num;
225 for(i=0;i<numberOfChildren;i++){
228 newNode=(
struct Node *)malloc(
sizeof(
struct Node));
229 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
232 printf(
"\n Allocation in buildTree failure!");
237 printf(
"\n Allocation in buildTree failure!");
243 newNode->m=u[treeInfo[currentRoot].children[i]];
247 currentNode->node_num=treeInfo[currentRoot].children[i];
248 currentNode->next=NULL;
249 newNode->firstNode=newNode->lastNode=currentNode;
255 newNode->brother=root->child;
274 void initializeRoot(
struct Node ** Root,
char * FileName,
double *u,
int rootNum,
int n){
276 struct NodeNum * currentNode;
278 struct ChildrenNum * treeInfo;
284 if(rootNum>n || rootNum <1){
285 printf(
"\n The node number of the root should be between [1, %d]!", n);
292 root=(
struct Node *)malloc(
sizeof(
struct Node));
293 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
296 printf(
"\n Allocation in computeGroups failure!");
301 printf(
"\n Allocation in computeGroups failure!");
309 root->brother=root->child=NULL;
311 currentNode->node_num=rootNum;
312 currentNode->next=NULL;
313 root->firstNode=root->lastNode=currentNode;
320 if (treeInfo[i].children_num)
321 free(treeInfo[i].children);
338 struct NodeNum * currentNode;
340 struct ChildrenNum * treeInfo;
354 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
356 printf(
"\n Allocation of treeInfo failure!");
361 treeInfo[i].children_num=2;
362 treeInfo[i].children=(
int *)malloc(
sizeof(
int)*2);
363 treeInfo[i].children[0]=2*i+1;
364 treeInfo[i].children[1]=2*i+2;
368 treeInfo[i].children_num=0;
369 treeInfo[i].children=NULL;
376 root=(
struct Node *)malloc(
sizeof(
struct Node));
377 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
380 printf(
"\n Allocation in computeGroups failure!");
385 printf(
"\n Allocation in computeGroups failure!");
393 root->brother=root->child=NULL;
395 currentNode->node_num=rootNum;
396 currentNode->next=NULL;
397 root->firstNode=root->lastNode=currentNode;
404 free(treeInfo[i].children);
420 struct NodeNum * currentNode;
422 struct ChildrenNum * treeInfo;
433 treeInfo=(
struct ChildrenNum *)malloc(
sizeof(
struct ChildrenNum)*n);
435 printf(
"\n Allocation of treeInfo failure!");
440 treeInfo[i].children_num=0;
441 treeInfo[i].children=NULL;
446 treeInfo[0].children_num=n-1;
447 treeInfo[0].children=(
int *)malloc(
sizeof(
int)*(n-1));
449 treeInfo[0].children[i-1]=i;
455 root=(
struct Node *)malloc(
sizeof(
struct Node));
456 currentNode=(
struct NodeNum *)malloc(
sizeof(
struct NodeNum));
459 printf(
"\n Allocation in computeGroups failure!");
464 printf(
"\n Allocation in computeGroups failure!");
472 root->brother=root->child=NULL;
474 currentNode->node_num=rootNum;
475 currentNode->next=NULL;
476 root->firstNode=root->lastNode=currentNode;
483 free(treeInfo[0].children);
494 void merge(
struct Node * root,
struct Node * maxNode ){
495 struct Node * childrenNode, *maxNodeChild;
497 root->m= (root->m* root->num + maxNode->m *maxNode->num)/(root->num + maxNode->num);
498 root->num+=maxNode->num;
499 root->lastNode->next=maxNode->firstNode;
500 root->lastNode=maxNode->lastNode;
506 if (root->child==maxNode){
507 root->child=maxNode->brother;
510 childrenNode=root->child;
512 while(childrenNode->brother!=maxNode){
513 childrenNode=childrenNode->brother;
516 childrenNode->brother=maxNode->brother;
523 maxNodeChild=maxNode->child;
527 while(maxNodeChild->brother)
528 maxNodeChild=maxNodeChild->brother;
531 maxNodeChild->brother=root->child;
532 root->child=maxNode->child;
550 struct Node * childrenNode, *maxNode;
567 childrenNode=root->child;
585 if (!childrenNode->flag)
588 if (childrenNode->m >= mean){
589 mean=childrenNode->m;
590 maxNode=childrenNode;
593 childrenNode=childrenNode->brother;
596 if ( (root->m <= 0) && (mean==0) ){
601 childrenNode=root->child;
603 merge(root, childrenNode);
604 childrenNode=root->child;
633 struct Node * childrenNode, *maxNode;
656 childrenNode=root->child;
682 if (!childrenNode->flag)
687 mean=childrenNode->m;
691 if (childrenNode->m >= mean){
692 mean=childrenNode->m;
693 maxNode=childrenNode;
696 childrenNode=childrenNode->brother;
719 struct NodeNum *currentNode;
731 currentNode=root->firstNode;
733 x[currentNode->node_num]=mean;
734 currentNode=currentNode->next;
742 child=child->brother;
754 struct NodeNum *currentNode;
757 printf(
"\n\n root->m =%2.5f, num:%d \n Nodes:",root->m,root->num);
759 currentNode=root->firstNode;
761 printf(
" %d ", currentNode->node_num);
762 currentNode=currentNode->next;
765 printf(
"\n root: %d, child:", root->m);
770 printf(
" %d", child->m);
771 child=child->brother;
779 child=child->brother;
793 struct Node *child, *temp;
794 struct NodeNum *currentNode;
817 currentNode=root->firstNode;
819 root->firstNode=currentNode->next;
822 currentNode=root->firstNode;
834 void orderTree(
double *x,
char * FileName,
double *u,
int rootNum,
int n){