1 /* maximizeGain.c */
2
3 #include "../Tree.h"
4
5 /*--------------------------------------------------------------------*/
6 /*
7 -------------------------------------------------------
8 purpose --
9
10 given a gain value assigned to each node,
11 find a set of nodes, no two in a child-ancestor
12 relationship, that maximizes the total gain.
13
14 this problem arises in finding the optimal domain/schur
15 complement partition for a semi-implicit factorization.
16
17 created -- 98jun20, cca
18 -------------------------------------------------------
19 */
20 IV *
Tree_maximizeGainIV(Tree * tree,IV * gainIV,int * ptotalgain,int msglvl,FILE * msgFile)21 Tree_maximizeGainIV (
22 Tree *tree,
23 IV *gainIV,
24 int *ptotalgain,
25 int msglvl,
26 FILE *msgFile
27 ) {
28 char *mark ;
29 int I, J, K, n, ndom, sum, totalgain ;
30 int *compids, *fch, *gain, *par, *sib, *subtreeGain ;
31 IV *compidsIV ;
32 /*
33 ---------------
34 check the input
35 ---------------
36 */
37 if ( tree == NULL || gainIV == NULL || ptotalgain == NULL
38 || (msglvl > 0 && msgFile == NULL) ) {
39 fprintf(stderr, "\n fatal error in Tree_maximizeGainIV()"
40 "\n bad input\n") ;
41 exit(-1) ;
42 }
43 n = tree->n ;
44 par = tree->par ;
45 fch = tree->fch ;
46 sib = tree->sib ;
47 if ( n != IV_size(gainIV) ) {
48 fprintf(stderr, "\n fatal error in Tree_maximizeGainIV()"
49 "\n tree size = %d, gain size = %d",
50 tree->n, IV_size(gainIV)) ;
51 exit(-1) ;
52 }
53 gain = IV_entries(gainIV) ;
54 /*
55 --------------------------------------------------
56 compute the subtree gains and mark candidate roots
57 --------------------------------------------------
58 */
59 mark = CVinit(n, 'N') ;
60 subtreeGain = IVinit(n, 0) ;
61 for ( J = Tree_postOTfirst(tree) ;
62 J != -1 ;
63 J = Tree_postOTnext(tree, J) ) {
64 if ( fch[J] == -1 ) {
65 mark[J] = 'R' ;
66 subtreeGain[J] = gain[J] ;
67 } else {
68 for ( I = fch[J], sum = 0 ; I != -1 ; I = sib[I] ) {
69 sum += subtreeGain[I] ;
70 }
71 if ( gain[J] >= sum ) {
72 subtreeGain[J] = gain[J] ;
73 mark[J] = 'R' ;
74 } else {
75 subtreeGain[J] = sum ;
76 }
77 }
78 }
79 /*
80 ----------------------
81 compute the total gain
82 ----------------------
83 */
84 for ( J = tree->root, totalgain = 0 ; J != -1 ; J = sib[J] ) {
85 totalgain += subtreeGain[J] ;
86 }
87 *ptotalgain = totalgain ;
88 /*
89 ----------------------------------------------
90 create and initialize the component ids vector
91 ----------------------------------------------
92 */
93 compidsIV = IV_new() ;
94 IV_init(compidsIV, n, NULL) ;
95 IV_fill(compidsIV, 0) ;
96 compids = IV_entries(compidsIV) ;
97 /*
98 ----------------------------------------------
99 fix the component ids of the nodes in the tree
100 ----------------------------------------------
101 */
102 for ( J = Tree_preOTfirst(tree), ndom = 0 ;
103 J != -1 ;
104 J = Tree_preOTnext(tree, J) ) {
105 if ( mark[J] == 'R' ) {
106 if ( (K = par[J]) != -1 && compids[K] != 0 ) {
107 compids[J] = compids[K] ;
108 } else {
109 compids[J] = ++ndom ;
110 }
111 } else if ( (K = par[J]) != -1 ) {
112 compids[J] = compids[K] ;
113 }
114 }
115 /*
116 ------------------------
117 free the working storage
118 ------------------------
119 */
120 IVfree(subtreeGain) ;
121 CVfree(mark) ;
122
123 return(compidsIV) ; }
124
125 /*--------------------------------------------------------------------*/
126