Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * sfm.c
00005  *
00006  * This file contains code that implementes an FM-based separator refinement
00007  *
00008  * Started 8/1/97
00009  * George
00010  *
00011  * $Id: sfm.c 10874 2011-10-17 23:13:00Z karypis $
00012  *
00013  */
00014 
00015 #include "metislib.h"
00016 
00017 
00018 /*************************************************************************/
00020 /**************************************************************************/
00021 void FM_2WayNodeRefine2Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter)
00022 {
00023   idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
00024   idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00025   idx_t *mptr, *mind, *moved, *swaps;
00026   rpq_t *queues[2]; 
00027   nrinfo_t *rinfo;
00028   idx_t higain, oldgain, mincut, initcut, mincutorder;  
00029   idx_t pass, to, other, limit;
00030   idx_t badmaxpwgt, mindiff, newdiff;
00031   idx_t u[2], g[2];
00032   real_t mult;   
00033 
00034   WCOREPUSH;
00035 
00036   nvtxs  = graph->nvtxs;
00037   xadj   = graph->xadj;
00038   adjncy = graph->adjncy;
00039   vwgt   = graph->vwgt;
00040 
00041   bndind = graph->bndind;
00042   bndptr = graph->bndptr;
00043   where  = graph->where;
00044   pwgts  = graph->pwgts;
00045   rinfo  = graph->nrinfo;
00046 
00047   queues[0] = rpqCreate(nvtxs);
00048   queues[1] = rpqCreate(nvtxs);
00049 
00050   moved = iwspacemalloc(ctrl, nvtxs);
00051   swaps = iwspacemalloc(ctrl, nvtxs);
00052   mptr  = iwspacemalloc(ctrl, nvtxs+1);
00053   mind  = iwspacemalloc(ctrl, 2*nvtxs);
00054 
00055   mult = 0.5*ctrl->ubfactors[0];
00056   badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
00057 
00058   IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00059     printf("Partitions-N2: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00060 
00061   for (pass=0; pass<niter; pass++) {
00062     iset(nvtxs, -1, moved);
00063     rpqReset(queues[0]);
00064     rpqReset(queues[1]);
00065 
00066     mincutorder = -1;
00067     initcut = mincut = graph->mincut;
00068     nbnd = graph->nbnd;
00069 
00070     /* use the swaps array in place of the traditional perm array to save memory */
00071     irandArrayPermute(nbnd, swaps, nbnd, 1);
00072     for (ii=0; ii<nbnd; ii++) {
00073       i = bndind[swaps[ii]];
00074       ASSERT(where[i] == 2);
00075       rpqInsert(queues[0], i, vwgt[i]-rinfo[i].edegrees[1]);
00076       rpqInsert(queues[1], i, vwgt[i]-rinfo[i].edegrees[0]);
00077     }
00078 
00079     ASSERT(CheckNodeBnd(graph, nbnd));
00080     ASSERT(CheckNodePartitionParams(graph));
00081 
00082     limit = (ctrl->compress ? gk_min(5*nbnd, 400) : gk_min(2*nbnd, 300));
00083 
00084     /******************************************************
00085     * Get into the FM loop
00086     *******************************************************/
00087     mptr[0] = nmind = 0;
00088     mindiff = iabs(pwgts[0]-pwgts[1]);
00089     to = (pwgts[0] < pwgts[1] ? 0 : 1);
00090     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00091       u[0] = rpqSeeTopVal(queues[0]);  
00092       u[1] = rpqSeeTopVal(queues[1]);
00093       if (u[0] != -1 && u[1] != -1) {
00094         g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];
00095         g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];
00096 
00097         to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2)); 
00098 
00099         if (pwgts[to]+vwgt[u[to]] > badmaxpwgt) 
00100           to = (to+1)%2;
00101       }
00102       else if (u[0] == -1 && u[1] == -1) {
00103         break;
00104       }
00105       else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
00106         to = 0;
00107       }
00108       else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
00109         to = 1;
00110       }
00111       else
00112         break;
00113 
00114       other = (to+1)%2;
00115 
00116       higain = rpqGetTop(queues[to]);
00117       if (moved[higain] == -1) /* Delete if it was in the separator originally */
00118         rpqDelete(queues[other], higain);
00119 
00120       ASSERT(bndptr[higain] != -1);
00121 
00122       /* The following check is to ensure we break out if there is a posibility
00123          of over-running the mind array.  */
00124       if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1) 
00125         break;
00126 
00127       pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
00128 
00129       newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
00130       if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
00131         mincut = pwgts[2];
00132         mincutorder = nswaps;
00133         mindiff = newdiff;
00134       }
00135       else {
00136         if (nswaps - mincutorder > 2*limit || 
00137             (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
00138           pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
00139           break; /* No further improvement, break out */
00140         }
00141       }
00142 
00143       BNDDelete(nbnd, bndind, bndptr, higain);
00144       pwgts[to] += vwgt[higain];
00145       where[higain] = to;
00146       moved[higain] = nswaps;
00147       swaps[nswaps] = higain;  
00148 
00149 
00150       /**********************************************************
00151       * Update the degrees of the affected nodes
00152       ***********************************************************/
00153       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00154         k = adjncy[j];
00155         if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00156           oldgain = vwgt[k]-rinfo[k].edegrees[to];
00157           rinfo[k].edegrees[to] += vwgt[higain];
00158           if (moved[k] == -1 || moved[k] == -(2+other))
00159             rpqUpdate(queues[other], k, oldgain-vwgt[higain]);
00160         }
00161         else if (where[k] == other) { /* This vertex is pulled into the separator */
00162           ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
00163           BNDInsert(nbnd, bndind, bndptr, k);
00164 
00165           mind[nmind++] = k;  /* Keep track for rollback */
00166           where[k] = 2;
00167           pwgts[other] -= vwgt[k];
00168 
00169           edegrees = rinfo[k].edegrees;
00170           edegrees[0] = edegrees[1] = 0;
00171           for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00172             kk = adjncy[jj];
00173             if (where[kk] != 2) 
00174               edegrees[where[kk]] += vwgt[kk];
00175             else {
00176               oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
00177               rinfo[kk].edegrees[other] -= vwgt[k];
00178               if (moved[kk] == -1 || moved[kk] == -(2+to))
00179                 rpqUpdate(queues[to], kk, oldgain+vwgt[k]);
00180             }
00181           }
00182 
00183           /* Insert the new vertex into the priority queue. Only one side! */
00184           if (moved[k] == -1) {
00185             rpqInsert(queues[to], k, vwgt[k]-edegrees[other]);
00186             moved[k] = -(2+to);
00187           }
00188         }
00189       }
00190       mptr[nswaps+1] = nmind;
00191 
00192       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
00193             printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] [%4"PRIDX" %4"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
00194 
00195     }
00196 
00197 
00198     /****************************************************************
00199     * Roll back computation 
00200     *****************************************************************/
00201     for (nswaps--; nswaps>mincutorder; nswaps--) {
00202       higain = swaps[nswaps];
00203 
00204       ASSERT(CheckNodePartitionParams(graph));
00205 
00206       to = where[higain];
00207       other = (to+1)%2;
00208       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00209       where[higain] = 2;
00210       BNDInsert(nbnd, bndind, bndptr, higain);
00211 
00212       edegrees = rinfo[higain].edegrees;
00213       edegrees[0] = edegrees[1] = 0;
00214       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00215         k = adjncy[j];
00216         if (where[k] == 2) 
00217           rinfo[k].edegrees[to] -= vwgt[higain];
00218         else
00219           edegrees[where[k]] += vwgt[k];
00220       }
00221 
00222       /* Push nodes out of the separator */
00223       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00224         k = mind[j];
00225         ASSERT(where[k] == 2);
00226         where[k] = other;
00227         INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
00228         BNDDelete(nbnd, bndind, bndptr, k);
00229         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00230           kk = adjncy[jj];
00231           if (where[kk] == 2) 
00232             rinfo[kk].edegrees[other] += vwgt[k];
00233         }
00234       }
00235     }
00236 
00237     ASSERT(mincut == pwgts[2]);
00238 
00239     IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00240       printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00241 
00242     graph->mincut = mincut;
00243     graph->nbnd = nbnd;
00244 
00245     if (mincutorder == -1 || mincut >= initcut)
00246       break;
00247   }
00248 
00249   rpqDestroy(queues[0]);
00250   rpqDestroy(queues[1]);
00251 
00252   WCOREPOP;
00253 }
00254 
00255 
00256 /*************************************************************************/
00262 /**************************************************************************/
00263 void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter)
00264 {
00265   idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind, iend;
00266   idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00267   idx_t *mptr, *mind, *swaps;
00268   rpq_t *queue; 
00269   nrinfo_t *rinfo;
00270   idx_t higain, mincut, initcut, mincutorder;   
00271   idx_t pass, to, other, limit;
00272   idx_t badmaxpwgt, mindiff, newdiff;
00273   real_t mult;
00274 
00275   WCOREPUSH;
00276 
00277   nvtxs  = graph->nvtxs;
00278   xadj   = graph->xadj;
00279   adjncy = graph->adjncy;
00280   vwgt   = graph->vwgt;
00281 
00282   bndind = graph->bndind;
00283   bndptr = graph->bndptr;
00284   where  = graph->where;
00285   pwgts  = graph->pwgts;
00286   rinfo  = graph->nrinfo;
00287 
00288   queue = rpqCreate(nvtxs);
00289 
00290   swaps = iwspacemalloc(ctrl, nvtxs);
00291   mptr  = iwspacemalloc(ctrl, nvtxs+1);
00292   mind  = iwspacemalloc(ctrl, 2*nvtxs);
00293 
00294   mult = 0.5*ctrl->ubfactors[0];
00295   badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
00296 
00297   IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00298     printf("Partitions-N1: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00299 
00300   to = (pwgts[0] < pwgts[1] ? 1 : 0);
00301   for (pass=0; pass<2*niter; pass++) {  /* the 2*niter is for the two sides */
00302     other = to; 
00303     to    = (to+1)%2;
00304 
00305     rpqReset(queue);
00306 
00307     mincutorder = -1;
00308     initcut = mincut = graph->mincut;
00309     nbnd = graph->nbnd;
00310 
00311     /* use the swaps array in place of the traditional perm array to save memory */
00312     irandArrayPermute(nbnd, swaps, nbnd, 1);
00313     for (ii=0; ii<nbnd; ii++) {
00314       i = bndind[swaps[ii]];
00315       ASSERT(where[i] == 2);
00316       rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);
00317     }
00318 
00319     ASSERT(CheckNodeBnd(graph, nbnd));
00320     ASSERT(CheckNodePartitionParams(graph));
00321 
00322     limit = (ctrl->compress ? gk_min(5*nbnd, 500) : gk_min(3*nbnd, 300));
00323 
00324     /******************************************************
00325     * Get into the FM loop
00326     *******************************************************/
00327     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux3Tmr));
00328     mptr[0] = nmind = 0;
00329     mindiff = iabs(pwgts[0]-pwgts[1]);
00330     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00331       if ((higain = rpqGetTop(queue)) == -1)
00332         break;
00333 
00334       ASSERT(bndptr[higain] != -1);
00335 
00336       /* The following check is to ensure we break out if there is a posibility
00337          of over-running the mind array.  */
00338       if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1) 
00339         break;
00340 
00341       if (pwgts[to]+vwgt[higain] > badmaxpwgt) 
00342         break;  /* No point going any further. Balance will be bad */
00343 
00344       pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
00345 
00346       newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
00347       if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
00348         mincut      = pwgts[2];
00349         mincutorder = nswaps;
00350         mindiff     = newdiff;
00351       }
00352       else {
00353         if (nswaps - mincutorder > 3*limit || 
00354             (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
00355           pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
00356           break; /* No further improvement, break out */
00357         }
00358       }
00359 
00360       BNDDelete(nbnd, bndind, bndptr, higain);
00361       pwgts[to]     += vwgt[higain];
00362       where[higain]  = to;
00363       swaps[nswaps]  = higain;  
00364 
00365 
00366       /**********************************************************
00367       * Update the degrees of the affected nodes
00368       ***********************************************************/
00369       IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux1Tmr));
00370       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00371         k = adjncy[j];
00372 
00373         if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00374           rinfo[k].edegrees[to] += vwgt[higain];
00375         }
00376         else if (where[k] == other) { /* This vertex is pulled into the separator */
00377           ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
00378           BNDInsert(nbnd, bndind, bndptr, k);
00379 
00380           mind[nmind++] = k;  /* Keep track for rollback */
00381           where[k] = 2;
00382           pwgts[other] -= vwgt[k];
00383 
00384           edegrees = rinfo[k].edegrees;
00385           edegrees[0] = edegrees[1] = 0;
00386           for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {
00387             kk = adjncy[jj];
00388             if (where[kk] != 2) 
00389               edegrees[where[kk]] += vwgt[kk];
00390             else {
00391               rinfo[kk].edegrees[other] -= vwgt[k];
00392 
00393               /* Since the moves are one-sided this vertex has not been moved yet */
00394               rpqUpdate(queue, kk, vwgt[kk]-rinfo[kk].edegrees[other]); 
00395             }
00396           }
00397 
00398           /* Insert the new vertex into the priority queue. Safe due to one-sided moves */
00399           rpqInsert(queue, k, vwgt[k]-edegrees[other]);
00400         }
00401       }
00402       mptr[nswaps+1] = nmind;
00403       IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux1Tmr));
00404 
00405 
00406       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
00407             printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"] [%3"PRIDX" %2"PRIDX"]\n", 
00408                 higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain], 
00409                 pwgts[0], pwgts[1], pwgts[2], nswaps, limit));
00410     }
00411     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux3Tmr));
00412 
00413 
00414     /****************************************************************
00415     * Roll back computation 
00416     *****************************************************************/
00417     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux2Tmr));
00418     for (nswaps--; nswaps>mincutorder; nswaps--) {
00419       higain = swaps[nswaps];
00420 
00421       ASSERT(CheckNodePartitionParams(graph));
00422       ASSERT(where[higain] == to);
00423 
00424       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00425       where[higain] = 2;
00426       BNDInsert(nbnd, bndind, bndptr, higain);
00427 
00428       edegrees = rinfo[higain].edegrees;
00429       edegrees[0] = edegrees[1] = 0;
00430       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00431         k = adjncy[j];
00432         if (where[k] == 2) 
00433           rinfo[k].edegrees[to] -= vwgt[higain];
00434         else
00435           edegrees[where[k]] += vwgt[k];
00436       }
00437 
00438       /* Push nodes out of the separator */
00439       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00440         k = mind[j];
00441         ASSERT(where[k] == 2);
00442         where[k] = other;
00443         INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
00444         BNDDelete(nbnd, bndind, bndptr, k);
00445         for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {
00446           kk = adjncy[jj];
00447           if (where[kk] == 2) 
00448             rinfo[kk].edegrees[other] += vwgt[k];
00449         }
00450       }
00451     }
00452     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux2Tmr));
00453 
00454     ASSERT(mincut == pwgts[2]);
00455 
00456     IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00457       printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00458 
00459     graph->mincut = mincut;
00460     graph->nbnd   = nbnd;
00461 
00462     if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))
00463       break;
00464   }
00465 
00466   rpqDestroy(queue);
00467 
00468   WCOREPOP;
00469 }
00470 
00471 
00472 /*************************************************************************/
00475 /*************************************************************************/
00476 void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph)
00477 {
00478   idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, gain;
00479   idx_t badmaxpwgt, higain, oldgain, pass, to, other;
00480   idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00481   idx_t *perm, *moved;
00482   rpq_t *queue; 
00483   nrinfo_t *rinfo;
00484   real_t mult;
00485 
00486   nvtxs  = graph->nvtxs;
00487   xadj   = graph->xadj;
00488   adjncy = graph->adjncy;
00489   vwgt   = graph->vwgt;
00490 
00491   bndind = graph->bndind;
00492   bndptr = graph->bndptr;
00493   where  = graph->where;
00494   pwgts  = graph->pwgts;
00495   rinfo  = graph->nrinfo;
00496 
00497   mult = 0.5*ctrl->ubfactors[0];
00498 
00499   badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));
00500   if (gk_max(pwgts[0], pwgts[1]) < badmaxpwgt)
00501     return;
00502   if (iabs(pwgts[0]-pwgts[1]) < 3*graph->tvwgt[0]/nvtxs)
00503     return;
00504 
00505   WCOREPUSH;
00506 
00507   to    = (pwgts[0] < pwgts[1] ? 0 : 1); 
00508   other = (to+1)%2;
00509 
00510   queue = rpqCreate(nvtxs);
00511 
00512   perm  = iwspacemalloc(ctrl, nvtxs);
00513   moved = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
00514 
00515   IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00516     printf("Partitions: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX" [B]\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00517 
00518   nbnd = graph->nbnd;
00519   irandArrayPermute(nbnd, perm, nbnd, 1);
00520   for (ii=0; ii<nbnd; ii++) {
00521     i = bndind[perm[ii]];
00522     ASSERT(where[i] == 2);
00523     rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);
00524   }
00525 
00526   ASSERT(CheckNodeBnd(graph, nbnd));
00527   ASSERT(CheckNodePartitionParams(graph));
00528 
00529   /******************************************************
00530   * Get into the FM loop
00531   *******************************************************/
00532   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00533     if ((higain = rpqGetTop(queue)) == -1)
00534       break;
00535 
00536     moved[higain] = 1;
00537 
00538     gain = vwgt[higain]-rinfo[higain].edegrees[other];
00539     badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));
00540 
00541     /* break if other is now underwight */
00542     if (pwgts[to] > pwgts[other])
00543       break;
00544 
00545     /* break if balance is achieved and no +ve or zero gain */
00546     if (gain < 0 && pwgts[other] < badmaxpwgt) 
00547       break;
00548 
00549     /* skip this vertex if it will violate balance on the other side */
00550     if (pwgts[to]+vwgt[higain] > badmaxpwgt) 
00551       continue;
00552 
00553     ASSERT(bndptr[higain] != -1);
00554 
00555     pwgts[2] -= gain;
00556 
00557     BNDDelete(nbnd, bndind, bndptr, higain);
00558     pwgts[to] += vwgt[higain];
00559     where[higain] = to;
00560 
00561     IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
00562           printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %3"PRIDX", \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));
00563 
00564 
00565     /**********************************************************
00566     * Update the degrees of the affected nodes
00567     ***********************************************************/
00568     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00569       k = adjncy[j];
00570       if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00571         rinfo[k].edegrees[to] += vwgt[higain];
00572       }
00573       else if (where[k] == other) { /* This vertex is pulled into the separator */
00574         ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
00575         BNDInsert(nbnd, bndind, bndptr, k);
00576 
00577         where[k] = 2;
00578         pwgts[other] -= vwgt[k];
00579 
00580         edegrees = rinfo[k].edegrees;
00581         edegrees[0] = edegrees[1] = 0;
00582         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00583           kk = adjncy[jj];
00584           if (where[kk] != 2) 
00585             edegrees[where[kk]] += vwgt[kk];
00586           else {
00587             ASSERT(bndptr[kk] != -1);
00588             oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
00589             rinfo[kk].edegrees[other] -= vwgt[k];
00590 
00591             if (moved[kk] == -1)
00592               rpqUpdate(queue, kk, oldgain+vwgt[k]);
00593           }
00594         }
00595 
00596         /* Insert the new vertex into the priority queue */
00597         rpqInsert(queue, k, vwgt[k]-edegrees[other]);
00598       }
00599     }
00600   }
00601 
00602   IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00603     printf("\tBalanced sep: %6"PRIDX" at %4"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", pwgts[2], nswaps, pwgts[0], pwgts[1], nbnd));
00604 
00605   graph->mincut = pwgts[2];
00606   graph->nbnd   = nbnd;
00607 
00608   rpqDestroy(queue);
00609 
00610   WCOREPOP;
00611 }
00612
libs/ck-libs/metis/libmetis/sfm.c
