source: branches/numpy/pymetis/metis-4.0/Lib/kwayfm.c @ 6971

Last change on this file since 6971 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.
File size: 21.0 KB
Line 
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**************************************************************************/
19void 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**************************************************************************/
222void 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**************************************************************************/
452void 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
Note: See TracBrowser for help on using the repository browser.