1 /*****************************************************************************
2 /
3 / SPACE (SPArse Cholesky Elimination) Library: ddbisect.c
4 /
5 / author J"urgen Schulze, University of Paderborn
6 / created 00mar09
7 /
8 / This file contains code for the construction/improvement of a vertex
9 / separator for a domain decomposition
10 /
11 ******************************************************************************
12
13 Data type: struct domdec
14 graph_t *G; pointer to graph object
15 int ndom; number of domains
16 int domwght; total weight of domains
17 int *vtype; type of node (DOMAIN or MULTISEC)
18 int *color; color of node (GRAY, BLACK, or WHITE)
19 int cwght[3]; weights of GRAY, BLACK, WHITE partitions
20 int *map; maps nodes to next coarser domain decomp.
21 struct domdec *prev; pointer to previous finer domain decomp.
22 struct domdec *next; pointer to next coarser domain decomp.
23 Comments:
24 o Structure holds the domain decompositions constructed by the
25 coarsening process; it also holds the colorings of the domain decomp.
26 computed by the refinement process
27 o vtype[v]: represents the status of a node in the domain decomposition
28 0, iff status of v is unknown
29 1, iff v is a domain vertex
30 2, iff v is a multisector vertex
31 3, iff multisec v is eliminated and now forms a domain
32 4, iff multisec v is absorbed by another multisec/domain
33 Methods in lib/ddbisect.c:
34 - void checkDDSep(domdec_t *dd);
35 - int findPseudoPeripheralDomain(domdec_t *dd, int domain);
36 o returns a domain with maximal excentricity by repeated breadth first
37 search; first bfs starts at node domain
38 - void constructLevelSep(domdec_t *dd, int domain);
39 o determines a vertex separator by breadth first search starting at node
40 domain;
41 - void initialDDSep(domdec_t *dd);
42 o computes an initial separator for the domain decomposition dd;
43 initially, all domains/multisecs are colored black; the function scans
44 over all connected components of dd; it first calls findPseudoPeripheral-
45 Domain to obtain a domain with maximal excentricity and then it calls
46 constructLevelSep for that domain.
47 - void updateB2W(bucket_t *w_bucket, bucket_t *b_bucket, domdec_t *dd,
48 int domain, int *tmp_color, int *deltaW, int *deltaB, int *deltaS);
49 o if domain flips its color from BLACK to WHITE, all neighboring domains
50 that share a common variable have to be updated (see my PhD thesis)
51 - void updateW2B(bucket_t *w_bucket, bucket_t *b_bucket, domdec_t *dd,
52 int domain, int *tmp_color, int *deltaW, int *deltaB, int *deltaS);
53 o if domain flips its color from WHITE to BLACK, all neighboring domains
54 that share a common variable have to be updated (see my PhD thesis)
55 - void improveDDSep(domdec_t *dd);
56 o Fiducia-Mattheyses variant to improve the coloring/separator of a
57 domain decomposition (see my PhD thesis)
58
59 ******************************************************************************/
60
61 #include <space.h>
62 /* #define DEBUG */
63
64
65 /******************************************************************************
66 ******************************************************************************/
67 void
checkDDSep(domdec_t * dd)68 checkDDSep(domdec_t *dd)
69 { int *xadj, *adjncy, *vwght, *vtype, *color, *cwght;
70 int nvtx, err, u, v, i, istart, istop, nBdom, nWdom;
71 int checkS, checkB, checkW;
72
73 nvtx = dd->G->nvtx;
74 xadj = dd->G->xadj;
75 adjncy = dd->G->adjncy;
76 vwght = dd->G->vwght;
77 vtype = dd->vtype;
78 color = dd->color;
79 cwght = dd->cwght;
80
81 err = FALSE;
82 printf("checking separator of domain decomposition (S %d, B %d, W %d)\n",
83 cwght[GRAY], cwght[BLACK], cwght[WHITE]);
84
85 checkS = checkB = checkW = 0;
86 for (u = 0; u < nvtx; u++)
87 /* check neighborhood of multisector nodes */
88 if (vtype[u] == 2)
89 { nBdom = nWdom = 0;
90 istart = xadj[u];
91 istop = xadj[u+1];
92 for (i = istart; i < istop; i++)
93 { v = adjncy[i];
94 if (color[v] == BLACK) nBdom++;
95 if (color[v] == WHITE) nWdom++;
96 }
97 switch(color[u])
98 { case GRAY:
99 checkS += vwght[u];
100 if ((nBdom == 0) || (nWdom == 0))
101 printf("WARNING: multisec %d belongs to S, but nBdom = %d and "
102 "nWdom = %d\n", u, nBdom, nWdom);
103 break;
104 case BLACK:
105 checkB += vwght[u];
106 if (nWdom > 0)
107 { printf("ERROR: black multisec %d adjacent to white domain\n", u);
108 err = TRUE;
109 }
110 break;
111 case WHITE:
112 checkW += vwght[u];
113 if (nBdom > 0)
114 { printf("ERROR: white multisec %d adjacent to black domain\n", u);
115 err = TRUE;
116 }
117 break;
118 default:
119 printf("ERROR: multisec %d has unrecognized color %d\n", u,
120 color[u]);
121 err = TRUE;
122 }
123 }
124
125 /* sum up size of white/black domains */
126 else /* if (vtype[u] == 1) */
127 switch(color[u])
128 { case BLACK:
129 checkB += vwght[u]; break;
130 case WHITE:
131 checkW += vwght[u]; break;
132 default:
133 printf("ERROR: domain %d has unrecognized color %d\n", u, color[u]);
134 err = TRUE;
135 }
136
137 /* check cwght[GRAY], cwght[BLACK], cwght[WHITE] */
138 if ((checkS != cwght[GRAY]) || (checkB != cwght[BLACK])
139 || (checkW != cwght[WHITE]))
140 { printf("ERROR in partitioning: checkS %d (S %d), checkB %d (B %d), "
141 "checkW %d (W %d)\n", checkS, cwght[GRAY], checkB, cwght[BLACK],
142 checkW, cwght[WHITE]);
143 err = TRUE;
144 }
145 if (err) quit();
146 }
147
148
149 /*****************************************************************************
150 ******************************************************************************/
151 int
findPseudoPeripheralDomain(domdec_t * dd,int domain)152 findPseudoPeripheralDomain(domdec_t* dd, int domain)
153 { int *xadj, *adjncy, *vtype, *level, *queue;
154 int nvtx, qhead, qtail, nlev, lastdomain, u, v, i, istart, istop;
155
156 nvtx = dd->G->nvtx;
157 xadj = dd->G->xadj;
158 adjncy = dd->G->adjncy;
159 vtype = dd->vtype;
160
161 /* ------------------------
162 allocate working storage
163 ------------------------ */
164 mymalloc(level, nvtx, int);
165 mymalloc(queue, nvtx, int);
166
167 /* ---------------------------------------
168 find a domain with maximal excentricity
169 --------------------------------------- */
170 nlev = 0; lastdomain = domain;
171 while (TRUE)
172 { for (u = 0; u < nvtx; u++)
173 level[u] = -1;
174 queue[0] = domain; level[domain] = 0;
175 qhead = 0; qtail = 1;
176 while (qhead != qtail)
177 { u = queue[qhead++];
178 if (vtype[u] == 1) /* remember last domain */
179 lastdomain = u;
180 istart = xadj[u];
181 istop = xadj[u+1];
182 for (i = istart; i < istop; i++)
183 { v = adjncy[i];
184 if (level[v] == -1)
185 { queue[qtail++] = v;
186 level[v] = level[u] + 1;
187 }
188 }
189 }
190 if (level[lastdomain] > nlev)
191 { nlev = level[lastdomain];
192 domain = lastdomain;
193 }
194 else break;
195 }
196
197 /* -------------------------------
198 free working storage and return
199 ------------------------------- */
200 free(level); free(queue);
201 return(domain);
202 }
203
204
205 /*****************************************************************************
206 *****************************************************************************/
207 void
constructLevelSep(domdec_t * dd,int domain)208 constructLevelSep(domdec_t* dd, int domain)
209 { int *xadj, *adjncy, *vwght, *vtype, *color, *cwght;
210 int *queue, *deltaS, *deltaB, *deltaW;
211 int nvtx, bestvalue, weight, qhead, qtail, qopt, q, dS, dB, dW;
212 int u, v, w, i, istart, istop, j, jstart, jstop;
213
214 /* ======================================================================
215 vtype[u]: (u domain)
216 1 => domain u has not been touched yet (not in queue, no color flip)
217 -1 => domain u is in queue and its deltaS, deltaB, deltaW values
218 have to be updated
219 -2 => domain u is in queue and no update necessary
220 -3 => domain u has flipped its color to black
221 deltaS[u], deltaB[u], deltaW[u]:
222 u domain: denotes the change in partition size, if u flips its color
223 u multisec: deltaB/deltaW denote number of adj. black/white domains
224 ====================================================================== */
225
226 nvtx = dd->G->nvtx;
227 xadj = dd->G->xadj;
228 adjncy = dd->G->adjncy;
229 vwght = dd->G->vwght;
230 vtype = dd->vtype;
231 color = dd->color;
232 cwght = dd->cwght;
233
234 /* ------------------------------------------
235 allocate working storage + initializations
236 ------------------------------------------ */
237 mymalloc(queue, nvtx, int);
238 mymalloc(deltaS, nvtx, int);
239 mymalloc(deltaB, nvtx, int);
240 mymalloc(deltaW, nvtx, int);
241 for (u = 0; u < nvtx; u++)
242 { deltaS[u] = deltaB[u] = deltaW[u] = 0;
243 if (vtype[u] == 2)
244 deltaW[u] = xadj[u+1] - xadj[u];
245 }
246
247 /* ---------------------------------------------
248 build a BFS tree rooted at domain
249 the separator is given by the level structure
250 --------------------------------------------- */
251 queue[0] = domain;
252 qhead = 0; qtail = 1;
253 vtype[domain] = -1;
254 while ((cwght[BLACK] < cwght[WHITE]) && (qhead != qtail))
255 { qopt = 0;
256 bestvalue = MAX_INT;
257
258 /* --------------------------------------------------------------------
259 run through queue, update domains if necessary, and find best domain
260 -------------------------------------------------------------------- */
261 for (q = qhead; q < qtail; q++)
262 { u = queue[q];
263 if (vtype[u] == -1)
264 { dB = vwght[u]; dW = -dB; dS = 0;
265 istart = xadj[u];
266 istop = xadj[u+1];
267 for (i = istart; i < istop; i++)
268 { v = adjncy[i]; /* color of multisec v */
269 weight = vwght[v]; /* is GRAY or WHITE */
270 if (color[v] == WHITE)
271 { dW -= weight; dS += weight; } /* multisec will move to S */
272 else if (deltaW[v] == 1)
273 { dB += weight; dS -= weight; } /* multisec will move to B */
274 }
275 deltaS[u] = dS; deltaB[u] = dB; deltaW[u] = dW;
276 vtype[u] = -2;
277 }
278 if (cwght[GRAY] + deltaS[u] < bestvalue)
279 { bestvalue = cwght[GRAY] + deltaS[u];
280 qopt = q;
281 }
282 }
283
284 /* ----------------------------------------------------
285 move best domain to head of queue and color it black
286 ---------------------------------------------------- */
287 u = queue[qopt];
288 swap(queue[qopt], queue[qhead], v);
289 qhead++;
290 color[u] = BLACK;
291 cwght[GRAY] += deltaS[u];
292 cwght[BLACK] += deltaB[u];
293 cwght[WHITE] += deltaW[u];
294 vtype[u] = -3;
295
296 /* ------------------------------------------------------------
297 update all multisecs that are adjacent to domain u and check
298 domains adjacent to the multisecs
299 ------------------------------------------------------------ */
300 istart = xadj[u];
301 istop = xadj[u+1];
302 for (i = istart; i < istop; i++)
303 { v = adjncy[i];
304 deltaB[v]++; deltaW[v]--;
305 if (deltaW[v] == 0) /* color of multisec v changed to BLACK */
306 color[v] = BLACK;
307 else if (deltaB[v] == 1) /* color of multisec v changed to GRAY */
308 { color[v] = GRAY;
309 jstart = xadj[v];
310 jstop = xadj[v+1];
311 for (j = jstart; j < jstop; j++)
312 { w = adjncy[j];
313 if (vtype[w] == 1) /* a new domain enters the queue */
314 { queue[qtail++] = w;
315 vtype[w] = -1;
316 }
317 else if (vtype[w] == -2) /* update (old) domain in queue */
318 vtype[w] = -1;
319 }
320 }
321 else if (deltaW[v] == 1) /* color of multisec v remains GRAY for */
322 { jstart = xadj[v]; /* the last time */
323 jstop = xadj[v+1];
324 for (j = jstart; j < jstop; j++)
325 { w = adjncy[j];
326 if (vtype[w] == -2)
327 vtype[w] = -1;
328 }
329 }
330 }
331 }
332
333 /* ---------------------------
334 reset vtype and free memory
335 --------------------------- */
336 for (i = 0; i < qtail; i++)
337 { u = queue[i];
338 vtype[u] = 1;
339 }
340 free(queue);
341 free(deltaS); free(deltaB); free(deltaW);
342 }
343
344
345 /*****************************************************************************
346 ******************************************************************************/
347 void
initialDDSep(domdec_t * dd)348 initialDDSep(domdec_t *dd)
349 { int *vtype, *color, *cwght;
350 int nvtx, totvwght, domain, u;
351
352 nvtx = dd->G->nvtx;
353 totvwght = dd->G->totvwght;
354 vtype = dd->vtype;
355 color = dd->color;
356 cwght = dd->cwght;
357
358 /* --------------------------------------------------------
359 initializations (all nodes are colored white by default)
360 -------------------------------------------------------- */
361 cwght[GRAY] = 0;
362 cwght[BLACK] = 0;
363 cwght[WHITE] = totvwght;
364 for (u = 0; u < nvtx; u++)
365 color[u] = WHITE;
366
367 /* ----------------------------------------------------------------------
368 scan over connected components and create level based vertex separator
369 ---------------------------------------------------------------------- */
370 for (u = 0; u < nvtx; u++)
371 if ((vtype[u] == 1) && (color[u] == WHITE))
372 { domain = findPseudoPeripheralDomain(dd, u);
373 constructLevelSep(dd, domain);
374 if (cwght[BLACK] >= cwght[WHITE])
375 break;
376 }
377 }
378
379
380 /*****************************************************************************
381 *****************************************************************************/
382 void
updateB2W(bucket_t * w_bucket,bucket_t * b_bucket,domdec_t * dd,int domain,int * tmp_color,int * deltaW,int * deltaB,int * deltaS)383 updateB2W(bucket_t *w_bucket, bucket_t *b_bucket, domdec_t *dd, int domain,
384 int *tmp_color, int *deltaW, int *deltaB, int *deltaS)
385 { int *xadj, *adjncy, *vwght, *vtype;
386 int weight, u, v, i, istart, istop, j, jstart, jstop;
387
388 xadj = dd->G->xadj;
389 adjncy = dd->G->adjncy;
390 vwght = dd->G->vwght;
391 vtype = dd->vtype;
392
393 istart = xadj[domain];
394 istop = xadj[domain+1];
395 for (i = istart; i < istop; i++)
396 { u = adjncy[i];
397 weight = vwght[u];
398 jstart = xadj[u];
399 jstop = xadj[u+1];
400
401 /* ---------------------------------------------------------------
402 subcase (1): before flipping domain to WHITE there was only one
403 other WHITE domain v. update deltaB[v] and deltaS[v]
404 --------------------------------------------------------------- */
405 if (deltaW[u] < 0)
406 { v = -(deltaW[u]+1);
407 deltaW[u] = 1;
408
409 #ifdef DEBUG
410 printf(" B2W case (1): (via multisec %d) removing domain %d from "
411 "w_bucket\n", u, v);
412 #endif
413
414 removeBucket(w_bucket, v);
415 deltaB[v] -= weight; deltaS[v] += weight;
416 insertBucket(w_bucket, deltaS[v], v);
417 }
418
419 /* ---------------------------------------------------------------
420 subcase (2): all other domains are BLACK. update deltaB, deltaS
421 of these BLACK domains. NOTE: subcase (3) may directly follow
422 --------------------------------------------------------------- */
423 if (deltaW[u] == 0)
424 { tmp_color[u] = GRAY;
425 for (j = jstart; j < jstop; j++)
426 { v = adjncy[j];
427 if (vtype[v] == 1)
428 {
429 #ifdef DEBUG
430 printf(" B2W case (2): (via multisec %d) removing domain %d from "
431 "b_bucket\n", u, v);
432 #endif
433
434 removeBucket(b_bucket, v);
435 deltaB[v] += weight; deltaS[v] -= weight;
436 insertBucket(b_bucket, deltaS[v], v);
437 }
438 }
439 }
440
441 if (deltaB[u] < 0) deltaB[u] = 1; /* the unique BLACK dom. flipped */
442 deltaB[u]--; deltaW[u]++;
443
444 /* -------------------------------------------------------------
445 subcase (3): after flipping domain to WHITE there is only one
446 remaining BLACK domain. search it and update deltaW, deltaS
447 furthermore, store the remaining BLACK domain in deltaB[u]
448 ------------------------------------------------------------- */
449 if (deltaB[u] == 1)
450 { for (j = jstart; j < jstop; j++)
451 { v = adjncy[j];
452 if ((tmp_color[v] == BLACK) && (vtype[v] == 1))
453 {
454 #ifdef DEBUG
455 printf(" B2W case (3): (via multisec %d) removing domain %d from "
456 "b_bucket\n", u, v);
457 #endif
458
459 removeBucket(b_bucket, v);
460 deltaW[v] += weight; deltaS[v] -= weight;
461 deltaB[u] = -(v+1);
462 insertBucket(b_bucket, deltaS[v], v);
463 }
464 }
465 }
466
467 /* -------------------------------------------------------------
468 subcase (4): after flipping domain to WHITE there is no other
469 BLACK domain. update deltaW, deltaS of the WHITE domains
470 ------------------------------------------------------------- */
471 if (deltaB[u] == 0)
472 { tmp_color[u] = WHITE;
473 for (j = jstart; j < jstop; j++)
474 { v = adjncy[j];
475 if (vtype[v] == 1)
476 {
477 #ifdef DEBUG
478 printf(" B2W case (4): (via multisec %d) removing domain %d from "
479 "w_bucket\n", u, v);
480 #endif
481
482 removeBucket(w_bucket, v);
483 deltaW[v] -= weight; deltaS[v] += weight;
484 insertBucket(w_bucket, deltaS[v], v);
485 }
486 }
487 }
488 }
489 }
490
491
492 /*****************************************************************************
493 *****************************************************************************/
494 void
updateW2B(bucket_t * w_bucket,bucket_t * b_bucket,domdec_t * dd,int domain,int * tmp_color,int * deltaW,int * deltaB,int * deltaS)495 updateW2B(bucket_t *w_bucket, bucket_t *b_bucket, domdec_t *dd, int domain,
496 int *tmp_color, int *deltaW, int *deltaB, int *deltaS)
497 { int *xadj, *adjncy, *vwght, *vtype;
498 int weight, u, v, i, istart, istop, j, jstart, jstop;
499
500 xadj = dd->G->xadj;
501 adjncy = dd->G->adjncy;
502 vwght = dd->G->vwght;
503 vtype = dd->vtype;
504
505 istart = xadj[domain];
506 istop = xadj[domain+1];
507 for (i = istart; i < istop; i++)
508 { u = adjncy[i];
509 weight = vwght[u];
510 jstart = xadj[u];
511 jstop = xadj[u+1];
512
513 /* ---------------------------------------------------------------
514 subcase (1): before flipping domain to BLACK there was only one
515 other BLACK domain v. update deltaW[v] and deltaS[v]
516 --------------------------------------------------------------- */
517 if (deltaB[u] < 0)
518 { v = -(deltaB[u]+1);
519 deltaB[u] = 1;
520
521 #ifdef DEBUG
522 printf(" W2B case (1): (via multisec %d) removing domain %d from "
523 "b_bucket\n", u, v);
524 #endif
525
526 removeBucket(b_bucket, v);
527 deltaW[v] -= weight; deltaS[v] += weight;
528 insertBucket(b_bucket, deltaS[v], v);
529 }
530
531 /* ---------------------------------------------------------------
532 subcase (2): all other domains are WHITE. update deltaW, deltaS
533 of these WHITE domains. NOTE: subcase (3) may directly follow
534 --------------------------------------------------------------- */
535 if (deltaB[u] == 0)
536 { tmp_color[u] = GRAY;
537 for (j = jstart; j < jstop; j++)
538 { v = adjncy[j];
539 if (vtype[v] == 1)
540 {
541 #ifdef DEBUG
542 printf(" W2B case (2): (via multisec %d) removing domain %d from "
543 "w_bucket\n", u, v);
544 #endif
545
546 removeBucket(w_bucket, v);
547 deltaW[v] += weight; deltaS[v] -= weight;
548 insertBucket(w_bucket, deltaS[v], v);
549 }
550 }
551 }
552
553 if (deltaW[u] < 0) deltaW[u] = 1; /* the unique WHITE dom. flipped */
554 deltaB[u]++; deltaW[u]--;
555
556 /* -------------------------------------------------------------
557 subcase (3): after flipping domain to BLACK there is only one
558 remaining WHITE domain. search it and update deltaB, deltaS
559 furthermore, store the remaining WHITE domain in deltaW[u]
560 ------------------------------------------------------------- */
561 if (deltaW[u] == 1)
562 { for (j = jstart; j < jstop; j++)
563 { v = adjncy[j];
564 if ((tmp_color[v] == WHITE) && (vtype[v] == 1))
565 {
566 #ifdef DEBUG
567 printf(" W2B case (3): (via multisec %d) removing domain %d from "
568 "w_bucket\n", u, v);
569 #endif
570
571 removeBucket(w_bucket, v);
572 deltaB[v] += weight; deltaS[v] -= weight;
573 deltaW[u] = -(v+1);
574 insertBucket(w_bucket, deltaS[v], v);
575 }
576 }
577 }
578
579 /* ---------------------------------------------------------------
580 subcase (4): after flipping domain to BLACK there is no other
581 WHITE domain. update deltaB, deltaS of the BLACK domains
582 --------------------------------------------------------------- */
583 if (deltaW[u] == 0)
584 { tmp_color[u] = BLACK;
585 for (j = jstart; j < jstop; j++)
586 { v = adjncy[j];
587 if (vtype[v] == 1)
588 {
589 #ifdef DEBUG
590 printf(" W2B case (4): (via multisec %d) removing domain %d from "
591 "b_bucket\n", u, v);
592 #endif
593
594 removeBucket(b_bucket, v);
595 deltaB[v] -= weight; deltaS[v] += weight;
596 insertBucket(b_bucket, deltaS[v], v);
597 }
598 }
599 }
600 }
601 }
602
603
604 /*****************************************************************************
605 ******************************************************************************/
606 void
improveDDSep(domdec_t * dd)607 improveDDSep(domdec_t *dd)
608 { bucket_t *b_bucket, *w_bucket;
609 int *xadj, *adjncy, *vwght, *vtype, *color, *cwght;
610 int *tmp_color, *deltaS, *deltaB, *deltaW;
611 int nvtx, weight, tmp_S, tmp_B, tmp_W;
612 int pos, bestglobalpos, badflips, b_domain, w_domain, domain, nxtdomain;
613 int fhead, ftail, u, v, i, istart, istop;
614 FLOAT bestglobalvalue, b_value, w_value, value;
615
616 /* ======================================================================
617 vtype[u]: (u domain)
618 1 => color of domain u has not been changed
619 < 0 => points to next domain in flipping list
620 (fhead points to first, ftail points to last domain in list)
621 = 0 => domain is last domain in flipping list
622 ====================================================================== */
623
624 nvtx = dd->G->nvtx;
625 xadj = dd->G->xadj;
626 adjncy = dd->G->adjncy;
627 vwght = dd->G->vwght;
628 vtype = dd->vtype;
629 color = dd->color;
630 cwght = dd->cwght;
631
632 mymalloc(tmp_color, nvtx, int);
633 mymalloc(deltaS, nvtx, int);
634 mymalloc(deltaB, nvtx, int);
635 mymalloc(deltaW, nvtx, int);
636
637 OUTER_LOOP_START:
638
639 /* ----------------------------------------------------------------------
640 copy data of actual bisection and initialize buckets and flipping list
641 ---------------------------------------------------------------------- */
642 tmp_S = cwght[GRAY];
643 tmp_B = cwght[BLACK];
644 tmp_W = cwght[WHITE];
645 bestglobalpos = badflips = 0;
646 bestglobalvalue = F(tmp_S, tmp_B, tmp_W);
647
648 b_bucket = setupBucket(nvtx, nvtx, (nvtx >> 1));
649 w_bucket = setupBucket(nvtx, nvtx, (nvtx >> 1));
650
651 fhead = 0; ftail = -1;
652 pos = 0;
653
654 /* ----------------------------------------------------------
655 initialize tmp_color, deltaB, and deltaW for all multisecs
656 ---------------------------------------------------------- */
657 for (u = 0; u < nvtx; u++)
658 if (vtype[u] == 2)
659 { deltaB[u] = deltaW[u] = 0;
660 istart = xadj[u];
661 istop = xadj[u+1];
662 for (i = istart; i < istop; i++)
663 { v = adjncy[i];
664 if (color[v] == BLACK) deltaB[u]++;
665 else deltaW[u]++;
666 }
667 if ((deltaB[u] > 0) && (deltaW[u] > 0)) /* update multisec coloring */
668 tmp_color[u] = GRAY;
669 else if (deltaB[u] > 0) tmp_color[u] = BLACK;
670 else tmp_color[u] = WHITE;
671 color[u] = tmp_color[u];
672 }
673
674 /* -----------------------------------------------------------------
675 initialize tmp_color, deltaS,B,W for all domains and fill buckets
676 ----------------------------------------------------------------- */
677 for (u = 0; u < nvtx; u++)
678 if (vtype[u] == 1)
679 { tmp_color[u] = color[u];
680 if (tmp_color[u] == BLACK) /* domain may be flipped to WHITE */
681 { deltaW[u] = vwght[u]; deltaB[u] = -deltaW[u]; deltaS[u] = 0;
682 istart = xadj[u];
683 istop = xadj[u+1];
684 for (i = istart; i < istop; i++)
685 { v = adjncy[i]; /* tmp_color[v] e {GRAY, BLACK} */
686 weight = vwght[v];
687 if (tmp_color[v] == BLACK) /* multisec v will move into S */
688 { deltaB[u] -= weight;
689 deltaS[u] += weight;
690 }
691 else if (deltaB[v] == 1) /* multisec v will move into W */
692 { deltaW[u] += weight;
693 deltaS[u] -= weight;
694 deltaB[v] = -(u+1);
695 }
696 }
697 insertBucket(b_bucket, deltaS[u], u);
698 }
699 if (tmp_color[u] == WHITE) /* domain may be flipped to BLACK */
700 { deltaB[u] = vwght[u]; deltaW[u] = -deltaB[u]; deltaS[u] = 0;
701 istart = xadj[u];
702 istop = xadj[u+1];
703 for (i = istart; i < istop; i++)
704 { v = adjncy[i]; /* tmp_color[v] e {GRAY, WHITE} */
705 weight = vwght[v];
706 if (tmp_color[v] == WHITE) /* multisec v will move into S */
707 { deltaW[u] -= weight;
708 deltaS[u] += weight;
709 }
710 else if (deltaW[v] == 1) /* multisec v will move into B */
711 { deltaB[u] += weight;
712 deltaS[u] -= weight;
713 deltaW[v] = -(u+1);
714 }
715 }
716 insertBucket(w_bucket, deltaS[u], u);
717 }
718 }
719
720 #ifdef DEBUG
721 printf("starting inner loop: b_bucket->nobj %d, w_bucket->nobj %d\n",
722 b_bucket->nobj, w_bucket->nobj);
723 waitkey();
724 #endif
725
726 INNER_LOOP_START:
727
728 /* -------------------------------------------
729 extract best domain from b_bucket, w_bucket
730 ------------------------------------------- */
731 b_value = w_value = MAX_FLOAT;
732 if ((b_domain = minBucket(b_bucket)) != -1)
733 { b_value = F((tmp_S+deltaS[b_domain]), (tmp_B+deltaB[b_domain]),
734 (tmp_W+deltaW[b_domain]));
735
736 #ifdef DEBUG
737 printf("best black domain: %d, deltaS %d, deltaB %d, deltaW %d, "
738 "cost %7.2f\n", b_domain, deltaS[b_domain], deltaB[b_domain],
739 deltaW[b_domain], b_value);
740 #endif
741 }
742 if ((w_domain = minBucket(w_bucket)) != -1)
743 { w_value = F((tmp_S+deltaS[w_domain]), (tmp_B+deltaB[w_domain]),
744 (tmp_W+deltaW[w_domain]));
745
746 #ifdef DEBUG
747 printf("best white domain: %d, deltaS %d, deltaB %d, deltaW %d, "
748 "cost %7.2f\n", w_domain, deltaS[w_domain], deltaB[w_domain],
749 deltaW[w_domain], w_value);
750 #endif
751 }
752
753 if ((b_domain == ERR) && (w_domain == ERR)) goto INNER_LOOP_END;
754
755 if (b_value + EPS < w_value)
756 { domain = b_domain; value = b_value;
757 removeBucket(b_bucket, domain);
758 }
759 else
760 { domain = w_domain; value = w_value;
761 removeBucket(w_bucket, domain);
762 }
763
764 #ifdef DEBUG
765 printf(" domain %d removed from bucket\n", domain);
766 #endif
767
768 /* -------------------------------------------------------------------
769 flip the color of domain and put it in list of log. flipped domains
770 ------------------------------------------------------------------- */
771 if (ftail != -1)
772 vtype[ftail] = -(domain+1); /* append domain */
773 else fhead = -(domain+1); /* list starts with domain */
774 vtype[domain] = 0; /* mark end of list */
775 ftail = domain; /* domain is last element in list */
776
777 if (tmp_color[domain] == BLACK)
778 { tmp_color[domain] = WHITE;
779 updateB2W(w_bucket,b_bucket,dd,domain,tmp_color,deltaW,deltaB,deltaS);
780 }
781 else if (tmp_color[domain] == WHITE)
782 { tmp_color[domain] = BLACK;
783 updateW2B(w_bucket,b_bucket,dd,domain,tmp_color,deltaW,deltaB,deltaS);
784 }
785 tmp_S += deltaS[domain];
786 tmp_B += deltaB[domain];
787 tmp_W += deltaW[domain];
788
789 pos++;
790 if (value + EPS < bestglobalvalue)
791 { bestglobalvalue = value;
792 bestglobalpos = pos;
793 badflips = 0;
794 }
795 else badflips++;
796 if (badflips < MAX_BAD_FLIPS) goto INNER_LOOP_START;
797
798 INNER_LOOP_END:
799
800 /* --------------------------------------------
801 end of inner loop: now do the physical flips
802 -------------------------------------------- */
803 pos = 0;
804 nxtdomain = fhead;
805 while (nxtdomain != 0)
806 { domain = -nxtdomain - 1;
807 if (pos < bestglobalpos)
808 { if (color[domain] == BLACK) color[domain] = WHITE;
809 else color[domain] = BLACK;
810 cwght[GRAY] += deltaS[domain];
811 cwght[BLACK] += deltaB[domain];
812 cwght[WHITE] += deltaW[domain];
813 pos++;
814 }
815 nxtdomain = vtype[domain];
816 vtype[domain] = 1;
817 }
818
819 /* ----------------------------------------------
820 partition improved => re-start the whole stuff
821 ---------------------------------------------- */
822 #ifdef DEBUG
823 printf(" INNER_LOOP_END (#pyhs. flips %d): S %d, B %d, W %d (%7.2f)\n",
824 bestglobalpos, cwght[GRAY], cwght[BLACK], cwght[WHITE],
825 bestglobalvalue);
826 waitkey();
827 #endif
828
829 /* JY: moved next instruction after the two
830 * freeBucket instructions because
831 * this was the cause of a memory leak.
832 * if (bestglobalpos > 0) goto OUTER_LOOP_START;
833 */
834
835 freeBucket(b_bucket);
836 freeBucket(w_bucket);
837
838 if (bestglobalpos > 0) goto OUTER_LOOP_START;
839 free(tmp_color); free(deltaS); free(deltaB); free(deltaW);
840 }
841
842