1 /* TwoSetViaBKL.c */
2
3 #include "../GPart.h"
4 #include "../../BKL.h"
5 #include "../../timings.h"
6
7 /*--------------------------------------------------------------------*/
8 /*
9 -----------------------------------------------------------------
10 given a domain decomposition, find a bisector
11 1. construct the domain/segment graph
12 2. use block kernihan-lin to get an initial bisector
13
14 alpha -- cost function parameter for BKL
15 seed -- random number seed
16 cpus -- array to store CPU times
17 cpus[0] -- time to find domain/segment map
18 cpus[1] -- time to find domain/segment bipartite graph
19 cpus[2] -- time to find two-set partition
20
21 return value -- cost of the partition
22
23 created -- 96mar09, cca
24 -----------------------------------------------------------------
25 */
26 double
GPart_TwoSetViaBKL(GPart * gpart,double alpha,int seed,double cpus[])27 GPart_TwoSetViaBKL (
28 GPart *gpart,
29 double alpha,
30 int seed,
31 double cpus[]
32 ) {
33 BKL *bkl ;
34 BPG *bpg ;
35 double t1, t2 ;
36 FILE *msgFile ;
37 float bestcost ;
38 Graph *g, *gc ;
39 int c, flag, ierr, msglvl, ndom, nseg, nvtx, v ;
40 int *compids, *cweights, *dscolors, *dsmap, *vwghts ;
41 IV *dsmapIV ;
42 /*
43 ---------------
44 check the input
45 ---------------
46 */
47 if ( gpart == NULL || cpus == NULL ) {
48 fprintf(stderr, "\n fatal error in GPart_DDsep(%p,%f,%d,%p)"
49 "\n bad input\n", gpart, alpha, seed, cpus) ;
50 exit(-1) ;
51 }
52 g = gpart->g ;
53 nvtx = gpart->nvtx ;
54 compids = IV_entries(&gpart->compidsIV) ;
55 cweights = IV_entries(&gpart->cweightsIV) ;
56 vwghts = g->vwghts ;
57 msglvl = gpart->msglvl ;
58 msgFile = gpart->msgFile ;
59 /*
60 HARDCODE THE ALPHA PARAMETER.
61 */
62 alpha = 1.0 ;
63 /*
64 ------------------------------
65 (1) get the domain/segment map
66 (2) get the compressed graph
67 (3) create the bipartite graph
68 ------------------------------
69 */
70 MARKTIME(t1) ;
71 dsmapIV = GPart_domSegMap(gpart, &ndom, &nseg) ;
72 dsmap = IV_entries(dsmapIV) ;
73 MARKTIME(t2) ;
74 cpus[0] = t2 - t1 ;
75 if ( msglvl > 1 ) {
76 fprintf(msgFile, "\n CPU %9.5f : generate domain-segment map",
77 t2 - t1) ;
78 fprintf(msgFile, "\n ndom = %d, nseg = %d", ndom, nseg) ;
79 fflush(msgFile) ;
80 }
81 /*
82 -----------------------------------------
83 create the domain/segment bipartite graph
84 -----------------------------------------
85 */
86 MARKTIME(t1) ;
87 gc = Graph_compress(gpart->g, dsmap, 1) ;
88 bpg = BPG_new() ;
89 BPG_init(bpg, ndom, nseg, gc) ;
90 MARKTIME(t2) ;
91 if ( msglvl > 1 ) {
92 fprintf(msgFile, "\n CPU %9.5f : create domain-segment graph",
93 t2 - t1) ;
94 fflush(msgFile) ;
95 }
96 cpus[1] = t2 - t1 ;
97 if ( msglvl > 2 ) {
98 if ( bpg->graph->vwghts != NULL ) {
99 fprintf(msgFile, "\n domain weights :") ;
100 IVfp80(msgFile, bpg->nX, bpg->graph->vwghts, 17, &ierr) ;
101 fprintf(msgFile, "\n segment weights :") ;
102 IVfp80(msgFile, bpg->nY, bpg->graph->vwghts+bpg->nX, 18, &ierr) ;
103 fflush(msgFile) ;
104 }
105 }
106 if ( msglvl > 3 ) {
107 fprintf(msgFile, "\n dsmapIV ") ;
108 IV_writeForHumanEye(dsmapIV, msgFile) ;
109 fprintf(msgFile, "\n\n domain/segment bipartite graph ") ;
110 BPG_writeForHumanEye(bpg, msgFile) ;
111 fflush(msgFile) ;
112 }
113 /*
114 ------------------------------------
115 create and initialize the BKL object
116 ------------------------------------
117 */
118 MARKTIME(t1) ;
119 flag = 5 ;
120 bkl = BKL_new() ;
121 BKL_init(bkl, bpg, alpha) ;
122 BKL_setInitPart(bkl, flag, seed, NULL) ;
123 bestcost = BKL_evalfcn(bkl) ;
124 gpart->ncomp = 2 ;
125 MARKTIME(t2) ;
126 cpus[2] = t2 - t1 ;
127 if ( msglvl > 1 ) {
128 fprintf(msgFile, "\n CPU %9.5f : initialize BKL object", t2 - t1) ;
129 fflush(msgFile) ;
130 }
131 if ( msglvl > 2 ) {
132 fprintf(msgFile, "\n BKL : flag = %d, seed = %d", flag, seed) ;
133 fprintf(msgFile, ", initial cost = %.2f", bestcost) ;
134 fflush(msgFile) ;
135 fprintf(msgFile, ", cweights = < %d %d %d >",
136 bkl->cweights[0], bkl->cweights[1], bkl->cweights[2]) ;
137 fflush(msgFile) ;
138 }
139 if ( msglvl > 2 ) {
140 fprintf(msgFile, "\n colors") ;
141 IVfp80(msgFile, bkl->nreg, bkl->colors, 80, &ierr) ;
142 fflush(msgFile) ;
143 }
144 if ( msglvl > 1 ) {
145 fprintf(msgFile, "\n BKL initial weights : ") ;
146 IVfp80(msgFile, 3, bkl->cweights, 25, &ierr) ;
147 fflush(msgFile) ;
148 }
149 /*
150 --------------------------------
151 improve the partition via fidmat
152 --------------------------------
153 */
154 MARKTIME(t1) ;
155 bestcost = BKL_fidmat(bkl) ;
156 MARKTIME(t2) ;
157 cpus[2] += t2 - t1 ;
158 if ( msglvl > 1 ) {
159 fprintf(msgFile, "\n CPU %9.5f : improve the partition via fidmat",
160 t2 - t1) ;
161 fflush(msgFile) ;
162 }
163 if ( msglvl > 1 ) {
164 fprintf(msgFile, "\n BKL : %d passes", bkl->npass) ;
165 fprintf(msgFile, ", %d flips", bkl->nflips) ;
166 fprintf(msgFile, ", %d gainevals", bkl->ngaineval) ;
167 fprintf(msgFile, ", %d improve steps", bkl->nimprove) ;
168 fprintf(msgFile, ", cost = %9.2f", bestcost) ;
169 }
170 if ( msglvl > 1 ) {
171 fprintf(msgFile,
172 "\n BKL STATS < %9d %9d %9d > %9.2f < %4d %4d %4d %4d %4d >",
173 bkl->cweights[0], bkl->cweights[1], bkl->cweights[2],
174 bestcost, bkl->npass, bkl->npatch, bkl->nflips, bkl->nimprove,
175 bkl->ngaineval) ;
176 fflush(msgFile) ;
177 }
178 if ( msglvl > 2 ) {
179 fprintf(msgFile, "\n colors") ;
180 IVfp80(msgFile, bkl->nreg, bkl->colors, 80, &ierr) ;
181 fflush(msgFile) ;
182 }
183 /*
184 ----------------------------
185 set compids[] and cweights[]
186 ----------------------------
187 */
188 MARKTIME(t1) ;
189 dscolors = bkl->colors ;
190 gpart->ncomp = 2 ;
191 IV_setSize(&gpart->cweightsIV, 3) ;
192 cweights = IV_entries(&gpart->cweightsIV) ;
193 cweights[0] = cweights[1] = cweights[2] = 0 ;
194 if ( vwghts == NULL ) {
195 for ( v = 0 ; v < nvtx ; v++ ) {
196 compids[v] = c = dscolors[dsmap[v]] ;
197 cweights[c]++ ;
198 }
199 } else {
200 for ( v = 0 ; v < nvtx ; v++ ) {
201 compids[v] = c = dscolors[dsmap[v]] ;
202 cweights[c] += vwghts[v] ;
203 }
204 }
205 if ( msglvl > 2 ) {
206 fprintf(msgFile, "\n BKL partition : < %d %d %d >",
207 cweights[0], cweights[1], cweights[2]) ;
208 fflush(msgFile) ;
209 }
210 /*
211 ------------------------------------
212 free the BKL object, the BPG object
213 and the domain/segment map IV object
214 ------------------------------------
215 */
216 BKL_free(bkl) ;
217 IV_free(dsmapIV) ;
218 BPG_free(bpg) ;
219 MARKTIME(t2) ;
220 cpus[2] += t2 - t1 ;
221
222 return((double) bestcost) ; }
223
224 /*--------------------------------------------------------------------*/
225