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$
00012  *
00013  */
00014 
00015 #include <metis.h>
00016 
00017 
00018 /*************************************************************************
00019 * This function performs a node-based FM refinement 
00020 **************************************************************************/
00021 void FM_2WayNodeRefine(CtrlType *ctrl, GraphType *graph, floattype ubfactor, int npasses)
00022 {
00023   int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
00024   idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00025   idxtype *mptr, *mind, *moved, *swaps, *perm;
00026   PQueueType parts[2]; 
00027   NRInfoType *rinfo;
00028   int higain, oldgain, mincut, initcut, mincutorder;    
00029   int pass, to, other, limit;
00030   int badmaxpwgt, mindiff, newdiff;
00031   int u[2], g[2];
00032 
00033   nvtxs = graph->nvtxs;
00034   xadj = graph->xadj;
00035   adjncy = graph->adjncy;
00036   vwgt = graph->vwgt;
00037 
00038   bndind = graph->bndind;
00039   bndptr = graph->bndptr;
00040   where = graph->where;
00041   pwgts = graph->pwgts;
00042   rinfo = graph->nrinfo;
00043 
00044 
00045   i = ComputeMaxNodeGain(nvtxs, xadj, adjncy, vwgt);
00046   PQueueInit(ctrl, &parts[0], nvtxs, i);
00047   PQueueInit(ctrl, &parts[1], nvtxs, i);
00048 
00049   moved = idxwspacemalloc(ctrl, nvtxs);
00050   swaps = idxwspacemalloc(ctrl, nvtxs);
00051   mptr  = idxwspacemalloc(ctrl, nvtxs+1);
00052   mind  = idxwspacemalloc(ctrl, nvtxs);
00053   perm  = idxwspacemalloc(ctrl, nvtxs);
00054 
00055   IFSET(ctrl->dbglvl, DBG_REFINE,
00056     printf("Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00057 
00058   badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2])/2);
00059 
00060   for (pass=0; pass<npasses; pass++) {
00061     idxset(nvtxs, -1, moved);
00062     PQueueReset(&parts[0]);
00063     PQueueReset(&parts[1]);
00064 
00065     mincutorder = -1;
00066     initcut = mincut = graph->mincut;
00067     nbnd = graph->nbnd;
00068 
00069     RandomPermute(nbnd, perm, 1);
00070     for (ii=0; ii<nbnd; ii++) {
00071       i = bndind[perm[ii]];
00072       ASSERT(where[i] == 2);
00073       PQueueInsert(&parts[0], i, vwgt[i]-rinfo[i].edegrees[1]);
00074       PQueueInsert(&parts[1], i, vwgt[i]-rinfo[i].edegrees[0]);
00075     }
00076 
00077     ASSERT(CheckNodeBnd(graph, nbnd));
00078     ASSERT(CheckNodePartitionParams(graph));
00079 
00080     limit = (ctrl->oflags&OFLAG_COMPRESS ? amin(5*nbnd, 400) : amin(2*nbnd, 300));
00081 
00082     /******************************************************
00083     * Get into the FM loop
00084     *******************************************************/
00085     mptr[0] = nmind = 0;
00086     mindiff = abs(pwgts[0]-pwgts[1]);
00087     to = (pwgts[0] < pwgts[1] ? 0 : 1);
00088     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00089       u[0] = PQueueSeeMax(&parts[0]);  
00090       u[1] = PQueueSeeMax(&parts[1]);
00091       if (u[0] != -1 && u[1] != -1) {
00092         g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];
00093         g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];
00094 
00095         to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2)); 
00096         /* to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : (pwgts[0] < pwgts[1] ? 0 : 1))); */
00097 
00098         if (pwgts[to]+vwgt[u[to]] > badmaxpwgt) 
00099           to = (to+1)%2;
00100       }
00101       else if (u[0] == -1 && u[1] == -1) {
00102         break;
00103       }
00104       else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
00105         to = 0;
00106       }
00107       else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
00108         to = 1;
00109       }
00110       else
00111         break;
00112 
00113       other = (to+1)%2;
00114 
00115       higain = PQueueGetMax(&parts[to]);
00116       if (moved[higain] == -1) /* Delete if it was in the separator originally */
00117         PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);
00118 
00119       ASSERT(bndptr[higain] != -1);
00120 
00121       pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
00122 
00123       newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
00124       if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
00125         mincut = pwgts[2];
00126         mincutorder = nswaps;
00127         mindiff = newdiff;
00128       }
00129       else {
00130         if (nswaps - mincutorder > limit) {
00131           pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
00132           break; /* No further improvement, break out */
00133         }
00134       }
00135 
00136       BNDDelete(nbnd, bndind, bndptr, higain);
00137       pwgts[to] += vwgt[higain];
00138       where[higain] = to;
00139       moved[higain] = nswaps;
00140       swaps[nswaps] = higain;  
00141 
00142 
00143       /**********************************************************
00144       * Update the degrees of the affected nodes
00145       ***********************************************************/
00146       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00147         k = adjncy[j];
00148         if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00149           oldgain = vwgt[k]-rinfo[k].edegrees[to];
00150           rinfo[k].edegrees[to] += vwgt[higain];
00151           if (moved[k] == -1 || moved[k] == -(2+other))
00152             PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);
00153         }
00154         else if (where[k] == other) { /* This vertex is pulled into the separator */
00155           ASSERTP(bndptr[k] == -1, ("%d %d %d\n", k, bndptr[k], where[k]));
00156           BNDInsert(nbnd, bndind, bndptr, k);
00157 
00158           mind[nmind++] = k;  /* Keep track for rollback */
00159           where[k] = 2;
00160           pwgts[other] -= vwgt[k];
00161 
00162           edegrees = rinfo[k].edegrees;
00163           edegrees[0] = edegrees[1] = 0;
00164           for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00165             kk = adjncy[jj];
00166             if (where[kk] != 2) 
00167               edegrees[where[kk]] += vwgt[kk];
00168             else {
00169               oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
00170               rinfo[kk].edegrees[other] -= vwgt[k];
00171               if (moved[kk] == -1 || moved[kk] == -(2+to))
00172                 PQueueUpdate(&parts[to], kk, oldgain, oldgain+vwgt[k]);
00173             }
00174           }
00175 
00176           /* Insert the new vertex into the priority queue. Only one side! */
00177           if (moved[k] == -1) {
00178             PQueueInsert(&parts[to], k, vwgt[k]-edegrees[other]);
00179             moved[k] = -(2+to);
00180           }
00181         }
00182       }
00183       mptr[nswaps+1] = nmind;
00184 
00185       IFSET(ctrl->dbglvl, DBG_MOVEINFO,
00186             printf("Moved %6d to %3d, Gain: %5d [%5d] [%4d %4d] \t[%5d %5d %5d]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
00187 
00188     }
00189 
00190 
00191     /****************************************************************
00192     * Roll back computation 
00193     *****************************************************************/
00194     for (nswaps--; nswaps>mincutorder; nswaps--) {
00195       higain = swaps[nswaps];
00196 
00197       ASSERT(CheckNodePartitionParams(graph));
00198 
00199       to = where[higain];
00200       other = (to+1)%2;
00201       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00202       where[higain] = 2;
00203       BNDInsert(nbnd, bndind, bndptr, higain);
00204 
00205       edegrees = rinfo[higain].edegrees;
00206       edegrees[0] = edegrees[1] = 0;
00207       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00208         k = adjncy[j];
00209         if (where[k] == 2) 
00210           rinfo[k].edegrees[to] -= vwgt[higain];
00211         else
00212           edegrees[where[k]] += vwgt[k];
00213       }
00214 
00215       /* Push nodes out of the separator */
00216       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00217         k = mind[j];
00218         ASSERT(where[k] == 2);
00219         where[k] = other;
00220         INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
00221         BNDDelete(nbnd, bndind, bndptr, k);
00222         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00223           kk = adjncy[jj];
00224           if (where[kk] == 2) 
00225             rinfo[kk].edegrees[other] += vwgt[k];
00226         }
00227       }
00228     }
00229 
00230     ASSERT(mincut == pwgts[2]);
00231 
00232     IFSET(ctrl->dbglvl, DBG_REFINE,
00233       printf("\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00234 
00235     graph->mincut = mincut;
00236     graph->nbnd = nbnd;
00237 
00238     if (mincutorder == -1 || mincut >= initcut)
00239       break;
00240   }
00241 
00242   PQueueFree(ctrl, &parts[0]);
00243   PQueueFree(ctrl, &parts[1]);
00244 
00245   idxwspacefree(ctrl, nvtxs+1);
00246   idxwspacefree(ctrl, nvtxs);
00247   idxwspacefree(ctrl, nvtxs);
00248   idxwspacefree(ctrl, nvtxs);
00249   idxwspacefree(ctrl, nvtxs);
00250 }
00251 
00252 
00253 /*************************************************************************
00254 * This function performs a node-based FM refinement 
00255 **************************************************************************/
00256 void FM_2WayNodeRefine2(CtrlType *ctrl, GraphType *graph, floattype ubfactor, int npasses)
00257 {
00258   int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
00259   idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00260   idxtype *mptr, *mind, *moved, *swaps, *perm;
00261   PQueueType parts[2]; 
00262   NRInfoType *rinfo;
00263   int higain, oldgain, mincut, initcut, mincutorder;    
00264   int pass, to, other, limit;
00265   int badmaxpwgt, mindiff, newdiff;
00266   int u[2], g[2];
00267 
00268   nvtxs = graph->nvtxs;
00269   xadj = graph->xadj;
00270   adjncy = graph->adjncy;
00271   vwgt = graph->vwgt;
00272 
00273   bndind = graph->bndind;
00274   bndptr = graph->bndptr;
00275   where = graph->where;
00276   pwgts = graph->pwgts;
00277   rinfo = graph->nrinfo;
00278 
00279 
00280   i = ComputeMaxNodeGain(nvtxs, xadj, adjncy, vwgt);
00281   PQueueInit(ctrl, &parts[0], nvtxs, i);
00282   PQueueInit(ctrl, &parts[1], nvtxs, i);
00283 
00284   moved = idxwspacemalloc(ctrl, nvtxs);
00285   swaps = idxwspacemalloc(ctrl, nvtxs);
00286   mptr  = idxwspacemalloc(ctrl, nvtxs+1);
00287   mind  = idxwspacemalloc(ctrl, nvtxs);
00288   perm  = idxwspacemalloc(ctrl, nvtxs);
00289 
00290   IFSET(ctrl->dbglvl, DBG_REFINE,
00291     printf("Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00292 
00293   badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2])/2);
00294 
00295   for (pass=0; pass<npasses; pass++) {
00296     idxset(nvtxs, -1, moved);
00297     PQueueReset(&parts[0]);
00298     PQueueReset(&parts[1]);
00299 
00300     mincutorder = -1;
00301     initcut = mincut = graph->mincut;
00302     nbnd = graph->nbnd;
00303 
00304     RandomPermute(nbnd, perm, 1);
00305     for (ii=0; ii<nbnd; ii++) {
00306       i = bndind[perm[ii]];
00307       ASSERT(where[i] == 2);
00308       PQueueInsert(&parts[0], i, vwgt[i]-rinfo[i].edegrees[1]);
00309       PQueueInsert(&parts[1], i, vwgt[i]-rinfo[i].edegrees[0]);
00310     }
00311 
00312     ASSERT(CheckNodeBnd(graph, nbnd));
00313     ASSERT(CheckNodePartitionParams(graph));
00314 
00315     limit = (ctrl->oflags&OFLAG_COMPRESS ? amin(5*nbnd, 400) : amin(2*nbnd, 300));
00316 
00317     /******************************************************
00318     * Get into the FM loop
00319     *******************************************************/
00320     mptr[0] = nmind = 0;
00321     mindiff = abs(pwgts[0]-pwgts[1]);
00322     to = (pwgts[0] < pwgts[1] ? 0 : 1);
00323     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00324       badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2]/2)/2);
00325 
00326       u[0] = PQueueSeeMax(&parts[0]);  
00327       u[1] = PQueueSeeMax(&parts[1]);
00328       if (u[0] != -1 && u[1] != -1) {
00329         g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];
00330         g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];
00331 
00332         to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2)); 
00333         /* to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : (pwgts[0] < pwgts[1] ? 0 : 1))); */
00334 
00335         if (pwgts[to]+vwgt[u[to]] > badmaxpwgt) 
00336           to = (to+1)%2;
00337       }
00338       else if (u[0] == -1 && u[1] == -1) {
00339         break;
00340       }
00341       else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
00342         to = 0;
00343       }
00344       else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
00345         to = 1;
00346       }
00347       else
00348         break;
00349 
00350       other = (to+1)%2;
00351 
00352       higain = PQueueGetMax(&parts[to]);
00353       if (moved[higain] == -1) /* Delete if it was in the separator originally */
00354         PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);
00355 
00356       ASSERT(bndptr[higain] != -1);
00357 
00358       pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
00359 
00360       newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
00361       if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
00362         mincut = pwgts[2];
00363         mincutorder = nswaps;
00364         mindiff = newdiff;
00365       }
00366       else {
00367         if (nswaps - mincutorder > limit) {
00368           pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
00369           break; /* No further improvement, break out */
00370         }
00371       }
00372 
00373       BNDDelete(nbnd, bndind, bndptr, higain);
00374       pwgts[to] += vwgt[higain];
00375       where[higain] = to;
00376       moved[higain] = nswaps;
00377       swaps[nswaps] = higain;  
00378 
00379 
00380       /**********************************************************
00381       * Update the degrees of the affected nodes
00382       ***********************************************************/
00383       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00384         k = adjncy[j];
00385         if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00386           oldgain = vwgt[k]-rinfo[k].edegrees[to];
00387           rinfo[k].edegrees[to] += vwgt[higain];
00388           if (moved[k] == -1 || moved[k] == -(2+other))
00389             PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);
00390         }
00391         else if (where[k] == other) { /* This vertex is pulled into the separator */
00392           ASSERTP(bndptr[k] == -1, ("%d %d %d\n", k, bndptr[k], where[k]));
00393           BNDInsert(nbnd, bndind, bndptr, k);
00394 
00395           mind[nmind++] = k;  /* Keep track for rollback */
00396           where[k] = 2;
00397           pwgts[other] -= vwgt[k];
00398 
00399           edegrees = rinfo[k].edegrees;
00400           edegrees[0] = edegrees[1] = 0;
00401           for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00402             kk = adjncy[jj];
00403             if (where[kk] != 2) 
00404               edegrees[where[kk]] += vwgt[kk];
00405             else {
00406               oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
00407               rinfo[kk].edegrees[other] -= vwgt[k];
00408               if (moved[kk] == -1 || moved[kk] == -(2+to))
00409                 PQueueUpdate(&parts[to], kk, oldgain, oldgain+vwgt[k]);
00410             }
00411           }
00412 
00413           /* Insert the new vertex into the priority queue. Only one side! */
00414           if (moved[k] == -1) {
00415             PQueueInsert(&parts[to], k, vwgt[k]-edegrees[other]);
00416             moved[k] = -(2+to);
00417           }
00418         }
00419       }
00420       mptr[nswaps+1] = nmind;
00421 
00422       IFSET(ctrl->dbglvl, DBG_MOVEINFO,
00423             printf("Moved %6d to %3d, Gain: %5d [%5d] [%4d %4d] \t[%5d %5d %5d]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
00424 
00425     }
00426 
00427 
00428     /****************************************************************
00429     * Roll back computation 
00430     *****************************************************************/
00431     for (nswaps--; nswaps>mincutorder; nswaps--) {
00432       higain = swaps[nswaps];
00433 
00434       ASSERT(CheckNodePartitionParams(graph));
00435 
00436       to = where[higain];
00437       other = (to+1)%2;
00438       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00439       where[higain] = 2;
00440       BNDInsert(nbnd, bndind, bndptr, higain);
00441 
00442       edegrees = rinfo[higain].edegrees;
00443       edegrees[0] = edegrees[1] = 0;
00444       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00445         k = adjncy[j];
00446         if (where[k] == 2) 
00447           rinfo[k].edegrees[to] -= vwgt[higain];
00448         else
00449           edegrees[where[k]] += vwgt[k];
00450       }
00451 
00452       /* Push nodes out of the separator */
00453       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00454         k = mind[j];
00455         ASSERT(where[k] == 2);
00456         where[k] = other;
00457         INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
00458         BNDDelete(nbnd, bndind, bndptr, k);
00459         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00460           kk = adjncy[jj];
00461           if (where[kk] == 2) 
00462             rinfo[kk].edegrees[other] += vwgt[k];
00463         }
00464       }
00465     }
00466 
00467     ASSERT(mincut == pwgts[2]);
00468 
00469     IFSET(ctrl->dbglvl, DBG_REFINE,
00470       printf("\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00471 
00472     graph->mincut = mincut;
00473     graph->nbnd = nbnd;
00474 
00475     if (mincutorder == -1 || mincut >= initcut)
00476       break;
00477   }
00478 
00479   PQueueFree(ctrl, &parts[0]);
00480   PQueueFree(ctrl, &parts[1]);
00481 
00482   idxwspacefree(ctrl, nvtxs+1);
00483   idxwspacefree(ctrl, nvtxs);
00484   idxwspacefree(ctrl, nvtxs);
00485   idxwspacefree(ctrl, nvtxs);
00486   idxwspacefree(ctrl, nvtxs);
00487 }
00488 
00489 
00490 /*************************************************************************
00491 * This function performs a node-based FM refinement 
00492 **************************************************************************/
00493 void FM_2WayNodeRefineEqWgt(CtrlType *ctrl, GraphType *graph, int npasses)
00494 {
00495   int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
00496   idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00497   idxtype *mptr, *mind, *moved, *swaps, *perm;
00498   PQueueType parts[2]; 
00499   NRInfoType *rinfo;
00500   int higain, oldgain, mincut, initcut, mincutorder;    
00501   int pass, to, other, limit;
00502   int mindiff, newdiff;
00503   int u[2], g[2];
00504 
00505   nvtxs = graph->nvtxs;
00506   xadj = graph->xadj;
00507   adjncy = graph->adjncy;
00508   vwgt = graph->vwgt;
00509 
00510   bndind = graph->bndind;
00511   bndptr = graph->bndptr;
00512   where = graph->where;
00513   pwgts = graph->pwgts;
00514   rinfo = graph->nrinfo;
00515 
00516 
00517   i = ComputeMaxNodeGain(nvtxs, xadj, adjncy, vwgt);
00518   PQueueInit(ctrl, &parts[0], nvtxs, i);
00519   PQueueInit(ctrl, &parts[1], nvtxs, i);
00520 
00521   moved = idxwspacemalloc(ctrl, nvtxs);
00522   swaps = idxwspacemalloc(ctrl, nvtxs);
00523   mptr  = idxwspacemalloc(ctrl, nvtxs+1);
00524   mind  = idxwspacemalloc(ctrl, nvtxs);
00525   perm  = idxwspacemalloc(ctrl, nvtxs);
00526 
00527   IFSET(ctrl->dbglvl, DBG_REFINE,
00528     printf("Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00529 
00530   for (pass=0; pass<npasses; pass++) {
00531     idxset(nvtxs, -1, moved);
00532     PQueueReset(&parts[0]);
00533     PQueueReset(&parts[1]);
00534 
00535     mincutorder = -1;
00536     initcut = mincut = graph->mincut;
00537     nbnd = graph->nbnd;
00538 
00539     RandomPermute(nbnd, perm, 1);
00540     for (ii=0; ii<nbnd; ii++) {
00541       i = bndind[perm[ii]];
00542       ASSERT(where[i] == 2);
00543       PQueueInsert(&parts[0], i, vwgt[i]-rinfo[i].edegrees[1]);
00544       PQueueInsert(&parts[1], i, vwgt[i]-rinfo[i].edegrees[0]);
00545     }
00546 
00547     ASSERT(CheckNodeBnd(graph, nbnd));
00548     ASSERT(CheckNodePartitionParams(graph));
00549 
00550     limit = (ctrl->oflags&OFLAG_COMPRESS ? amin(5*nbnd, 400) : amin(2*nbnd, 300));
00551 
00552     /******************************************************
00553     * Get into the FM loop
00554     *******************************************************/
00555     mptr[0] = nmind = 0;
00556     mindiff = abs(pwgts[0]-pwgts[1]);
00557     to = (pwgts[0] < pwgts[1] ? 0 : 1);
00558     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00559       to = (pwgts[0] < pwgts[1] ? 0 : 1);
00560 
00561       if (pwgts[0] == pwgts[1]) {
00562         u[0] = PQueueSeeMax(&parts[0]);  
00563         u[1] = PQueueSeeMax(&parts[1]);
00564         if (u[0] != -1 && u[1] != -1) {
00565           g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];
00566           g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];
00567 
00568           to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2)); 
00569         }
00570       }
00571       other = (to+1)%2;
00572 
00573       if ((higain = PQueueGetMax(&parts[to])) == -1)
00574         break;
00575 
00576       if (moved[higain] == -1) /* Delete if it was in the separator originally */
00577         PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);
00578 
00579       ASSERT(bndptr[higain] != -1);
00580 
00581       pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
00582 
00583       newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
00584       if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
00585         mincut = pwgts[2];
00586         mincutorder = nswaps;
00587         mindiff = newdiff;
00588       }
00589       else {
00590         if (nswaps - mincutorder > limit) {
00591           pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
00592           break; /* No further improvement, break out */
00593         }
00594       }
00595 
00596       BNDDelete(nbnd, bndind, bndptr, higain);
00597       pwgts[to] += vwgt[higain];
00598       where[higain] = to;
00599       moved[higain] = nswaps;
00600       swaps[nswaps] = higain;  
00601 
00602 
00603       /**********************************************************
00604       * Update the degrees of the affected nodes
00605       ***********************************************************/
00606       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00607         k = adjncy[j];
00608         if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00609           oldgain = vwgt[k]-rinfo[k].edegrees[to];
00610           rinfo[k].edegrees[to] += vwgt[higain];
00611           if (moved[k] == -1 || moved[k] == -(2+other))
00612             PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);
00613         }
00614         else if (where[k] == other) { /* This vertex is pulled into the separator */
00615           ASSERTP(bndptr[k] == -1, ("%d %d %d\n", k, bndptr[k], where[k]));
00616           BNDInsert(nbnd, bndind, bndptr, k);
00617 
00618           mind[nmind++] = k;  /* Keep track for rollback */
00619           where[k] = 2;
00620           pwgts[other] -= vwgt[k];
00621 
00622           edegrees = rinfo[k].edegrees;
00623           edegrees[0] = edegrees[1] = 0;
00624           for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00625             kk = adjncy[jj];
00626             if (where[kk] != 2) 
00627               edegrees[where[kk]] += vwgt[kk];
00628             else {
00629               oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
00630               rinfo[kk].edegrees[other] -= vwgt[k];
00631               if (moved[kk] == -1 || moved[kk] == -(2+to))
00632                 PQueueUpdate(&parts[to], kk, oldgain, oldgain+vwgt[k]);
00633             }
00634           }
00635 
00636           /* Insert the new vertex into the priority queue. Only one side! */
00637           if (moved[k] == -1) {
00638             PQueueInsert(&parts[to], k, vwgt[k]-edegrees[other]);
00639             moved[k] = -(2+to);
00640           }
00641         }
00642       }
00643       mptr[nswaps+1] = nmind;
00644 
00645       IFSET(ctrl->dbglvl, DBG_MOVEINFO,
00646             printf("Moved %6d to %3d, Gain: %5d [%5d] [%4d %4d] \t[%5d %5d %5d]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
00647 
00648     }
00649 
00650 
00651     /****************************************************************
00652     * Roll back computation 
00653     *****************************************************************/
00654     for (nswaps--; nswaps>mincutorder; nswaps--) {
00655       higain = swaps[nswaps];
00656 
00657       ASSERT(CheckNodePartitionParams(graph));
00658 
00659       to = where[higain];
00660       other = (to+1)%2;
00661       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00662       where[higain] = 2;
00663       BNDInsert(nbnd, bndind, bndptr, higain);
00664 
00665       edegrees = rinfo[higain].edegrees;
00666       edegrees[0] = edegrees[1] = 0;
00667       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00668         k = adjncy[j];
00669         if (where[k] == 2) 
00670           rinfo[k].edegrees[to] -= vwgt[higain];
00671         else
00672           edegrees[where[k]] += vwgt[k];
00673       }
00674 
00675       /* Push nodes out of the separator */
00676       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00677         k = mind[j];
00678         ASSERT(where[k] == 2);
00679         where[k] = other;
00680         INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
00681         BNDDelete(nbnd, bndind, bndptr, k);
00682         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00683           kk = adjncy[jj];
00684           if (where[kk] == 2) 
00685             rinfo[kk].edegrees[other] += vwgt[k];
00686         }
00687       }
00688     }
00689 
00690     ASSERT(mincut == pwgts[2]);
00691 
00692     IFSET(ctrl->dbglvl, DBG_REFINE,
00693       printf("\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00694 
00695     graph->mincut = mincut;
00696     graph->nbnd = nbnd;
00697 
00698     if (mincutorder == -1 || mincut >= initcut)
00699       break;
00700   }
00701 
00702   PQueueFree(ctrl, &parts[0]);
00703   PQueueFree(ctrl, &parts[1]);
00704 
00705   idxwspacefree(ctrl, nvtxs+1);
00706   idxwspacefree(ctrl, nvtxs);
00707   idxwspacefree(ctrl, nvtxs);
00708   idxwspacefree(ctrl, nvtxs);
00709   idxwspacefree(ctrl, nvtxs);
00710 }
00711 
00712 
00713 /*************************************************************************
00714 * This function performs a node-based FM refinement. This is the 
00715 * one-way version 
00716 **************************************************************************/
00717 void FM_2WayNodeRefine_OneSided(CtrlType *ctrl, GraphType *graph, floattype ubfactor, int npasses)
00718 {
00719   int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
00720   idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00721   idxtype *mptr, *mind, *swaps, *perm;
00722   PQueueType parts; 
00723   NRInfoType *rinfo;
00724   int higain, oldgain, mincut, initcut, mincutorder;    
00725   int pass, to, other, limit;
00726   int badmaxpwgt, mindiff, newdiff;
00727 
00728   nvtxs = graph->nvtxs;
00729   xadj = graph->xadj;
00730   adjncy = graph->adjncy;
00731   vwgt = graph->vwgt;
00732 
00733   bndind = graph->bndind;
00734   bndptr = graph->bndptr;
00735   where = graph->where;
00736   pwgts = graph->pwgts;
00737   rinfo = graph->nrinfo;
00738 
00739   PQueueInit(ctrl, &parts, nvtxs, ComputeMaxNodeGain(nvtxs, xadj, adjncy, vwgt));
00740 
00741   perm  = idxwspacemalloc(ctrl, nvtxs);
00742   swaps = idxwspacemalloc(ctrl, nvtxs);
00743   mptr  = idxwspacemalloc(ctrl, nvtxs+1);
00744   mind  = idxwspacemalloc(ctrl, nvtxs);
00745 
00746   IFSET(ctrl->dbglvl, DBG_REFINE,
00747     printf("Partitions-N1: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00748 
00749   badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2])/2);
00750 
00751   to = (pwgts[0] < pwgts[1] ? 1 : 0);
00752   for (pass=0; pass<npasses; pass++) {
00753     other = to; 
00754     to = (to+1)%2;
00755 
00756     PQueueReset(&parts);
00757 
00758     mincutorder = -1;
00759     initcut = mincut = graph->mincut;
00760     nbnd = graph->nbnd;
00761 
00762     RandomPermute(nbnd, perm, 1);
00763     for (ii=0; ii<nbnd; ii++) {
00764       i = bndind[perm[ii]];
00765       ASSERT(where[i] == 2);
00766       PQueueInsert(&parts, i, vwgt[i]-rinfo[i].edegrees[other]);
00767     }
00768 
00769     ASSERT(CheckNodeBnd(graph, nbnd));
00770     ASSERT(CheckNodePartitionParams(graph));
00771 
00772     limit = (ctrl->oflags&OFLAG_COMPRESS ? amin(5*nbnd, 400) : amin(2*nbnd, 300));
00773 
00774     /******************************************************
00775     * Get into the FM loop
00776     *******************************************************/
00777     mptr[0] = nmind = 0;
00778     mindiff = abs(pwgts[0]-pwgts[1]);
00779     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00780 
00781       if ((higain = PQueueGetMax(&parts)) == -1)
00782         break;
00783 
00784       ASSERT(bndptr[higain] != -1);
00785 
00786       if (pwgts[to]+vwgt[higain] > badmaxpwgt)
00787         break;  /* No point going any further. Balance will be bad */
00788 
00789       pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
00790 
00791       newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
00792       if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
00793         mincut = pwgts[2];
00794         mincutorder = nswaps;
00795         mindiff = newdiff;
00796       }
00797       else {
00798         if (nswaps - mincutorder > limit) {
00799           pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
00800           break; /* No further improvement, break out */
00801         }
00802       }
00803 
00804       BNDDelete(nbnd, bndind, bndptr, higain);
00805       pwgts[to] += vwgt[higain];
00806       where[higain] = to;
00807       swaps[nswaps] = higain;  
00808 
00809 
00810       /**********************************************************
00811       * Update the degrees of the affected nodes
00812       ***********************************************************/
00813       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00814         k = adjncy[j];
00815         if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00816           rinfo[k].edegrees[to] += vwgt[higain];
00817         }
00818         else if (where[k] == other) { /* This vertex is pulled into the separator */
00819           ASSERTP(bndptr[k] == -1, ("%d %d %d\n", k, bndptr[k], where[k]));
00820           BNDInsert(nbnd, bndind, bndptr, k);
00821 
00822           mind[nmind++] = k;  /* Keep track for rollback */
00823           where[k] = 2;
00824           pwgts[other] -= vwgt[k];
00825 
00826           edegrees = rinfo[k].edegrees;
00827           edegrees[0] = edegrees[1] = 0;
00828           for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00829             kk = adjncy[jj];
00830             if (where[kk] != 2) 
00831               edegrees[where[kk]] += vwgt[kk];
00832             else {
00833               oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
00834               rinfo[kk].edegrees[other] -= vwgt[k];
00835 
00836               /* Since the moves are one-sided this vertex has not been moved yet */
00837               PQueueUpdateUp(&parts, kk, oldgain, oldgain+vwgt[k]); 
00838             }
00839           }
00840 
00841           /* Insert the new vertex into the priority queue. Safe due to one-sided moves */
00842           PQueueInsert(&parts, k, vwgt[k]-edegrees[other]);
00843         }
00844       }
00845       mptr[nswaps+1] = nmind;
00846 
00847 
00848       IFSET(ctrl->dbglvl, DBG_MOVEINFO,
00849             printf("Moved %6d to %3d, Gain: %5d [%5d] \t[%5d %5d %5d] [%3d %2d]\n", 
00850                        higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain], pwgts[0], pwgts[1], pwgts[2], nswaps, limit));
00851 
00852     }
00853 
00854 
00855     /****************************************************************
00856     * Roll back computation 
00857     *****************************************************************/
00858     for (nswaps--; nswaps>mincutorder; nswaps--) {
00859       higain = swaps[nswaps];
00860 
00861       ASSERT(CheckNodePartitionParams(graph));
00862       ASSERT(where[higain] == to);
00863 
00864       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00865       where[higain] = 2;
00866       BNDInsert(nbnd, bndind, bndptr, higain);
00867 
00868       edegrees = rinfo[higain].edegrees;
00869       edegrees[0] = edegrees[1] = 0;
00870       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00871         k = adjncy[j];
00872         if (where[k] == 2) 
00873           rinfo[k].edegrees[to] -= vwgt[higain];
00874         else
00875           edegrees[where[k]] += vwgt[k];
00876       }
00877 
00878       /* Push nodes out of the separator */
00879       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00880         k = mind[j];
00881         ASSERT(where[k] == 2);
00882         where[k] = other;
00883         INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
00884         BNDDelete(nbnd, bndind, bndptr, k);
00885         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00886           kk = adjncy[jj];
00887           if (where[kk] == 2) 
00888             rinfo[kk].edegrees[other] += vwgt[k];
00889         }
00890       }
00891     }
00892 
00893     ASSERT(mincut == pwgts[2]);
00894 
00895     IFSET(ctrl->dbglvl, DBG_REFINE,
00896       printf("\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00897 
00898     graph->mincut = mincut;
00899     graph->nbnd = nbnd;
00900 
00901     if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))
00902       break;
00903   }
00904 
00905   PQueueFree(ctrl, &parts);
00906 
00907   idxwspacefree(ctrl, nvtxs);
00908   idxwspacefree(ctrl, nvtxs+1);
00909   idxwspacefree(ctrl, nvtxs);
00910   idxwspacefree(ctrl, nvtxs);
00911 }
00912 
00913 
00914 
00915 /*************************************************************************
00916 * This function performs a node-based FM refinement 
00917 **************************************************************************/
00918 void FM_2WayNodeBalance(CtrlType *ctrl, GraphType *graph, floattype ubfactor)
00919 {
00920   int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps;
00921   idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00922   idxtype *perm, *moved;
00923   PQueueType parts; 
00924   NRInfoType *rinfo;
00925   int higain, oldgain;  
00926   int pass, to, other;
00927 
00928   nvtxs = graph->nvtxs;
00929   xadj = graph->xadj;
00930   adjncy = graph->adjncy;
00931   vwgt = graph->vwgt;
00932 
00933   bndind = graph->bndind;
00934   bndptr = graph->bndptr;
00935   where = graph->where;
00936   pwgts = graph->pwgts;
00937   rinfo = graph->nrinfo;
00938 
00939   if (abs(pwgts[0]-pwgts[1]) < (int)((ubfactor-1.0)*(pwgts[0]+pwgts[1])))
00940     return;
00941   if (abs(pwgts[0]-pwgts[1]) < 3*idxsum(nvtxs, vwgt)/nvtxs)
00942     return;
00943 
00944   to = (pwgts[0] < pwgts[1] ? 0 : 1); 
00945   other = (to+1)%2;
00946 
00947   PQueueInit(ctrl, &parts, nvtxs, ComputeMaxNodeGain(nvtxs, xadj, adjncy, vwgt));
00948 
00949   perm = idxwspacemalloc(ctrl, nvtxs);
00950   moved = idxset(nvtxs, -1, idxwspacemalloc(ctrl, nvtxs));
00951 
00952   IFSET(ctrl->dbglvl, DBG_REFINE,
00953     printf("Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d [B]\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00954 
00955   nbnd = graph->nbnd;
00956   RandomPermute(nbnd, perm, 1);
00957   for (ii=0; ii<nbnd; ii++) {
00958     i = bndind[perm[ii]];
00959     ASSERT(where[i] == 2);
00960     PQueueInsert(&parts, i, vwgt[i]-rinfo[i].edegrees[other]);
00961   }
00962 
00963   ASSERT(CheckNodeBnd(graph, nbnd));
00964   ASSERT(CheckNodePartitionParams(graph));
00965 
00966   /******************************************************
00967   * Get into the FM loop
00968   *******************************************************/
00969   for (nswaps=0; nswaps<nvtxs; nswaps++) {
00970     if ((higain = PQueueGetMax(&parts)) == -1)
00971       break;
00972 
00973     moved[higain] = 1;
00974 
00975     if (pwgts[other] - rinfo[higain].edegrees[other] < (pwgts[0]+pwgts[1])/2) 
00976       continue;
00977 #ifdef XXX
00978     if (pwgts[other] - rinfo[higain].edegrees[other] < pwgts[to]+vwgt[higain]) 
00979       break;
00980 #endif
00981 
00982     ASSERT(bndptr[higain] != -1);
00983 
00984     pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
00985 
00986     BNDDelete(nbnd, bndind, bndptr, higain);
00987     pwgts[to] += vwgt[higain];
00988     where[higain] = to;
00989 
00990     IFSET(ctrl->dbglvl, DBG_MOVEINFO,
00991           printf("Moved %6d to %3d, Gain: %3d, \t[%5d %5d %5d]\n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));
00992 
00993 
00994     /**********************************************************
00995     * Update the degrees of the affected nodes
00996     ***********************************************************/
00997     for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00998       k = adjncy[j];
00999       if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
01000         rinfo[k].edegrees[to] += vwgt[higain];
01001       }
01002       else if (where[k] == other) { /* This vertex is pulled into the separator */
01003         ASSERTP(bndptr[k] == -1, ("%d %d %d\n", k, bndptr[k], where[k]));
01004         BNDInsert(nbnd, bndind, bndptr, k);
01005 
01006         where[k] = 2;
01007         pwgts[other] -= vwgt[k];
01008 
01009         edegrees = rinfo[k].edegrees;
01010         edegrees[0] = edegrees[1] = 0;
01011         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
01012           kk = adjncy[jj];
01013           if (where[kk] != 2) 
01014             edegrees[where[kk]] += vwgt[kk];
01015           else {
01016             ASSERT(bndptr[kk] != -1);
01017             oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
01018             rinfo[kk].edegrees[other] -= vwgt[k];
01019 
01020             if (moved[kk] == -1)
01021               PQueueUpdateUp(&parts, kk, oldgain, oldgain+vwgt[k]);
01022           }
01023         }
01024 
01025         /* Insert the new vertex into the priority queue */
01026         PQueueInsert(&parts, k, vwgt[k]-edegrees[other]);
01027       }
01028     }
01029 
01030     if (pwgts[to] > pwgts[other])
01031       break;
01032   }
01033 
01034   IFSET(ctrl->dbglvl, DBG_REFINE,
01035     printf("\tBalanced sep: %6d at %4d, PWGTS: [%6d %6d], NBND: %6d\n", pwgts[2], nswaps, pwgts[0], pwgts[1], nbnd));
01036 
01037   graph->mincut = pwgts[2];
01038   graph->nbnd = nbnd;
01039 
01040 
01041   PQueueFree(ctrl, &parts);
01042 
01043   idxwspacefree(ctrl, nvtxs);
01044   idxwspacefree(ctrl, nvtxs);
01045 }
01046 
01047 
01048 /*************************************************************************
01049 * This function computes the maximum possible gain for a vertex
01050 **************************************************************************/
01051 int ComputeMaxNodeGain(int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt)
01052 {
01053   int i, j, k, max;
01054 
01055   max = 0;
01056   for (j=xadj[0]; j<xadj[1]; j++)
01057     max += vwgt[adjncy[j]];
01058 
01059   for (i=1; i<nvtxs; i++) {
01060     for (k=0, j=xadj[i]; j<xadj[i+1]; j++)
01061       k += vwgt[adjncy[j]];
01062     if (max < k)
01063       max = k;
01064   }
01065 
01066   return max;
01067 }
01068    
01069
libs/ck-libs/parmetis/METISLib/sfm.c
