Charm++: Charm Source Code Documentation

00001 /*
00002  * kwayvolfm.c
00003  *
00004  * This file contains code that implements the multilevel k-way refinement
00005  *
00006  * Started 7/8/98
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_KWayVolRefine(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, 
00020                           floattype ubfactor, int npasses, int ffactor)
00021 {
00022   int i, ii, iii, j, jj, k, kk, l, u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain; 
00023   int from, me, to, oldcut, oldvol, vwgt;
00024   idxtype *xadj, *adjncy, *adjwgt;
00025   idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
00026   VEDegreeType *myedegrees;
00027   VRInfoType *myrinfo; 
00028 
00029   nvtxs = graph->nvtxs;
00030   xadj = graph->xadj;
00031   adjncy = graph->adjncy;
00032   adjwgt = graph->adjwgt;
00033 
00034   bndptr = graph->bndptr;
00035   bndind = graph->bndind;
00036 
00037   where = graph->where;
00038   pwgts = graph->pwgts;
00039   
00040   /* Setup the weight intervals of the various subdomains */
00041   minwgt =  idxwspacemalloc(ctrl, nparts);
00042   maxwgt = idxwspacemalloc(ctrl, nparts);
00043   itpwgts = idxwspacemalloc(ctrl, nparts);
00044   tvwgt = idxsum(nparts, pwgts);
00045   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00046 
00047   updind = idxmalloc(nvtxs, "Random_KWayVolRefine: updind");
00048   marker = idxsmalloc(nvtxs, 0, "Random_KWayVolRefine: marker");
00049   phtable = idxsmalloc(nparts, -1, "Random_KWayVolRefine: phtable");
00050 
00051   for (i=0; i<nparts; i++) {
00052     itpwgts[i] = tpwgts[i]*tvwgt;
00053     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00054     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00055   }
00056 
00057   perm = idxwspacemalloc(ctrl, nvtxs);
00058 
00059   IFSET(ctrl->dbglvl, DBG_REFINE,
00060      printf("VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d\n",
00061              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00062              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00063              graph->mincut, graph->minvol));
00064 
00065   for (pass=0; pass<npasses; pass++) {
00066     ASSERT(ComputeCut(graph, where) == graph->mincut);
00067 
00068     oldcut = graph->mincut;
00069     oldvol = graph->minvol;
00070 
00071     RandomPermute(graph->nbnd, perm, 1);
00072     for (nmoves=iii=0; iii<graph->nbnd; iii++) {
00073       ii = perm[iii];
00074       if (ii >= graph->nbnd)
00075         continue;
00076       i = bndind[ii];
00077       myrinfo = graph->vrinfo+i;
00078 
00079       if (myrinfo->gv >= 0) { /* Total volume gain is too high */
00080         from = where[i];
00081         vwgt = graph->vwgt[i];
00082 
00083         if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from]) 
00084           continue;   /* This cannot be moved! */
00085 
00086         xgain = (myrinfo->id == 0 && myrinfo->ed > 0 ? graph->vsize[i] : 0);
00087 
00088         myedegrees = myrinfo->edegrees;
00089         myndegrees = myrinfo->ndegrees;
00090 
00091         for (k=0; k<myndegrees; k++) {
00092           to = myedegrees[k].pid;
00093           if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*myedegrees[k].gv && xgain+myedegrees[k].gv >= 0)  
00094             break;
00095         }
00096         if (k == myndegrees)
00097           continue;  /* break out if you did not find a candidate */
00098 
00099         for (j=k+1; j<myndegrees; j++) {
00100           to = myedegrees[j].pid;
00101           if (pwgts[to]+vwgt > maxwgt[to])
00102             continue;
00103           if (myedegrees[j].gv > myedegrees[k].gv ||
00104               (myedegrees[j].gv == myedegrees[k].gv && myedegrees[j].ed > myedegrees[k].ed) ||
00105               (myedegrees[j].gv == myedegrees[k].gv && myedegrees[j].ed == myedegrees[k].ed &&
00106                itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
00107             k = j;
00108         }
00109 
00110         to = myedegrees[k].pid;
00111 
00112         j = 0;
00113         if (xgain+myedegrees[k].gv > 0 || myedegrees[k].ed-myrinfo->id > 0)
00114           j = 1;
00115         else if (myedegrees[k].ed-myrinfo->id == 0) {
00116           if ((iii&5) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
00117             j = 1;
00118         }
00119         if (j == 0)
00120           continue;
00121           
00122         /*=====================================================================
00123         * If we got here, we can now move the vertex from 'from' to 'to' 
00124         *======================================================================*/
00125         INC_DEC(pwgts[to], pwgts[from], vwgt);
00126         graph->mincut -= myedegrees[k].ed-myrinfo->id;
00127         graph->minvol -= (xgain+myedegrees[k].gv);
00128         where[i] = to;
00129 
00130         IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n", 
00131               i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->id, graph->mincut, graph->minvol));
00132 
00133         KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
00134 
00135         nmoves++;
00136 
00137         /* CheckVolKWayPartitionParams(ctrl, graph, nparts); */
00138       }
00139     }
00140 
00141     IFSET(ctrl->dbglvl, DBG_REFINE,
00142        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
00143                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00144                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut, 
00145                graph->minvol));
00146 
00147     if (graph->minvol == oldvol && graph->mincut == oldcut)
00148       break;
00149   }
00150 
00151   GKfree(&marker, &updind, &phtable, LTERM);
00152 
00153   idxwspacefree(ctrl, nparts);
00154   idxwspacefree(ctrl, nparts);
00155   idxwspacefree(ctrl, nparts);
00156   idxwspacefree(ctrl, nvtxs);
00157 }
00158 
00159 
00160 /*************************************************************************
00161 * This function performs k-way refinement
00162 **************************************************************************/
00163 void Random_KWayVolRefineMConn(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, 
00164             floattype ubfactor, int npasses, int ffactor)
00165 {
00166   int i, ii, iii, j, jj, k, kk, l, u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain; 
00167   int from, me, to, oldcut, oldvol, vwgt, nadd, maxndoms;
00168   idxtype *xadj, *adjncy, *adjwgt;
00169   idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
00170   idxtype *pmat, *pmatptr, *ndoms;
00171   VEDegreeType *myedegrees;
00172   VRInfoType *myrinfo; 
00173 
00174   nvtxs = graph->nvtxs;
00175   xadj = graph->xadj;
00176   adjncy = graph->adjncy;
00177   adjwgt = graph->adjwgt;
00178 
00179   bndptr = graph->bndptr;
00180   bndind = graph->bndind;
00181 
00182   where = graph->where;
00183   pwgts = graph->pwgts;
00184   
00185   /* Setup the weight intervals of the various subdomains */
00186   minwgt =  idxwspacemalloc(ctrl, nparts);
00187   maxwgt = idxwspacemalloc(ctrl, nparts);
00188   itpwgts = idxwspacemalloc(ctrl, nparts);
00189   tvwgt = idxsum(nparts, pwgts);
00190   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00191 
00192   updind = idxmalloc(nvtxs, "Random_KWayVolRefine: updind");
00193   marker = idxsmalloc(nvtxs, 0, "Random_KWayVolRefine: marker");
00194   phtable = idxsmalloc(nparts, -1, "Random_KWayVolRefine: phtable");
00195 
00196   pmat = ctrl->wspace.pmat;
00197   ndoms = idxwspacemalloc(ctrl, nparts);
00198 
00199   ComputeVolSubDomainGraph(graph, nparts, pmat, ndoms);
00200 
00201   for (i=0; i<nparts; i++) {
00202     itpwgts[i] = tpwgts[i]*tvwgt;
00203     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00204     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00205   }
00206 
00207   perm = idxwspacemalloc(ctrl, nvtxs);
00208 
00209   IFSET(ctrl->dbglvl, DBG_REFINE,
00210      printf("VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d\n",
00211              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00212              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00213              graph->mincut, graph->minvol));
00214 
00215   for (pass=0; pass<npasses; pass++) {
00216     ASSERT(ComputeCut(graph, where) == graph->mincut);
00217 
00218     maxndoms = ndoms[idxamax(nparts, ndoms)];
00219 
00220     oldcut = graph->mincut;
00221     oldvol = graph->minvol;
00222 
00223     RandomPermute(graph->nbnd, perm, 1);
00224     for (nmoves=iii=0; iii<graph->nbnd; iii++) {
00225       ii = perm[iii];
00226       if (ii >= graph->nbnd)
00227         continue;
00228       i = bndind[ii];
00229       myrinfo = graph->vrinfo+i;
00230 
00231       if (myrinfo->gv >= 0) { /* Total volume gain is too high */
00232         from = where[i];
00233         vwgt = graph->vwgt[i];
00234 
00235         if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from]) 
00236           continue;   /* This cannot be moved! */
00237 
00238         xgain = (myrinfo->id == 0 && myrinfo->ed > 0 ? graph->vsize[i] : 0);
00239 
00240         myedegrees = myrinfo->edegrees;
00241         myndegrees = myrinfo->ndegrees;
00242 
00243         /* Determine the valid domains */
00244         for (j=0; j<myndegrees; j++) {
00245           to = myedegrees[j].pid;
00246           phtable[to] = 1;
00247           pmatptr = pmat + to*nparts;
00248           for (nadd=0, k=0; k<myndegrees; k++) {
00249             if (k == j)
00250               continue;
00251 
00252             l = myedegrees[k].pid;
00253             if (pmatptr[l] == 0) {
00254               if (ndoms[l] > maxndoms-1) {
00255                 phtable[to] = 0;
00256                 nadd = maxndoms;
00257                 break;
00258               }
00259               nadd++;
00260             }
00261           }
00262           if (ndoms[to]+nadd > maxndoms)
00263             phtable[to] = 0;
00264           if (nadd == 0)
00265             phtable[to] = 2;
00266         }
00267 
00268         for (k=0; k<myndegrees; k++) {
00269           to = myedegrees[k].pid;
00270           if (!phtable[to])
00271             continue;
00272           if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*myedegrees[k].gv && xgain+myedegrees[k].gv >= 0)  
00273             break;
00274         }
00275         if (k == myndegrees)
00276           continue;  /* break out if you did not find a candidate */
00277 
00278         for (j=k+1; j<myndegrees; j++) {
00279           to = myedegrees[j].pid;
00280           if (!phtable[to] || pwgts[to]+vwgt > maxwgt[to])
00281             continue;
00282           if (myedegrees[j].gv > myedegrees[k].gv ||
00283               (myedegrees[j].gv == myedegrees[k].gv && myedegrees[j].ed > myedegrees[k].ed) ||
00284               (myedegrees[j].gv == myedegrees[k].gv && myedegrees[j].ed == myedegrees[k].ed &&
00285                itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
00286             k = j;
00287         }
00288 
00289         to = myedegrees[k].pid;
00290 
00291         j = 0;
00292         if (xgain+myedegrees[k].gv > 0 || myedegrees[k].ed-myrinfo->id > 0)
00293           j = 1;
00294         else if (myedegrees[k].ed-myrinfo->id == 0) {
00295           if ((iii&5) == 0 || phtable[myedegrees[k].pid] == 2 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
00296             j = 1;
00297         }
00298 
00299         if (j == 0)
00300           continue;
00301 
00302         for (j=0; j<myndegrees; j++) 
00303           phtable[myedegrees[j].pid] = -1;
00304 
00305           
00306         /*=====================================================================
00307         * If we got here, we can now move the vertex from 'from' to 'to' 
00308         *======================================================================*/
00309         INC_DEC(pwgts[to], pwgts[from], vwgt);
00310         graph->mincut -= myedegrees[k].ed-myrinfo->id;
00311         graph->minvol -= (xgain+myedegrees[k].gv);
00312         where[i] = to;
00313 
00314         IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n", 
00315               i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->id, graph->mincut, graph->minvol));
00316 
00317         /* Update pmat to reflect the move of 'i' */
00318         pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
00319         pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
00320         if (pmat[from*nparts+to] == 0) {
00321           ndoms[from]--;
00322           if (ndoms[from]+1 == maxndoms)
00323             maxndoms = ndoms[idxamax(nparts, ndoms)];
00324         }
00325         if (pmat[to*nparts+from] == 0) {
00326           ndoms[to]--;
00327           if (ndoms[to]+1 == maxndoms)
00328             maxndoms = ndoms[idxamax(nparts, ndoms)];
00329         }
00330 
00331         for (j=xadj[i]; j<xadj[i+1]; j++) {
00332           ii = adjncy[j];
00333           me = where[ii];
00334 
00335           /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
00336           if (me != from && me != to) {
00337             pmat[me*nparts+from] -= adjwgt[j];
00338             pmat[from*nparts+me] -= adjwgt[j];
00339             if (pmat[me*nparts+from] == 0) {
00340               ndoms[me]--;
00341               if (ndoms[me]+1 == maxndoms)
00342                 maxndoms = ndoms[idxamax(nparts, ndoms)];
00343             }
00344             if (pmat[from*nparts+me] == 0) {
00345               ndoms[from]--;
00346               if (ndoms[from]+1 == maxndoms)
00347                 maxndoms = ndoms[idxamax(nparts, ndoms)];
00348             }
00349 
00350             if (pmat[me*nparts+to] == 0) {
00351               ndoms[me]++;
00352               if (ndoms[me] > maxndoms) {
00353                 IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms));
00354                 maxndoms = ndoms[me];
00355               }
00356             }
00357             if (pmat[to*nparts+me] == 0) {
00358               ndoms[to]++;
00359               if (ndoms[to] > maxndoms) {
00360                 IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms));
00361                 maxndoms = ndoms[to];
00362               }
00363             }
00364             pmat[me*nparts+to] += adjwgt[j];
00365             pmat[to*nparts+me] += adjwgt[j];
00366           }
00367         }
00368 
00369         KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
00370 
00371         nmoves++;
00372 
00373         /* CheckVolKWayPartitionParams(ctrl, graph, nparts); */
00374       }
00375     }
00376 
00377     IFSET(ctrl->dbglvl, DBG_REFINE,
00378        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
00379                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00380                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut, 
00381                graph->minvol));
00382 
00383     if (graph->minvol == oldvol && graph->mincut == oldcut)
00384       break;
00385   }
00386 
00387   GKfree(&marker, &updind, &phtable, LTERM);
00388 
00389   idxwspacefree(ctrl, nparts);
00390   idxwspacefree(ctrl, nparts);
00391   idxwspacefree(ctrl, nparts);
00392   idxwspacefree(ctrl, nparts);
00393   idxwspacefree(ctrl, nvtxs);
00394 }
00395 
00396 
00397 
00398 
00399 /*************************************************************************
00400 * This function performs k-way refinement
00401 **************************************************************************/
00402 void Greedy_KWayVolBalance(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, 
00403                            floattype ubfactor, int npasses)
00404 {
00405   int i, ii, iii, j, jj, k, kk, l, u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain; 
00406   int from, me, to, vwgt, gain;
00407   idxtype *xadj, *adjncy, *adjwgt;
00408   idxtype *where, *pwgts, *perm, *moved, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
00409   VEDegreeType *myedegrees;
00410   VRInfoType *myrinfo; 
00411   PQueueType queue;
00412 
00413   nvtxs = graph->nvtxs;
00414   xadj = graph->xadj;
00415   adjncy = graph->adjncy;
00416   adjwgt = graph->adjwgt;
00417 
00418   bndptr = graph->bndptr;
00419   bndind = graph->bndind;
00420 
00421   where = graph->where;
00422   pwgts = graph->pwgts;
00423   
00424   /* Setup the weight intervals of the various subdomains */
00425   minwgt =  idxwspacemalloc(ctrl, nparts);
00426   maxwgt = idxwspacemalloc(ctrl, nparts);
00427   itpwgts = idxwspacemalloc(ctrl, nparts);
00428   tvwgt = idxsum(nparts, pwgts);
00429   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00430 
00431   updind = idxmalloc(nvtxs, "Random_KWayVolRefine: updind");
00432   marker = idxsmalloc(nvtxs, 0, "Random_KWayVolRefine: marker");
00433   phtable = idxsmalloc(nparts, -1, "Random_KWayVolRefine: phtable");
00434 
00435   for (i=0; i<nparts; i++) {
00436     itpwgts[i] = tpwgts[i]*tvwgt;
00437     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00438     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00439   }
00440 
00441   perm = idxwspacemalloc(ctrl, nvtxs);
00442   moved = idxwspacemalloc(ctrl, nvtxs);
00443 
00444   PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
00445 
00446   IFSET(ctrl->dbglvl, DBG_REFINE,
00447      printf("VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d [B]\n",
00448              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00449              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00450              graph->mincut, graph->minvol));
00451 
00452 
00453   for (pass=0; pass<npasses; pass++) {
00454     ASSERT(ComputeCut(graph, where) == graph->mincut);
00455     /* Check to see if things are out of balance, given the tolerance */
00456     for (i=0; i<nparts; i++) {
00457       if (pwgts[i] > maxwgt[i])
00458         break;
00459     }
00460     if (i == nparts) /* Things are balanced. Return right away */
00461       break;
00462 
00463     PQueueReset(&queue);
00464     idxset(nvtxs, -1, moved);
00465 
00466     RandomPermute(graph->nbnd, perm, 1);
00467     for (ii=0; ii<graph->nbnd; ii++) {
00468       i = bndind[perm[ii]];
00469       PQueueInsert(&queue, i, graph->vrinfo[i].gv);
00470       moved[i] = 2;
00471     }
00472 
00473     for (nmoves=0;;) {
00474       if ((i = PQueueGetMax(&queue)) == -1) 
00475         break;
00476       moved[i] = 1;
00477 
00478       myrinfo = graph->vrinfo+i;
00479       from = where[i];
00480       vwgt = graph->vwgt[i];
00481 
00482       if (pwgts[from]-vwgt < minwgt[from]) 
00483         continue;   /* This cannot be moved! */
00484 
00485       xgain = (myrinfo->id == 0 && myrinfo->ed > 0 ? graph->vsize[i] : 0);
00486 
00487       myedegrees = myrinfo->edegrees;
00488       myndegrees = myrinfo->ndegrees;
00489 
00490       for (k=0; k<myndegrees; k++) {
00491         to = myedegrees[k].pid;
00492         if (pwgts[to]+vwgt <= maxwgt[to] || 
00493             itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from]) 
00494           break;
00495       }
00496       if (k == myndegrees)
00497         continue;  /* break out if you did not find a candidate */
00498 
00499       for (j=k+1; j<myndegrees; j++) {
00500         to = myedegrees[j].pid;
00501         if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]) 
00502           k = j;
00503       }
00504 
00505       to = myedegrees[k].pid;
00506 
00507       if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && 
00508           (xgain+myedegrees[k].gv < 0 || 
00509            (xgain+myedegrees[k].gv == 0 &&  myedegrees[k].ed-myrinfo->id < 0))
00510          )
00511         continue;
00512   
00513 
00514       /*=====================================================================
00515       * If we got here, we can now move the vertex from 'from' to 'to' 
00516       *======================================================================*/
00517       INC_DEC(pwgts[to], pwgts[from], vwgt);
00518       graph->mincut -= myedegrees[k].ed-myrinfo->id;
00519       graph->minvol -= (xgain+myedegrees[k].gv);
00520       where[i] = to;
00521 
00522       IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n", 
00523             i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->id, graph->mincut, graph->minvol));
00524 
00525       KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
00526 
00527       nmoves++;
00528 
00529       /*CheckVolKWayPartitionParams(ctrl, graph, nparts); */
00530     }
00531 
00532     IFSET(ctrl->dbglvl, DBG_REFINE,
00533        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
00534                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00535                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut, 
00536                graph->minvol));
00537 
00538   }
00539 
00540   GKfree(&marker, &updind, &phtable, LTERM);
00541 
00542   PQueueFree(ctrl, &queue);
00543 
00544   idxwspacefree(ctrl, nparts);
00545   idxwspacefree(ctrl, nparts);
00546   idxwspacefree(ctrl, nparts);
00547   idxwspacefree(ctrl, nvtxs);
00548   idxwspacefree(ctrl, nvtxs);
00549 }
00550 
00551 
00552 
00553 /*************************************************************************
00554 * This function performs k-way refinement
00555 **************************************************************************/
00556 void Greedy_KWayVolBalanceMConn(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, 
00557                                 floattype ubfactor, int npasses)
00558 {
00559   int i, ii, iii, j, jj, k, kk, l, u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain; 
00560   int from, me, to, vwgt, gain, maxndoms, nadd;
00561   idxtype *xadj, *adjncy, *adjwgt;
00562   idxtype *where, *pwgts, *perm, *moved, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
00563   idxtype *pmat, *pmatptr, *ndoms;
00564   VEDegreeType *myedegrees;
00565   VRInfoType *myrinfo; 
00566   PQueueType queue;
00567 
00568   nvtxs = graph->nvtxs;
00569   xadj = graph->xadj;
00570   adjncy = graph->adjncy;
00571   adjwgt = graph->adjwgt;
00572 
00573   bndptr = graph->bndptr;
00574   bndind = graph->bndind;
00575 
00576   where = graph->where;
00577   pwgts = graph->pwgts;
00578   
00579   /* Setup the weight intervals of the various subdomains */
00580   minwgt =  idxwspacemalloc(ctrl, nparts);
00581   maxwgt = idxwspacemalloc(ctrl, nparts);
00582   itpwgts = idxwspacemalloc(ctrl, nparts);
00583   tvwgt = idxsum(nparts, pwgts);
00584   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00585 
00586   updind = idxmalloc(nvtxs, "Random_KWayVolRefine: updind");
00587   marker = idxsmalloc(nvtxs, 0, "Random_KWayVolRefine: marker");
00588   phtable = idxsmalloc(nparts, -1, "Random_KWayVolRefine: phtable");
00589 
00590   pmat = ctrl->wspace.pmat;
00591   ndoms = idxwspacemalloc(ctrl, nparts);
00592 
00593   ComputeVolSubDomainGraph(graph, nparts, pmat, ndoms);
00594 
00595   for (i=0; i<nparts; i++) {
00596     itpwgts[i] = tpwgts[i]*tvwgt;
00597     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00598     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00599   }
00600 
00601   perm = idxwspacemalloc(ctrl, nvtxs);
00602   moved = idxwspacemalloc(ctrl, nvtxs);
00603 
00604   PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
00605 
00606   IFSET(ctrl->dbglvl, DBG_REFINE,
00607      printf("VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d [B]\n",
00608              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00609              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00610              graph->mincut, graph->minvol));
00611 
00612 
00613   for (pass=0; pass<npasses; pass++) {
00614     ASSERT(ComputeCut(graph, where) == graph->mincut);
00615     /* Check to see if things are out of balance, given the tolerance */
00616     for (i=0; i<nparts; i++) {
00617       if (pwgts[i] > maxwgt[i])
00618         break;
00619     }
00620     if (i == nparts) /* Things are balanced. Return right away */
00621       break;
00622 
00623     PQueueReset(&queue);
00624     idxset(nvtxs, -1, moved);
00625 
00626     RandomPermute(graph->nbnd, perm, 1);
00627     for (ii=0; ii<graph->nbnd; ii++) {
00628       i = bndind[perm[ii]];
00629       PQueueInsert(&queue, i, graph->vrinfo[i].gv);
00630       moved[i] = 2;
00631     }
00632 
00633     maxndoms = ndoms[idxamax(nparts, ndoms)];
00634 
00635     for (nmoves=0;;) {
00636       if ((i = PQueueGetMax(&queue)) == -1) 
00637         break;
00638       moved[i] = 1;
00639 
00640       myrinfo = graph->vrinfo+i;
00641       from = where[i];
00642       vwgt = graph->vwgt[i];
00643 
00644       if (pwgts[from]-vwgt < minwgt[from]) 
00645         continue;   /* This cannot be moved! */
00646 
00647       xgain = (myrinfo->id == 0 && myrinfo->ed > 0 ? graph->vsize[i] : 0);
00648 
00649       myedegrees = myrinfo->edegrees;
00650       myndegrees = myrinfo->ndegrees;
00651 
00652       /* Determine the valid domains */
00653       for (j=0; j<myndegrees; j++) {
00654         to = myedegrees[j].pid;
00655         phtable[to] = 1;
00656         pmatptr = pmat + to*nparts;
00657         for (nadd=0, k=0; k<myndegrees; k++) {
00658           if (k == j)
00659             continue;
00660 
00661           l = myedegrees[k].pid;
00662           if (pmatptr[l] == 0) {
00663             if (ndoms[l] > maxndoms-1) {
00664               phtable[to] = 0;
00665               nadd = maxndoms;
00666               break;
00667             }
00668             nadd++;
00669           }
00670         }
00671         if (ndoms[to]+nadd > maxndoms)
00672           phtable[to] = 0;
00673       }
00674 
00675       for (k=0; k<myndegrees; k++) {
00676         to = myedegrees[k].pid;
00677         if (!phtable[to])
00678           continue;
00679         if (pwgts[to]+vwgt <= maxwgt[to] || 
00680             itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from]) 
00681           break;
00682       }
00683       if (k == myndegrees)
00684         continue;  /* break out if you did not find a candidate */
00685 
00686       for (j=k+1; j<myndegrees; j++) {
00687         to = myedegrees[j].pid;
00688         if (!phtable[to])
00689           continue;
00690         if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]) 
00691           k = j;
00692       }
00693 
00694       to = myedegrees[k].pid;
00695 
00696       for (j=0; j<myndegrees; j++) 
00697         phtable[myedegrees[j].pid] = -1;
00698 
00699       if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && 
00700           (xgain+myedegrees[k].gv < 0 || 
00701            (xgain+myedegrees[k].gv == 0 &&  myedegrees[k].ed-myrinfo->id < 0))
00702          )
00703         continue;
00704   
00705 
00706       /*=====================================================================
00707       * If we got here, we can now move the vertex from 'from' to 'to' 
00708       *======================================================================*/
00709       INC_DEC(pwgts[to], pwgts[from], vwgt);
00710       graph->mincut -= myedegrees[k].ed-myrinfo->id;
00711       graph->minvol -= (xgain+myedegrees[k].gv);
00712       where[i] = to;
00713 
00714       IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n", 
00715             i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->id, graph->mincut, graph->minvol));
00716 
00717       /* Update pmat to reflect the move of 'i' */
00718       pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
00719       pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
00720       if (pmat[from*nparts+to] == 0) {
00721         ndoms[from]--;
00722         if (ndoms[from]+1 == maxndoms)
00723           maxndoms = ndoms[idxamax(nparts, ndoms)];
00724       }
00725       if (pmat[to*nparts+from] == 0) {
00726         ndoms[to]--;
00727         if (ndoms[to]+1 == maxndoms)
00728           maxndoms = ndoms[idxamax(nparts, ndoms)];
00729       }
00730 
00731       for (j=xadj[i]; j<xadj[i+1]; j++) {
00732         ii = adjncy[j];
00733         me = where[ii];
00734 
00735         /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
00736         if (me != from && me != to) {
00737           pmat[me*nparts+from] -= adjwgt[j];
00738           pmat[from*nparts+me] -= adjwgt[j];
00739           if (pmat[me*nparts+from] == 0) {
00740             ndoms[me]--;
00741             if (ndoms[me]+1 == maxndoms)
00742               maxndoms = ndoms[idxamax(nparts, ndoms)];
00743           }
00744           if (pmat[from*nparts+me] == 0) {
00745             ndoms[from]--;
00746             if (ndoms[from]+1 == maxndoms)
00747               maxndoms = ndoms[idxamax(nparts, ndoms)];
00748           }
00749 
00750           if (pmat[me*nparts+to] == 0) {
00751             ndoms[me]++;
00752             if (ndoms[me] > maxndoms) {
00753               IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms));
00754               maxndoms = ndoms[me];
00755             }
00756           }
00757           if (pmat[to*nparts+me] == 0) {
00758             ndoms[to]++;
00759             if (ndoms[to] > maxndoms) {
00760               IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms));
00761               maxndoms = ndoms[to];
00762             }
00763           }
00764           pmat[me*nparts+to] += adjwgt[j];
00765           pmat[to*nparts+me] += adjwgt[j];
00766         }
00767       }
00768 
00769       KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
00770 
00771       nmoves++;
00772 
00773       /*CheckVolKWayPartitionParams(ctrl, graph, nparts); */
00774     }
00775 
00776     IFSET(ctrl->dbglvl, DBG_REFINE,
00777        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
00778                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00779                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut, 
00780                graph->minvol));
00781 
00782   }
00783 
00784   GKfree(&marker, &updind, &phtable, LTERM);
00785 
00786   PQueueFree(ctrl, &queue);
00787 
00788   idxwspacefree(ctrl, nparts);
00789   idxwspacefree(ctrl, nparts);
00790   idxwspacefree(ctrl, nparts);
00791   idxwspacefree(ctrl, nparts);
00792   idxwspacefree(ctrl, nvtxs);
00793   idxwspacefree(ctrl, nvtxs);
00794 }
00795 
00796 
00797 
00798 
00799 /*************************************************************************
00800 * This function updates the edge and volume gains as a result of moving
00801 * v from 'from' to 'to'.
00802 * The working arrays marker and phtable are assumed to be initialized to
00803 * -1, and they left to -1 upon return
00804 **************************************************************************/
00805 void KWayVolUpdate(CtrlType *ctrl, GraphType *graph, int v, int from, int to,
00806                    idxtype *marker, idxtype *phtable, idxtype *updind)
00807 {
00808   int ii, iii, j, jj, k, kk, l, u, nupd, other, me, myidx; 
00809   idxtype *xadj, *vsize, *adjncy, *adjwgt, *where;
00810   VEDegreeType *myedegrees, *oedegrees;
00811   VRInfoType *myrinfo, *orinfo;
00812 
00813   xadj = graph->xadj;
00814   adjncy = graph->adjncy;
00815   adjwgt = graph->adjwgt;
00816   vsize = graph->vsize;
00817   where = graph->where;
00818 
00819   myrinfo = graph->vrinfo+v;
00820   myedegrees = myrinfo->edegrees;
00821 
00822 
00823   /*======================================================================
00824    * Remove the contributions on the gain made by 'v'. 
00825    *=====================================================================*/
00826   for (k=0; k<myrinfo->ndegrees; k++)
00827     phtable[myedegrees[k].pid] = k;
00828   phtable[from] = k;
00829 
00830   myidx = phtable[to];  /* Keep track of the index in myedegrees of the 'to' domain */
00831 
00832   for (j=xadj[v]; j<xadj[v+1]; j++) {
00833     ii = adjncy[j];
00834     other = where[ii];
00835     orinfo = graph->vrinfo+ii;
00836     oedegrees = orinfo->edegrees;
00837 
00838     if (other == from) {
00839       for (k=0; k<orinfo->ndegrees; k++) {
00840         if (phtable[oedegrees[k].pid] == -1) 
00841           oedegrees[k].gv += vsize[v];
00842       }
00843     }
00844     else {
00845       ASSERT(phtable[other] != -1);
00846 
00847       if (myedegrees[phtable[other]].ned > 1) {
00848         for (k=0; k<orinfo->ndegrees; k++) {
00849           if (phtable[oedegrees[k].pid] == -1) 
00850             oedegrees[k].gv += vsize[v];
00851         }
00852       }
00853       else { /* There is only one connection */
00854         for (k=0; k<orinfo->ndegrees; k++) {
00855           if (phtable[oedegrees[k].pid] != -1) 
00856             oedegrees[k].gv -= vsize[v];
00857         }
00858       }
00859     }
00860   }
00861 
00862   for (k=0; k<myrinfo->ndegrees; k++)
00863     phtable[myedegrees[k].pid] = -1;
00864   phtable[from] = -1;
00865 
00866 
00867   /*======================================================================
00868    * Update the id/ed of vertex 'v'
00869    *=====================================================================*/
00870   myrinfo->ed += myrinfo->id-myedegrees[myidx].ed;
00871   SWAP(myrinfo->id, myedegrees[myidx].ed, j);
00872   SWAP(myrinfo->nid, myedegrees[myidx].ned, j);
00873   if (myedegrees[myidx].ed == 0) 
00874     myedegrees[myidx] = myedegrees[--myrinfo->ndegrees];
00875   else
00876     myedegrees[myidx].pid = from;
00877 
00878   /*======================================================================
00879    * Update the degrees of adjacent vertices and their volume gains
00880    *=====================================================================*/
00881   marker[v] = 1;
00882   updind[0] = v;
00883   nupd = 1;
00884   for (j=xadj[v]; j<xadj[v+1]; j++) {
00885     ii = adjncy[j];
00886     me = where[ii];
00887 
00888     if (!marker[ii]) {  /* The marking is done for boundary and max gv calculations */
00889       marker[ii] = 2;
00890       updind[nupd++] = ii;
00891     }
00892 
00893     myrinfo = graph->vrinfo+ii;
00894     if (myrinfo->edegrees == NULL) {
00895       myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
00896       ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
00897     }
00898     myedegrees = myrinfo->edegrees;
00899 
00900     if (me == from) {
00901       INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00902       myrinfo->nid--;
00903     } 
00904     else if (me == to) {
00905       INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00906       myrinfo->nid++;
00907     }
00908 
00909     /* Remove the edgeweight from the 'pid == from' entry of the vertex */
00910     if (me != from) {
00911       for (k=0; k<myrinfo->ndegrees; k++) {
00912         if (myedegrees[k].pid == from) {
00913           if (myedegrees[k].ned == 1) {
00914             myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00915             marker[ii] = 1;  /* You do a complete .gv calculation */
00916 
00917             /* All vertices adjacent to 'ii' need to be updated */
00918             for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
00919               u = adjncy[jj];
00920               other = where[u];
00921               orinfo = graph->vrinfo+u;
00922               oedegrees = orinfo->edegrees;
00923 
00924               for (kk=0; kk<orinfo->ndegrees; kk++) {
00925                 if (oedegrees[kk].pid == from) {
00926                   oedegrees[kk].gv -= vsize[ii];
00927                   break;
00928                 }
00929               }
00930             }
00931           }
00932           else {
00933             myedegrees[k].ed -= adjwgt[j];
00934             myedegrees[k].ned--;
00935 
00936             /* Update the gv due to single 'ii' connection to 'from' */
00937             if (myedegrees[k].ned == 1) {
00938               /* find the vertex 'u' that 'ii' was connected into 'from' */
00939               for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
00940                 u = adjncy[jj];
00941                 other = where[u];
00942                 orinfo = graph->vrinfo+u;
00943                 oedegrees = orinfo->edegrees;
00944 
00945                 if (other == from) {
00946                   for (kk=0; kk<orinfo->ndegrees; kk++) 
00947                     oedegrees[kk].gv += vsize[ii];
00948                   break;  
00949                 }
00950               }
00951             }
00952           }
00953 
00954           break; 
00955         }
00956       }
00957     }
00958 
00959     /* Add the edgeweight to the 'pid == to' entry of the vertex */
00960     if (me != to) {
00961       for (k=0; k<myrinfo->ndegrees; k++) {
00962         if (myedegrees[k].pid == to) {
00963           myedegrees[k].ed += adjwgt[j];
00964           myedegrees[k].ned++;
00965 
00966           /* Update the gv due to non-single 'ii' connection to 'to' */
00967           if (myedegrees[k].ned == 2) {
00968             /* find the vertex 'u' that 'ii' was connected into 'to' */
00969             for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
00970               u = adjncy[jj];
00971               other = where[u];
00972               orinfo = graph->vrinfo+u;
00973               oedegrees = orinfo->edegrees;
00974 
00975               if (u != v && other == to) {
00976                 for (kk=0; kk<orinfo->ndegrees; kk++) 
00977                   oedegrees[kk].gv -= vsize[ii];
00978                 break;  
00979               }
00980             }
00981           }
00982           break;
00983         }
00984       }
00985 
00986       if (k == myrinfo->ndegrees) {
00987         myedegrees[myrinfo->ndegrees].pid = to;
00988         myedegrees[myrinfo->ndegrees].ed = adjwgt[j];
00989         myedegrees[myrinfo->ndegrees++].ned = 1;
00990         marker[ii] = 1;  /* You do a complete .gv calculation */
00991 
00992         /* All vertices adjacent to 'ii' need to be updated */
00993         for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
00994           u = adjncy[jj];
00995           other = where[u];
00996           orinfo = graph->vrinfo+u;
00997           oedegrees = orinfo->edegrees;
00998 
00999           for (kk=0; kk<orinfo->ndegrees; kk++) {
01000             if (oedegrees[kk].pid == to) {
01001               oedegrees[kk].gv += vsize[ii];
01002               if (!marker[u]) { /* Need to update boundary etc */
01003                 marker[u] = 2;
01004                 updind[nupd++] = u;
01005               }
01006               break;
01007             }
01008           }
01009         }
01010       }
01011     }
01012 
01013     ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
01014   }
01015 
01016   /*======================================================================
01017    * Add the contributions on the volume gain due to 'v'
01018    *=====================================================================*/
01019   myrinfo = graph->vrinfo+v;
01020   myedegrees = myrinfo->edegrees;
01021   for (k=0; k<myrinfo->ndegrees; k++)
01022     phtable[myedegrees[k].pid] = k;
01023   phtable[to] = k;
01024 
01025   for (j=xadj[v]; j<xadj[v+1]; j++) {
01026     ii = adjncy[j];
01027     other = where[ii];
01028     orinfo = graph->vrinfo+ii;
01029     oedegrees = orinfo->edegrees;
01030 
01031     if (other == to) {
01032       for (k=0; k<orinfo->ndegrees; k++) {
01033         if (phtable[oedegrees[k].pid] == -1) 
01034           oedegrees[k].gv -= vsize[v];
01035       }
01036     }
01037     else {
01038       ASSERT(phtable[other] != -1);
01039 
01040       if (myedegrees[phtable[other]].ned > 1) {
01041         for (k=0; k<orinfo->ndegrees; k++) {
01042           if (phtable[oedegrees[k].pid] == -1) 
01043             oedegrees[k].gv -= vsize[v];
01044         }
01045       }
01046       else { /* There is only one connection */
01047         for (k=0; k<orinfo->ndegrees; k++) {
01048           if (phtable[oedegrees[k].pid] != -1) 
01049             oedegrees[k].gv += vsize[v];
01050         }
01051       }
01052     }
01053   }
01054   for (k=0; k<myrinfo->ndegrees; k++)
01055     phtable[myedegrees[k].pid] = -1;
01056   phtable[to] = -1;
01057 
01058 
01059   /*======================================================================
01060    * Recompute the volume information of the 'hard' nodes, and update the
01061    * max volume gain for all the update vertices
01062    *=====================================================================*/
01063   ComputeKWayVolume(graph, nupd, updind, marker, phtable);
01064 
01065 
01066   /*======================================================================
01067    * Maintain a consistent boundary
01068    *=====================================================================*/
01069   for (j=0; j<nupd; j++) {
01070     k = updind[j];
01071     marker[k] = 0;
01072     myrinfo = graph->vrinfo+k;
01073 
01074     if ((myrinfo->gv >= 0 || myrinfo->ed-myrinfo->id >= 0) && graph->bndptr[k] == -1)
01075       BNDInsert(graph->nbnd, graph->bndind, graph->bndptr, k);
01076 
01077     if (myrinfo->gv < 0 && myrinfo->ed-myrinfo->id < 0 && graph->bndptr[k] != -1)
01078       BNDDelete(graph->nbnd, graph->bndind, graph->bndptr, k);
01079   }
01080 
01081 }
01082 
01083 
01084 
01085 
01086 /*************************************************************************
01087 * This function computes the initial id/ed 
01088 **************************************************************************/
01089 void ComputeKWayVolume(GraphType *graph, int nupd, idxtype *updind, idxtype *marker, idxtype *phtable)
01090 {
01091   int ii, iii, i, j, k, kk, l, nvtxs, me, other, pid;
01092   idxtype *xadj, *vsize, *adjncy, *adjwgt, *where;
01093   VRInfoType *rinfo, *myrinfo, *orinfo;
01094   VEDegreeType *myedegrees, *oedegrees;
01095 
01096   nvtxs = graph->nvtxs;
01097   xadj = graph->xadj;
01098   vsize = graph->vsize;
01099   adjncy = graph->adjncy;
01100   adjwgt = graph->adjwgt;
01101   where = graph->where;
01102   rinfo = graph->vrinfo;
01103 
01104 
01105   /*------------------------------------------------------------
01106   / Compute now the iv/ev degrees
01107   /------------------------------------------------------------*/
01108   for (iii=0; iii<nupd; iii++) {
01109     i = updind[iii];
01110     me = where[i];
01111 
01112     myrinfo = rinfo+i;
01113     myedegrees = myrinfo->edegrees;
01114 
01115     if (marker[i] == 1) {  /* Only complete gain updates go through */
01116       for (k=0; k<myrinfo->ndegrees; k++) 
01117         myedegrees[k].gv = 0;
01118 
01119       for (j=xadj[i]; j<xadj[i+1]; j++) {
01120         ii = adjncy[j];
01121         other = where[ii];
01122         orinfo = rinfo+ii;
01123         oedegrees = orinfo->edegrees;
01124 
01125         for (kk=0; kk<orinfo->ndegrees; kk++) 
01126           phtable[oedegrees[kk].pid] = kk;
01127         phtable[other] = 1;
01128 
01129         if (me == other) {
01130           /* Find which domains 'i' is connected and 'ii' is not and update their gain */
01131           for (k=0; k<myrinfo->ndegrees; k++) {
01132             if (phtable[myedegrees[k].pid] == -1)
01133               myedegrees[k].gv -= vsize[ii];
01134           }
01135         }
01136         else {
01137           ASSERT(phtable[me] != -1);
01138 
01139           /* I'm the only connection of 'ii' in 'me' */
01140           if (oedegrees[phtable[me]].ned == 1) { 
01141             /* Increase the gains for all the common domains between 'i' and 'ii' */
01142             for (k=0; k<myrinfo->ndegrees; k++) {
01143               if (phtable[myedegrees[k].pid] != -1) 
01144                 myedegrees[k].gv += vsize[ii];
01145             }
01146           }
01147           else {
01148             /* Find which domains 'i' is connected and 'ii' is not and update their gain */
01149             for (k=0; k<myrinfo->ndegrees; k++) {
01150               if (phtable[myedegrees[k].pid] == -1) 
01151                 myedegrees[k].gv -= vsize[ii];
01152             }
01153           }
01154         }
01155 
01156         for (kk=0; kk<orinfo->ndegrees; kk++) 
01157           phtable[oedegrees[kk].pid] = -1;
01158         phtable[other] = -1;
01159   
01160       }
01161     }
01162 
01163     myrinfo->gv = -MAXIDX;
01164     for (k=0; k<myrinfo->ndegrees; k++) {
01165       if (myedegrees[k].gv > myrinfo->gv)
01166         myrinfo->gv = myedegrees[k].gv;
01167     }
01168     if (myrinfo->ed > 0 && myrinfo->id == 0)
01169       myrinfo->gv += vsize[i];
01170 
01171   }
01172 
01173 }
01174 
01175 
01176 
01177 /*************************************************************************
01178 * This function computes the total volume
01179 **************************************************************************/
01180 int ComputeVolume(GraphType *graph, idxtype *where)
01181 {
01182   int i, j, k, me, nvtxs, nparts, totalv;
01183   idxtype *xadj, *adjncy, *vsize, *marker;
01184 
01185 
01186   nvtxs = graph->nvtxs;
01187   xadj = graph->xadj;
01188   adjncy = graph->adjncy;
01189   vsize = (graph->vsize == NULL ? graph->vwgt : graph->vsize);
01190 
01191   nparts = where[idxamax(nvtxs, where)]+1;
01192   marker = idxsmalloc(nparts, -1, "ComputeVolume: marker");
01193 
01194   totalv = 0;
01195 
01196   for (i=0; i<nvtxs; i++) {
01197     marker[where[i]] = i;
01198     for (j=xadj[i]; j<xadj[i+1]; j++) {
01199       k = where[adjncy[j]];
01200       if (marker[k] != i) {
01201         marker[k] = i;
01202         totalv += vsize[i];
01203       }
01204     }
01205   }
01206 
01207   free(marker);
01208 
01209   return totalv;
01210 }
01211 
01212 
01213 
01214 
01215 
01216 /*************************************************************************
01217 * This function computes the initial id/ed 
01218 **************************************************************************/
01219 void CheckVolKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
01220 {
01221   int i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
01222   idxtype *xadj, *vsize, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
01223   VRInfoType *rinfo, *myrinfo, *orinfo, tmprinfo;
01224   VEDegreeType *myedegrees, *oedegrees, *tmpdegrees;
01225 
01226   nvtxs = graph->nvtxs;
01227   xadj = graph->xadj;
01228   vsize = graph->vsize;
01229   adjncy = graph->adjncy;
01230   adjwgt = graph->adjwgt;
01231   where = graph->where;
01232   rinfo = graph->vrinfo;
01233 
01234   tmpdegrees = (VEDegreeType *)GKmalloc(nparts*sizeof(VEDegreeType), "CheckVolKWayPartitionParams: tmpdegrees");
01235 
01236   /*------------------------------------------------------------
01237   / Compute now the iv/ev degrees
01238   /------------------------------------------------------------*/
01239   for (i=0; i<nvtxs; i++) {
01240     me = where[i];
01241 
01242     myrinfo = rinfo+i;
01243     myedegrees = myrinfo->edegrees;
01244 
01245     for (k=0; k<myrinfo->ndegrees; k++)
01246       tmpdegrees[k] = myedegrees[k];
01247 
01248     tmprinfo.ndegrees = myrinfo->ndegrees;
01249     tmprinfo.id = myrinfo->id;
01250     tmprinfo.ed = myrinfo->ed;
01251 
01252     myrinfo = &tmprinfo;
01253     myedegrees = tmpdegrees;
01254 
01255 
01256     for (k=0; k<myrinfo->ndegrees; k++)
01257       myedegrees[k].gv = 0;
01258 
01259     for (j=xadj[i]; j<xadj[i+1]; j++) {
01260       ii = adjncy[j];
01261       other = where[ii];
01262       orinfo = rinfo+ii;
01263       oedegrees = orinfo->edegrees;
01264 
01265       if (me == other) {
01266         /* Find which domains 'i' is connected and 'ii' is not and update their gain */
01267         for (k=0; k<myrinfo->ndegrees; k++) {
01268           pid = myedegrees[k].pid;
01269           for (kk=0; kk<orinfo->ndegrees; kk++) {
01270             if (oedegrees[kk].pid == pid)
01271               break;
01272           }
01273           if (kk == orinfo->ndegrees) 
01274             myedegrees[k].gv -= vsize[ii];
01275         }
01276       }
01277       else {
01278         /* Find the orinfo[me].ed and see if I'm the only connection */
01279         for (k=0; k<orinfo->ndegrees; k++) {
01280           if (oedegrees[k].pid == me)
01281             break;
01282         }
01283 
01284         if (oedegrees[k].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
01285           for (k=0; k<myrinfo->ndegrees; k++) {
01286             if (myedegrees[k].pid == other) {
01287               myedegrees[k].gv += vsize[ii];
01288               break;
01289             }
01290           }
01291 
01292           /* Increase the gains for all the common domains between 'i' and 'ii' */
01293           for (k=0; k<myrinfo->ndegrees; k++) {
01294             if ((pid = myedegrees[k].pid) == other)
01295               continue;
01296             for (kk=0; kk<orinfo->ndegrees; kk++) {
01297               if (oedegrees[kk].pid == pid) {
01298                 myedegrees[k].gv += vsize[ii];
01299                 break;
01300               }
01301             }
01302           }
01303 
01304         }
01305         else {
01306           /* Find which domains 'i' is connected and 'ii' is not and update their gain */
01307           for (k=0; k<myrinfo->ndegrees; k++) {
01308             if ((pid = myedegrees[k].pid) == other)
01309               continue;
01310             for (kk=0; kk<orinfo->ndegrees; kk++) {
01311               if (oedegrees[kk].pid == pid)
01312                 break;
01313             }
01314             if (kk == orinfo->ndegrees) 
01315               myedegrees[k].gv -= vsize[ii];
01316           }
01317         }
01318       }
01319     }
01320 
01321     myrinfo = rinfo+i;
01322     myedegrees = myrinfo->edegrees;
01323 
01324     for (k=0; k<myrinfo->ndegrees; k++) {
01325       pid = myedegrees[k].pid;
01326       for (kk=0; kk<tmprinfo.ndegrees; kk++) {
01327         if (tmpdegrees[kk].pid == pid) {
01328           if (tmpdegrees[kk].gv != myedegrees[k].gv)
01329             printf("[%d %d %d %d]\n", i, pid, myedegrees[k].gv, tmpdegrees[kk].gv);
01330           break;
01331         }
01332       }
01333     }
01334 
01335   }
01336 
01337   free(tmpdegrees);
01338 
01339 }
01340 
01341 
01342 /*************************************************************************
01343 * This function computes the subdomain graph
01344 **************************************************************************/
01345 void ComputeVolSubDomainGraph(GraphType *graph, int nparts, idxtype *pmat, idxtype *ndoms)
01346 {
01347   int i, j, k, me, nvtxs, ndegrees;
01348   idxtype *xadj, *adjncy, *adjwgt, *where;
01349   VRInfoType *rinfo;
01350   VEDegreeType *edegrees;
01351 
01352   nvtxs = graph->nvtxs;
01353   xadj = graph->xadj;
01354   adjncy = graph->adjncy;
01355   adjwgt = graph->adjwgt;
01356   where = graph->where;
01357   rinfo = graph->vrinfo;
01358 
01359   idxset(nparts*nparts, 0, pmat);
01360 
01361   for (i=0; i<nvtxs; i++) {
01362     if (rinfo[i].ed > 0) {
01363       me = where[i];
01364       ndegrees = rinfo[i].ndegrees;
01365       edegrees = rinfo[i].edegrees;
01366 
01367       k = me*nparts;
01368       for (j=0; j<ndegrees; j++) 
01369         pmat[k+edegrees[j].pid] += edegrees[j].ed;
01370     }
01371   }
01372 
01373   for (i=0; i<nparts; i++) {
01374     ndoms[i] = 0;
01375     for (j=0; j<nparts; j++) {
01376       if (pmat[i*nparts+j] > 0)
01377         ndoms[i]++;
01378     }
01379   }
01380 }
01381 
01382 
01383 
01384 /*************************************************************************
01385 * This function computes the subdomain graph
01386 **************************************************************************/
01387 void EliminateVolSubDomainEdges(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts)
01388 {
01389   int i, ii, j, k, me, other, nvtxs, total, max, avg, totalout, nind, ncand, ncand2, target, target2, nadd;
01390   int min, move, cpwgt, tvwgt;
01391   idxtype *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt, *pmat, *ndoms, *mypmat, *otherpmat, *ind;
01392   KeyValueType *cand, *cand2;
01393 
01394   nvtxs = graph->nvtxs;
01395   xadj = graph->xadj;
01396   adjncy = graph->adjncy;
01397   vwgt = graph->vwgt;
01398   adjwgt = graph->adjwgt;
01399 
01400   where = graph->where;
01401   pwgts = idxset(nparts, 0, graph->pwgts);
01402 
01403   maxpwgt = idxwspacemalloc(ctrl, nparts);
01404   ndoms = idxwspacemalloc(ctrl, nparts);
01405   otherpmat = idxwspacemalloc(ctrl, nparts);
01406   ind = idxwspacemalloc(ctrl, nvtxs);
01407   pmat = idxset(nparts*nparts, 0, ctrl->wspace.pmat);
01408 
01409   cand = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
01410   cand2 = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
01411 
01412   /* Compute the pmat matrix */
01413   for (i=0; i<nvtxs; i++) {
01414     me = where[i];
01415     pwgts[me] += vwgt[i];
01416     for (j=xadj[i]; j<xadj[i+1]; j++) {
01417       k = adjncy[j];
01418       if (where[k] != me) 
01419         pmat[me*nparts+where[k]] += adjwgt[j];
01420     }
01421   }
01422 
01423   /* Compute the maximum allowed weight for each domain */
01424   tvwgt = idxsum(nparts, pwgts);
01425   for (i=0; i<nparts; i++)
01426     maxpwgt[i] = 1.25*tpwgts[i]*tvwgt;
01427 
01428   /* Determine the domain connectivity */
01429   for (i=0; i<nparts; i++) {
01430     for (k=0, j=0; j<nparts; j++) {
01431       if (pmat[i*nparts+j] > 0)
01432         k++;
01433     }
01434     ndoms[i] = k;
01435   }
01436 
01437   /* Get into the loop eliminating subdomain connections */
01438   for (;;) {
01439     total = idxsum(nparts, ndoms);
01440     avg = total/nparts;
01441     max = ndoms[idxamax(nparts, ndoms)];
01442 
01443     /* printf("Adjacent Subdomain Stats: Total: %3d, Max: %3d, Avg: %3d\n", total, max, avg); */
01444 
01445     if (max < 1.5*avg)
01446       break;
01447 
01448     me = idxamax(nparts, ndoms);
01449     mypmat = pmat + me*nparts;
01450     totalout = idxsum(nparts, mypmat);
01451 
01452     /*printf("Me: %d, TotalOut: %d,\n", me, totalout);*/
01453 
01454     /* Sort the connections according to their cut */
01455     for (ncand2=0, i=0; i<nparts; i++) {
01456       if (mypmat[i] > 0) {
01457         cand2[ncand2].key = mypmat[i];
01458         cand2[ncand2++].val = i;
01459       }
01460     }
01461     ikeysort(ncand2, cand2);
01462 
01463     move = 0;
01464     for (min=0; min<ncand2; min++) {
01465       if (cand2[min].key > totalout/(2*ndoms[me])) 
01466         break;
01467 
01468       other = cand2[min].val;
01469 
01470       /*printf("\tMinOut: %d to %d\n", mypmat[other], other);*/
01471 
01472       idxset(nparts, 0, otherpmat);
01473 
01474       /* Go and find the vertices in 'other' that are connected in 'me' */
01475       for (nind=0, i=0; i<nvtxs; i++) {
01476         if (where[i] == other) {
01477           for (j=xadj[i]; j<xadj[i+1]; j++) {
01478             if (where[adjncy[j]] == me) {
01479               ind[nind++] = i;
01480               break;
01481             }
01482           }
01483         }
01484       }
01485 
01486       /* Go and construct the otherpmat to see where these nind vertices are connected to */
01487       for (cpwgt=0, ii=0; ii<nind; ii++) {
01488         i = ind[ii];
01489         cpwgt += vwgt[i];
01490 
01491         for (j=xadj[i]; j<xadj[i+1]; j++) {
01492           k = adjncy[j];
01493           if (where[k] != other) 
01494             otherpmat[where[k]] += adjwgt[j];
01495         }
01496       }
01497 
01498       for (ncand=0, i=0; i<nparts; i++) {
01499         if (otherpmat[i] > 0) {
01500           cand[ncand].key = -otherpmat[i];
01501           cand[ncand++].val = i;
01502         }
01503       }
01504       ikeysort(ncand, cand);
01505 
01506       /* 
01507        * Go through and the select the first domain that is common with 'me', and
01508        * does not increase the ndoms[target] higher than my ndoms, subject to the
01509        * maxpwgt constraint. Traversal is done from the mostly connected to the least.
01510        */
01511       target = target2 = -1;
01512       for (i=0; i<ncand; i++) {
01513         k = cand[i].val;
01514 
01515         if (mypmat[k] > 0) {
01516           if (pwgts[k] + cpwgt > maxpwgt[k])  /* Check if balance will go off */
01517             continue;
01518 
01519           for (j=0; j<nparts; j++) {
01520             if (otherpmat[j] > 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0)
01521               break;
01522           }
01523           if (j == nparts) { /* No bad second level effects */
01524             for (nadd=0, j=0; j<nparts; j++) {
01525               if (otherpmat[j] > 0 && pmat[nparts*k+j] == 0)
01526                 nadd++;
01527             }
01528 
01529             /*printf("\t\tto=%d, nadd=%d, %d\n", k, nadd, ndoms[k]);*/
01530             if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) {
01531               target2 = k;
01532             }
01533             if (nadd == 0) {
01534               target = k;
01535               break;
01536             }
01537           }
01538         }
01539       }
01540       if (target == -1 && target2 != -1)
01541         target = target2;
01542 
01543       if (target == -1) {
01544         /* printf("\t\tCould not make the move\n");*/
01545         continue;
01546       }
01547 
01548       /*printf("\t\tMoving to %d\n", target);*/
01549 
01550       /* Update the partition weights */
01551       INC_DEC(pwgts[target], pwgts[other], cpwgt);
01552 
01553       /* Set all nind vertices to belong to 'target' */
01554       for (ii=0; ii<nind; ii++) {
01555         i = ind[ii];
01556         where[i] = target;
01557 
01558         /* First remove any contribution that this vertex may have made */
01559         for (j=xadj[i]; j<xadj[i+1]; j++) {
01560           k = adjncy[j];
01561           if (where[k] != other) {
01562             if (pmat[nparts*other + where[k]] == 0)
01563               printf("Something wrong\n");
01564             pmat[nparts*other + where[k]] -= adjwgt[j];
01565             if (pmat[nparts*other + where[k]] == 0)
01566               ndoms[other]--;
01567 
01568             if (pmat[nparts*where[k] + other] == 0)
01569               printf("Something wrong\n");
01570             pmat[nparts*where[k] + other] -= adjwgt[j];
01571             if (pmat[nparts*where[k] + other] == 0)
01572               ndoms[where[k]]--;
01573           }
01574         }
01575 
01576         /* Next add the new contributions as a result of the move */
01577         for (j=xadj[i]; j<xadj[i+1]; j++) {
01578           k = adjncy[j];
01579           if (where[k] != target) {
01580             if (pmat[nparts*target + where[k]] == 0)
01581               ndoms[target]++;
01582             pmat[nparts*target + where[k]] += adjwgt[j];
01583   
01584             if (pmat[nparts*where[k] + target] == 0)
01585               ndoms[where[k]]++;
01586             pmat[nparts*where[k] + target] += adjwgt[j];
01587           }
01588         }
01589       }
01590 
01591       move = 1;
01592       break;
01593     }
01594 
01595     if (move == 0)
01596       break;
01597   }
01598 
01599   idxwspacefree(ctrl, nparts);
01600   idxwspacefree(ctrl, nparts);
01601   idxwspacefree(ctrl, nparts);
01602   idxwspacefree(ctrl, nvtxs);
01603 
01604   GKfree(&cand, &cand2, LTERM);
01605 }
01606 
01607 
01608 
01609 /*************************************************************************
01610 * This function finds all the connected components induced by the 
01611 * partitioning vector in wgraph->where and tries to push them around to 
01612 * remove some of them
01613 **************************************************************************/
01614 void EliminateVolComponents(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor)
01615 {
01616   int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, ncand, other, target, deltawgt;
01617   idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt;
01618   idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps;
01619   KeyValueType *cand;
01620   int recompute=0;
01621 
01622   nvtxs = graph->nvtxs;
01623   xadj = graph->xadj;
01624   adjncy = graph->adjncy;
01625   vwgt = graph->vwgt;
01626   adjwgt = graph->adjwgt;
01627 
01628   where = graph->where;
01629   pwgts = idxset(nparts, 0, graph->pwgts);
01630 
01631   touched = idxset(nvtxs, 0, idxwspacemalloc(ctrl, nvtxs));
01632   cptr    = idxwspacemalloc(ctrl, nvtxs+1);
01633   cind    = idxwspacemalloc(ctrl, nvtxs);
01634   perm    = idxwspacemalloc(ctrl, nvtxs);
01635   todo    = idxwspacemalloc(ctrl, nvtxs);
01636   maxpwgt = idxwspacemalloc(ctrl, nparts);
01637   cpvec   = idxwspacemalloc(ctrl, nparts);
01638   npcmps  = idxset(nparts, 0, idxwspacemalloc(ctrl, nparts));
01639 
01640   for (i=0; i<nvtxs; i++) 
01641     perm[i] = todo[i] = i;
01642 
01643   /* Find the connected componends induced by the partition */
01644   ncmps = -1;
01645   first = last = 0;
01646   nleft = nvtxs;
01647   while (nleft > 0) {
01648     if (first == last) { /* Find another starting vertex */
01649       cptr[++ncmps] = first;
01650       ASSERT(touched[todo[0]] == 0);
01651       i = todo[0];
01652       cind[last++] = i;
01653       touched[i] = 1;
01654       me = where[i];
01655       npcmps[me]++;
01656     }
01657 
01658     i = cind[first++];
01659     k = perm[i];
01660     j = todo[k] = todo[--nleft];
01661     perm[j] = k;
01662 
01663     for (j=xadj[i]; j<xadj[i+1]; j++) {
01664       k = adjncy[j];
01665       if (where[k] == me && !touched[k]) {
01666         cind[last++] = k;
01667         touched[k] = 1;
01668       }
01669     }
01670   }
01671   cptr[++ncmps] = first;
01672 
01673   /* printf("I found %d components, for this %d-way partition\n", ncmps, nparts); */
01674 
01675   if (ncmps > nparts) { /* There are more components than processors */
01676     cand = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
01677 
01678     /* First determine the partition sizes and max allowed load imbalance */
01679     for (i=0; i<nvtxs; i++) 
01680       pwgts[where[i]] += vwgt[i];
01681     tvwgt = idxsum(nparts, pwgts);
01682     for (i=0; i<nparts; i++)
01683       maxpwgt[i] = ubfactor*tpwgts[i]*tvwgt;
01684 
01685     deltawgt = tvwgt/(100*nparts);
01686     deltawgt = 5;
01687 
01688     for (i=0; i<ncmps; i++) {
01689       me = where[cind[cptr[i]]];  /* Get the domain of this component */
01690       if (npcmps[me] == 1)
01691         continue;  /* Skip it because it is contigous */
01692 
01693       /*printf("Trying to move %d from %d\n", i, me); */
01694 
01695       /* Determine the connectivity */
01696       idxset(nparts, 0, cpvec);
01697       for (cwgt=0, j=cptr[i]; j<cptr[i+1]; j++) {
01698         ii = cind[j];
01699         cwgt += vwgt[ii];
01700         for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
01701           other = where[adjncy[jj]];
01702           if (me != other)
01703             cpvec[other] += adjwgt[jj];
01704         }
01705       }
01706 
01707       /*printf("\tCmp weight: %d\n", cwgt);*/
01708 
01709       if (cwgt > .30*pwgts[me])
01710         continue;  /* Skip the component if it is over 30% of the weight */
01711 
01712       for (ncand=0, j=0; j<nparts; j++) {
01713         if (cpvec[j] > 0) {
01714           cand[ncand].key = -cpvec[j];
01715           cand[ncand++].val = j;
01716         }
01717       }
01718       if (ncand == 0)
01719         continue;
01720 
01721       ikeysort(ncand, cand);
01722 
01723       target = -1;
01724       for (j=0; j<ncand; j++) {
01725         k = cand[j].val;
01726         if (cwgt < deltawgt || pwgts[k] + cwgt < maxpwgt[k]) {
01727           target = k;
01728           break;
01729         }
01730       }
01731 
01732       /*printf("\tMoving it to %d [%d]\n", target, cpvec[target]);*/
01733 
01734       if (target != -1) {
01735         /* Assign all the vertices of 'me' to 'target' and update data structures */
01736         pwgts[me] -= cwgt;
01737         pwgts[target] += cwgt;
01738         npcmps[me]--;
01739 
01740         for (j=cptr[i]; j<cptr[i+1]; j++) 
01741           where[cind[j]] = target;
01742 
01743         graph->mincut -= cpvec[target];
01744         recompute = 1;
01745       }
01746     }
01747 
01748     free(cand);
01749   }
01750 
01751   if (recompute) {
01752     int ttlv;
01753     idxtype *marker;
01754 
01755     marker = idxset(nparts, -1, cpvec);
01756     for (ttlv=0, i=0; i<nvtxs; i++) {
01757       marker[where[i]] = i;
01758       for (j=xadj[i]; j<xadj[i+1]; j++) {
01759         if (marker[where[adjncy[j]]] != i) {
01760           ttlv += graph->vsize[i];
01761           marker[where[adjncy[j]]] = i;
01762         }
01763       }
01764     }
01765     graph->minvol = ttlv;
01766   }
01767 
01768   idxwspacefree(ctrl, nparts);
01769   idxwspacefree(ctrl, nparts);
01770   idxwspacefree(ctrl, nparts);
01771   idxwspacefree(ctrl, nvtxs);
01772   idxwspacefree(ctrl, nvtxs);
01773   idxwspacefree(ctrl, nvtxs);
01774   idxwspacefree(ctrl, nvtxs);
01775   idxwspacefree(ctrl, nvtxs+1);
01776 
01777 }
01778
libs/ck-libs/parmetis/METISLib/kwayvolfm.c
