1 /*
2 * kwayfm.c
3 *
4 * This file contains code that implements the multilevel k-way refinement
5 *
6 * Started 7/28/97
7 * George
8 *
9 * $Id: kwayfm.c,v 1.1 1998/11/27 17:59:16 karypis Exp $
10 *
11 */
12
13 #include <metis.h>
14
15
16 /*************************************************************************
17 * This function performs k-way refinement
18 **************************************************************************/
Random_KWayEdgeRefine(CtrlType * ctrl,GraphType * graph,int nparts,float * tpwgts,float ubfactor,int npasses,int ffactor)19 void Random_KWayEdgeRefine(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses, int ffactor)
20 {
21 int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees;
22 int from, me, to, oldcut, vwgt, gain;
23 idxtype *xadj, *adjncy, *adjwgt;
24 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
25 EDegreeType *myedegrees;
26 RInfoType *myrinfo;
27
28 nvtxs = graph->nvtxs;
29 xadj = graph->xadj;
30 adjncy = graph->adjncy;
31 adjwgt = graph->adjwgt;
32
33 bndptr = graph->bndptr;
34 bndind = graph->bndind;
35
36 where = graph->where;
37 pwgts = graph->pwgts;
38
39 /* Setup the weight intervals of the various subdomains */
40 minwgt = idxwspacemalloc(ctrl, nparts);
41 maxwgt = idxwspacemalloc(ctrl, nparts);
42 itpwgts = idxwspacemalloc(ctrl, nparts);
43 tvwgt = idxsum(nparts, pwgts);
44 ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
45
46 for (i=0; i<nparts; i++) {
47 itpwgts[i] = tpwgts[i]*tvwgt;
48 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
49 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
50 }
51
52 perm = idxwspacemalloc(ctrl, nvtxs);
53
54 IFSET(ctrl->dbglvl, DBG_REFINE,
55 printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
56 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
57 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
58 graph->mincut));
59
60 for (pass=0; pass<npasses; pass++) {
61 ASSERT(ComputeCut(graph, where) == graph->mincut);
62
63 oldcut = graph->mincut;
64 nbnd = graph->nbnd;
65
66 RandomPermute(nbnd, perm, 1);
67 for (nmoves=iii=0; iii<graph->nbnd; iii++) {
68 ii = perm[iii];
69 if (ii >= nbnd)
70 continue;
71 i = bndind[ii];
72
73 myrinfo = graph->rinfo+i;
74
75 if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */
76 from = where[i];
77 vwgt = graph->vwgt[i];
78
79 if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from])
80 continue; /* This cannot be moved! */
81
82 myedegrees = myrinfo->edegrees;
83 myndegrees = myrinfo->ndegrees;
84
85 j = myrinfo->id;
86 for (k=0; k<myndegrees; k++) {
87 to = myedegrees[k].pid;
88 gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */
89 if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0)
90 break;
91 }
92 if (k == myndegrees)
93 continue; /* break out if you did not find a candidate */
94
95 for (j=k+1; j<myndegrees; j++) {
96 to = myedegrees[j].pid;
97 if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
98 (myedegrees[j].ed == myedegrees[k].ed &&
99 itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
100 k = j;
101 }
102
103 to = myedegrees[k].pid;
104
105 j = 0;
106 if (myedegrees[k].ed-myrinfo->id > 0)
107 j = 1;
108 else if (myedegrees[k].ed-myrinfo->id == 0) {
109 if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
110 j = 1;
111 }
112 if (j == 0)
113 continue;
114
115 /*=====================================================================
116 * If we got here, we can now move the vertex from 'from' to 'to'
117 *======================================================================*/
118 graph->mincut -= myedegrees[k].ed-myrinfo->id;
119
120 IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
121
122 /* Update where, weight, and ID/ED information of the vertex you moved */
123 where[i] = to;
124 INC_DEC(pwgts[to], pwgts[from], vwgt);
125 myrinfo->ed += myrinfo->id-myedegrees[k].ed;
126 SWAP(myrinfo->id, myedegrees[k].ed, j);
127 if (myedegrees[k].ed == 0)
128 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
129 else
130 myedegrees[k].pid = from;
131
132 if (myrinfo->ed-myrinfo->id < 0)
133 BNDDelete(nbnd, bndind, bndptr, i);
134
135 /* Update the degrees of adjacent vertices */
136 for (j=xadj[i]; j<xadj[i+1]; j++) {
137 ii = adjncy[j];
138 me = where[ii];
139
140 myrinfo = graph->rinfo+ii;
141 if (myrinfo->edegrees == NULL) {
142 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
143 ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
144 }
145 myedegrees = myrinfo->edegrees;
146
147 ASSERT(CheckRInfo(myrinfo));
148
149 if (me == from) {
150 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
151
152 if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
153 BNDInsert(nbnd, bndind, bndptr, ii);
154 }
155 else if (me == to) {
156 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
157
158 if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
159 BNDDelete(nbnd, bndind, bndptr, ii);
160 }
161
162 /* Remove contribution from the .ed of 'from' */
163 if (me != from) {
164 for (k=0; k<myrinfo->ndegrees; k++) {
165 if (myedegrees[k].pid == from) {
166 if (myedegrees[k].ed == adjwgt[j])
167 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
168 else
169 myedegrees[k].ed -= adjwgt[j];
170 break;
171 }
172 }
173 }
174
175 /* Add contribution to the .ed of 'to' */
176 if (me != to) {
177 for (k=0; k<myrinfo->ndegrees; k++) {
178 if (myedegrees[k].pid == to) {
179 myedegrees[k].ed += adjwgt[j];
180 break;
181 }
182 }
183 if (k == myrinfo->ndegrees) {
184 myedegrees[myrinfo->ndegrees].pid = to;
185 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
186 }
187 }
188
189 ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
190 ASSERT(CheckRInfo(myrinfo));
191
192 }
193 nmoves++;
194 }
195 }
196
197 graph->nbnd = nbnd;
198
199 IFSET(ctrl->dbglvl, DBG_REFINE,
200 printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
201 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
202 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut, ComputeVolume(graph, where)));
203
204 if (graph->mincut == oldcut)
205 break;
206 }
207
208 idxwspacefree(ctrl, nparts);
209 idxwspacefree(ctrl, nparts);
210 idxwspacefree(ctrl, nparts);
211 idxwspacefree(ctrl, nvtxs);
212 }
213
214
215
216
217
218
219 /*************************************************************************
220 * This function performs k-way refinement
221 **************************************************************************/
Greedy_KWayEdgeRefine(CtrlType * ctrl,GraphType * graph,int nparts,float * tpwgts,float ubfactor,int npasses)222 void Greedy_KWayEdgeRefine(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses)
223 {
224 int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain;
225 int from, me, to, oldcut, vwgt;
226 idxtype *xadj, *adjncy, *adjwgt;
227 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
228 EDegreeType *myedegrees;
229 RInfoType *myrinfo;
230 PQueueType queue;
231
232 nvtxs = graph->nvtxs;
233 xadj = graph->xadj;
234 adjncy = graph->adjncy;
235 adjwgt = graph->adjwgt;
236
237 bndind = graph->bndind;
238 bndptr = graph->bndptr;
239
240 where = graph->where;
241 pwgts = graph->pwgts;
242
243 /* Setup the weight intervals of the various subdomains */
244 minwgt = idxwspacemalloc(ctrl, nparts);
245 maxwgt = idxwspacemalloc(ctrl, nparts);
246 itpwgts = idxwspacemalloc(ctrl, nparts);
247 tvwgt = idxsum(nparts, pwgts);
248 ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
249
250 for (i=0; i<nparts; i++) {
251 itpwgts[i] = tpwgts[i]*tvwgt;
252 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
253 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
254 }
255
256 perm = idxwspacemalloc(ctrl, nvtxs);
257 moved = idxwspacemalloc(ctrl, nvtxs);
258
259 PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
260
261 IFSET(ctrl->dbglvl, DBG_REFINE,
262 printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
263 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
264 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
265 graph->mincut));
266
267 for (pass=0; pass<npasses; pass++) {
268 ASSERT(ComputeCut(graph, where) == graph->mincut);
269
270 PQueueReset(&queue);
271 idxset(nvtxs, -1, moved);
272
273 oldcut = graph->mincut;
274 nbnd = graph->nbnd;
275
276 RandomPermute(nbnd, perm, 1);
277 for (ii=0; ii<nbnd; ii++) {
278 i = bndind[perm[ii]];
279 PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
280 moved[i] = 2;
281 }
282
283 for (iii=0;;iii++) {
284 if ((i = PQueueGetMax(&queue)) == -1)
285 break;
286 moved[i] = 1;
287
288 myrinfo = graph->rinfo+i;
289 from = where[i];
290 vwgt = graph->vwgt[i];
291
292 if (pwgts[from]-vwgt < minwgt[from])
293 continue; /* This cannot be moved! */
294
295 myedegrees = myrinfo->edegrees;
296 myndegrees = myrinfo->ndegrees;
297
298 j = myrinfo->id;
299 for (k=0; k<myndegrees; k++) {
300 to = myedegrees[k].pid;
301 gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */
302 if (pwgts[to]+vwgt <= maxwgt[to]+gain && gain >= 0)
303 break;
304 }
305 if (k == myndegrees)
306 continue; /* break out if you did not find a candidate */
307
308 for (j=k+1; j<myndegrees; j++) {
309 to = myedegrees[j].pid;
310 if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
311 (myedegrees[j].ed == myedegrees[k].ed &&
312 itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
313 k = j;
314 }
315
316 to = myedegrees[k].pid;
317
318 j = 0;
319 if (myedegrees[k].ed-myrinfo->id > 0)
320 j = 1;
321 else if (myedegrees[k].ed-myrinfo->id == 0) {
322 if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
323 j = 1;
324 }
325 if (j == 0)
326 continue;
327
328 /*=====================================================================
329 * If we got here, we can now move the vertex from 'from' to 'to'
330 *======================================================================*/
331 graph->mincut -= myedegrees[k].ed-myrinfo->id;
332
333 IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
334
335 /* Update where, weight, and ID/ED information of the vertex you moved */
336 where[i] = to;
337 INC_DEC(pwgts[to], pwgts[from], vwgt);
338 myrinfo->ed += myrinfo->id-myedegrees[k].ed;
339 SWAP(myrinfo->id, myedegrees[k].ed, j);
340 if (myedegrees[k].ed == 0)
341 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
342 else
343 myedegrees[k].pid = from;
344
345 if (myrinfo->ed < myrinfo->id)
346 BNDDelete(nbnd, bndind, bndptr, i);
347
348 /* Update the degrees of adjacent vertices */
349 for (j=xadj[i]; j<xadj[i+1]; j++) {
350 ii = adjncy[j];
351 me = where[ii];
352
353 myrinfo = graph->rinfo+ii;
354 if (myrinfo->edegrees == NULL) {
355 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
356 ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
357 }
358 myedegrees = myrinfo->edegrees;
359
360 ASSERT(CheckRInfo(myrinfo));
361
362 oldgain = (myrinfo->ed-myrinfo->id);
363
364 if (me == from) {
365 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
366
367 if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
368 BNDInsert(nbnd, bndind, bndptr, ii);
369 }
370 else if (me == to) {
371 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
372
373 if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
374 BNDDelete(nbnd, bndind, bndptr, ii);
375 }
376
377 /* Remove contribution from the .ed of 'from' */
378 if (me != from) {
379 for (k=0; k<myrinfo->ndegrees; k++) {
380 if (myedegrees[k].pid == from) {
381 if (myedegrees[k].ed == adjwgt[j])
382 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
383 else
384 myedegrees[k].ed -= adjwgt[j];
385 break;
386 }
387 }
388 }
389
390 /* Add contribution to the .ed of 'to' */
391 if (me != to) {
392 for (k=0; k<myrinfo->ndegrees; k++) {
393 if (myedegrees[k].pid == to) {
394 myedegrees[k].ed += adjwgt[j];
395 break;
396 }
397 }
398 if (k == myrinfo->ndegrees) {
399 myedegrees[myrinfo->ndegrees].pid = to;
400 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
401 }
402 }
403
404 /* Update the queue */
405 if (me == to || me == from) {
406 gain = myrinfo->ed-myrinfo->id;
407 if (moved[ii] == 2) {
408 if (gain >= 0)
409 PQueueUpdate(&queue, ii, oldgain, gain);
410 else {
411 PQueueDelete(&queue, ii, oldgain);
412 moved[ii] = -1;
413 }
414 }
415 else if (moved[ii] == -1 && gain >= 0) {
416 PQueueInsert(&queue, ii, gain);
417 moved[ii] = 2;
418 }
419 }
420
421 ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
422 ASSERT(CheckRInfo(myrinfo));
423
424 }
425 }
426
427 graph->nbnd = nbnd;
428
429 IFSET(ctrl->dbglvl, DBG_REFINE,
430 printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Cut: %6d\n",
431 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
432 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, graph->mincut));
433
434 if (graph->mincut == oldcut)
435 break;
436 }
437
438 PQueueFree(ctrl, &queue);
439
440 idxwspacefree(ctrl, nparts);
441 idxwspacefree(ctrl, nparts);
442 idxwspacefree(ctrl, nparts);
443 idxwspacefree(ctrl, nvtxs);
444 idxwspacefree(ctrl, nvtxs);
445
446 }
447
448
449 /*************************************************************************
450 * This function performs k-way refinement
451 **************************************************************************/
Greedy_KWayEdgeBalance(CtrlType * ctrl,GraphType * graph,int nparts,float * tpwgts,float ubfactor,int npasses)452 void Greedy_KWayEdgeBalance(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses)
453 {
454 int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves;
455 int from, me, to, oldcut, vwgt;
456 idxtype *xadj, *adjncy, *adjwgt;
457 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
458 EDegreeType *myedegrees;
459 RInfoType *myrinfo;
460 PQueueType queue;
461
462 nvtxs = graph->nvtxs;
463 xadj = graph->xadj;
464 adjncy = graph->adjncy;
465 adjwgt = graph->adjwgt;
466
467 bndind = graph->bndind;
468 bndptr = graph->bndptr;
469
470 where = graph->where;
471 pwgts = graph->pwgts;
472
473 /* Setup the weight intervals of the various subdomains */
474 minwgt = idxwspacemalloc(ctrl, nparts);
475 maxwgt = idxwspacemalloc(ctrl, nparts);
476 itpwgts = idxwspacemalloc(ctrl, nparts);
477 tvwgt = idxsum(nparts, pwgts);
478 ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
479
480 for (i=0; i<nparts; i++) {
481 itpwgts[i] = tpwgts[i]*tvwgt;
482 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
483 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
484 }
485
486 perm = idxwspacemalloc(ctrl, nvtxs);
487 moved = idxwspacemalloc(ctrl, nvtxs);
488
489 PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
490
491 IFSET(ctrl->dbglvl, DBG_REFINE,
492 printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
493 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
494 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
495 graph->mincut));
496
497 for (pass=0; pass<npasses; pass++) {
498 ASSERT(ComputeCut(graph, where) == graph->mincut);
499
500 /* Check to see if things are out of balance, given the tolerance */
501 for (i=0; i<nparts; i++) {
502 if (pwgts[i] > maxwgt[i])
503 break;
504 }
505 if (i == nparts) /* Things are balanced. Return right away */
506 break;
507
508 PQueueReset(&queue);
509 idxset(nvtxs, -1, moved);
510
511 oldcut = graph->mincut;
512 nbnd = graph->nbnd;
513
514 RandomPermute(nbnd, perm, 1);
515 for (ii=0; ii<nbnd; ii++) {
516 i = bndind[perm[ii]];
517 PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
518 moved[i] = 2;
519 }
520
521 nmoves = 0;
522 for (;;) {
523 if ((i = PQueueGetMax(&queue)) == -1)
524 break;
525 moved[i] = 1;
526
527 myrinfo = graph->rinfo+i;
528 from = where[i];
529 vwgt = graph->vwgt[i];
530
531 if (pwgts[from]-vwgt < minwgt[from])
532 continue; /* This cannot be moved! */
533
534 myedegrees = myrinfo->edegrees;
535 myndegrees = myrinfo->ndegrees;
536
537 for (k=0; k<myndegrees; k++) {
538 to = myedegrees[k].pid;
539 if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
540 break;
541 }
542 if (k == myndegrees)
543 continue; /* break out if you did not find a candidate */
544
545 for (j=k+1; j<myndegrees; j++) {
546 to = myedegrees[j].pid;
547 if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])
548 k = j;
549 }
550
551 to = myedegrees[k].pid;
552
553 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->id < 0)
554 continue;
555
556 /*=====================================================================
557 * If we got here, we can now move the vertex from 'from' to 'to'
558 *======================================================================*/
559 graph->mincut -= myedegrees[k].ed-myrinfo->id;
560
561 IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
562
563 /* Update where, weight, and ID/ED information of the vertex you moved */
564 where[i] = to;
565 INC_DEC(pwgts[to], pwgts[from], vwgt);
566 myrinfo->ed += myrinfo->id-myedegrees[k].ed;
567 SWAP(myrinfo->id, myedegrees[k].ed, j);
568 if (myedegrees[k].ed == 0)
569 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
570 else
571 myedegrees[k].pid = from;
572
573 if (myrinfo->ed == 0)
574 BNDDelete(nbnd, bndind, bndptr, i);
575
576 /* Update the degrees of adjacent vertices */
577 for (j=xadj[i]; j<xadj[i+1]; j++) {
578 ii = adjncy[j];
579 me = where[ii];
580
581 myrinfo = graph->rinfo+ii;
582 if (myrinfo->edegrees == NULL) {
583 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
584 ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
585 }
586 myedegrees = myrinfo->edegrees;
587
588 ASSERT(CheckRInfo(myrinfo));
589
590 oldgain = (myrinfo->ed-myrinfo->id);
591
592 if (me == from) {
593 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
594
595 if (myrinfo->ed > 0 && bndptr[ii] == -1)
596 BNDInsert(nbnd, bndind, bndptr, ii);
597 }
598 else if (me == to) {
599 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
600
601 if (myrinfo->ed == 0 && bndptr[ii] != -1)
602 BNDDelete(nbnd, bndind, bndptr, ii);
603 }
604
605 /* Remove contribution from the .ed of 'from' */
606 if (me != from) {
607 for (k=0; k<myrinfo->ndegrees; k++) {
608 if (myedegrees[k].pid == from) {
609 if (myedegrees[k].ed == adjwgt[j])
610 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
611 else
612 myedegrees[k].ed -= adjwgt[j];
613 break;
614 }
615 }
616 }
617
618 /* Add contribution to the .ed of 'to' */
619 if (me != to) {
620 for (k=0; k<myrinfo->ndegrees; k++) {
621 if (myedegrees[k].pid == to) {
622 myedegrees[k].ed += adjwgt[j];
623 break;
624 }
625 }
626 if (k == myrinfo->ndegrees) {
627 myedegrees[myrinfo->ndegrees].pid = to;
628 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
629 }
630 }
631
632 /* Update the queue */
633 if (me == to || me == from) {
634 gain = myrinfo->ed-myrinfo->id;
635 if (moved[ii] == 2) {
636 if (myrinfo->ed > 0)
637 PQueueUpdate(&queue, ii, oldgain, gain);
638 else {
639 PQueueDelete(&queue, ii, oldgain);
640 moved[ii] = -1;
641 }
642 }
643 else if (moved[ii] == -1 && myrinfo->ed > 0) {
644 PQueueInsert(&queue, ii, gain);
645 moved[ii] = 2;
646 }
647 }
648
649 ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
650 ASSERT(CheckRInfo(myrinfo));
651 }
652 nmoves++;
653 }
654
655 graph->nbnd = nbnd;
656
657 IFSET(ctrl->dbglvl, DBG_REFINE,
658 printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d\n",
659 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
660 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut));
661 }
662
663 PQueueFree(ctrl, &queue);
664
665 idxwspacefree(ctrl, nparts);
666 idxwspacefree(ctrl, nparts);
667 idxwspacefree(ctrl, nparts);
668 idxwspacefree(ctrl, nvtxs);
669 idxwspacefree(ctrl, nvtxs);
670
671 }
672
673