1 /* Tree.h */ 2 3 #include "../cfiles.h" 4 #include "../IV.h" 5 #include "../DV.h" 6 7 /*--------------------------------------------------------------------*/ 8 /* 9 ----------------------- 10 simple tree object 11 12 created -- 95nov15, cca 13 ----------------------- 14 */ 15 typedef struct _Tree Tree ; 16 struct _Tree { 17 int n ; 18 int root ; 19 int *par ; 20 int *fch ; 21 int *sib ; 22 } ; 23 /*--------------------------------------------------------------------*/ 24 /* 25 ------------------------------------------------------------------------ 26 ----- methods found in basics.c ---------------------------------------- 27 ------------------------------------------------------------------------ 28 */ 29 /* 30 ----------------------------------------------- 31 purpose -- create and return a new Tree object 32 33 created -- 95nov15, cca 34 ----------------------------------------------- 35 */ 36 Tree * 37 Tree_new ( 38 void 39 ) ; 40 /* 41 ------------------------------------------------------ 42 purpose -- set the default fields for the Tree object 43 44 created -- 95nov15, cca 45 ------------------------------------------------------ 46 */ 47 void 48 Tree_setDefaultFields ( 49 Tree *tree 50 ) ; 51 /* 52 -------------------------------- 53 purpose -- clear the data fields 54 55 created -- 95nov15, cca 56 -------------------------------- 57 */ 58 void 59 Tree_clearData ( 60 Tree *tree 61 ) ; 62 /* 63 -------------------------------- 64 purpose -- free the Tree object 65 66 created -- 95nov15, cca 67 -------------------------------- 68 */ 69 void 70 Tree_free ( 71 Tree *tree 72 ) ; 73 /*--------------------------------------------------------------------*/ 74 /* 75 ------------------------------------------------------------------------ 76 ----- methods found in instance.c -------------------------------------- 77 ------------------------------------------------------------------------ 78 */ 79 /* 80 ------------------------------------------------- 81 purpose -- return the number of nodes in the tree 82 83 created -- 98jun12, cca 84 ------------------------------------------------- 85 */ 86 int 87 Tree_nnodes ( 88 Tree *tree 89 ) ; 90 /* 91 -------------------------------------- 92 purpose -- return the root of the tree 93 94 created -- 98jun12, cca 95 -------------------------------------- 96 */ 97 int 98 Tree_root ( 99 Tree *tree 100 ) ; 101 /* 102 ------------------------------------------------ 103 purpose -- return a pointer to the parent vector 104 105 created -- 98jun12, cca 106 ------------------------------------------------ 107 */ 108 int * 109 Tree_par ( 110 Tree *tree 111 ) ; 112 /* 113 ----------------------------------------------------- 114 purpose -- return a pointer to the first child vector 115 116 created -- 98jun12, cca 117 ----------------------------------------------------- 118 */ 119 int * 120 Tree_fch ( 121 Tree *tree 122 ) ; 123 /* 124 ------------------------------------------------- 125 purpose -- return a pointer to the sibling vector 126 127 created -- 98jun12, cca 128 ------------------------------------------------- 129 */ 130 int * 131 Tree_sib ( 132 Tree *tree 133 ) ; 134 /*--------------------------------------------------------------------*/ 135 /* 136 ------------------------------------------------------------------------ 137 ----- methods found in init.c ------------------------------------------ 138 ------------------------------------------------------------------------ 139 */ 140 /* 141 ----------------------- 142 simplest constructor 143 144 created -- 95nov15, cca 145 ----------------------- 146 */ 147 void 148 Tree_init1 ( 149 Tree *tree, 150 int size 151 ) ; 152 /* 153 -------------------------------- 154 initialize given a parent vector 155 156 created -- 95nov15, cca 157 -------------------------------- 158 */ 159 void 160 Tree_init2 ( 161 Tree *tree, 162 int size, 163 int par[] 164 ) ; 165 /* 166 --------------------------------- 167 initialize given the tree vectors 168 169 created -- 95nov15, cca 170 --------------------------------- 171 */ 172 void 173 Tree_init3 ( 174 Tree *tree, 175 int size, 176 int par[], 177 int fch[], 178 int sib[] 179 ) ; 180 /* 181 ------------------------------------ 182 set the fch[], sib[] and root fields 183 184 created -- 95nov15, cca 185 ------------------------------------ 186 */ 187 void 188 Tree_setFchSibRoot ( 189 Tree *tree 190 ) ; 191 /* 192 ----------------------- 193 set the root field 194 195 created -- 95nov15, cca 196 ----------------------- 197 */ 198 void 199 Tree_setRoot ( 200 Tree *tree 201 ) ; 202 /*--------------------------------------------------------------------*/ 203 /* 204 ------------------------------------------------------------------------ 205 ----- methods found in maximizeGain.c ---------------------------------- 206 ------------------------------------------------------------------------ 207 */ 208 /* 209 ------------------------------------------------------- 210 purpose -- 211 212 given a gain value assigned to each node, 213 find a set of nodes, no two in a child-ancestor 214 relationship, that maximizes the total gain. 215 216 this problem arises in finding the optimal domain/schur 217 complement partition for a semi-implicit factorization. 218 219 created -- 98jun20, cca 220 ------------------------------------------------------- 221 */ 222 IV * 223 Tree_maximizeGainIV ( 224 Tree *tree, 225 IV *gainIV, 226 int *ptotalgain, 227 int msglvl, 228 FILE *msgFile 229 ) ; 230 /*--------------------------------------------------------------------*/ 231 /* 232 ------------------------------------------------------------------------ 233 ----- methods found in subtree.c --------------------------------------- 234 ------------------------------------------------------------------------ 235 */ 236 /* 237 ------------------------------------------------- 238 purpose -- to initialize subtree with the subtree 239 of tree using nodes in nodeidsIV 240 241 return values --- 242 1 -- normal return 243 -1 -- subtree is NULL 244 -2 -- nodeidsIV is NULL 245 -3 -- tree is NULL 246 -4 -- nodeidsIV is invalid 247 248 created -- 98oct15, cca 249 ------------------------------------------------- 250 */ 251 int 252 Tree_initFromSubtree ( 253 Tree *subtree, 254 IV *nodeidsIV, 255 Tree *tree 256 ) ; 257 /*--------------------------------------------------------------------*/ 258 /* 259 ------------------------------------------------------------------------ 260 ----- methods found in util.c ------------------------------------------ 261 ------------------------------------------------------------------------ 262 */ 263 /* 264 ------------------------------------------------- 265 return the first vertex in a post-order traversal 266 267 created -- 95nov15, cca 268 ------------------------------------------------- 269 */ 270 int 271 Tree_postOTfirst ( 272 Tree *tree 273 ) ; 274 /* 275 ---------------------------------------------------------- 276 return the vertex that follows v in a post-order traversal 277 ---------------------------------------------------------- 278 */ 279 int 280 Tree_postOTnext ( 281 Tree *tree, 282 int v 283 ) ; 284 /* 285 ------------------------------------------------ 286 return the first vertex in a pre-order traversal 287 288 created -- 95nov15, cca 289 ------------------------------------------------ 290 */ 291 int 292 Tree_preOTfirst ( 293 Tree *tree 294 ) ; 295 /* 296 --------------------------------------------------------- 297 return the vertex that follows v in a pre-order traversal 298 299 created -- 95nov15, cca 300 --------------------------------------------------------- 301 */ 302 int 303 Tree_preOTnext ( 304 Tree *tree, 305 int v 306 ) ; 307 /* 308 --------------------------------------- 309 return the number of leaves in the tree 310 311 created -- 95nov15, cca 312 --------------------------------------- 313 */ 314 int 315 Tree_nleaves ( 316 Tree *tree 317 ) ; 318 /* 319 ----------------------------------------------- 320 return the number of roots of the tree (forest) 321 322 created -- 95nov15, cca 323 ----------------------------------------------- 324 */ 325 int 326 Tree_nroots ( 327 Tree *tree 328 ) ; 329 /* 330 ----------------------------------------- 331 return the number of children of a vertex 332 333 created -- 95nov15, cca 334 ----------------------------------------- 335 */ 336 int 337 Tree_nchild ( 338 Tree *tree, 339 int v 340 ) ; 341 /* 342 ------------------------------------------- 343 this method returns an IV object that holds 344 the number of children for the tree nodes. 345 346 created -- 96dec18, cca 347 ------------------------------------------- 348 */ 349 IV * 350 Tree_nchildIV ( 351 Tree *tree 352 ) ; 353 /* 354 ----------------------------- 355 return the height of the tree 356 357 created -- 96aug23, cca 358 ----------------------------- 359 */ 360 int 361 Tree_height ( 362 Tree *tree 363 ) ; 364 /* 365 ------------------------------------------------------------- 366 return the maximum number of children of any node in the tree 367 368 created -- 96sep05, cca 369 ------------------------------------------------------------- 370 */ 371 int 372 Tree_maxNchild ( 373 Tree *tree 374 ) ; 375 /* 376 --------------------------------------------- 377 return the number of bytes used by the object 378 --------------------------------------------- 379 */ 380 int 381 Tree_sizeOf ( 382 Tree *tree 383 ) ; 384 /*--------------------------------------------------------------------*/ 385 /* 386 ------------------------------------------------------------------------ 387 ----- methods found in metrics.c --------------------------------------- 388 ------------------------------------------------------------------------ 389 */ 390 /* 391 ------------------------------------------------------ 392 create and return a subtree metric IV object 393 input : vmetricIV -- a metric defined on the vertices 394 return : tmetricIV -- a metric defined on the subtrees 395 396 created -- 96jun23, cca 397 ------------------------------------------------------ 398 */ 399 IV * 400 Tree_setSubtreeImetric ( 401 Tree *tree, 402 IV *vmetricIV 403 ) ; 404 /* 405 ------------------------------------------------------ 406 create and return a subtree metric DV object 407 input : vmetricDV -- a metric defined on the vertices 408 return : tmetricDV -- a metric defined on the subtrees 409 410 created -- 96jun23, cca 411 ------------------------------------------------------ 412 */ 413 DV * 414 Tree_setSubtreeDmetric ( 415 Tree *tree, 416 DV *vmetricDV 417 ) ; 418 /* 419 ------------------------------------------------------------ 420 create and return a depth metric IV object 421 input : vmetricIV -- a metric defined on the vertices 422 output : dmetric[] -- a depth metric defined on the vertices 423 424 dmetric[u] = vmetric[u] + dmetric[par[u]] if par[u] != -1 425 = vmetric[u] if par[u] == -1 426 427 created -- 96jun23, cca 428 ------------------------------------------------------------ 429 */ 430 IV * 431 Tree_setDepthImetric ( 432 Tree *tree, 433 IV *vmetricIV 434 ) ; 435 /* 436 ------------------------------------------------------------ 437 create and return a depth metric DV object 438 input : vmetricDV -- a metric defined on the vertices 439 output : dmetric[] -- a depth metric defined on the vertices 440 441 dmetric[u] = vmetric[u] + dmetric[par[u]] if par[u] != -1 442 = vmetric[u] if par[u] == -1 443 444 created -- 96jun23, cca 445 ------------------------------------------------------------ 446 */ 447 DV * 448 Tree_setDepthDmetric ( 449 Tree *tree, 450 DV *vmetricDV 451 ) ; 452 /* 453 ------------------------------------------------------------------ 454 create and return a height metric IV object 455 input : vmetricIV -- a metric defined on the vertices 456 output : dmetricIV -- a depth metric defined on the vertices 457 458 hmetric[v] = vmetric[v] + max{p(u) = v} hmetric[u] if fch[v] != -1 459 = vmetric[v] if fch[v] == -1 460 461 created -- 96jun23, cca 462 ------------------------------------------------------------------ 463 */ 464 IV * 465 Tree_setHeightImetric ( 466 Tree *tree, 467 IV *vmetricIV 468 ) ; 469 /* 470 ------------------------------------------------------------------ 471 create and return a height metric DV object 472 input : vmetricDV -- a metric defined on the vertices 473 output : dmetricDV -- a depth metric defined on the vertices 474 475 hmetric[v] = vmetric[v] + max{p(u) = v} hmetric[u] if fch[v] != -1 476 = vmetric[v] if fch[v] == -1 477 478 created -- 96jun23, cca 479 ------------------------------------------------------------------ 480 */ 481 DV * 482 Tree_setHeightDmetric ( 483 Tree *tree, 484 DV *vmetricDV 485 ) ; 486 /*--------------------------------------------------------------------*/ 487 /* 488 ------------------------------------------------------------------------ 489 ----- methods found in justify.c --------------------------------------- 490 ------------------------------------------------------------------------ 491 */ 492 /* 493 ------------------------------------------------------------ 494 left-justify a tree by subtree size 495 children are linked in ascending order of their subtree size 496 497 created -- 95nov15, cca 498 ------------------------------------------------------------ 499 */ 500 void 501 Tree_leftJustify ( 502 Tree *tree 503 ) ; 504 /* 505 ------------------------------------------------------ 506 left-justify a tree by a metric 507 children are linked in ascending order of their metric 508 509 created -- 96jun23, cca 510 ------------------------------------------------------ 511 */ 512 void 513 Tree_leftJustifyI ( 514 Tree *tree, 515 IV *metricIV 516 ) ; 517 /* 518 ------------------------------------------------------ 519 left-justify a tree by a metric 520 children are linked in ascending order of their metric 521 522 created -- 96jun23, cca 523 ------------------------------------------------------ 524 */ 525 void 526 Tree_leftJustifyD ( 527 Tree *tree, 528 DV *metricDV 529 ) ; 530 /*--------------------------------------------------------------------*/ 531 /* 532 ------------------------------------------------------------------------ 533 ----- methods found in perms.c ----------------------------------------- 534 ------------------------------------------------------------------------ 535 */ 536 /* 537 -------------------------------------- 538 fill the new-to-old permutation vector 539 540 created -- 95nov15, cca 541 -------------------------------------- 542 */ 543 void 544 Tree_fillNewToOldPerm ( 545 Tree *tree, 546 int newToOld[] 547 ) ; 548 /* 549 -------------------------------------- 550 fill the old-to-new permutation vector 551 552 created -- 95nov15, cca 553 -------------------------------------- 554 */ 555 void 556 Tree_fillOldToNewPerm ( 557 Tree *tree, 558 int oldToNew[] 559 ) ; 560 /* 561 ------------------------------------------------------ 562 fill the new-to-old and old-to-new permutation vectors 563 564 created -- 95nov15, cca 565 ------------------------------------------------------ 566 */ 567 void 568 Tree_fillBothPerms ( 569 Tree *tree, 570 int newToOld[], 571 int oldToNew[] 572 ) ; 573 /*--------------------------------------------------------------------*/ 574 /* 575 ------------------------------------------------------------------------ 576 ----- methods found in IO.c -------------------------------------------- 577 ------------------------------------------------------------------------ 578 */ 579 /* 580 ------------------------------------------------ 581 purpose -- to read in an Tree object from a file 582 583 input -- 584 585 fn -- filename, must be *.treeb or *.treef 586 587 return value -- 1 if success, 0 if failure 588 589 created -- 95nov15, cca 590 ------------------------------------------------ 591 */ 592 int 593 Tree_readFromFile ( 594 Tree *tree, 595 char *fn 596 ) ; 597 /* 598 ------------------------------------------------------- 599 purpose -- to read an Tree object from a formatted file 600 601 return value -- 1 if success, 0 if failure 602 603 created -- 95nov15, cca 604 ------------------------------------------------------- 605 */ 606 int 607 Tree_readFromFormattedFile ( 608 Tree *tree, 609 FILE *fp 610 ) ; 611 /* 612 --------------------------------------------------- 613 purpose -- to read an Tree object from a binary file 614 615 return value -- 1 if success, 0 if failure 616 617 created -- 95nov15, cca 618 --------------------------------------------------- 619 */ 620 int 621 Tree_readFromBinaryFile ( 622 Tree *tree, 623 FILE *fp 624 ) ; 625 /* 626 -------------------------------------------- 627 purpose -- to write an Tree object to a file 628 629 input -- 630 631 fn -- filename 632 *.treeb -- binary 633 *.treef -- formatted 634 anything else -- for human eye 635 636 return value -- 1 if success, 0 otherwise 637 638 created -- 95nov15, cca 639 -------------------------------------------- 640 */ 641 int 642 Tree_writeToFile ( 643 Tree *tree, 644 char *fn 645 ) ; 646 /*--------------------------------------------------------------------*/ 647 /* 648 ------------------------------------------------------ 649 purpose -- to write an Tree object to a formatted file 650 651 return value -- 1 if success, 0 otherwise 652 653 created -- 95nov15, cca 654 ------------------------------------------------------ 655 */ 656 int 657 Tree_writeToFormattedFile ( 658 Tree *tree, 659 FILE *fp 660 ) ; 661 /* 662 --------------------------------------------------- 663 purpose -- to write an Tree object to a binary file 664 665 return value -- 1 if success, 0 otherwise 666 667 created -- 95nov15, cca 668 --------------------------------------------------- 669 */ 670 int 671 Tree_writeToBinaryFile ( 672 Tree *tree, 673 FILE *fp 674 ) ; 675 /* 676 -------------------------------------------------- 677 purpose -- to write an Tree object for a human eye 678 679 return value -- 1 if success, 0 otherwise 680 681 created -- 95nov15, cca 682 -------------------------------------------------- 683 */ 684 int 685 Tree_writeForHumanEye ( 686 Tree *tree, 687 FILE *fp 688 ) ; 689 /* 690 ---------------------------------------------------------- 691 purpose -- to write out the statistics for the Tree object 692 693 return value -- 1 if success, 0 otherwise 694 695 created -- 95nov15, cca 696 ---------------------------------------------------------- 697 */ 698 int 699 Tree_writeStats ( 700 Tree *tree, 701 FILE *fp 702 ) ; 703 /*--------------------------------------------------------------------*/ 704 /* 705 ------------------------------------------------------------------------ 706 ----- methods found in compress.c -------------------------------------- 707 ------------------------------------------------------------------------ 708 */ 709 /* 710 -------------------------------------------- 711 create and return an IV object that contains 712 the map from vertices to fundamental chains. 713 714 return value -- # of fundamental chains 715 716 created -- 96jun23, cca 717 ------------------------------------------- 718 */ 719 IV * 720 Tree_fundChainMap ( 721 Tree *tree 722 ) ; 723 /* 724 ----------------------------------------------------------------- 725 compress a tree based on a map from old vertices to new vertices. 726 the restriction on the map is that the set {u | map[u] = U} must 727 be connected for all U. 728 729 created -- 95nov15, cca 730 modified -- 96jan04, cca 731 bug fixed, N computed incorrectly 732 modified -- 96jun23, cca 733 in calling sequence, int map[] converted to IV *mapIV 734 ----------------------------------------------------------------- 735 */ 736 Tree * 737 Tree_compress ( 738 Tree *tree, 739 IV *mapIV 740 ) ; 741 /*--------------------------------------------------------------------*/ 742 /* 743 ------------------------------------------------------------------------ 744 ----- methods found in permute.c --------------------------------------- 745 ------------------------------------------------------------------------ 746 */ 747 /* 748 ----------------------- 749 return a permuted tree 750 751 created -- 96jan04, cca 752 ----------------------- 753 */ 754 Tree * 755 Tree_permute ( 756 Tree *tree, 757 int newToOld[], 758 int oldToNew[] 759 ) ; 760 /*--------------------------------------------------------------------*/ 761 /* 762 ------------------------------------------------------------------------ 763 ----- methods found in setBoxes.c -------------------------------------- 764 ------------------------------------------------------------------------ 765 */ 766 /* 767 ------------------------------------------------------------- 768 purpose -- fill boxes arrays for display of a tree 769 770 vmetric[] -- vector of metric on the nodes 771 tmetric[] -- vector of metric on the subtrees 772 xmin, xmax, ymin, ymax -- bounds on box for root 773 west[], east[], south[], north[] -- vector to hold bounds for 774 the nodes in the tree 775 776 return value -- 777 1 --> success 778 2 --> no success, maxnchild > 3 779 780 created -- 96dec20, cca 781 ------------------------------------------------------------- 782 */ 783 int 784 Tree_setBoxesII ( 785 Tree *tree, 786 int vmetric[], 787 int tmetric[], 788 double xmin, 789 double xmax, 790 double ymin, 791 double ymax, 792 double west[], 793 double east[], 794 double south[], 795 double north[] 796 ) ; 797 /* 798 ------------------------------------------------------------- 799 purpose -- fill boxes arrays for display of a tree 800 801 vmetric[] -- vector of metric on the nodes 802 tmetric[] -- vector of metric on the subtrees 803 xmin, xmax, ymin, ymax -- bounds on box for root 804 west[], east[], south[], north[] -- vector to hold bounds for 805 the nodes in the tree 806 807 return value -- 808 1 --> success 809 2 --> no success, maxnchild > 3 810 811 created -- 96dec20, cca 812 ------------------------------------------------------------- 813 */ 814 int 815 Tree_setBoxesDD ( 816 Tree *tree, 817 double vmetric[], 818 double tmetric[], 819 double xmin, 820 double xmax, 821 double ymin, 822 double ymax, 823 double west[], 824 double east[], 825 double south[], 826 double north[] 827 ) ; 828 /*--------------------------------------------------------------------*/ 829 /* 830 ------------------------------------------------------------------------ 831 ----- methods found in getCoords.c ------------------------------------- 832 ------------------------------------------------------------------------ 833 */ 834 /* 835 ------------------------------------------------ 836 purpose -- to get simple x[] and y[] coordinates 837 for the tree vertices 838 839 return values -- 840 1 -- normal return 841 -1 -- tree is NULL 842 -2 -- heightflag is invalid 843 -3 -- coordflag is invalid 844 -4 -- xDV is NULL 845 -5 -- yDV is NULL 846 847 created -- 99jan07, cca 848 ------------------------------------------------ 849 */ 850 int 851 Tree_getSimpleCoords ( 852 Tree *tree, 853 char heightflag, 854 char coordflag, 855 DV *xDV, 856 DV *yDV 857 ) ; 858 /*--------------------------------------------------------------------*/ 859 /* 860 ------------------------------------------------------------------------ 861 ----- methods found in draw.c ------------------------------------------ 862 ------------------------------------------------------------------------ 863 */ 864 /* 865 ------------------------------------------------------------ 866 purpose -- to write an EPS file with a picture of a tree. 867 each node can have its own radius and label 868 869 filename -- name of the file to be written 870 xDV -- x coordinates 871 yDV -- y coordinates 872 rscale -- scaling factor for radius of nodes 873 radiusDV -- radius of nodes, if NULL then radius = 1 874 labelflag -- flag to specify whether labels are to be drawn 875 1 -- draw labels 876 otherwise -- do not draw labels 877 fontscale -- scaling factor for font 878 labelsIV -- IV object that contains the labels of the nodes. 879 if NULL then the node ids are used 880 bbox[] -- bounding box for figure 881 bbox[0] -- x_min 882 bbox[1] -- y_min 883 bbox[2] -- x_max 884 bbox[3] -- y_max 885 frame[] -- frame to hold tree 886 frame[0] -- x_min 887 frame[1] -- y_min 888 frame[2] -- x_max 889 frame[3] -- y_max 890 bounds[] -- bounds for local coordinates 891 if bounds is NULL then 892 the tree fills the frame. note, this is a nonlinear process 893 when the nodes have non-constant radii, and may not converge 894 when the maximum radius is large when compared to the frame. 895 if the process does not converge, a message is printed and 896 the program exits. 897 else 898 bounds[0] -- xi_min 899 bounds[1] -- eta_min 900 bounds[2] -- xi_max 901 bounds[3] -- eta_max 902 endif 903 904 recommendations, 905 bbox[] = { 0, 0, 500, 200 } for tall skinny trees 906 { 0, 0, 500, 500 } for wide trees 907 frame[0] = bbox[0] + 10 908 frame[1] = bbox[1] + 10 909 frame[2] = bbox[2] - 10 910 frame[3] = bbox[3] - 10 911 912 return value 913 1 -- normal return 914 -1 -- tree is NULL 915 -2 -- filename is NULL 916 -3 -- xDV is NULL 917 -4 -- yDV is NULL 918 -5 -- rscale is negative 919 -6 -- fontscale is negative 920 -7 -- bbox is NULL 921 -8 -- frame is NULL 922 923 created -- 99jan07, cca 924 ------------------------------------------------------------ 925 */ 926 int 927 Tree_drawToEPS ( 928 Tree *tree, 929 char *filename, 930 DV *xDV, 931 DV *yDV, 932 double rscale, 933 DV *radiusDV, 934 int labelflag, 935 double fontscale, 936 IV *labelsIV, 937 double bbox[], 938 double frame[], 939 double bounds[] 940 ) ; 941 /*--------------------------------------------------------------------*/ 942