Charm++: Charm Source Code Documentation

00001 /*
00002  * kwayfm.c
00003  *
00004  * This file contains code that implements the multilevel k-way refinement
00005  *
00006  * Started 7/28/97
00007  * George
00008  *
00009  * $Id$
00010  *
00011  */
00012 
00013 #include <metis.h>
00014 
00015 
00016 /*************************************************************************
00017 * This function performs k-way refinement
00018 **************************************************************************/
00019 void Random_KWayEdgeRefine(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor, int npasses, int ffactor)
00020 {
00021   int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees; 
00022   int from, me, to, oldcut, vwgt, gain;
00023   idxtype *xadj, *adjncy, *adjwgt;
00024   idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
00025   EDegreeType *myedegrees;
00026   RInfoType *myrinfo;
00027 
00028   nvtxs = graph->nvtxs;
00029   xadj = graph->xadj;
00030   adjncy = graph->adjncy;
00031   adjwgt = graph->adjwgt;
00032 
00033   bndptr = graph->bndptr;
00034   bndind = graph->bndind;
00035 
00036   where = graph->where;
00037   pwgts = graph->pwgts;
00038   
00039   /* Setup the weight intervals of the various subdomains */
00040   minwgt =  idxwspacemalloc(ctrl, nparts);
00041   maxwgt = idxwspacemalloc(ctrl, nparts);
00042   itpwgts = idxwspacemalloc(ctrl, nparts);
00043   tvwgt = idxsum(nparts, pwgts);
00044   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00045 
00046   for (i=0; i<nparts; i++) {
00047     itpwgts[i] = tpwgts[i]*tvwgt;
00048     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00049     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00050   }
00051 
00052   perm = idxwspacemalloc(ctrl, nvtxs);
00053 
00054   IFSET(ctrl->dbglvl, DBG_REFINE,
00055      printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
00056              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00057              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00058              graph->mincut));
00059 
00060   for (pass=0; pass<npasses; pass++) {
00061     ASSERT(ComputeCut(graph, where) == graph->mincut);
00062 
00063     oldcut = graph->mincut;
00064     nbnd = graph->nbnd;
00065 
00066     RandomPermute(nbnd, perm, 1);
00067     for (nmoves=iii=0; iii<graph->nbnd; iii++) {
00068       ii = perm[iii];
00069       if (ii >= nbnd)
00070         continue;
00071       i = bndind[ii];
00072 
00073       myrinfo = graph->rinfo+i;
00074 
00075       if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */
00076         from = where[i];
00077         vwgt = graph->vwgt[i];
00078 
00079         if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from]) 
00080           continue;   /* This cannot be moved! */
00081 
00082         myedegrees = myrinfo->edegrees;
00083         myndegrees = myrinfo->ndegrees;
00084 
00085         j = myrinfo->id;
00086         for (k=0; k<myndegrees; k++) {
00087           to = myedegrees[k].pid;
00088           gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */ 
00089           if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0)  
00090             break;
00091         }
00092         if (k == myndegrees)
00093           continue;  /* break out if you did not find a candidate */
00094 
00095         for (j=k+1; j<myndegrees; j++) {
00096           to = myedegrees[j].pid;
00097           if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
00098               (myedegrees[j].ed == myedegrees[k].ed && 
00099                itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
00100             k = j;
00101         }
00102 
00103         to = myedegrees[k].pid;
00104 
00105         j = 0;
00106         if (myedegrees[k].ed-myrinfo->id > 0)
00107           j = 1;
00108         else if (myedegrees[k].ed-myrinfo->id == 0) {
00109           if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
00110             j = 1;
00111         }
00112         if (j == 0)
00113           continue;
00114           
00115         /*=====================================================================
00116         * If we got here, we can now move the vertex from 'from' to 'to' 
00117         *======================================================================*/
00118         graph->mincut -= myedegrees[k].ed-myrinfo->id;
00119 
00120         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));
00121 
00122         /* Update where, weight, and ID/ED information of the vertex you moved */
00123         where[i] = to;
00124         INC_DEC(pwgts[to], pwgts[from], vwgt);
00125         myrinfo->ed += myrinfo->id-myedegrees[k].ed;
00126         SWAP(myrinfo->id, myedegrees[k].ed, j);
00127         if (myedegrees[k].ed == 0) 
00128           myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00129         else
00130           myedegrees[k].pid = from;
00131 
00132         if (myrinfo->ed-myrinfo->id < 0)
00133           BNDDelete(nbnd, bndind, bndptr, i);
00134 
00135         /* Update the degrees of adjacent vertices */
00136         for (j=xadj[i]; j<xadj[i+1]; j++) {
00137           ii = adjncy[j];
00138           me = where[ii];
00139 
00140           myrinfo = graph->rinfo+ii;
00141           if (myrinfo->edegrees == NULL) {
00142             myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00143             ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
00144           }
00145           myedegrees = myrinfo->edegrees;
00146 
00147           ASSERT(CheckRInfo(myrinfo));
00148 
00149           if (me == from) {
00150             INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00151 
00152             if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
00153               BNDInsert(nbnd, bndind, bndptr, ii);
00154           }
00155           else if (me == to) {
00156             INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00157 
00158             if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
00159               BNDDelete(nbnd, bndind, bndptr, ii);
00160           }
00161 
00162           /* Remove contribution from the .ed of 'from' */
00163           if (me != from) {
00164             for (k=0; k<myrinfo->ndegrees; k++) {
00165               if (myedegrees[k].pid == from) {
00166                 if (myedegrees[k].ed == adjwgt[j])
00167                   myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00168                 else
00169                   myedegrees[k].ed -= adjwgt[j];
00170                 break;
00171               }
00172             }
00173           }
00174 
00175           /* Add contribution to the .ed of 'to' */
00176           if (me != to) {
00177             for (k=0; k<myrinfo->ndegrees; k++) {
00178               if (myedegrees[k].pid == to) {
00179                 myedegrees[k].ed += adjwgt[j];
00180                 break;
00181               }
00182             }
00183             if (k == myrinfo->ndegrees) {
00184               myedegrees[myrinfo->ndegrees].pid = to;
00185               myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
00186             }
00187           }
00188 
00189           ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
00190           ASSERT(CheckRInfo(myrinfo));
00191 
00192         }
00193         nmoves++;
00194       }
00195     }
00196 
00197     graph->nbnd = nbnd;
00198 
00199     IFSET(ctrl->dbglvl, DBG_REFINE,
00200        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
00201                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00202                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut, ComputeVolume(graph, where)));
00203 
00204     if (graph->mincut == oldcut)
00205       break;
00206   }
00207 
00208   idxwspacefree(ctrl, nparts);
00209   idxwspacefree(ctrl, nparts);
00210   idxwspacefree(ctrl, nparts);
00211   idxwspacefree(ctrl, nvtxs);
00212 }
00213 
00214 
00215 
00216 
00217 
00218 
00219 /*************************************************************************
00220 * This function performs k-way refinement
00221 **************************************************************************/
00222 void Greedy_KWayEdgeRefine(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor, int npasses)
00223 {
00224   int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain; 
00225   int from, me, to, oldcut, vwgt;
00226   idxtype *xadj, *adjncy, *adjwgt;
00227   idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
00228   EDegreeType *myedegrees;
00229   RInfoType *myrinfo;
00230   PQueueType queue;
00231 
00232   nvtxs = graph->nvtxs;
00233   xadj = graph->xadj;
00234   adjncy = graph->adjncy;
00235   adjwgt = graph->adjwgt;
00236 
00237   bndind = graph->bndind;
00238   bndptr = graph->bndptr;
00239 
00240   where = graph->where;
00241   pwgts = graph->pwgts;
00242   
00243   /* Setup the weight intervals of the various subdomains */
00244   minwgt =  idxwspacemalloc(ctrl, nparts);
00245   maxwgt = idxwspacemalloc(ctrl, nparts);
00246   itpwgts = idxwspacemalloc(ctrl, nparts);
00247   tvwgt = idxsum(nparts, pwgts);
00248   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00249 
00250   for (i=0; i<nparts; i++) {
00251     itpwgts[i] = tpwgts[i]*tvwgt;
00252     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00253     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00254   }
00255 
00256   perm = idxwspacemalloc(ctrl, nvtxs);
00257   moved = idxwspacemalloc(ctrl, nvtxs);
00258 
00259   PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
00260 
00261   IFSET(ctrl->dbglvl, DBG_REFINE,
00262      printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
00263              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00264              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00265              graph->mincut));
00266 
00267   for (pass=0; pass<npasses; pass++) {
00268     ASSERT(ComputeCut(graph, where) == graph->mincut);
00269 
00270     PQueueReset(&queue);
00271     idxset(nvtxs, -1, moved);
00272 
00273     oldcut = graph->mincut;
00274     nbnd = graph->nbnd;
00275 
00276     RandomPermute(nbnd, perm, 1);
00277     for (ii=0; ii<nbnd; ii++) {
00278       i = bndind[perm[ii]];
00279       PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
00280       moved[i] = 2;
00281     }
00282 
00283     for (iii=0;;iii++) {
00284       if ((i = PQueueGetMax(&queue)) == -1) 
00285         break;
00286       moved[i] = 1;
00287 
00288       myrinfo = graph->rinfo+i;
00289       from = where[i];
00290       vwgt = graph->vwgt[i];
00291 
00292       if (pwgts[from]-vwgt < minwgt[from]) 
00293         continue;   /* This cannot be moved! */
00294 
00295       myedegrees = myrinfo->edegrees;
00296       myndegrees = myrinfo->ndegrees;
00297 
00298       j = myrinfo->id;
00299       for (k=0; k<myndegrees; k++) {
00300         to = myedegrees[k].pid;
00301         gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */ 
00302         if (pwgts[to]+vwgt <= maxwgt[to]+gain && gain >= 0)  
00303           break;
00304       }
00305       if (k == myndegrees)
00306         continue;  /* break out if you did not find a candidate */
00307 
00308       for (j=k+1; j<myndegrees; j++) {
00309         to = myedegrees[j].pid;
00310         if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
00311             (myedegrees[j].ed == myedegrees[k].ed && 
00312              itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
00313           k = j;
00314       }
00315 
00316       to = myedegrees[k].pid;
00317 
00318       j = 0;
00319       if (myedegrees[k].ed-myrinfo->id > 0)
00320         j = 1;
00321       else if (myedegrees[k].ed-myrinfo->id == 0) {
00322         if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
00323           j = 1;
00324       }
00325       if (j == 0)
00326         continue;
00327           
00328       /*=====================================================================
00329       * If we got here, we can now move the vertex from 'from' to 'to' 
00330       *======================================================================*/
00331       graph->mincut -= myedegrees[k].ed-myrinfo->id;
00332 
00333       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));
00334 
00335       /* Update where, weight, and ID/ED information of the vertex you moved */
00336       where[i] = to;
00337       INC_DEC(pwgts[to], pwgts[from], vwgt);
00338       myrinfo->ed += myrinfo->id-myedegrees[k].ed;
00339       SWAP(myrinfo->id, myedegrees[k].ed, j);
00340       if (myedegrees[k].ed == 0) 
00341         myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00342       else
00343         myedegrees[k].pid = from;
00344 
00345       if (myrinfo->ed < myrinfo->id)
00346         BNDDelete(nbnd, bndind, bndptr, i);
00347 
00348       /* Update the degrees of adjacent vertices */
00349       for (j=xadj[i]; j<xadj[i+1]; j++) {
00350         ii = adjncy[j];
00351         me = where[ii];
00352 
00353         myrinfo = graph->rinfo+ii;
00354         if (myrinfo->edegrees == NULL) {
00355           myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00356           ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
00357         }
00358         myedegrees = myrinfo->edegrees;
00359 
00360         ASSERT(CheckRInfo(myrinfo));
00361 
00362         oldgain = (myrinfo->ed-myrinfo->id);
00363 
00364         if (me == from) {
00365           INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00366 
00367           if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
00368             BNDInsert(nbnd, bndind, bndptr, ii);
00369         }
00370         else if (me == to) {
00371           INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00372 
00373           if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
00374             BNDDelete(nbnd, bndind, bndptr, ii);
00375         }
00376 
00377         /* Remove contribution from the .ed of 'from' */
00378         if (me != from) {
00379           for (k=0; k<myrinfo->ndegrees; k++) {
00380             if (myedegrees[k].pid == from) {
00381               if (myedegrees[k].ed == adjwgt[j])
00382                 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00383               else
00384                 myedegrees[k].ed -= adjwgt[j];
00385               break;
00386             }
00387           }
00388         }
00389 
00390         /* Add contribution to the .ed of 'to' */
00391         if (me != to) {
00392           for (k=0; k<myrinfo->ndegrees; k++) {
00393             if (myedegrees[k].pid == to) {
00394               myedegrees[k].ed += adjwgt[j];
00395               break;
00396             }
00397           }
00398           if (k == myrinfo->ndegrees) {
00399             myedegrees[myrinfo->ndegrees].pid = to;
00400             myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
00401           }
00402         }
00403 
00404         /* Update the queue */
00405         if (me == to || me == from) { 
00406           gain = myrinfo->ed-myrinfo->id;
00407           if (moved[ii] == 2) {
00408             if (gain >= 0)
00409               PQueueUpdate(&queue, ii, oldgain, gain);
00410             else {
00411               PQueueDelete(&queue, ii, oldgain);
00412               moved[ii] = -1;
00413             }
00414           }
00415           else if (moved[ii] == -1 && gain >= 0) {
00416             PQueueInsert(&queue, ii, gain);
00417             moved[ii] = 2;
00418           }
00419         } 
00420 
00421         ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
00422         ASSERT(CheckRInfo(myrinfo));
00423 
00424       }
00425     }
00426 
00427     graph->nbnd = nbnd;
00428 
00429     IFSET(ctrl->dbglvl, DBG_REFINE,
00430        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Cut: %6d\n",
00431                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00432                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, graph->mincut));
00433 
00434     if (graph->mincut == oldcut)
00435       break;
00436   }
00437 
00438   PQueueFree(ctrl, &queue);
00439 
00440   idxwspacefree(ctrl, nparts);
00441   idxwspacefree(ctrl, nparts);
00442   idxwspacefree(ctrl, nparts);
00443   idxwspacefree(ctrl, nvtxs);
00444   idxwspacefree(ctrl, nvtxs);
00445 
00446 }
00447 
00448 
00449 /*************************************************************************
00450 * This function performs k-way refinement
00451 **************************************************************************/
00452 void Greedy_KWayEdgeBalance(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor, int npasses)
00453 {
00454   int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves; 
00455   int from, me, to, oldcut, vwgt;
00456   idxtype *xadj, *adjncy, *adjwgt;
00457   idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
00458   EDegreeType *myedegrees;
00459   RInfoType *myrinfo;
00460   PQueueType queue;
00461 
00462   nvtxs = graph->nvtxs;
00463   xadj = graph->xadj;
00464   adjncy = graph->adjncy;
00465   adjwgt = graph->adjwgt;
00466 
00467   bndind = graph->bndind;
00468   bndptr = graph->bndptr;
00469 
00470   where = graph->where;
00471   pwgts = graph->pwgts;
00472   
00473   /* Setup the weight intervals of the various subdomains */
00474   minwgt =  idxwspacemalloc(ctrl, nparts);
00475   maxwgt = idxwspacemalloc(ctrl, nparts);
00476   itpwgts = idxwspacemalloc(ctrl, nparts);
00477   tvwgt = idxsum(nparts, pwgts);
00478   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00479 
00480   for (i=0; i<nparts; i++) {
00481     itpwgts[i] = tpwgts[i]*tvwgt;
00482     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00483     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00484   }
00485 
00486   perm = idxwspacemalloc(ctrl, nvtxs);
00487   moved = idxwspacemalloc(ctrl, nvtxs);
00488 
00489   PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
00490 
00491   IFSET(ctrl->dbglvl, DBG_REFINE,
00492      printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
00493              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00494              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00495              graph->mincut));
00496 
00497   for (pass=0; pass<npasses; pass++) {
00498     ASSERT(ComputeCut(graph, where) == graph->mincut);
00499 
00500     /* Check to see if things are out of balance, given the tolerance */
00501     for (i=0; i<nparts; i++) {
00502       if (pwgts[i] > maxwgt[i])
00503         break;
00504     }
00505     if (i == nparts) /* Things are balanced. Return right away */
00506       break;
00507 
00508     PQueueReset(&queue);
00509     idxset(nvtxs, -1, moved);
00510 
00511     oldcut = graph->mincut;
00512     nbnd = graph->nbnd;
00513 
00514     RandomPermute(nbnd, perm, 1);
00515     for (ii=0; ii<nbnd; ii++) {
00516       i = bndind[perm[ii]];
00517       PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
00518       moved[i] = 2;
00519     }
00520 
00521     nmoves = 0;
00522     for (;;) {
00523       if ((i = PQueueGetMax(&queue)) == -1) 
00524         break;
00525       moved[i] = 1;
00526 
00527       myrinfo = graph->rinfo+i;
00528       from = where[i];
00529       vwgt = graph->vwgt[i];
00530 
00531       if (pwgts[from]-vwgt < minwgt[from]) 
00532         continue;   /* This cannot be moved! */
00533 
00534       myedegrees = myrinfo->edegrees;
00535       myndegrees = myrinfo->ndegrees;
00536 
00537       for (k=0; k<myndegrees; k++) {
00538         to = myedegrees[k].pid;
00539         if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from]) 
00540           break;
00541       }
00542       if (k == myndegrees)
00543         continue;  /* break out if you did not find a candidate */
00544 
00545       for (j=k+1; j<myndegrees; j++) {
00546         to = myedegrees[j].pid;
00547         if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]) 
00548           k = j;
00549       }
00550 
00551       to = myedegrees[k].pid;
00552 
00553       if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->id < 0) 
00554         continue;
00555 
00556       /*=====================================================================
00557       * If we got here, we can now move the vertex from 'from' to 'to' 
00558       *======================================================================*/
00559       graph->mincut -= myedegrees[k].ed-myrinfo->id;
00560 
00561       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));
00562 
00563       /* Update where, weight, and ID/ED information of the vertex you moved */
00564       where[i] = to;
00565       INC_DEC(pwgts[to], pwgts[from], vwgt);
00566       myrinfo->ed += myrinfo->id-myedegrees[k].ed;
00567       SWAP(myrinfo->id, myedegrees[k].ed, j);
00568       if (myedegrees[k].ed == 0) 
00569         myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00570       else
00571         myedegrees[k].pid = from;
00572 
00573       if (myrinfo->ed == 0)
00574         BNDDelete(nbnd, bndind, bndptr, i);
00575 
00576       /* Update the degrees of adjacent vertices */
00577       for (j=xadj[i]; j<xadj[i+1]; j++) {
00578         ii = adjncy[j];
00579         me = where[ii];
00580 
00581         myrinfo = graph->rinfo+ii;
00582         if (myrinfo->edegrees == NULL) {
00583           myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00584           ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
00585         }
00586         myedegrees = myrinfo->edegrees;
00587 
00588         ASSERT(CheckRInfo(myrinfo));
00589 
00590         oldgain = (myrinfo->ed-myrinfo->id);
00591 
00592         if (me == from) {
00593           INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00594 
00595           if (myrinfo->ed > 0 && bndptr[ii] == -1)
00596             BNDInsert(nbnd, bndind, bndptr, ii);
00597         }
00598         else if (me == to) {
00599           INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00600 
00601           if (myrinfo->ed == 0 && bndptr[ii] != -1)
00602             BNDDelete(nbnd, bndind, bndptr, ii);
00603         }
00604 
00605         /* Remove contribution from the .ed of 'from' */
00606         if (me != from) {
00607           for (k=0; k<myrinfo->ndegrees; k++) {
00608             if (myedegrees[k].pid == from) {
00609               if (myedegrees[k].ed == adjwgt[j])
00610                 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00611               else
00612                 myedegrees[k].ed -= adjwgt[j];
00613               break;
00614             }
00615           }
00616         }
00617 
00618         /* Add contribution to the .ed of 'to' */
00619         if (me != to) {
00620           for (k=0; k<myrinfo->ndegrees; k++) {
00621             if (myedegrees[k].pid == to) {
00622               myedegrees[k].ed += adjwgt[j];
00623               break;
00624             }
00625           }
00626           if (k == myrinfo->ndegrees) {
00627             myedegrees[myrinfo->ndegrees].pid = to;
00628             myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
00629           }
00630         }
00631 
00632         /* Update the queue */
00633         if (me == to || me == from) { 
00634           gain = myrinfo->ed-myrinfo->id;
00635           if (moved[ii] == 2) {
00636             if (myrinfo->ed > 0)
00637               PQueueUpdate(&queue, ii, oldgain, gain);
00638             else {
00639               PQueueDelete(&queue, ii, oldgain);
00640               moved[ii] = -1;
00641             }
00642           }
00643           else if (moved[ii] == -1 && myrinfo->ed > 0) {
00644             PQueueInsert(&queue, ii, gain);
00645             moved[ii] = 2;
00646           }
00647         } 
00648 
00649         ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
00650         ASSERT(CheckRInfo(myrinfo));
00651       }
00652       nmoves++;
00653     }
00654 
00655     graph->nbnd = nbnd;
00656 
00657     IFSET(ctrl->dbglvl, DBG_REFINE,
00658        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d\n",
00659                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00660                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut));
00661   }
00662 
00663   PQueueFree(ctrl, &queue);
00664 
00665   idxwspacefree(ctrl, nparts);
00666   idxwspacefree(ctrl, nparts);
00667   idxwspacefree(ctrl, nparts);
00668   idxwspacefree(ctrl, nvtxs);
00669   idxwspacefree(ctrl, nvtxs);
00670 
00671 }
00672
libs/ck-libs/parmetis/METISLib/kwayfm.c
