Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * subdomains.c
00005  *
00006  * This file contains functions that deal with prunning the number of
00007  * adjacent subdomains in KMETIS
00008  *
00009  * Started 7/15/98
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 
00019 /*************************************************************************
00020 * This function performs k-way refinement
00021 **************************************************************************/
00022 void Random_KWayEdgeRefineMConn(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor, int npasses, int ffactor)
00023 {
00024   int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees; 
00025   int from, me, to, oldcut, vwgt, gain;
00026   int maxndoms, nadd;
00027   idxtype *xadj, *adjncy, *adjwgt;
00028   idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
00029   idxtype *phtable, *pmat, *pmatptr, *ndoms;
00030   EDegreeType *myedegrees;
00031   RInfoType *myrinfo;
00032 
00033   nvtxs = graph->nvtxs;
00034   xadj = graph->xadj;
00035   adjncy = graph->adjncy;
00036   adjwgt = graph->adjwgt;
00037 
00038   bndptr = graph->bndptr;
00039   bndind = graph->bndind;
00040 
00041   where = graph->where;
00042   pwgts = graph->pwgts;
00043 
00044   pmat = ctrl->wspace.pmat;
00045   phtable = idxwspacemalloc(ctrl, nparts);
00046   ndoms = idxwspacemalloc(ctrl, nparts);
00047 
00048   ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
00049 
00050   /* Setup the weight intervals of the various subdomains */
00051   minwgt =  idxwspacemalloc(ctrl, nparts);
00052   maxwgt = idxwspacemalloc(ctrl, nparts);
00053   itpwgts = idxwspacemalloc(ctrl, nparts);
00054   tvwgt = idxsum(nparts, pwgts);
00055   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00056 
00057   for (i=0; i<nparts; i++) {
00058     itpwgts[i] = tpwgts[i]*tvwgt;
00059     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00060     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00061   }
00062 
00063   perm = idxwspacemalloc(ctrl, nvtxs);
00064 
00065   IFSET(ctrl->dbglvl, DBG_REFINE,
00066      printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
00067              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00068              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00069              graph->mincut));
00070 
00071   for (pass=0; pass<npasses; pass++) {
00072     ASSERT(ComputeCut(graph, where) == graph->mincut);
00073 
00074     maxndoms = ndoms[idxamax(nparts, ndoms)];
00075 
00076     oldcut = graph->mincut;
00077     nbnd = graph->nbnd;
00078 
00079     RandomPermute(nbnd, perm, 1);
00080     for (nmoves=iii=0; iii<graph->nbnd; iii++) {
00081       ii = perm[iii];
00082       if (ii >= nbnd)
00083         continue;
00084       i = bndind[ii];
00085 
00086       myrinfo = graph->rinfo+i;
00087 
00088       if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */
00089         from = where[i];
00090         vwgt = graph->vwgt[i];
00091 
00092         if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from]) 
00093           continue;   /* This cannot be moved! */
00094 
00095         myedegrees = myrinfo->edegrees;
00096         myndegrees = myrinfo->ndegrees;
00097 
00098         /* Determine the valid domains */
00099         for (j=0; j<myndegrees; j++) {
00100           to = myedegrees[j].pid;
00101           phtable[to] = 1;
00102           pmatptr = pmat + to*nparts;
00103           for (nadd=0, k=0; k<myndegrees; k++) {
00104             if (k == j)
00105               continue;
00106 
00107             l = myedegrees[k].pid;
00108             if (pmatptr[l] == 0) {
00109               if (ndoms[l] > maxndoms-1) {
00110                 phtable[to] = 0;
00111                 nadd = maxndoms;
00112                 break;
00113               }
00114               nadd++;
00115             }
00116           }
00117           if (ndoms[to]+nadd > maxndoms)
00118             phtable[to] = 0;
00119           if (nadd == 0)
00120             phtable[to] = 2;
00121         }
00122 
00123         /* Find the first valid move */
00124         j = myrinfo->id;
00125         for (k=0; k<myndegrees; k++) {
00126           to = myedegrees[k].pid;
00127           if (!phtable[to])
00128             continue;
00129           gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */ 
00130           if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0)  
00131             break;
00132         }
00133         if (k == myndegrees)
00134           continue;  /* break out if you did not find a candidate */
00135 
00136         for (j=k+1; j<myndegrees; j++) {
00137           to = myedegrees[j].pid;
00138           if (!phtable[to])
00139             continue;
00140           if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
00141               (myedegrees[j].ed == myedegrees[k].ed && 
00142                itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
00143             k = j;
00144         }
00145 
00146         to = myedegrees[k].pid;
00147 
00148         j = 0;
00149         if (myedegrees[k].ed-myrinfo->id > 0)
00150           j = 1;
00151         else if (myedegrees[k].ed-myrinfo->id == 0) {
00152           if (/*(iii&7) == 0  ||*/ phtable[myedegrees[k].pid] == 2 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
00153             j = 1;
00154         }
00155         if (j == 0)
00156           continue;
00157           
00158         /*=====================================================================
00159         * If we got here, we can now move the vertex from 'from' to 'to' 
00160         *======================================================================*/
00161         graph->mincut -= myedegrees[k].ed-myrinfo->id;
00162 
00163         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));
00164 
00165         /* Update pmat to reflect the move of 'i' */
00166         pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
00167         pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
00168         if (pmat[from*nparts+to] == 0) {
00169           ndoms[from]--;
00170           if (ndoms[from]+1 == maxndoms)
00171             maxndoms = ndoms[idxamax(nparts, ndoms)];
00172         }
00173         if (pmat[to*nparts+from] == 0) {
00174           ndoms[to]--;
00175           if (ndoms[to]+1 == maxndoms)
00176             maxndoms = ndoms[idxamax(nparts, ndoms)];
00177         }
00178 
00179         /* Update where, weight, and ID/ED information of the vertex you moved */
00180         where[i] = to;
00181         INC_DEC(pwgts[to], pwgts[from], vwgt);
00182         myrinfo->ed += myrinfo->id-myedegrees[k].ed;
00183         SWAP(myrinfo->id, myedegrees[k].ed, j);
00184         if (myedegrees[k].ed == 0) 
00185           myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00186         else
00187           myedegrees[k].pid = from;
00188 
00189         if (myrinfo->ed-myrinfo->id < 0)
00190           BNDDelete(nbnd, bndind, bndptr, i);
00191 
00192         /* Update the degrees of adjacent vertices */
00193         for (j=xadj[i]; j<xadj[i+1]; j++) {
00194           ii = adjncy[j];
00195           me = where[ii];
00196 
00197           myrinfo = graph->rinfo+ii;
00198           if (myrinfo->edegrees == NULL) {
00199             myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00200             ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
00201           }
00202           myedegrees = myrinfo->edegrees;
00203 
00204           ASSERT(CheckRInfo(myrinfo));
00205 
00206           if (me == from) {
00207             INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00208 
00209             if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
00210               BNDInsert(nbnd, bndind, bndptr, ii);
00211           }
00212           else if (me == to) {
00213             INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00214 
00215             if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
00216               BNDDelete(nbnd, bndind, bndptr, ii);
00217           }
00218 
00219           /* Remove contribution from the .ed of 'from' */
00220           if (me != from) {
00221             for (k=0; k<myrinfo->ndegrees; k++) {
00222               if (myedegrees[k].pid == from) {
00223                 if (myedegrees[k].ed == adjwgt[j])
00224                   myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00225                 else
00226                   myedegrees[k].ed -= adjwgt[j];
00227                 break;
00228               }
00229             }
00230           }
00231 
00232           /* Add contribution to the .ed of 'to' */
00233           if (me != to) {
00234             for (k=0; k<myrinfo->ndegrees; k++) {
00235               if (myedegrees[k].pid == to) {
00236                 myedegrees[k].ed += adjwgt[j];
00237                 break;
00238               }
00239             }
00240             if (k == myrinfo->ndegrees) {
00241               myedegrees[myrinfo->ndegrees].pid = to;
00242               myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
00243             }
00244           }
00245 
00246           /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
00247           if (me != from && me != to) {
00248             pmat[me*nparts+from] -= adjwgt[j];
00249             pmat[from*nparts+me] -= adjwgt[j];
00250             if (pmat[me*nparts+from] == 0) {
00251               ndoms[me]--;
00252               if (ndoms[me]+1 == maxndoms)
00253                 maxndoms = ndoms[idxamax(nparts, ndoms)];
00254             }
00255             if (pmat[from*nparts+me] == 0) {
00256               ndoms[from]--;
00257               if (ndoms[from]+1 == maxndoms)
00258                 maxndoms = ndoms[idxamax(nparts, ndoms)];
00259             }
00260 
00261             if (pmat[me*nparts+to] == 0) {
00262               ndoms[me]++;
00263               if (ndoms[me] > maxndoms) {
00264                 IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms));
00265                 maxndoms = ndoms[me];
00266               }
00267             }
00268             if (pmat[to*nparts+me] == 0) {
00269               ndoms[to]++;
00270               if (ndoms[to] > maxndoms) {
00271                 IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms));
00272                 maxndoms = ndoms[to];
00273               }
00274             }
00275             pmat[me*nparts+to] += adjwgt[j];
00276             pmat[to*nparts+me] += adjwgt[j];
00277           }
00278 
00279           ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
00280           ASSERT(CheckRInfo(myrinfo));
00281 
00282         }
00283         nmoves++;
00284       }
00285     }
00286 
00287     graph->nbnd = nbnd;
00288 
00289     IFSET(ctrl->dbglvl, DBG_REFINE,
00290        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %5d, Vol: %5d, %d\n",
00291                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00292                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, 
00293                graph->mincut, ComputeVolume(graph, where), idxsum(nparts, ndoms)));
00294 
00295     if (graph->mincut == oldcut)
00296       break;
00297   }
00298 
00299   idxwspacefree(ctrl, nparts);
00300   idxwspacefree(ctrl, nparts);
00301   idxwspacefree(ctrl, nparts);
00302   idxwspacefree(ctrl, nparts);
00303   idxwspacefree(ctrl, nparts);
00304   idxwspacefree(ctrl, nvtxs);
00305 }
00306 
00307 
00308 
00309 /*************************************************************************
00310 * This function performs k-way refinement
00311 **************************************************************************/
00312 void Greedy_KWayEdgeBalanceMConn(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor, int npasses)
00313 {
00314   int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves; 
00315   int from, me, to, oldcut, vwgt, maxndoms, nadd;
00316   idxtype *xadj, *adjncy, *adjwgt;
00317   idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
00318   idxtype *phtable, *pmat, *pmatptr, *ndoms;
00319   EDegreeType *myedegrees;
00320   RInfoType *myrinfo;
00321   PQueueType queue;
00322 
00323   nvtxs = graph->nvtxs;
00324   xadj = graph->xadj;
00325   adjncy = graph->adjncy;
00326   adjwgt = graph->adjwgt;
00327 
00328   bndind = graph->bndind;
00329   bndptr = graph->bndptr;
00330 
00331   where = graph->where;
00332   pwgts = graph->pwgts;
00333   
00334   pmat = ctrl->wspace.pmat;
00335   phtable = idxwspacemalloc(ctrl, nparts);
00336   ndoms = idxwspacemalloc(ctrl, nparts);
00337 
00338   ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
00339 
00340 
00341   /* Setup the weight intervals of the various subdomains */
00342   minwgt =  idxwspacemalloc(ctrl, nparts);
00343   maxwgt = idxwspacemalloc(ctrl, nparts);
00344   itpwgts = idxwspacemalloc(ctrl, nparts);
00345   tvwgt = idxsum(nparts, pwgts);
00346   ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
00347 
00348   for (i=0; i<nparts; i++) {
00349     itpwgts[i] = tpwgts[i]*tvwgt;
00350     maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
00351     minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
00352   }
00353 
00354   perm = idxwspacemalloc(ctrl, nvtxs);
00355   moved = idxwspacemalloc(ctrl, nvtxs);
00356 
00357   PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
00358 
00359   IFSET(ctrl->dbglvl, DBG_REFINE,
00360      printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
00361              pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], 
00362              1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
00363              graph->mincut));
00364 
00365   for (pass=0; pass<npasses; pass++) {
00366     ASSERT(ComputeCut(graph, where) == graph->mincut);
00367 
00368     /* Check to see if things are out of balance, given the tolerance */
00369     for (i=0; i<nparts; i++) {
00370       if (pwgts[i] > maxwgt[i])
00371         break;
00372     }
00373     if (i == nparts) /* Things are balanced. Return right away */
00374       break;
00375 
00376     PQueueReset(&queue);
00377     idxset(nvtxs, -1, moved);
00378 
00379     oldcut = graph->mincut;
00380     nbnd = graph->nbnd;
00381 
00382     RandomPermute(nbnd, perm, 1);
00383     for (ii=0; ii<nbnd; ii++) {
00384       i = bndind[perm[ii]];
00385       PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
00386       moved[i] = 2;
00387     }
00388 
00389     maxndoms = ndoms[idxamax(nparts, ndoms)];
00390 
00391     for (nmoves=0;;) {
00392       if ((i = PQueueGetMax(&queue)) == -1) 
00393         break;
00394       moved[i] = 1;
00395 
00396       myrinfo = graph->rinfo+i;
00397       from = where[i];
00398       vwgt = graph->vwgt[i];
00399 
00400       if (pwgts[from]-vwgt < minwgt[from]) 
00401         continue;   /* This cannot be moved! */
00402 
00403       myedegrees = myrinfo->edegrees;
00404       myndegrees = myrinfo->ndegrees;
00405 
00406       /* Determine the valid domains */
00407       for (j=0; j<myndegrees; j++) {
00408         to = myedegrees[j].pid;
00409         phtable[to] = 1;
00410         pmatptr = pmat + to*nparts;
00411         for (nadd=0, k=0; k<myndegrees; k++) {
00412           if (k == j)
00413             continue;
00414 
00415           l = myedegrees[k].pid;
00416           if (pmatptr[l] == 0) {
00417             if (ndoms[l] > maxndoms-1) {
00418               phtable[to] = 0;
00419               nadd = maxndoms;
00420               break;
00421             }
00422             nadd++;
00423           }
00424         }
00425         if (ndoms[to]+nadd > maxndoms)
00426           phtable[to] = 0;
00427       }
00428 
00429       for (k=0; k<myndegrees; k++) {
00430         to = myedegrees[k].pid;
00431         if (!phtable[to])
00432           continue;
00433         if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from]) 
00434           break;
00435       }
00436       if (k == myndegrees)
00437         continue;  /* break out if you did not find a candidate */
00438 
00439       for (j=k+1; j<myndegrees; j++) {
00440         to = myedegrees[j].pid;
00441         if (!phtable[to])
00442           continue;
00443         if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]) 
00444           k = j;
00445       }
00446 
00447       to = myedegrees[k].pid;
00448 
00449       if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->id < 0) 
00450         continue;
00451 
00452       /*=====================================================================
00453       * If we got here, we can now move the vertex from 'from' to 'to' 
00454       *======================================================================*/
00455       graph->mincut -= myedegrees[k].ed-myrinfo->id;
00456 
00457       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));
00458 
00459       /* Update pmat to reflect the move of 'i' */
00460       pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
00461       pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
00462       if (pmat[from*nparts+to] == 0) {
00463         ndoms[from]--;
00464         if (ndoms[from]+1 == maxndoms)
00465           maxndoms = ndoms[idxamax(nparts, ndoms)];
00466       }
00467       if (pmat[to*nparts+from] == 0) {
00468         ndoms[to]--;
00469         if (ndoms[to]+1 == maxndoms)
00470           maxndoms = ndoms[idxamax(nparts, ndoms)];
00471       }
00472 
00473 
00474       /* Update where, weight, and ID/ED information of the vertex you moved */
00475       where[i] = to;
00476       INC_DEC(pwgts[to], pwgts[from], vwgt);
00477       myrinfo->ed += myrinfo->id-myedegrees[k].ed;
00478       SWAP(myrinfo->id, myedegrees[k].ed, j);
00479       if (myedegrees[k].ed == 0) 
00480         myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00481       else
00482         myedegrees[k].pid = from;
00483 
00484       if (myrinfo->ed == 0)
00485         BNDDelete(nbnd, bndind, bndptr, i);
00486 
00487       /* Update the degrees of adjacent vertices */
00488       for (j=xadj[i]; j<xadj[i+1]; j++) {
00489         ii = adjncy[j];
00490         me = where[ii];
00491 
00492         myrinfo = graph->rinfo+ii;
00493         if (myrinfo->edegrees == NULL) {
00494           myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00495           ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
00496         }
00497         myedegrees = myrinfo->edegrees;
00498 
00499         ASSERT(CheckRInfo(myrinfo));
00500 
00501         oldgain = (myrinfo->ed-myrinfo->id);
00502 
00503         if (me == from) {
00504           INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00505 
00506           if (myrinfo->ed > 0 && bndptr[ii] == -1)
00507             BNDInsert(nbnd, bndind, bndptr, ii);
00508         }
00509         else if (me == to) {
00510           INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00511 
00512           if (myrinfo->ed == 0 && bndptr[ii] != -1)
00513             BNDDelete(nbnd, bndind, bndptr, ii);
00514         }
00515 
00516         /* Remove contribution from the .ed of 'from' */
00517         if (me != from) {
00518           for (k=0; k<myrinfo->ndegrees; k++) {
00519             if (myedegrees[k].pid == from) {
00520               if (myedegrees[k].ed == adjwgt[j])
00521                 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00522               else
00523                 myedegrees[k].ed -= adjwgt[j];
00524               break;
00525             }
00526           }
00527         }
00528 
00529         /* Add contribution to the .ed of 'to' */
00530         if (me != to) {
00531           for (k=0; k<myrinfo->ndegrees; k++) {
00532             if (myedegrees[k].pid == to) {
00533               myedegrees[k].ed += adjwgt[j];
00534               break;
00535             }
00536           }
00537           if (k == myrinfo->ndegrees) {
00538             myedegrees[myrinfo->ndegrees].pid = to;
00539             myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
00540           }
00541         }
00542 
00543         /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
00544         if (me != from && me != to) {
00545           pmat[me*nparts+from] -= adjwgt[j];
00546           pmat[from*nparts+me] -= adjwgt[j];
00547           if (pmat[me*nparts+from] == 0) {
00548             ndoms[me]--;
00549             if (ndoms[me]+1 == maxndoms)
00550               maxndoms = ndoms[idxamax(nparts, ndoms)];
00551           }
00552           if (pmat[from*nparts+me] == 0) {
00553             ndoms[from]--;
00554             if (ndoms[from]+1 == maxndoms)
00555               maxndoms = ndoms[idxamax(nparts, ndoms)];
00556           }
00557 
00558           if (pmat[me*nparts+to] == 0) {
00559             ndoms[me]++;
00560             if (ndoms[me] > maxndoms) {
00561               IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms));
00562               maxndoms = ndoms[me];
00563             }
00564           }
00565           if (pmat[to*nparts+me] == 0) {
00566             ndoms[to]++;
00567             if (ndoms[to] > maxndoms) {
00568               IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms));
00569               maxndoms = ndoms[to];
00570             }
00571           }
00572           pmat[me*nparts+to] += adjwgt[j];
00573           pmat[to*nparts+me] += adjwgt[j];
00574         }
00575 
00576         /* Update the queue */
00577         if (me == to || me == from) { 
00578           gain = myrinfo->ed-myrinfo->id;
00579           if (moved[ii] == 2) {
00580             if (myrinfo->ed > 0)
00581               PQueueUpdate(&queue, ii, oldgain, gain);
00582             else {
00583               PQueueDelete(&queue, ii, oldgain);
00584               moved[ii] = -1;
00585             }
00586           }
00587           else if (moved[ii] == -1 && myrinfo->ed > 0) {
00588             PQueueInsert(&queue, ii, gain);
00589             moved[ii] = 2;
00590           }
00591         } 
00592 
00593         ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
00594         ASSERT(CheckRInfo(myrinfo));
00595       }
00596       nmoves++;
00597     }
00598 
00599     graph->nbnd = nbnd;
00600 
00601     IFSET(ctrl->dbglvl, DBG_REFINE,
00602        printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, %d\n",
00603                pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
00604                1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut,idxsum(nparts, ndoms)));
00605   }
00606 
00607   PQueueFree(ctrl, &queue);
00608 
00609   idxwspacefree(ctrl, nparts);
00610   idxwspacefree(ctrl, nparts);
00611   idxwspacefree(ctrl, nparts);
00612   idxwspacefree(ctrl, nparts);
00613   idxwspacefree(ctrl, nparts);
00614   idxwspacefree(ctrl, nvtxs);
00615   idxwspacefree(ctrl, nvtxs);
00616 
00617 }
00618 
00619 
00620 
00621 
00622 /*************************************************************************
00623 * This function computes the subdomain graph
00624 **************************************************************************/
00625 void PrintSubDomainGraph(GraphType *graph, int nparts, idxtype *where)
00626 {
00627   int i, j, k, me, nvtxs, total, max;
00628   idxtype *xadj, *adjncy, *adjwgt, *pmat;
00629 
00630   nvtxs = graph->nvtxs;
00631   xadj = graph->xadj;
00632   adjncy = graph->adjncy;
00633   adjwgt = graph->adjwgt;
00634 
00635   pmat = idxsmalloc(nparts*nparts, 0, "ComputeSubDomainGraph: pmat");
00636 
00637   for (i=0; i<nvtxs; i++) {
00638     me = where[i];
00639     for (j=xadj[i]; j<xadj[i+1]; j++) {
00640       k = adjncy[j];
00641       if (where[k] != me) 
00642         pmat[me*nparts+where[k]] += adjwgt[j];
00643     }
00644   }
00645 
00646   /* printf("Subdomain Info\n"); */
00647   total = max = 0;
00648   for (i=0; i<nparts; i++) {
00649     for (k=0, j=0; j<nparts; j++) {
00650       if (pmat[i*nparts+j] > 0)
00651         k++;
00652     }
00653     total += k;
00654 
00655     if (k > max)
00656       max = k;
00657 /*
00658     printf("%2d -> %2d  ", i, k);
00659     for (j=0; j<nparts; j++) {
00660       if (pmat[i*nparts+j] > 0)
00661         printf("[%2d %4d] ", j, pmat[i*nparts+j]);
00662     }
00663     printf("\n");
00664 */
00665   }
00666   printf("Total adjacent subdomains: %d, Max: %d\n", total, max);
00667 
00668   free(pmat);
00669 }
00670 
00671 
00672 
00673 /*************************************************************************
00674 * This function computes the subdomain graph
00675 **************************************************************************/
00676 void ComputeSubDomainGraph(GraphType *graph, int nparts, idxtype *pmat, idxtype *ndoms)
00677 {
00678   int i, j, k, me, nvtxs, ndegrees;
00679   idxtype *xadj, *adjncy, *adjwgt, *where;
00680   RInfoType *rinfo;
00681   EDegreeType *edegrees;
00682 
00683   nvtxs = graph->nvtxs;
00684   xadj = graph->xadj;
00685   adjncy = graph->adjncy;
00686   adjwgt = graph->adjwgt;
00687   where = graph->where;
00688   rinfo = graph->rinfo;
00689 
00690   idxset(nparts*nparts, 0, pmat);
00691 
00692   for (i=0; i<nvtxs; i++) {
00693     if (rinfo[i].ed > 0) {
00694       me = where[i];
00695       ndegrees = rinfo[i].ndegrees;
00696       edegrees = rinfo[i].edegrees;
00697 
00698       k = me*nparts;
00699       for (j=0; j<ndegrees; j++) 
00700         pmat[k+edegrees[j].pid] += edegrees[j].ed;
00701     }
00702   }
00703 
00704   for (i=0; i<nparts; i++) {
00705     ndoms[i] = 0;
00706     for (j=0; j<nparts; j++) {
00707       if (pmat[i*nparts+j] > 0)
00708         ndoms[i]++;
00709     }
00710   }
00711 
00712 }
00713 
00714 
00715 
00716 
00717 
00718 /*************************************************************************
00719 * This function computes the subdomain graph
00720 **************************************************************************/
00721 void EliminateSubDomainEdges(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts)
00722 {
00723   int i, ii, j, k, me, other, nvtxs, total, max, avg, totalout, nind, ncand, ncand2, target, target2, nadd;
00724   int min, move, cpwgt, tvwgt;
00725   idxtype *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt, *pmat, *ndoms, *mypmat, *otherpmat, *ind;
00726   KeyValueType *cand, *cand2;
00727 
00728   nvtxs = graph->nvtxs;
00729   xadj = graph->xadj;
00730   adjncy = graph->adjncy;
00731   vwgt = graph->vwgt;
00732   adjwgt = graph->adjwgt;
00733 
00734   where = graph->where;
00735   pwgts = graph->pwgts;  /* We assume that this is properly initialized */
00736 
00737   maxpwgt = idxwspacemalloc(ctrl, nparts);
00738   ndoms = idxwspacemalloc(ctrl, nparts);
00739   otherpmat = idxwspacemalloc(ctrl, nparts);
00740   ind = idxwspacemalloc(ctrl, nvtxs);
00741   pmat = ctrl->wspace.pmat;
00742 
00743   cand = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
00744   cand2 = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
00745 
00746   /* Compute the pmat matrix and ndoms */
00747   ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
00748 
00749 
00750   /* Compute the maximum allowed weight for each domain */
00751   tvwgt = idxsum(nparts, pwgts);
00752   for (i=0; i<nparts; i++)
00753     maxpwgt[i] = 1.25*tpwgts[i]*tvwgt;
00754 
00755 
00756   /* Get into the loop eliminating subdomain connections */
00757   for (;;) {
00758     total = idxsum(nparts, ndoms);
00759     avg = total/nparts;
00760     max = ndoms[idxamax(nparts, ndoms)];
00761 
00762     /* printf("Adjacent Subdomain Stats: Total: %3d, Max: %3d, Avg: %3d [%5d]\n", total, max, avg, idxsum(nparts*nparts, pmat)); */
00763 
00764     if (max < 1.4*avg)
00765       break;
00766 
00767     me = idxamax(nparts, ndoms);
00768     mypmat = pmat + me*nparts;
00769     totalout = idxsum(nparts, mypmat);
00770 
00771     /*printf("Me: %d, TotalOut: %d,\n", me, totalout);*/
00772 
00773     /* Sort the connections according to their cut */
00774     for (ncand2=0, i=0; i<nparts; i++) {
00775       if (mypmat[i] > 0) {
00776         cand2[ncand2].key = mypmat[i];
00777         cand2[ncand2++].val = i;
00778       }
00779     }
00780     ikeysort(ncand2, cand2);
00781 
00782     move = 0;
00783     for (min=0; min<ncand2; min++) {
00784       if (cand2[min].key > totalout/(2*ndoms[me])) 
00785         break;
00786 
00787       other = cand2[min].val;
00788 
00789       /*printf("\tMinOut: %d to %d\n", mypmat[other], other);*/
00790 
00791       idxset(nparts, 0, otherpmat);
00792 
00793       /* Go and find the vertices in 'other' that are connected in 'me' */
00794       for (nind=0, i=0; i<nvtxs; i++) {
00795         if (where[i] == other) {
00796           for (j=xadj[i]; j<xadj[i+1]; j++) {
00797             if (where[adjncy[j]] == me) {
00798               ind[nind++] = i;
00799               break;
00800             }
00801           }
00802         }
00803       }
00804 
00805       /* Go and construct the otherpmat to see where these nind vertices are connected to */
00806       for (cpwgt=0, ii=0; ii<nind; ii++) {
00807         i = ind[ii];
00808         cpwgt += vwgt[i];
00809 
00810         for (j=xadj[i]; j<xadj[i+1]; j++) 
00811           otherpmat[where[adjncy[j]]] += adjwgt[j];
00812       }
00813       otherpmat[other] = 0;
00814 
00815       for (ncand=0, i=0; i<nparts; i++) {
00816         if (otherpmat[i] > 0) {
00817           cand[ncand].key = -otherpmat[i];
00818           cand[ncand++].val = i;
00819         }
00820       }
00821       ikeysort(ncand, cand);
00822 
00823       /* 
00824        * Go through and the select the first domain that is common with 'me', and
00825        * does not increase the ndoms[target] higher than my ndoms, subject to the
00826        * maxpwgt constraint. Traversal is done from the mostly connected to the least.
00827        */
00828       target = target2 = -1;
00829       for (i=0; i<ncand; i++) {
00830         k = cand[i].val;
00831 
00832         if (mypmat[k] > 0) {
00833           if (pwgts[k] + cpwgt > maxpwgt[k])  /* Check if balance will go off */
00834             continue;
00835 
00836           for (j=0; j<nparts; j++) {
00837             if (otherpmat[j] > 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0)
00838               break;
00839           }
00840           if (j == nparts) { /* No bad second level effects */
00841             for (nadd=0, j=0; j<nparts; j++) {
00842               if (otherpmat[j] > 0 && pmat[nparts*k+j] == 0)
00843                 nadd++;
00844             }
00845 
00846             /*printf("\t\tto=%d, nadd=%d, %d\n", k, nadd, ndoms[k]);*/
00847             if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) {
00848               target2 = k;
00849             }
00850             if (nadd == 0) {
00851               target = k;
00852               break;
00853             }
00854           }
00855         }
00856       }
00857       if (target == -1 && target2 != -1)
00858         target = target2;
00859 
00860       if (target == -1) {
00861         /* printf("\t\tCould not make the move\n");*/
00862         continue;
00863       }
00864 
00865       /*printf("\t\tMoving to %d\n", target);*/
00866 
00867       /* Update the partition weights */
00868       INC_DEC(pwgts[target], pwgts[other], cpwgt);
00869 
00870       MoveGroupMConn(ctrl, graph, ndoms, pmat, nparts, target, nind, ind);
00871 
00872       move = 1;
00873       break;
00874     }
00875 
00876     if (move == 0)
00877       break;
00878   }
00879 
00880   idxwspacefree(ctrl, nparts);
00881   idxwspacefree(ctrl, nparts);
00882   idxwspacefree(ctrl, nparts);
00883   idxwspacefree(ctrl, nvtxs);
00884 
00885   GKfree(&cand, &cand2, LTERM);
00886 }
00887 
00888 
00889 /*************************************************************************
00890 * This function moves a collection of vertices and updates their rinfo
00891 **************************************************************************/
00892 void MoveGroupMConn(CtrlType *ctrl, GraphType *graph, idxtype *ndoms, idxtype *pmat,
00893                     int nparts, int to, int nind, idxtype *ind)
00894 {
00895   int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees; 
00896   int from, me;
00897   idxtype *xadj, *adjncy, *adjwgt;
00898   idxtype *where, *bndptr, *bndind;
00899   EDegreeType *myedegrees;
00900   RInfoType *myrinfo;
00901 
00902   nvtxs = graph->nvtxs;
00903   xadj = graph->xadj;
00904   adjncy = graph->adjncy;
00905   adjwgt = graph->adjwgt;
00906 
00907   where = graph->where;
00908   bndptr = graph->bndptr;
00909   bndind = graph->bndind;
00910 
00911   nbnd = graph->nbnd;
00912 
00913   for (iii=0; iii<nind; iii++) {
00914     i = ind[iii];
00915     from = where[i];
00916 
00917     myrinfo = graph->rinfo+i;
00918     if (myrinfo->edegrees == NULL) {
00919       myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00920       ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
00921       myrinfo->ndegrees = 0;
00922     }
00923     myedegrees = myrinfo->edegrees;
00924 
00925     /* find the location of 'to' in myrinfo or create it if it is not there */
00926     for (k=0; k<myrinfo->ndegrees; k++) {
00927       if (myedegrees[k].pid == to)
00928         break;
00929     }
00930     if (k == myrinfo->ndegrees) {
00931       myedegrees[k].pid = to;
00932       myedegrees[k].ed = 0;
00933       myrinfo->ndegrees++;
00934     }
00935 
00936     graph->mincut -= myedegrees[k].ed-myrinfo->id;
00937 
00938     /* Update pmat to reflect the move of 'i' */
00939     pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
00940     pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
00941     if (pmat[from*nparts+to] == 0) 
00942       ndoms[from]--;
00943     if (pmat[to*nparts+from] == 0) 
00944       ndoms[to]--;
00945 
00946     /* Update where, weight, and ID/ED information of the vertex you moved */
00947     where[i] = to;
00948     myrinfo->ed += myrinfo->id-myedegrees[k].ed;
00949     SWAP(myrinfo->id, myedegrees[k].ed, j);
00950     if (myedegrees[k].ed == 0) 
00951       myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00952     else
00953       myedegrees[k].pid = from;
00954 
00955     if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1)
00956       BNDDelete(nbnd, bndind, bndptr, i);
00957 
00958     /* Update the degrees of adjacent vertices */
00959     for (j=xadj[i]; j<xadj[i+1]; j++) {
00960       ii = adjncy[j];
00961       me = where[ii];
00962 
00963       myrinfo = graph->rinfo+ii;
00964       if (myrinfo->edegrees == NULL) {
00965         myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
00966         ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
00967       }
00968       myedegrees = myrinfo->edegrees;
00969 
00970       ASSERT(CheckRInfo(myrinfo));
00971 
00972       if (me == from) {
00973         INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00974 
00975         if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
00976           BNDInsert(nbnd, bndind, bndptr, ii);
00977       }
00978       else if (me == to) {
00979         INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00980 
00981         if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
00982           BNDDelete(nbnd, bndind, bndptr, ii);
00983       }
00984 
00985       /* Remove contribution from the .ed of 'from' */
00986       if (me != from) {
00987         for (k=0; k<myrinfo->ndegrees; k++) {
00988           if (myedegrees[k].pid == from) {
00989             if (myedegrees[k].ed == adjwgt[j])
00990               myedegrees[k] = myedegrees[--myrinfo->ndegrees];
00991             else
00992               myedegrees[k].ed -= adjwgt[j];
00993             break;
00994           }
00995         }
00996       }
00997 
00998       /* Add contribution to the .ed of 'to' */
00999       if (me != to) {
01000         for (k=0; k<myrinfo->ndegrees; k++) {
01001           if (myedegrees[k].pid == to) {
01002             myedegrees[k].ed += adjwgt[j];
01003             break;
01004           }
01005         }
01006         if (k == myrinfo->ndegrees) {
01007           myedegrees[myrinfo->ndegrees].pid = to;
01008           myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
01009         }
01010       }
01011 
01012       /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
01013       if (me != from && me != to) {
01014         pmat[me*nparts+from] -= adjwgt[j];
01015         pmat[from*nparts+me] -= adjwgt[j];
01016         if (pmat[me*nparts+from] == 0) 
01017           ndoms[me]--;
01018         if (pmat[from*nparts+me] == 0) 
01019           ndoms[from]--;
01020 
01021         if (pmat[me*nparts+to] == 0) 
01022           ndoms[me]++;
01023         if (pmat[to*nparts+me] == 0) 
01024           ndoms[to]++;
01025 
01026         pmat[me*nparts+to] += adjwgt[j];
01027         pmat[to*nparts+me] += adjwgt[j];
01028       }
01029 
01030       ASSERT(CheckRInfo(myrinfo));
01031     }
01032 
01033     ASSERT(CheckRInfo(graph->rinfo+i));
01034   }
01035 
01036   graph->nbnd = nbnd;
01037 
01038 }
01039 
01040 
01041 
01042 
01043 /*************************************************************************
01044 * This function finds all the connected components induced by the 
01045 * partitioning vector in wgraph->where and tries to push them around to 
01046 * remove some of them
01047 **************************************************************************/
01048 void EliminateComponents(CtrlType *ctrl, GraphType *graph, int nparts, floattype *tpwgts, floattype ubfactor)
01049 {
01050   int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, other, target, deltawgt;
01051   idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt;
01052   idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps;
01053 
01054   nvtxs = graph->nvtxs;
01055   xadj = graph->xadj;
01056   adjncy = graph->adjncy;
01057   vwgt = graph->vwgt;
01058   adjwgt = graph->adjwgt;
01059 
01060   where = graph->where;
01061   pwgts = graph->pwgts;
01062 
01063   touched = idxset(nvtxs, 0, idxwspacemalloc(ctrl, nvtxs));
01064   cptr    = idxwspacemalloc(ctrl, nvtxs+1);
01065   cind    = idxwspacemalloc(ctrl, nvtxs);
01066   perm    = idxwspacemalloc(ctrl, nvtxs);
01067   todo    = idxwspacemalloc(ctrl, nvtxs);
01068   maxpwgt = idxwspacemalloc(ctrl, nparts);
01069   cpvec   = idxwspacemalloc(ctrl, nparts);
01070   npcmps  = idxset(nparts, 0, idxwspacemalloc(ctrl, nparts));
01071 
01072   for (i=0; i<nvtxs; i++) 
01073     perm[i] = todo[i] = i;
01074 
01075   /* Find the connected componends induced by the partition */
01076   ncmps = -1;
01077   first = last = 0;
01078   nleft = nvtxs;
01079   while (nleft > 0) {
01080     if (first == last) { /* Find another starting vertex */
01081       cptr[++ncmps] = first;
01082       ASSERT(touched[todo[0]] == 0);
01083       i = todo[0];
01084       cind[last++] = i;
01085       touched[i] = 1;
01086       me = where[i];
01087       npcmps[me]++;
01088     }
01089 
01090     i = cind[first++];
01091     k = perm[i];
01092     j = todo[k] = todo[--nleft];
01093     perm[j] = k;
01094 
01095     for (j=xadj[i]; j<xadj[i+1]; j++) {
01096       k = adjncy[j];
01097       if (where[k] == me && !touched[k]) {
01098         cind[last++] = k;
01099         touched[k] = 1;
01100       }
01101     }
01102   }
01103   cptr[++ncmps] = first;
01104 
01105   /* printf("I found %d components, for this %d-way partition\n", ncmps, nparts); */
01106 
01107   if (ncmps > nparts) { /* There are more components than processors */
01108     /* First determine the max allowed load imbalance */
01109     tvwgt = idxsum(nparts, pwgts);
01110     for (i=0; i<nparts; i++)
01111       maxpwgt[i] = ubfactor*tpwgts[i]*tvwgt;
01112 
01113     deltawgt = 5;
01114 
01115     for (i=0; i<ncmps; i++) {
01116       me = where[cind[cptr[i]]];  /* Get the domain of this component */
01117       if (npcmps[me] == 1)
01118         continue;  /* Skip it because it is contigous */
01119 
01120       /*printf("Trying to move %d from %d\n", i, me); */
01121 
01122       /* Determine the weight of the block to be moved and abort if too high */
01123       for (cwgt=0, j=cptr[i]; j<cptr[i+1]; j++) 
01124         cwgt += vwgt[cind[j]];
01125 
01126       if (cwgt > .30*pwgts[me])
01127         continue;  /* Skip the component if it is over 30% of the weight */
01128 
01129       /* Determine the connectivity */
01130       idxset(nparts, 0, cpvec);
01131       for (j=cptr[i]; j<cptr[i+1]; j++) {
01132         ii = cind[j];
01133         for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) 
01134           cpvec[where[adjncy[jj]]] += adjwgt[jj];
01135       }
01136       cpvec[me] = 0;
01137 
01138       target = -1;
01139       for (j=0; j<nparts; j++) {
01140         if (cpvec[j] > 0 && (cwgt < deltawgt || pwgts[j] + cwgt < maxpwgt[j])) {
01141           if (target == -1 || cpvec[target] < cpvec[j])
01142             target = j;
01143         }
01144       }
01145 
01146       /* printf("\tMoving it to %d [%d]\n", target, cpvec[target]);*/
01147 
01148       if (target != -1) {
01149         /* Assign all the vertices of 'me' to 'target' and update data structures */
01150         INC_DEC(pwgts[target], pwgts[me], cwgt);
01151         npcmps[me]--;
01152 
01153         MoveGroup(ctrl, graph, nparts, target, i, cptr, cind);
01154       }
01155     }
01156 
01157   }
01158 
01159   idxwspacefree(ctrl, nparts);
01160   idxwspacefree(ctrl, nparts);
01161   idxwspacefree(ctrl, nparts);
01162   idxwspacefree(ctrl, nvtxs);
01163   idxwspacefree(ctrl, nvtxs);
01164   idxwspacefree(ctrl, nvtxs);
01165   idxwspacefree(ctrl, nvtxs);
01166   idxwspacefree(ctrl, nvtxs+1);
01167 
01168 }
01169 
01170 
01171 /*************************************************************************
01172 * This function moves a collection of vertices and updates their rinfo
01173 **************************************************************************/
01174 void MoveGroup(CtrlType *ctrl, GraphType *graph, int nparts, int to, int gid, idxtype *ptr, idxtype *ind)
01175 {
01176   int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees; 
01177   int from, me;
01178   idxtype *xadj, *adjncy, *adjwgt;
01179   idxtype *where, *bndptr, *bndind;
01180   EDegreeType *myedegrees;
01181   RInfoType *myrinfo;
01182 
01183   nvtxs = graph->nvtxs;
01184   xadj = graph->xadj;
01185   adjncy = graph->adjncy;
01186   adjwgt = graph->adjwgt;
01187 
01188   where = graph->where;
01189   bndptr = graph->bndptr;
01190   bndind = graph->bndind;
01191 
01192   nbnd = graph->nbnd;
01193 
01194   for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
01195     i = ind[iii];
01196     from = where[i];
01197 
01198     myrinfo = graph->rinfo+i;
01199     if (myrinfo->edegrees == NULL) {
01200       myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
01201       ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
01202       myrinfo->ndegrees = 0;
01203     }
01204     myedegrees = myrinfo->edegrees;
01205 
01206     /* find the location of 'to' in myrinfo or create it if it is not there */
01207     for (k=0; k<myrinfo->ndegrees; k++) {
01208       if (myedegrees[k].pid == to)
01209         break;
01210     }
01211     if (k == myrinfo->ndegrees) {
01212       myedegrees[k].pid = to;
01213       myedegrees[k].ed = 0;
01214       myrinfo->ndegrees++;
01215     }
01216 
01217     graph->mincut -= myedegrees[k].ed-myrinfo->id;
01218 
01219 
01220     /* Update where, weight, and ID/ED information of the vertex you moved */
01221     where[i] = to;
01222     myrinfo->ed += myrinfo->id-myedegrees[k].ed;
01223     SWAP(myrinfo->id, myedegrees[k].ed, j);
01224     if (myedegrees[k].ed == 0) 
01225       myedegrees[k] = myedegrees[--myrinfo->ndegrees];
01226     else
01227       myedegrees[k].pid = from;
01228 
01229     if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1)
01230       BNDDelete(nbnd, bndind, bndptr, i);
01231 
01232     /* Update the degrees of adjacent vertices */
01233     for (j=xadj[i]; j<xadj[i+1]; j++) {
01234       ii = adjncy[j];
01235       me = where[ii];
01236 
01237       myrinfo = graph->rinfo+ii;
01238       if (myrinfo->edegrees == NULL) {
01239         myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
01240         ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
01241       }
01242       myedegrees = myrinfo->edegrees;
01243 
01244       ASSERT(CheckRInfo(myrinfo));
01245 
01246       if (me == from) {
01247         INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
01248 
01249         if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
01250           BNDInsert(nbnd, bndind, bndptr, ii);
01251       }
01252       else if (me == to) {
01253         INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
01254 
01255         if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
01256           BNDDelete(nbnd, bndind, bndptr, ii);
01257       }
01258 
01259       /* Remove contribution from the .ed of 'from' */
01260       if (me != from) {
01261         for (k=0; k<myrinfo->ndegrees; k++) {
01262           if (myedegrees[k].pid == from) {
01263             if (myedegrees[k].ed == adjwgt[j])
01264               myedegrees[k] = myedegrees[--myrinfo->ndegrees];
01265             else
01266               myedegrees[k].ed -= adjwgt[j];
01267             break;
01268           }
01269         }
01270       }
01271 
01272       /* Add contribution to the .ed of 'to' */
01273       if (me != to) {
01274         for (k=0; k<myrinfo->ndegrees; k++) {
01275           if (myedegrees[k].pid == to) {
01276             myedegrees[k].ed += adjwgt[j];
01277             break;
01278           }
01279         }
01280         if (k == myrinfo->ndegrees) {
01281           myedegrees[myrinfo->ndegrees].pid = to;
01282           myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
01283         }
01284       }
01285 
01286       ASSERT(CheckRInfo(myrinfo));
01287     }
01288 
01289     ASSERT(CheckRInfo(graph->rinfo+i));
01290   }
01291 
01292   graph->nbnd = nbnd;
01293 
01294 }
01295
libs/ck-libs/parmetis/METISLib/subdomains.c
