1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * sfm.c
5 *
6 * This file contains code that implementes an FM-based separator refinement
7 *
8 * Started 8/1/97
9 * George
10 *
11 * $Id: sfm.c 10874 2011-10-17 23:13:00Z karypis $
12 *
13 */
14
15 #include "metislib.h"
16
17
18 /*************************************************************************/
19 /*! This function performs a node-based FM refinement */
20 /**************************************************************************/
FM_2WayNodeRefine2Sided(ctrl_t * ctrl,graph_t * graph,idx_t niter)21 void FM_2WayNodeRefine2Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter)
22 {
23 idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
24 idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
25 idx_t *mptr, *mind, *moved, *swaps;
26 rpq_t *queues[2];
27 nrinfo_t *rinfo;
28 idx_t higain, oldgain, mincut, initcut, mincutorder;
29 idx_t pass, to, other, limit;
30 idx_t badmaxpwgt, mindiff, newdiff;
31 idx_t u[2], g[2];
32 real_t mult;
33
34 WCOREPUSH;
35
36 nvtxs = graph->nvtxs;
37 xadj = graph->xadj;
38 adjncy = graph->adjncy;
39 vwgt = graph->vwgt;
40
41 bndind = graph->bndind;
42 bndptr = graph->bndptr;
43 where = graph->where;
44 pwgts = graph->pwgts;
45 rinfo = graph->nrinfo;
46
47 queues[0] = rpqCreate(nvtxs);
48 queues[1] = rpqCreate(nvtxs);
49
50 moved = iwspacemalloc(ctrl, nvtxs);
51 swaps = iwspacemalloc(ctrl, nvtxs);
52 mptr = iwspacemalloc(ctrl, nvtxs+1);
53 mind = iwspacemalloc(ctrl, 2*nvtxs);
54
55 mult = 0.5*ctrl->ubfactors[0];
56 badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
57
58 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
59 printf("Partitions-N2: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
60
61 for (pass=0; pass<niter; pass++) {
62 iset(nvtxs, -1, moved);
63 rpqReset(queues[0]);
64 rpqReset(queues[1]);
65
66 mincutorder = -1;
67 initcut = mincut = graph->mincut;
68 nbnd = graph->nbnd;
69
70 /* use the swaps array in place of the traditional perm array to save memory */
71 irandArrayPermute(nbnd, swaps, nbnd, 1);
72 for (ii=0; ii<nbnd; ii++) {
73 i = bndind[swaps[ii]];
74 ASSERT(where[i] == 2);
75 rpqInsert(queues[0], i, vwgt[i]-rinfo[i].edegrees[1]);
76 rpqInsert(queues[1], i, vwgt[i]-rinfo[i].edegrees[0]);
77 }
78
79 ASSERT(CheckNodeBnd(graph, nbnd));
80 ASSERT(CheckNodePartitionParams(graph));
81
82 limit = (ctrl->compress ? gk_min(5*nbnd, 400) : gk_min(2*nbnd, 300));
83
84 /******************************************************
85 * Get into the FM loop
86 *******************************************************/
87 mptr[0] = nmind = 0;
88 mindiff = iabs(pwgts[0]-pwgts[1]);
89 to = (pwgts[0] < pwgts[1] ? 0 : 1);
90 for (nswaps=0; nswaps<nvtxs; nswaps++) {
91 u[0] = rpqSeeTopVal(queues[0]);
92 u[1] = rpqSeeTopVal(queues[1]);
93 if (u[0] != -1 && u[1] != -1) {
94 g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];
95 g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];
96
97 to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2));
98
99 if (pwgts[to]+vwgt[u[to]] > badmaxpwgt)
100 to = (to+1)%2;
101 }
102 else if (u[0] == -1 && u[1] == -1) {
103 break;
104 }
105 else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
106 to = 0;
107 }
108 else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
109 to = 1;
110 }
111 else
112 break;
113
114 other = (to+1)%2;
115
116 higain = rpqGetTop(queues[to]);
117 if (moved[higain] == -1) /* Delete if it was in the separator originally */
118 rpqDelete(queues[other], higain);
119
120 ASSERT(bndptr[higain] != -1);
121
122 /* The following check is to ensure we break out if there is a posibility
123 of over-running the mind array. */
124 if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)
125 break;
126
127 pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
128
129 newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
130 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
131 mincut = pwgts[2];
132 mincutorder = nswaps;
133 mindiff = newdiff;
134 }
135 else {
136 if (nswaps - mincutorder > 2*limit ||
137 (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
138 pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
139 break; /* No further improvement, break out */
140 }
141 }
142
143 BNDDelete(nbnd, bndind, bndptr, higain);
144 pwgts[to] += vwgt[higain];
145 where[higain] = to;
146 moved[higain] = nswaps;
147 swaps[nswaps] = higain;
148
149
150 /**********************************************************
151 * Update the degrees of the affected nodes
152 ***********************************************************/
153 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
154 k = adjncy[j];
155 if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
156 oldgain = vwgt[k]-rinfo[k].edegrees[to];
157 rinfo[k].edegrees[to] += vwgt[higain];
158 if (moved[k] == -1 || moved[k] == -(2+other))
159 rpqUpdate(queues[other], k, oldgain-vwgt[higain]);
160 }
161 else if (where[k] == other) { /* This vertex is pulled into the separator */
162 ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
163 BNDInsert(nbnd, bndind, bndptr, k);
164
165 mind[nmind++] = k; /* Keep track for rollback */
166 where[k] = 2;
167 pwgts[other] -= vwgt[k];
168
169 edegrees = rinfo[k].edegrees;
170 edegrees[0] = edegrees[1] = 0;
171 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
172 kk = adjncy[jj];
173 if (where[kk] != 2)
174 edegrees[where[kk]] += vwgt[kk];
175 else {
176 oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
177 rinfo[kk].edegrees[other] -= vwgt[k];
178 if (moved[kk] == -1 || moved[kk] == -(2+to))
179 rpqUpdate(queues[to], kk, oldgain+vwgt[k]);
180 }
181 }
182
183 /* Insert the new vertex into the priority queue. Only one side! */
184 if (moved[k] == -1) {
185 rpqInsert(queues[to], k, vwgt[k]-edegrees[other]);
186 moved[k] = -(2+to);
187 }
188 }
189 }
190 mptr[nswaps+1] = nmind;
191
192 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
193 printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] [%4"PRIDX" %4"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
194
195 }
196
197
198 /****************************************************************
199 * Roll back computation
200 *****************************************************************/
201 for (nswaps--; nswaps>mincutorder; nswaps--) {
202 higain = swaps[nswaps];
203
204 ASSERT(CheckNodePartitionParams(graph));
205
206 to = where[higain];
207 other = (to+1)%2;
208 INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
209 where[higain] = 2;
210 BNDInsert(nbnd, bndind, bndptr, higain);
211
212 edegrees = rinfo[higain].edegrees;
213 edegrees[0] = edegrees[1] = 0;
214 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
215 k = adjncy[j];
216 if (where[k] == 2)
217 rinfo[k].edegrees[to] -= vwgt[higain];
218 else
219 edegrees[where[k]] += vwgt[k];
220 }
221
222 /* Push nodes out of the separator */
223 for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
224 k = mind[j];
225 ASSERT(where[k] == 2);
226 where[k] = other;
227 INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
228 BNDDelete(nbnd, bndind, bndptr, k);
229 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
230 kk = adjncy[jj];
231 if (where[kk] == 2)
232 rinfo[kk].edegrees[other] += vwgt[k];
233 }
234 }
235 }
236
237 ASSERT(mincut == pwgts[2]);
238
239 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
240 printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
241
242 graph->mincut = mincut;
243 graph->nbnd = nbnd;
244
245 if (mincutorder == -1 || mincut >= initcut)
246 break;
247 }
248
249 rpqDestroy(queues[0]);
250 rpqDestroy(queues[1]);
251
252 WCOREPOP;
253 }
254
255
256 /*************************************************************************/
257 /*! This function performs a node-based FM refinement.
258 Each refinement iteration is split into two sub-iterations.
259 In each sub-iteration only moves to one of the left/right partitions
260 is allowed; hence, it is one-sided.
261 */
262 /**************************************************************************/
FM_2WayNodeRefine1Sided(ctrl_t * ctrl,graph_t * graph,idx_t niter)263 void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter)
264 {
265 idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind, iend;
266 idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
267 idx_t *mptr, *mind, *swaps;
268 rpq_t *queue;
269 nrinfo_t *rinfo;
270 idx_t higain, mincut, initcut, mincutorder;
271 idx_t pass, to, other, limit;
272 idx_t badmaxpwgt, mindiff, newdiff;
273 real_t mult;
274
275 WCOREPUSH;
276
277 nvtxs = graph->nvtxs;
278 xadj = graph->xadj;
279 adjncy = graph->adjncy;
280 vwgt = graph->vwgt;
281
282 bndind = graph->bndind;
283 bndptr = graph->bndptr;
284 where = graph->where;
285 pwgts = graph->pwgts;
286 rinfo = graph->nrinfo;
287
288 queue = rpqCreate(nvtxs);
289
290 swaps = iwspacemalloc(ctrl, nvtxs);
291 mptr = iwspacemalloc(ctrl, nvtxs+1);
292 mind = iwspacemalloc(ctrl, 2*nvtxs);
293
294 mult = 0.5*ctrl->ubfactors[0];
295 badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
296
297 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
298 printf("Partitions-N1: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
299
300 to = (pwgts[0] < pwgts[1] ? 1 : 0);
301 for (pass=0; pass<2*niter; pass++) { /* the 2*niter is for the two sides */
302 other = to;
303 to = (to+1)%2;
304
305 rpqReset(queue);
306
307 mincutorder = -1;
308 initcut = mincut = graph->mincut;
309 nbnd = graph->nbnd;
310
311 /* use the swaps array in place of the traditional perm array to save memory */
312 irandArrayPermute(nbnd, swaps, nbnd, 1);
313 for (ii=0; ii<nbnd; ii++) {
314 i = bndind[swaps[ii]];
315 ASSERT(where[i] == 2);
316 rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);
317 }
318
319 ASSERT(CheckNodeBnd(graph, nbnd));
320 ASSERT(CheckNodePartitionParams(graph));
321
322 limit = (ctrl->compress ? gk_min(5*nbnd, 500) : gk_min(3*nbnd, 300));
323
324 /******************************************************
325 * Get into the FM loop
326 *******************************************************/
327 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux3Tmr));
328 mptr[0] = nmind = 0;
329 mindiff = iabs(pwgts[0]-pwgts[1]);
330 for (nswaps=0; nswaps<nvtxs; nswaps++) {
331 if ((higain = rpqGetTop(queue)) == -1)
332 break;
333
334 ASSERT(bndptr[higain] != -1);
335
336 /* The following check is to ensure we break out if there is a posibility
337 of over-running the mind array. */
338 if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)
339 break;
340
341 if (pwgts[to]+vwgt[higain] > badmaxpwgt)
342 break; /* No point going any further. Balance will be bad */
343
344 pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
345
346 newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
347 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
348 mincut = pwgts[2];
349 mincutorder = nswaps;
350 mindiff = newdiff;
351 }
352 else {
353 if (nswaps - mincutorder > 3*limit ||
354 (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
355 pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
356 break; /* No further improvement, break out */
357 }
358 }
359
360 BNDDelete(nbnd, bndind, bndptr, higain);
361 pwgts[to] += vwgt[higain];
362 where[higain] = to;
363 swaps[nswaps] = higain;
364
365
366 /**********************************************************
367 * Update the degrees of the affected nodes
368 ***********************************************************/
369 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux1Tmr));
370 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
371 k = adjncy[j];
372
373 if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
374 rinfo[k].edegrees[to] += vwgt[higain];
375 }
376 else if (where[k] == other) { /* This vertex is pulled into the separator */
377 ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
378 BNDInsert(nbnd, bndind, bndptr, k);
379
380 mind[nmind++] = k; /* Keep track for rollback */
381 where[k] = 2;
382 pwgts[other] -= vwgt[k];
383
384 edegrees = rinfo[k].edegrees;
385 edegrees[0] = edegrees[1] = 0;
386 for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {
387 kk = adjncy[jj];
388 if (where[kk] != 2)
389 edegrees[where[kk]] += vwgt[kk];
390 else {
391 rinfo[kk].edegrees[other] -= vwgt[k];
392
393 /* Since the moves are one-sided this vertex has not been moved yet */
394 rpqUpdate(queue, kk, vwgt[kk]-rinfo[kk].edegrees[other]);
395 }
396 }
397
398 /* Insert the new vertex into the priority queue. Safe due to one-sided moves */
399 rpqInsert(queue, k, vwgt[k]-edegrees[other]);
400 }
401 }
402 mptr[nswaps+1] = nmind;
403 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux1Tmr));
404
405
406 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
407 printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"] [%3"PRIDX" %2"PRIDX"]\n",
408 higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain],
409 pwgts[0], pwgts[1], pwgts[2], nswaps, limit));
410 }
411 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux3Tmr));
412
413
414 /****************************************************************
415 * Roll back computation
416 *****************************************************************/
417 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux2Tmr));
418 for (nswaps--; nswaps>mincutorder; nswaps--) {
419 higain = swaps[nswaps];
420
421 ASSERT(CheckNodePartitionParams(graph));
422 ASSERT(where[higain] == to);
423
424 INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
425 where[higain] = 2;
426 BNDInsert(nbnd, bndind, bndptr, higain);
427
428 edegrees = rinfo[higain].edegrees;
429 edegrees[0] = edegrees[1] = 0;
430 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
431 k = adjncy[j];
432 if (where[k] == 2)
433 rinfo[k].edegrees[to] -= vwgt[higain];
434 else
435 edegrees[where[k]] += vwgt[k];
436 }
437
438 /* Push nodes out of the separator */
439 for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
440 k = mind[j];
441 ASSERT(where[k] == 2);
442 where[k] = other;
443 INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
444 BNDDelete(nbnd, bndind, bndptr, k);
445 for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {
446 kk = adjncy[jj];
447 if (where[kk] == 2)
448 rinfo[kk].edegrees[other] += vwgt[k];
449 }
450 }
451 }
452 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux2Tmr));
453
454 ASSERT(mincut == pwgts[2]);
455
456 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
457 printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
458
459 graph->mincut = mincut;
460 graph->nbnd = nbnd;
461
462 if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))
463 break;
464 }
465
466 rpqDestroy(queue);
467
468 WCOREPOP;
469 }
470
471
472 /*************************************************************************/
473 /*! This function balances the left/right partitions of a separator
474 tri-section */
475 /*************************************************************************/
FM_2WayNodeBalance(ctrl_t * ctrl,graph_t * graph)476 void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph)
477 {
478 idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, gain;
479 idx_t badmaxpwgt, higain, oldgain, pass, to, other;
480 idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
481 idx_t *perm, *moved;
482 rpq_t *queue;
483 nrinfo_t *rinfo;
484 real_t mult;
485
486 nvtxs = graph->nvtxs;
487 xadj = graph->xadj;
488 adjncy = graph->adjncy;
489 vwgt = graph->vwgt;
490
491 bndind = graph->bndind;
492 bndptr = graph->bndptr;
493 where = graph->where;
494 pwgts = graph->pwgts;
495 rinfo = graph->nrinfo;
496
497 mult = 0.5*ctrl->ubfactors[0];
498
499 badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));
500 if (gk_max(pwgts[0], pwgts[1]) < badmaxpwgt)
501 return;
502 if (iabs(pwgts[0]-pwgts[1]) < 3*graph->tvwgt[0]/nvtxs)
503 return;
504
505 WCOREPUSH;
506
507 to = (pwgts[0] < pwgts[1] ? 0 : 1);
508 other = (to+1)%2;
509
510 queue = rpqCreate(nvtxs);
511
512 perm = iwspacemalloc(ctrl, nvtxs);
513 moved = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
514
515 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
516 printf("Partitions: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX" [B]\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
517
518 nbnd = graph->nbnd;
519 irandArrayPermute(nbnd, perm, nbnd, 1);
520 for (ii=0; ii<nbnd; ii++) {
521 i = bndind[perm[ii]];
522 ASSERT(where[i] == 2);
523 rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);
524 }
525
526 ASSERT(CheckNodeBnd(graph, nbnd));
527 ASSERT(CheckNodePartitionParams(graph));
528
529 /******************************************************
530 * Get into the FM loop
531 *******************************************************/
532 for (nswaps=0; nswaps<nvtxs; nswaps++) {
533 if ((higain = rpqGetTop(queue)) == -1)
534 break;
535
536 moved[higain] = 1;
537
538 gain = vwgt[higain]-rinfo[higain].edegrees[other];
539 badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));
540
541 /* break if other is now underwight */
542 if (pwgts[to] > pwgts[other])
543 break;
544
545 /* break if balance is achieved and no +ve or zero gain */
546 if (gain < 0 && pwgts[other] < badmaxpwgt)
547 break;
548
549 /* skip this vertex if it will violate balance on the other side */
550 if (pwgts[to]+vwgt[higain] > badmaxpwgt)
551 continue;
552
553 ASSERT(bndptr[higain] != -1);
554
555 pwgts[2] -= gain;
556
557 BNDDelete(nbnd, bndind, bndptr, higain);
558 pwgts[to] += vwgt[higain];
559 where[higain] = to;
560
561 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
562 printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %3"PRIDX", \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));
563
564
565 /**********************************************************
566 * Update the degrees of the affected nodes
567 ***********************************************************/
568 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
569 k = adjncy[j];
570 if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
571 rinfo[k].edegrees[to] += vwgt[higain];
572 }
573 else if (where[k] == other) { /* This vertex is pulled into the separator */
574 ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
575 BNDInsert(nbnd, bndind, bndptr, k);
576
577 where[k] = 2;
578 pwgts[other] -= vwgt[k];
579
580 edegrees = rinfo[k].edegrees;
581 edegrees[0] = edegrees[1] = 0;
582 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
583 kk = adjncy[jj];
584 if (where[kk] != 2)
585 edegrees[where[kk]] += vwgt[kk];
586 else {
587 ASSERT(bndptr[kk] != -1);
588 oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
589 rinfo[kk].edegrees[other] -= vwgt[k];
590
591 if (moved[kk] == -1)
592 rpqUpdate(queue, kk, oldgain+vwgt[k]);
593 }
594 }
595
596 /* Insert the new vertex into the priority queue */
597 rpqInsert(queue, k, vwgt[k]-edegrees[other]);
598 }
599 }
600 }
601
602 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
603 printf("\tBalanced sep: %6"PRIDX" at %4"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", pwgts[2], nswaps, pwgts[0], pwgts[1], nbnd));
604
605 graph->mincut = pwgts[2];
606 graph->nbnd = nbnd;
607
608 rpqDestroy(queue);
609
610 WCOREPOP;
611 }
612
613