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