1 /* compress.c */
2
3 #include "../ETree.h"
4
5 #define MYDEBUG 0
6
7 /*--------------------------------------------------------------------*/
8 /*
9 -------------------------------------------------------
10 purpose --
11 to create and return an IV object that contains the map
12 from old to new fronts that are fundamental chains.
13
14 created -- 96jun23, cca
15 -------------------------------------------------------
16 */
17 IV *
ETree_fundChainMap(ETree * etree)18 ETree_fundChainMap (
19 ETree *etree
20 ) {
21 int nfront, nvtx ;
22 IV *frontmapIV ;
23 /*
24 ---------------
25 check the input
26 ---------------
27 */
28 if ( etree == NULL || etree->tree == NULL
29 || (nfront = etree->nfront) <= 0 || (nvtx = etree->nvtx) <= 0 ) {
30 fprintf(stderr, "\n fatal error in ETree_fundChainMap(%p)"
31 "\n bad input\n", etree) ;
32 exit(-1) ;
33 }
34 /*
35 -------------------------------------
36 call the Tree object's method to get
37 the map from old fronts to new fronts
38 -------------------------------------
39 */
40 frontmapIV = Tree_fundChainMap(etree->tree) ;
41
42 return(frontmapIV) ; }
43
44 /*--------------------------------------------------------------------*/
45 /*
46 -------------------------------------------------------
47 purpose --
48 to create and return an IV object that contains the map
49 from old to new fronts that are fundamental supernodes
50
51 created -- 96jun23, cca
52 -------------------------------------------------------
53 */
54 IV *
ETree_fundSupernodeMap(ETree * etree)55 ETree_fundSupernodeMap (
56 ETree *etree
57 ) {
58 int child, front, nfront, nfs, nvtx ;
59 int *bndwghts, *fch, *frontmap, *nodwghts, *par, *sib ;
60 IV *frontmapIV ;
61 /*
62 ---------------
63 check the input
64 ---------------
65 */
66 if ( etree == NULL || etree->tree == NULL
67 || (nfront = etree->nfront) <= 0 || (nvtx = etree->nvtx) <= 0 ) {
68 fprintf(stderr, "\n fatal error in ETree_fundSupernodeMap(%p)"
69 "\n bad input\n", etree) ;
70 exit(-1) ;
71 }
72 par = etree->tree->par ;
73 fch = etree->tree->fch ;
74 sib = etree->tree->sib ;
75 nodwghts = IV_entries(etree->nodwghtsIV) ;
76 bndwghts = IV_entries(etree->bndwghtsIV) ;
77 /*
78 ------------------------------------------
79 fill the map from old fronts to new fronts
80 ------------------------------------------
81 */
82 frontmapIV = IV_new() ;
83 IV_init(frontmapIV, nfront, NULL) ;
84 frontmap = IV_entries(frontmapIV) ;
85 nfs = 0 ;
86 front = etree->tree->root ;
87 while ( front != -1 ) {
88 while ( fch[front] != -1 ) {
89 front = fch[front] ;
90 }
91 frontmap[front] = nfs++ ;
92 while ( sib[front] == -1 && par[front] != -1 ) {
93 front = par[front] ;
94 child = fch[front] ;
95 if ( sib[child] != -1
96 || (nodwghts[front] + bndwghts[front] != bndwghts[child]) ) {
97 frontmap[front] = nfs++ ;
98 } else {
99 frontmap[front] = frontmap[child] ;
100 }
101 }
102 front = sib[front] ;
103 }
104
105 return(frontmapIV) ; }
106
107 /*--------------------------------------------------------------------*/
108 /*
109 -----------------------------------------------------------
110 compress an ETree object given a map from old to new nodes.
111 note, a new node must be a connected set of the old nodes.
112
113 return value -- pointer to new ETree object
114
115 created -- 96jun23, cca.
116 -----------------------------------------------------------
117 */
118 ETree *
ETree_compress(ETree * etree,IV * frontmapIV)119 ETree_compress (
120 ETree *etree,
121 IV *frontmapIV
122 ) {
123 ETree *etree2 ;
124 int nfront, newfront, newnfront, newparfront, nvtx, oldfront,
125 parfront, v ;
126 int *bndwghts, *frontmap, *newbndwghts, *newnodwghts, *newpar,
127 *newvtxToFront, *nodwghts, *par, *vtxToFront ;
128 /*
129 ---------------
130 check the input
131 ---------------
132 */
133 if ( etree == NULL || (nfront = etree->nfront) <= 0
134 || (nvtx = etree->nvtx) <= 0 || frontmapIV == NULL ) {
135 fprintf(stderr, "\n fatal error in ETree_compress(%p,%p)"
136 "\n bad input\n", etree, frontmapIV) ;
137 exit(-1) ;
138 }
139 /*
140 --------------------------------
141 pull out pointers and dimensions
142 --------------------------------
143 */
144 nfront = etree->nfront ;
145 nvtx = etree->nvtx ;
146 par = etree->tree->par ;
147 nodwghts = IV_entries(etree->nodwghtsIV) ;
148 bndwghts = IV_entries(etree->bndwghtsIV) ;
149 vtxToFront = IV_entries(etree->vtxToFrontIV) ;
150 newnfront = 1 + IV_max(frontmapIV) ;
151 frontmap = IV_entries(frontmapIV) ;
152 #if MYDEBUG > 0
153 fprintf(stdout, "\n newnfront = %d", newnfront) ;
154 #endif
155 /*
156 -------------------------------
157 initialize the new ETree object
158 -------------------------------
159 */
160 etree2 = ETree_new() ;
161 ETree_init1(etree2, newnfront, nvtx) ;
162 newpar = etree2->tree->par ;
163 newnodwghts = IV_entries(etree2->nodwghtsIV) ;
164 newbndwghts = IV_entries(etree2->bndwghtsIV) ;
165 newvtxToFront = IV_entries(etree2->vtxToFrontIV) ;
166 #if MYDEBUG > 0
167 fprintf(stdout, "\n newnodwghts") ;
168 IV_writeForHumanEye(etree2->nodwghtsIV, stdout) ;
169 #endif
170 /*
171 ------------------------
172 fill the new tree fields
173 ------------------------
174 */
175 for ( oldfront = 0 ; oldfront < nfront ; oldfront++ ) {
176 newfront = frontmap[oldfront] ;
177 parfront = par[oldfront] ;
178 #if MYDEBUG > 0
179 fprintf(stdout,
180 "\n oldfront = %d, nodwght = %d, parfront = %d, newfront = %d",
181 oldfront, nodwghts[oldfront], parfront, newfront) ;
182 fflush(stdout) ;
183 #endif
184 newnodwghts[newfront] += nodwghts[oldfront] ;
185 #if MYDEBUG > 0
186 fprintf(stdout,
187 "\n nodwghts[%d] = %d, newnodwghts[%d] = %d",
188 oldfront, nodwghts[oldfront],
189 newfront, newnodwghts[newfront]) ;
190 fflush(stdout) ;
191 #endif
192 if ( parfront != -1
193 && (newparfront = frontmap[parfront]) != newfront ) {
194 newpar[newfront] = newparfront ;
195 newbndwghts[newfront] = bndwghts[oldfront] ;
196 #if MYDEBUG > 0
197 fprintf(stdout, "\n newparfront = %d", newparfront) ;
198 fprintf(stdout,
199 "\n setting newpar[%d] = %d, newbndwghts[%d] = %d",
200 newfront, newpar[newfront],
201 newfront, newbndwghts[newfront]) ;
202 fflush(stdout) ;
203 #endif
204 }
205 }
206 Tree_setFchSibRoot(etree2->tree) ;
207 /*
208 ---------------------------------------
209 set the map from vertices to new fronts
210 ---------------------------------------
211 */
212 for ( v = 0 ; v < nvtx ; v++ ) {
213 newvtxToFront[v] = frontmap[vtxToFront[v]] ;
214 }
215
216 return(etree2) ; }
217
218 /*--------------------------------------------------------------------*/
219