1 /* transform.c */
2
3 #include "../ETree.h"
4
5 #define MYDEBUG 0
6
7 /*--------------------------------------------------------------------*/
8 /*
9 ------------------------------------------------------
10 transform an ETree object by
11 (1) merging small fronts into larger fronts
12 using the ETree_mergeFrontsOne() method
13 (2) merging small fronts into larger fronts
14 using the ETree_mergeFrontsAll() method
15 (3) merging small fronts into larger fronts
16 using the ETree_mergeFrontsAny() method
17 (4) split a large front into a chain of smaller fronts
18 using the ETree_splitFronts() method
19
20 created -- 96jun27, cca
21 ------------------------------------------------------
22 */
23 ETree *
ETree_transform(ETree * etree,int vwghts[],int maxzeros,int maxfrontsize,int seed)24 ETree_transform (
25 ETree *etree,
26 int vwghts[],
27 int maxzeros,
28 int maxfrontsize,
29 int seed
30 ) {
31 ETree *etree2 ;
32 int nfront, nvtx ;
33 IV *nzerosIV ;
34 /*
35 ---------------
36 check the input
37 ---------------
38 */
39 if ( etree == NULL
40 || (nfront = etree->nfront) <= 0
41 || (nvtx = etree->nvtx) <= 0
42 || maxfrontsize <= 0 ) {
43 fprintf(stderr, "\n fatal error in ETree_transform(%p,%p,%d,%d,%d)"
44 "\n bad input\n", etree, vwghts, maxzeros, maxfrontsize,
45 seed) ;
46 exit(-1) ;
47 }
48 nzerosIV = IV_new();
49 IV_init(nzerosIV, nfront, NULL) ;
50 IV_fill(nzerosIV, 0) ;
51 /*
52 --------------------------
53 first, merge only children
54 --------------------------
55 */
56 etree2 = ETree_mergeFrontsOne(etree, maxzeros, nzerosIV) ;
57 ETree_free(etree) ;
58 etree = etree2 ;
59 /*
60 --------------------------
61 second, merge all children
62 --------------------------
63 */
64 etree2 = ETree_mergeFrontsAll(etree, maxzeros, nzerosIV) ;
65 ETree_free(etree) ;
66 etree = etree2 ;
67 /*
68 -------------------------
69 third, merge any children
70 -------------------------
71 */
72 etree2 = ETree_mergeFrontsAny(etree, maxzeros, nzerosIV) ;
73 ETree_free(etree) ;
74 etree = etree2 ;
75 /*
76 -----------------------------------
77 fourth, split large interior fronts
78 -----------------------------------
79 */
80 etree2 = ETree_splitFronts(etree, vwghts, maxfrontsize, seed) ;
81 ETree_free(etree) ;
82 etree = etree2 ;
83 /*
84 ------------------------
85 free the working storage
86 ------------------------
87 */
88 IV_free(nzerosIV) ;
89
90 return(etree) ; }
91
92 /*--------------------------------------------------------------------*/
93 /*
94 ------------------------------------------------------
95 transform an ETree object by
96 (1) merging small fronts into larger fronts
97 using the ETree_mergeFrontsOne() method
98 (2) merging small fronts into larger fronts
99 using the ETree_mergeFrontsAll() method
100 (3) split a large front into a chain of smaller fronts
101 using the ETree_splitFronts() method
102
103 created -- 96jun27, cca
104 ------------------------------------------------------
105 */
106 ETree *
ETree_transform2(ETree * etree,int vwghts[],int maxzeros,int maxfrontsize,int seed)107 ETree_transform2 (
108 ETree *etree,
109 int vwghts[],
110 int maxzeros,
111 int maxfrontsize,
112 int seed
113 ) {
114 ETree *etree2 ;
115 int nfront, nvtx ;
116 IV *nzerosIV ;
117 /*
118 ---------------
119 check the input
120 ---------------
121 */
122 if ( etree == NULL
123 || (nfront = etree->nfront) <= 0
124 || (nvtx = etree->nvtx) <= 0
125 || maxfrontsize <= 0 ) {
126 fprintf(stderr, "\n fatal error in ETree_transform2(%p,%p,%d,%d,%d)"
127 "\n bad input\n", etree, vwghts, maxzeros, maxfrontsize,
128 seed) ;
129 exit(-1) ;
130 }
131 nzerosIV = IV_new();
132 IV_init(nzerosIV, nfront, NULL) ;
133 IV_fill(nzerosIV, 0) ;
134 /*
135 --------------------------
136 first, merge only children
137 --------------------------
138 */
139 etree2 = ETree_mergeFrontsOne(etree, maxzeros, nzerosIV) ;
140 ETree_free(etree) ;
141 etree = etree2 ;
142 /*
143 --------------------------
144 second, merge all children
145 --------------------------
146 */
147 etree2 = ETree_mergeFrontsAll(etree, maxzeros, nzerosIV) ;
148 ETree_free(etree) ;
149 etree = etree2 ;
150 /*
151 -----------------------------------
152 fourth, split large interior fronts
153 -----------------------------------
154 */
155 etree2 = ETree_splitFronts(etree, vwghts, maxfrontsize, seed) ;
156 ETree_free(etree) ;
157 etree = etree2 ;
158 /*
159 ------------------------
160 free the working storage
161 ------------------------
162 */
163 IV_free(nzerosIV) ;
164
165 return(etree) ; }
166
167 /*--------------------------------------------------------------------*/
168 /*
169 --------------------------------------------------------------------
170 purpose -- merge the front tree allowing only chains of nodes to
171 merge that create at most maxzeros zero entries inside a front
172
173 return --
174 IV object that has the old front to new front map
175
176 created -- 98jan29, cca
177 --------------------------------------------------------------------
178 */
179 ETree *
ETree_mergeFrontsOne(ETree * etree,int maxzeros,IV * nzerosIV)180 ETree_mergeFrontsOne (
181 ETree *etree,
182 int maxzeros,
183 IV *nzerosIV
184 ) {
185 ETree *etree2 ;
186 int costJ, J, K, nfront, nvtx, nnew ;
187 int *bndwghts, *fch, *map, *nodwghts, *nzeros, *rep, *sib, *temp ;
188 IV *mapIV ;
189 Tree *tree ;
190 /*
191 ---------------
192 check the input
193 ---------------
194 */
195 if ( etree == NULL || nzerosIV == NULL
196 || (nfront = etree->nfront) <= 0
197 || (nvtx = etree->nvtx) <= 0 ) {
198 fprintf(stderr, "\n fatal error in ETree_mergeFrontsOne(%p,%d,%p)"
199 "\n bad input\n", etree, maxzeros, nzerosIV) ;
200 exit(-1) ;
201 }
202 if ( IV_size(nzerosIV) != nfront ) {
203 fprintf(stderr, "\n fatal error in ETree_mergeFrontsOne(%p,%d,%p)"
204 "\n size(nzerosIV) = %d, nfront = %d\n",
205 etree, maxzeros, nzerosIV, IV_size(nzerosIV), nfront) ;
206 exit(-1) ;
207 }
208 nzeros = IV_entries(nzerosIV) ;
209 tree = etree->tree ;
210 fch = ETree_fch(etree) ;
211 sib = ETree_sib(etree) ;
212 /*
213 ----------------------
214 set up working storage
215 ----------------------
216 */
217 nodwghts = IVinit(nfront, 0) ;
218 IVcopy(nfront, nodwghts, ETree_nodwghts(etree)) ;
219 bndwghts = ETree_bndwghts(etree) ;
220 rep = IVinit(nfront, -1) ;
221 IVramp(nfront, rep, 0, 1) ;
222 /*
223 ------------------------------------------
224 perform a post-order traversal of the tree
225 ------------------------------------------
226 */
227 for ( K = Tree_postOTfirst(tree) ;
228 K != -1 ;
229 K = Tree_postOTnext(tree, K) ) {
230 #if MYDEBUG > 0
231 fprintf(stdout, "\n\n ##### visiting front %d", K) ;
232 fflush(stdout) ;
233 #endif
234 if ( (J = fch[K]) != -1 && sib[J] == -1 ) {
235 costJ = nodwghts[J]*(nodwghts[K] + bndwghts[K] - bndwghts[J]) ;
236 #if MYDEBUG > 0
237 fprintf(stdout, "\n nzeros[%d] = %d, costJ = %d",
238 J, nzeros[J], costJ) ;
239 fflush(stdout) ;
240 #endif
241 if ( nzeros[J] + costJ <= maxzeros ) {
242 rep[J] = K ;
243 nodwghts[K] += nodwghts[J] ;
244 nzeros[K] = nzeros[J] + costJ ;
245 #if MYDEBUG > 0
246 fprintf(stdout,
247 "\n merging %d into %d, |%d| = %d, nzeros = %d",
248 J, K, K, nodwghts[K], nzeros[K]) ;
249 fflush(stdout) ;
250 #endif
251 }
252 }
253 }
254 #if MYDEBUG > 0
255 fprintf(stdout, "\n\n whoa, finished") ;
256 fflush(stdout) ;
257 #endif
258 /*
259 -------------------------------------------------
260 take the map from fronts to representative fronts
261 and make the map from old fronts to new fronts
262 -------------------------------------------------
263 */
264 mapIV = IV_new() ;
265 IV_init(mapIV, nfront, NULL) ;
266 map = IV_entries(mapIV) ;
267 for ( J = 0, nnew = 0 ; J < nfront ; J++ ) {
268 if ( rep[J] == J ) {
269 map[J] = nnew++ ;
270 } else {
271 K = J ;
272 while ( rep[K] != K ) {
273 K = rep[K] ;
274 }
275 rep[J] = K ;
276 }
277 }
278 for ( J = 0 ; J < nfront ; J++ ) {
279 if ( (K = rep[J]) != J ) {
280 map[J] = map[K] ;
281 }
282 }
283 /*
284 -------------------------------
285 get the compressed ETree object
286 -------------------------------
287 */
288 etree2 = ETree_compress(etree, mapIV) ;
289 /*
290 -------------------------
291 remap the nzeros[] vector
292 -------------------------
293 */
294 temp = IVinit(nfront, NULL) ;
295 IVcopy(nfront, temp, nzeros) ;
296 IV_setSize(nzerosIV, nnew) ;
297 nzeros = IV_entries(nzerosIV) ;
298 for ( J = 0 ; J < nfront ; J++ ) {
299 if ( rep[J] == J ) {
300 nzeros[map[J]] = temp[J] ;
301 }
302 }
303 IVfree(temp) ;
304 /*
305 ------------------------
306 free the working storage
307 ------------------------
308 */
309 IVfree(nodwghts) ;
310 IVfree(rep) ;
311 IV_free(mapIV) ;
312
313 return(etree2) ; }
314
315 /*--------------------------------------------------------------------*/
316 /*
317 -------------------------------------------------------
318 purpose -- merge the front tree allowing a parent
319 to absorb all children when that creates
320 at most maxzeros zero entries inside a front
321
322 return --
323 IV object that has the old front to new front map
324
325 created -- 98jan29, cca
326 -------------------------------------------------------
327 */
328 ETree *
ETree_mergeFrontsAll(ETree * etree,int maxzeros,IV * nzerosIV)329 ETree_mergeFrontsAll (
330 ETree *etree,
331 int maxzeros,
332 IV *nzerosIV
333 ) {
334 ETree *etree2 ;
335 int cost, J, Jall, K, KandBnd, nfront, nvtx, nnew ;
336 int *bndwghts, *fch, *map, *nodwghts, *nzeros, *rep, *sib, *temp ;
337 IV *mapIV ;
338 Tree *tree ;
339 /*
340 ---------------
341 check the input
342 ---------------
343 */
344 if ( etree == NULL || nzerosIV == NULL
345 || (nfront = etree->nfront) <= 0
346 || (nvtx = etree->nvtx) <= 0 ) {
347 fprintf(stderr, "\n fatal error in ETree_mergeFrontsAll(%p,%d,%p)"
348 "\n bad input\n", etree, maxzeros, nzerosIV) ;
349 if ( etree != NULL ) {
350 fprintf(stderr, "\n nfront = %d, nvtx = %d",
351 etree->nfront, etree->nvtx) ;
352 }
353 exit(-1) ;
354 }
355 if ( IV_size(nzerosIV) != nfront ) {
356 fprintf(stderr, "\n fatal error in ETree_mergeFrontsAll(%p,%d,%p)"
357 "\n size(nzerosIV) = %d, nfront = %d\n",
358 etree, maxzeros, nzerosIV, IV_size(nzerosIV), nfront) ;
359 exit(-1) ;
360 }
361 nzeros = IV_entries(nzerosIV) ;
362 /*
363 ----------------------
364 set up working storage
365 ----------------------
366 */
367 tree = etree->tree ;
368 fch = ETree_fch(etree) ;
369 sib = ETree_sib(etree) ;
370 nodwghts = IVinit(nfront, 0) ;
371 IVcopy(nfront, nodwghts, ETree_nodwghts(etree)) ;
372 bndwghts = ETree_bndwghts(etree) ;
373 rep = IVinit(nfront, -1) ;
374 IVramp(nfront, rep, 0, 1) ;
375 /*
376 ------------------------------------------
377 perform a post-order traversal of the tree
378 ------------------------------------------
379 */
380 for ( K = Tree_postOTfirst(tree) ;
381 K != -1 ;
382 K = Tree_postOTnext(tree, K) ) {
383 #if MYDEBUG > 0
384 fprintf(stdout, "\n\n ##### visiting front %d", K) ;
385 fflush(stdout) ;
386 #endif
387 if ( (J = fch[K]) != -1 ) {
388 KandBnd = nodwghts[K] + bndwghts[K] ;
389 Jall = 0 ;
390 cost = 2*nzeros[K] ;
391 for ( J = fch[K] ; J != -1 ; J = sib[J] ) {
392 Jall += nodwghts[J] ;
393 cost -= nodwghts[J]*nodwghts[J] ;
394 cost += 2*nodwghts[J]*(KandBnd - bndwghts[J]) ;
395 cost += 2*nzeros[J] ;
396 }
397 cost += Jall*Jall ;
398 cost = cost/2 ;
399 #if MYDEBUG > 0
400 fprintf(stdout, "\n cost = %d", cost) ;
401 fflush(stdout) ;
402 #endif
403 if ( cost <= maxzeros ) {
404 for ( J = fch[K] ; J != -1 ; J = sib[J] ) {
405 #if MYDEBUG > 0
406 fprintf(stdout, "\n merging %d into %d", J, K) ;
407 fflush(stdout) ;
408 #endif
409 rep[J] = K ;
410 nodwghts[K] += nodwghts[J] ;
411 }
412 nzeros[K] = cost ;
413 }
414 }
415 }
416 #if MYDEBUG > 0
417 fprintf(stdout, "\n\n whoa, finished") ;
418 fflush(stdout) ;
419 #endif
420 /*
421 -------------------------------------------------
422 take the map from fronts to representative fronts
423 and make the map from old fronts to new fronts
424 -------------------------------------------------
425 */
426 mapIV = IV_new() ;
427 IV_init(mapIV, nfront, NULL) ;
428 map = IV_entries(mapIV) ;
429 for ( J = 0, nnew = 0 ; J < nfront ; J++ ) {
430 if ( rep[J] == J ) {
431 map[J] = nnew++ ;
432 } else {
433 K = J ;
434 while ( rep[K] != K ) {
435 K = rep[K] ;
436 }
437 rep[J] = K ;
438 }
439 }
440 for ( J = 0 ; J < nfront ; J++ ) {
441 if ( (K = rep[J]) != J ) {
442 map[J] = map[K] ;
443 }
444 }
445 /*
446 -------------------------------
447 get the compressed ETree object
448 -------------------------------
449 */
450 etree2 = ETree_compress(etree, mapIV) ;
451 /*
452 -------------------------
453 remap the nzeros[] vector
454 -------------------------
455 */
456 temp = IVinit(nfront, NULL) ;
457 IVcopy(nfront, temp, nzeros) ;
458 IV_setSize(nzerosIV, nnew) ;
459 nzeros = IV_entries(nzerosIV) ;
460 for ( J = 0 ; J < nfront ; J++ ) {
461 if ( rep[J] == J ) {
462 nzeros[map[J]] = temp[J] ;
463 }
464 }
465 IVfree(temp) ;
466 /*
467 ------------------------
468 free the working storage
469 ------------------------
470 */
471 IVfree(nodwghts) ;
472 IVfree(rep) ;
473 IV_free(mapIV) ;
474
475 return(etree2) ; }
476
477 /*--------------------------------------------------------------------*/
478 /*
479 ---------------------------
480 static prototype definition
481 ---------------------------
482 */
483 static void visitAny ( int K, int par[], int fch[], int sib[],
484 int nodwghts[], int bndwghts[], int map[],
485 int cost[], int nzeros[], int maxzeros) ;
486 /*--------------------------------------------------------------------*/
487 /*
488 --------------------------------------------------------------------
489 purpose -- merge the front tree allowing at most
490 maxzeros zero entries inside a front
491
492 return --
493 IV object that has the old front to new front map
494
495 created -- 96jun23, cca
496 modified -- 97dec18, cca
497 bug fixed that incorrectly counted the number of zeros in a front
498 --------------------------------------------------------------------
499 */
500 ETree *
ETree_mergeFrontsAny(ETree * etree,int maxzeros,IV * nzerosIV)501 ETree_mergeFrontsAny (
502 ETree *etree,
503 int maxzeros,
504 IV *nzerosIV
505 ) {
506 ETree *etree2 ;
507 int J, K, nfront, nvtx, nnew ;
508 int *bndwghts, *cost, *fch, *map, *nodwghts,
509 *nzeros, *par, *place, *rep, *sib, *temp ;
510 IV *mapIV ;
511 Tree *tree ;
512 /*
513 ---------------
514 check the input
515 ---------------
516 */
517 if ( etree == NULL
518 || (nfront = etree->nfront) <= 0
519 || (nvtx = etree->nvtx) <= 0 ) {
520 fprintf(stderr, "\n fatal error in ETree_mergeFrontsAny(%p,%d)"
521 "\n bad input\n", etree, maxzeros) ;
522 exit(-1) ;
523 }
524 if ( IV_size(nzerosIV) != nfront ) {
525 fprintf(stderr, "\n fatal error in ETree_mergeFrontsAny(%p,%d,%p)"
526 "\n size(nzerosIV) = %d, nfront = %d\n",
527 etree, maxzeros, nzerosIV, IV_size(nzerosIV), nfront) ;
528 exit(-1) ;
529 }
530 nzeros = IV_entries(nzerosIV) ;
531 tree = etree->tree ;
532 nodwghts = IVinit(nfront, 0) ;
533 bndwghts = IVinit(nfront, 0) ;
534 par = IVinit(nfront, -1) ;
535 fch = IVinit(nfront, -1) ;
536 sib = IVinit(nfront, -1) ;
537 IVcopy(nfront, par, tree->par) ;
538 IVcopy(nfront, fch, tree->fch) ;
539 IVcopy(nfront, sib, tree->sib) ;
540 IVcopy(nfront, nodwghts, IV_entries(etree->nodwghtsIV)) ;
541 IVcopy(nfront, bndwghts, IV_entries(etree->bndwghtsIV)) ;
542 /*
543 ----------------------
544 set up working storage
545 ----------------------
546 */
547 rep = IVinit(nfront, -1) ;
548 IVramp(nfront, rep, 0, 1) ;
549 cost = IVinit(nfront, 0) ;
550 /*
551 ------------------------------------------
552 perform a post-order traversal of the tree
553 ------------------------------------------
554 */
555 for ( J = Tree_postOTfirst(tree) ;
556 J != -1 ;
557 J = Tree_postOTnext(tree, J) ) {
558 #if MYDEBUG > 0
559 fprintf(stdout, "\n\n ##### visiting front %d", J) ;
560 fflush(stdout) ;
561 #endif
562 visitAny(J, par, fch, sib, nodwghts, bndwghts,
563 rep, cost, nzeros, maxzeros) ;
564 }
565 #if MYDEBUG > 0
566 fprintf(stdout, "\n\n whoa, finished") ;
567 fflush(stdout) ;
568 #endif
569 /*
570 -------------------------------------------------
571 take the map from fronts to representative fronts
572 and make the map from old fronts to new fronts
573 -------------------------------------------------
574 */
575 mapIV = IV_new() ;
576 IV_init(mapIV, nfront, NULL) ;
577 map = IV_entries(mapIV) ;
578 place = IVinit(nfront, -1) ;
579 for ( J = 0, nnew = 0 ; J < nfront ; J++ ) {
580 #if MYDEBUG > 0
581 fprintf(stdout, "\n rep[%d] = %d", J, rep[J]) ;
582 fflush(stdout) ;
583 #endif
584 if ( rep[J] != J ) {
585 K = J ;
586 while ( rep[K] != K ) {
587 #if MYDEBUG > 0
588 fprintf(stdout, "\n rep[%d] = %d", K, rep[K]) ;
589 fflush(stdout) ;
590 #endif
591 K = rep[K] ;
592 }
593 rep[J] = K ;
594 #if MYDEBUG > 0
595 fprintf(stdout, "\n setting rep[%d] = %d", J, rep[J]) ;
596 fflush(stdout) ;
597 #endif
598 } else {
599 place[J] = nnew++ ;
600 }
601 }
602 for ( J = 0 ; J < nfront ; J++ ) {
603 K = rep[J] ;
604 map[J] = place[K] ;
605 }
606 /*
607 -------------------------------
608 get the compressed ETree object
609 -------------------------------
610 */
611 etree2 = ETree_compress(etree, mapIV) ;
612 /*
613 -------------------------
614 remap the nzeros[] vector
615 -------------------------
616 */
617 temp = IVinit(nfront, NULL) ;
618 IVcopy(nfront, temp, nzeros) ;
619 IV_setSize(nzerosIV, nnew) ;
620 nzeros = IV_entries(nzerosIV) ;
621 for ( J = 0 ; J < nfront ; J++ ) {
622 if ( rep[J] == J ) {
623 nzeros[map[J]] = temp[J] ;
624 }
625 }
626 IVfree(temp) ;
627 /*
628 ------------------------
629 free the working storage
630 ------------------------
631 */
632 IVfree(par) ;
633 IVfree(fch) ;
634 IVfree(sib) ;
635 IVfree(nodwghts) ;
636 IVfree(bndwghts) ;
637 IVfree(rep) ;
638 IVfree(cost) ;
639 IVfree(place) ;
640 IV_free(mapIV) ;
641
642 return(etree2) ; }
643
644 /*--------------------------------------------------------------------*/
645 static void
visitAny(int K,int par[],int fch[],int sib[],int nodwghts[],int bndwghts[],int rep[],int cost[],int nzeros[],int maxzeros)646 visitAny (
647 int K,
648 int par[],
649 int fch[],
650 int sib[],
651 int nodwghts[],
652 int bndwghts[],
653 int rep[],
654 int cost[],
655 int nzeros[],
656 int maxzeros
657 ) {
658 int bestJ, firstI, J, lastI, nextJ, prevJ ;
659
660 if ( fch[K] == -1 ) {
661 return ;
662 }
663 #if MYDEBUG > 0
664 fprintf(stdout, "\n inside visitAny(%d), nzeros(%d) = %d",
665 K, K, nzeros[K]) ;
666 #endif
667 /*
668 ----------------------------------
669 find the child with the least cost
670 ----------------------------------
671 */
672 #if MYDEBUG > 0
673 fprintf(stdout, "\n nodwght %d, bndwght %d",
674 nodwghts[K], bndwghts[K]) ;
675 #endif
676 bestJ = -1 ;
677 for ( J = fch[K] ; J != -1 ; J = sib[J] ) {
678 cost[J] = nzeros[J]
679 + nodwghts[J] * (nodwghts[K] + bndwghts[K] - bndwghts[J]) ;
680 #if MYDEBUG > 0
681 fprintf(stdout, "\n child %d, nodwght %d, bndwght %d, cost %d",
682 J, nodwghts[J], bndwghts[J], cost[J]) ;
683 #endif
684 if ( bestJ == -1
685 || cost[J] < cost[bestJ]
686 || (cost[J] == cost[bestJ] && nodwghts[J] < nodwghts[bestJ]) ) {
687 bestJ = J ;
688 }
689 }
690 if ( (cost[bestJ] + nzeros[K] > maxzeros)
691 || (sib[fch[K]] != -1 && par[K] == -1) ) {
692 #if MYDEBUG > 0
693 fprintf(stdout,
694 "\n no merge: cost[%d] + nzeros[%d] = %d + %d > %d",
695 bestJ, K, cost[bestJ], nzeros[K], maxzeros) ;
696 #endif
697 /*
698 --------------------------------
699 no child can be absorbed, return
700 --------------------------------
701 */
702 return ;
703 }
704 #if MYDEBUG > 0
705 fprintf(stdout, "\n merging child %d into %d", bestJ, K) ;
706 #endif
707 /*
708 -------------------------
709 absorb child bestJ into K
710 -------------------------
711 */
712 for ( J = fch[K], prevJ = -1 ; J != bestJ ; J = sib[J] ) {
713 prevJ = J ;
714 }
715 nextJ = sib[bestJ] ;
716 #if MYDEBUG > 0
717 fprintf(stdout, "\n previous sibling = %d, next sibling = %d",
718 prevJ, nextJ) ;
719 #endif
720 if ( (firstI = fch[bestJ]) == -1 ) {
721 if ( prevJ == -1 ) {
722 fch[K] = nextJ ;
723 #if MYDEBUG > 0
724 fprintf(stdout, "\n setting fch[%d] = %d", K, fch[K]) ;
725 #endif
726 } else {
727 sib[prevJ] = nextJ ;
728 #if MYDEBUG > 0
729 fprintf(stdout, "\n setting sib[%d] = %d", prevJ, sib[prevJ]) ;
730 #endif
731 }
732 } else {
733 firstI = fch[bestJ] ;
734 par[firstI] = K ;
735 #if MYDEBUG > 0
736 fprintf(stdout, "\n setting par[%d] = %d", firstI, par[firstI]) ;
737 #endif
738 if ( (lastI = sib[firstI]) != -1 ) {
739 while ( sib[lastI] != -1 ) {
740 par[lastI] = K ;
741 #if MYDEBUG > 0
742 fprintf(stdout,
743 "\n setting par[%d] = %d", lastI, par[lastI]) ;
744 #endif
745 lastI = sib[lastI] ;
746 }
747 par[lastI] = K ;
748 #if MYDEBUG > 0
749 fprintf(stdout, "\n setting par[%d] = %d", lastI, par[lastI]) ;
750 #endif
751 }
752 if ( prevJ == -1 ) {
753 fch[K] = firstI ;
754 #if MYDEBUG > 0
755 fprintf(stdout, "\n setting fch[%d] = %d", K, fch[K]) ;
756 #endif
757 } else {
758 sib[prevJ] = firstI ;
759 #if MYDEBUG > 0
760 fprintf(stdout, "\n setting sib[%d] = %d", prevJ, sib[prevJ]) ;
761 #endif
762 }
763 if ( lastI != -1 ) {
764 sib[lastI] = nextJ ;
765 #if MYDEBUG > 0
766 fprintf(stdout, "\n setting sib[%d] = %d", lastI, sib[lastI]) ;
767 #endif
768 }
769 }
770 rep[bestJ] = K ;
771 nodwghts[K] += nodwghts[bestJ] ;
772 nzeros[K] += cost[bestJ] ;
773 #if MYDEBUG > 0
774 fprintf(stdout, "\n setting rep[%d] = %d", bestJ, rep[bestJ]) ;
775 fprintf(stdout, "\n setting nodwghts[%d] = %d", K, nodwghts[K]) ;
776 fprintf(stdout, "\n setting nzeros[%d] = %d", K, nzeros[K]) ;
777 #endif
778 /*
779 -------------
780 visit K again
781 -------------
782 */
783 #if MYDEBUG > 0
784 fprintf(stdout, "\n\n ### visiting front %d", K) ;
785 fflush(stdout) ;
786 #endif
787 visitAny(K, par, fch, sib, nodwghts, bndwghts,
788 rep, cost, nzeros, maxzeros) ;
789
790 return ; }
791
792 /*--------------------------------------------------------------------*/
793 /*
794 -------------------------------------------------
795 expand an ETree object by splitting a large front
796 into a chain of smaller fronts.
797
798 created -- 96jun27, cca
799 -------------------------------------------------
800 */
801 ETree *
ETree_splitFronts(ETree * etree,int vwghts[],int maxfrontsize,int seed)802 ETree_splitFronts (
803 ETree *etree,
804 int vwghts[],
805 int maxfrontsize,
806 int seed
807 ) {
808 ETree *etree2 ;
809 int count, front, ii, I, Inew, J, Jnew, nbnd, newsize, nint, nfront,
810 nfront2, nsplit, nvtx, prev, size, sizeJ, v, vwght ;
811 int *bndwghts, *fch, *head, *indices, *link, *newbndwghts, *newmap,
812 *newnodwghts, *newpar, *nodwghts, *roots, *sib, *vtxToFront ;
813 Tree *tree ;
814 /*
815 ---------------
816 check the input
817 ---------------
818 */
819 if ( etree == NULL
820 || (nfront = etree->nfront) <= 0
821 || (nvtx = etree->nvtx) <= 0
822 || maxfrontsize <= 0 ) {
823 fprintf(stderr, "\n fatal error in ETree_splitFronts(%p,%p,%d,%d)"
824 "\n bad input\n", etree, vwghts, maxfrontsize, seed) ;
825 exit(-1) ;
826 }
827 tree = etree->tree ;
828 fch = tree->fch ;
829 sib = tree->sib ;
830 nodwghts = IV_entries(etree->nodwghtsIV) ;
831 bndwghts = IV_entries(etree->bndwghtsIV) ;
832 vtxToFront = IV_entries(etree->vtxToFrontIV) ;
833 /*
834 --------------------------
835 set up the working storage
836 --------------------------
837 */
838 newpar = IVinit(nvtx, -1) ;
839 roots = IVinit(nfront, -1) ;
840 newmap = IVinit(nvtx, -1) ;
841 newnodwghts = IVinit(nvtx, -1) ;
842 newbndwghts = IVinit(nvtx, -1) ;
843 head = IVinit(nfront, -1) ;
844 link = IVinit(nvtx, -1) ;
845 indices = IVinit(nvtx, -1) ;
846 for ( v = 0 ; v < nvtx ; v++ ) {
847 front = vtxToFront[v] ;
848 link[v] = head[front] ;
849 head[front] = v ;
850 }
851 /*
852 ------------------------------------------------
853 execute a post-order traversal of the front tree
854 ------------------------------------------------
855 */
856 nfront2 = 0 ;
857 for ( J = Tree_postOTfirst(tree) ;
858 J != -1 ;
859 J = Tree_postOTnext(tree, J) ) {
860 sizeJ = 0 ;
861 for ( v = head[J], count = 0 ; v != -1 ; v = link[v] ) {
862 indices[count++] = v ;
863 vwght = (vwghts != NULL) ? vwghts[v] : 1 ;
864 sizeJ += vwght ;
865 }
866 if ( sizeJ != nodwghts[J] ) {
867 fprintf(stderr, "\n fatal error in ETree_splitFronts(%p,%p,%d,%d)"
868 "\n J = %d, sizeJ = %d, nodwght = %d\n",
869 etree, vwghts, maxfrontsize, seed, J, sizeJ, nodwghts[J]) ;
870 exit(-1) ;
871 }
872 #if MYDEBUG > 0
873 fprintf(stdout, "\n\n checking out front %d, size %d", J, sizeJ) ;
874 #endif
875 if ( sizeJ <= maxfrontsize || fch[J] == -1 ) {
876 /*
877 -------------------------------------------
878 this front is small enough (or is a domain)
879 -------------------------------------------
880 */
881 Jnew = nfront2++ ;
882 for ( ii = 0 ; ii < count ; ii++ ) {
883 v = indices[ii] ;
884 newmap[v] = Jnew ;
885 #if MYDEBUG > 1
886 fprintf(stdout, "\n mapping vertex %d into new front %d",
887 v, Jnew) ;
888 #endif
889 }
890 for ( I = fch[J] ; I != -1 ; I = sib[I] ) {
891 Inew = roots[I] ;
892 newpar[Inew] = Jnew ;
893 }
894 newnodwghts[Jnew] = nodwghts[J] ;
895 newbndwghts[Jnew] = bndwghts[J] ;
896 roots[J] = Jnew ;
897 #if MYDEBUG > 0
898 fprintf(stdout, "\n front is small enough, Jnew = %d", Jnew) ;
899 #endif
900 } else {
901 /*
902 ------------------------------------------
903 this front is too large, split into pieces
904 whose size differs by one vertex
905 ------------------------------------------
906 */
907 nsplit = (sizeJ + maxfrontsize - 1)/maxfrontsize ;
908 newsize = sizeJ / nsplit ;
909 if ( sizeJ % nsplit != 0 ) {
910 newsize++ ;
911 }
912 #if MYDEBUG > 0
913 fprintf(stdout,
914 "\n front is too large, %d target fronts, target size = %d",
915 nsplit, newsize) ;
916 #endif
917 prev = -1 ;
918 nint = nodwghts[J] ;
919 nbnd = nint + bndwghts[J] ;
920 if ( seed > 0 ) {
921 IVshuffle(count, indices, seed) ;
922 }
923 ii = 0 ;
924 while ( ii < count ) {
925 Jnew = nfront2++ ;
926 size = 0 ;
927 while ( ii < count ) {
928 v = indices[ii] ;
929 vwght = (vwghts != NULL) ? vwghts[v] : 1 ;
930 #if MYDEBUG > 0
931 fprintf(stdout,
932 "\n ii = %d, v = %d, vwght = %d, size = %d",
933 ii, v, vwght, size) ;
934 #endif
935 /*
936 -----------------------------------------------
937 97aug28, cca
938 bug fix. front is created even if it is too big
939 -----------------------------------------------
940 */
941 if ( newsize >= size + vwght || size == 0 ) {
942 newmap[v] = Jnew ;
943 size += vwght ;
944 #if MYDEBUG > 0
945 fprintf(stdout,
946 "\n mapping vertex %d into new front %d, size = %d",
947 v, Jnew, size) ;
948 #endif
949 ii++ ;
950 } else {
951 break ;
952 }
953 }
954 if ( prev == -1 ) {
955 for ( I = fch[J] ; I != -1 ; I = sib[I] ) {
956 Inew = roots[I] ;
957 newpar[Inew] = Jnew ;
958 }
959 } else {
960 newpar[prev] = Jnew ;
961 }
962 prev = Jnew ;
963 newnodwghts[Jnew] = size ;
964 nbnd = nbnd - size ;
965 newbndwghts[Jnew] = nbnd ;
966 #if MYDEBUG > 0
967 fprintf(stdout, "\n new front %d, size %d, bnd %d",
968 Jnew, newnodwghts[Jnew], newbndwghts[Jnew]) ;
969 #endif
970 }
971 roots[J] = Jnew ;
972 }
973 }
974 /*
975 ---------------------------
976 create the new ETree object
977 ---------------------------
978 */
979 etree2 = ETree_new() ;
980 ETree_init1(etree2, nfront2, nvtx) ;
981 IVcopy(nfront2, etree2->tree->par, newpar) ;
982 Tree_setFchSibRoot(etree2->tree) ;
983 IVcopy(nvtx, IV_entries(etree2->vtxToFrontIV), newmap) ;
984 IVcopy(nfront2, IV_entries(etree2->nodwghtsIV), newnodwghts) ;
985 IVcopy(nfront2, IV_entries(etree2->bndwghtsIV), newbndwghts) ;
986 /*
987 ------------------------
988 free the working storage
989 ------------------------
990 */
991 IVfree(newpar) ;
992 IVfree(roots) ;
993 IVfree(newmap) ;
994 IVfree(newnodwghts) ;
995 IVfree(newbndwghts) ;
996 IVfree(head) ;
997 IVfree(link) ;
998 IVfree(indices) ;
999
1000 return(etree2) ; }
1001
1002 /*--------------------------------------------------------------------*/
1003