Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * parmetis.c
00005  *
00006  * This file contains top level routines that are used by ParMETIS
00007  *
00008  * Started 10/14/97
00009  * George
00010  *
00011  * $Id: parmetis.c 10481 2011-07-05 18:01:23Z karypis $
00012  *
00013  */
00014 
00015 #include "metislib.h"
00016 
00017 
00018 /*************************************************************************/
00027 /*************************************************************************/
00028 int METIS_NodeNDP(idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
00029            idx_t npes, idx_t *options, idx_t *perm, idx_t *iperm, idx_t *sizes) 
00030 {
00031   idx_t i, ii, j, l, nnvtxs=0;
00032   graph_t *graph;
00033   ctrl_t *ctrl;
00034   idx_t *cptr, *cind;
00035 
00036   ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL);
00037   if (!ctrl) return METIS_ERROR_INPUT;
00038 
00039   IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
00040   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));
00041 
00042   /* compress the graph; not that compression only happens if not prunning 
00043      has taken place. */
00044   if (ctrl->compress) {
00045     cptr = imalloc(nvtxs+1, "OMETIS: cptr");
00046     cind = imalloc(nvtxs, "OMETIS: cind");
00047 
00048     graph = CompressGraph(ctrl, nvtxs, xadj, adjncy, vwgt, cptr, cind);
00049     if (graph == NULL) {
00050       /* if there was no compression, cleanup the compress flag */
00051       gk_free((void **)&cptr, &cind, LTERM);
00052       ctrl->compress = 0;
00053     }
00054     else {
00055       nnvtxs = graph->nvtxs;
00056     }
00057   }
00058 
00059   /* if no compression, setup the graph in the normal way. */
00060   if (ctrl->compress == 0) 
00061     graph = SetupGraph(ctrl, nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);
00062 
00063 
00064   /* allocate workspace memory */
00065   AllocateWorkSpace(ctrl, graph);
00066 
00067 
00068   /* do the nested dissection ordering  */
00069   iset(2*npes-1, 0, sizes);
00070   MlevelNestedDissectionP(ctrl, graph, iperm, graph->nvtxs, npes, 0, sizes);
00071 
00072 
00073   /* Uncompress the ordering */
00074   if (ctrl->compress) { 
00075     /* construct perm from iperm */
00076     for (i=0; i<nnvtxs; i++)
00077       perm[iperm[i]] = i; 
00078     for (l=ii=0; ii<nnvtxs; ii++) {
00079       i = perm[ii];
00080       for (j=cptr[i]; j<cptr[i+1]; j++)
00081         iperm[cind[j]] = l++;
00082     }
00083 
00084     gk_free((void **)&cptr, &cind, LTERM);
00085   }
00086 
00087 
00088   for (i=0; i<nvtxs; i++)
00089     perm[iperm[i]] = i;
00090 
00091   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->TotalTmr));
00092   IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
00093 
00094   /* clean up */
00095   FreeCtrl(&ctrl);
00096 
00097   return METIS_OK;
00098 }
00099 
00100 
00101 /*************************************************************************/
00104 /**************************************************************************/
00105 void MlevelNestedDissectionP(ctrl_t *ctrl, graph_t *graph, idx_t *order, 
00106          idx_t lastvtx, idx_t npes, idx_t cpos, idx_t *sizes)
00107 {
00108   idx_t i, j, nvtxs, nbnd;
00109   idx_t *label, *bndind;
00110   graph_t *lgraph, *rgraph;
00111 
00112   nvtxs = graph->nvtxs;
00113 
00114   if (nvtxs == 0) {
00115     FreeGraph(&graph);
00116     return;
00117   }
00118 
00119   MlevelNodeBisectionMultiple(ctrl, graph);
00120 
00121   IFSET(ctrl->dbglvl, METIS_DBG_SEPINFO, 
00122       printf("Nvtxs: %6"PRIDX", [%6"PRIDX" %6"PRIDX" %6"PRIDX"]\n", 
00123         graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
00124 
00125   if (cpos < npes-1) {
00126     sizes[2*npes-2-cpos]       = graph->pwgts[2];
00127     sizes[2*npes-2-(2*cpos+1)] = graph->pwgts[1];
00128     sizes[2*npes-2-(2*cpos+2)] = graph->pwgts[0];
00129   }
00130 
00131   /* Order the nodes in the separator */
00132   nbnd   = graph->nbnd;
00133   bndind = graph->bndind;
00134   label  = graph->label;
00135   for (i=0; i<nbnd; i++) 
00136     order[label[bndind[i]]] = --lastvtx;
00137 
00138   SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
00139 
00140   /* Free the memory of the top level graph */
00141   FreeGraph(&graph);
00142 
00143   if ((lgraph->nvtxs > MMDSWITCH || 2*cpos+2 < npes-1) && lgraph->nedges > 0) 
00144     MlevelNestedDissectionP(ctrl, lgraph, order, lastvtx-rgraph->nvtxs, npes, 2*cpos+2, sizes);
00145   else {
00146     MMDOrder(ctrl, lgraph, order, lastvtx-rgraph->nvtxs); 
00147     FreeGraph(&lgraph);
00148   }
00149   if ((rgraph->nvtxs > MMDSWITCH || 2*cpos+1 < npes-1) && rgraph->nedges > 0) 
00150     MlevelNestedDissectionP(ctrl, rgraph, order, lastvtx, npes, 2*cpos+1, sizes);
00151   else {
00152     MMDOrder(ctrl, rgraph, order, lastvtx); 
00153     FreeGraph(&rgraph);
00154   }
00155 }
00156 
00157 
00158 /*************************************************************************/
00160 /**************************************************************************/
00161 int METIS_ComputeVertexSeparator(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, 
00162            idx_t *vwgt, idx_t *options, idx_t *r_sepsize, idx_t *part) 
00163 {
00164   idx_t i, j;
00165   graph_t *graph;
00166   ctrl_t *ctrl;
00167 
00168   if ((ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL)) == NULL)
00169     return METIS_ERROR_INPUT;
00170 
00171   InitRandom(ctrl->seed);
00172 
00173   graph = SetupGraph(ctrl, *nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);
00174 
00175   AllocateWorkSpace(ctrl, graph);
00176 
00177   /*============================================================
00178    * Perform the bisection
00179    *============================================================*/ 
00180   ctrl->CoarsenTo = 100;
00181 
00182   MlevelNodeBisectionMultiple(ctrl, graph);
00183 
00184   *r_sepsize = graph->pwgts[2];
00185   icopy(*nvtxs, graph->where, part);
00186 
00187   FreeGraph(&graph);
00188 
00189   FreeCtrl(&ctrl);
00190 
00191   return METIS_OK;
00192 }
00193 
00194 
00195 /*************************************************************************/
00198 /*************************************************************************/
00199 int METIS_NodeRefine(idx_t nvtxs, idx_t *xadj, idx_t *vwgt, idx_t *adjncy, 
00200            idx_t *where, idx_t *hmarker, real_t ubfactor)
00201 {
00202   graph_t *graph;
00203   ctrl_t *ctrl;
00204 
00205   /* set up the run time parameters */
00206   ctrl = SetupCtrl(METIS_OP_OMETIS, NULL, 1, 3, NULL, NULL);
00207   if (!ctrl) return METIS_ERROR_INPUT;
00208 
00209   /* set up the graph */
00210   graph = SetupGraph(ctrl, nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);
00211 
00212   /* allocate workspace memory */
00213   AllocateWorkSpace(ctrl, graph);
00214 
00215   /* set up the memory and the input partition */
00216   Allocate2WayNodePartitionMemory(ctrl, graph);
00217   icopy(nvtxs, where, graph->where);
00218 
00219   Compute2WayNodePartitionParams(ctrl, graph);
00220 
00221   FM_2WayNodeRefine1SidedP(ctrl, graph, hmarker, ubfactor, 10); 
00222   /* FM_2WayNodeRefine2SidedP(ctrl, graph, hmarker, ubfactor, 10); */
00223 
00224   icopy(nvtxs, graph->where, where);
00225 
00226   FreeGraph(&graph);
00227   FreeCtrl(&ctrl);
00228 
00229   return METIS_OK;
00230 }
00231 
00232 
00233 /*************************************************************************/
00236 /*************************************************************************/
00237 void FM_2WayNodeRefine1SidedP(ctrl_t *ctrl, graph_t *graph, 
00238           idx_t *hmarker, real_t ubfactor, idx_t npasses)
00239 {
00240   idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind, nbad, qsize;
00241   idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00242   idx_t *mptr, *mind, *swaps, *inqueue;
00243   rpq_t *queue; 
00244   nrinfo_t *rinfo;
00245   idx_t higain, oldgain, mincut, initcut, mincutorder;  
00246   idx_t pass, from, to, limit;
00247   idx_t badmaxpwgt, mindiff, newdiff;
00248 
00249   WCOREPUSH;
00250 
00251   ASSERT(graph->mincut == graph->pwgts[2]);
00252 
00253   nvtxs  = graph->nvtxs;
00254   xadj   = graph->xadj;
00255   adjncy = graph->adjncy;
00256   vwgt   = graph->vwgt;
00257 
00258   bndind = graph->bndind;
00259   bndptr = graph->bndptr;
00260   where  = graph->where;
00261   pwgts  = graph->pwgts;
00262   rinfo  = graph->nrinfo;
00263 
00264   queue = rpqCreate(nvtxs);
00265       
00266   inqueue = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
00267   swaps   = iwspacemalloc(ctrl, nvtxs);
00268   mptr    = iwspacemalloc(ctrl, nvtxs+1);
00269   mind    = iwspacemalloc(ctrl, 2*nvtxs);
00270 
00271   badmaxpwgt = (idx_t)(ubfactor*gk_max(pwgts[0], pwgts[1]));
00272 
00273   IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00274     printf("Partitions-N1: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"] "
00275            "MaxPwgt[%6"PRIDX"]. ISep: %6"PRIDX"\n", 
00276            pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, badmaxpwgt, 
00277            graph->mincut));
00278 
00279   to = (pwgts[0] < pwgts[1] ? 1 : 0);
00280   for (pass=0; pass<npasses; pass++) {
00281     from = to; 
00282     to   = (from+1)%2;
00283 
00284     rpqReset(queue);
00285 
00286     mincutorder = -1;
00287     initcut = mincut = graph->mincut;
00288     nbnd = graph->nbnd;
00289 
00290     /* use the swaps array in place of the traditional perm array to save memory */
00291     irandArrayPermute(nbnd, swaps, nbnd, 1);
00292     for (ii=0; ii<nbnd; ii++) {
00293       i = bndind[swaps[ii]];
00294       ASSERT(where[i] == 2);
00295       if (hmarker[i] == -1 || hmarker[i] == to) {
00296         rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[from]);
00297         inqueue[i] = pass;
00298       }
00299     }
00300     qsize = rpqLength(queue);
00301 
00302     ASSERT(CheckNodeBnd(graph, nbnd));
00303     ASSERT(CheckNodePartitionParams(graph));
00304 
00305     limit = nbnd;
00306 
00307     /******************************************************
00308     * Get into the FM loop
00309     *******************************************************/
00310     mptr[0] = nmind = nbad = 0;
00311     mindiff = abs(pwgts[0]-pwgts[1]);
00312     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00313       if ((higain = rpqGetTop(queue)) == -1) 
00314         break;
00315 
00316       ASSERT(bndptr[higain] != -1);
00317 
00318       /* The following check is to ensure we break out if there is a posibility
00319          of over-running the mind array.  */
00320       if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)
00321         break;
00322 
00323       inqueue[higain] = -1;
00324 
00325       if (pwgts[to]+vwgt[higain] > badmaxpwgt) { /* Skip this vertex */
00326         if (nbad++ > limit) 
00327           break; 
00328         else {
00329           nswaps--;
00330           continue;  
00331         }
00332       }
00333 
00334       pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[from]);
00335 
00336       newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[from]-rinfo[higain].edegrees[from]));
00337       if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
00338         mincut      = pwgts[2];
00339         mincutorder = nswaps;
00340         mindiff     = newdiff;
00341         nbad        = 0;
00342       }
00343       else {
00344         if (nbad++ > limit) {
00345           pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[from]);
00346           break; /* No further improvement, break out */
00347         }
00348       }
00349 
00350       BNDDelete(nbnd, bndind, bndptr, higain);
00351       pwgts[to] += vwgt[higain];
00352       where[higain] = to;
00353       swaps[nswaps] = higain;  
00354 
00355 
00356       /**********************************************************
00357       * Update the degrees of the affected nodes
00358       ***********************************************************/
00359       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00360         k = adjncy[j];
00361         if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
00362           rinfo[k].edegrees[to] += vwgt[higain];
00363         }
00364         else if (where[k] == from) { /* This vertex is pulled into the separator */
00365           ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
00366           BNDInsert(nbnd, bndind, bndptr, k);
00367 
00368           mind[nmind++] = k;  /* Keep track for rollback */
00369           where[k]      = 2;
00370           pwgts[from]  -= vwgt[k];
00371 
00372           edegrees = rinfo[k].edegrees;
00373           edegrees[0] = edegrees[1] = 0;
00374           for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00375             kk = adjncy[jj];
00376             if (where[kk] != 2) 
00377               edegrees[where[kk]] += vwgt[kk];
00378             else {
00379               oldgain = vwgt[kk]-rinfo[kk].edegrees[from];
00380               rinfo[kk].edegrees[from] -= vwgt[k];
00381 
00382               /* Update the gain of this node if it was not skipped */
00383               if (inqueue[kk] == pass)
00384                 rpqUpdate(queue, kk, oldgain+vwgt[k]); 
00385             }
00386           }
00387 
00388           /* Insert the new vertex into the priority queue. Safe due to one-sided moves */
00389           if (hmarker[k] == -1 || hmarker[k] == to) {
00390             rpqInsert(queue, k, vwgt[k]-edegrees[from]);
00391             inqueue[k] = pass;
00392           }
00393         }
00394       }
00395       mptr[nswaps+1] = nmind;
00396 
00397 
00398       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
00399             printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"] [%3"PRIDX" %2"PRIDX"]\n", 
00400                    higain, to, (vwgt[higain]-rinfo[higain].edegrees[from]), 
00401                    vwgt[higain], pwgts[0], pwgts[1], pwgts[2], nswaps, limit));
00402 
00403     }
00404 
00405 
00406     /****************************************************************
00407     * Roll back computation 
00408     *****************************************************************/
00409     for (nswaps--; nswaps>mincutorder; nswaps--) {
00410       higain = swaps[nswaps];
00411 
00412       ASSERT(CheckNodePartitionParams(graph));
00413       ASSERT(where[higain] == to);
00414 
00415       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00416       where[higain] = 2;
00417       BNDInsert(nbnd, bndind, bndptr, higain);
00418 
00419       edegrees = rinfo[higain].edegrees;
00420       edegrees[0] = edegrees[1] = 0;
00421       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00422         k = adjncy[j];
00423         if (where[k] == 2) 
00424           rinfo[k].edegrees[to] -= vwgt[higain];
00425         else
00426           edegrees[where[k]] += vwgt[k];
00427       }
00428 
00429       /* Push nodes out of the separator */
00430       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00431         k = mind[j];
00432         ASSERT(where[k] == 2);
00433         where[k] = from;
00434         INC_DEC(pwgts[from], pwgts[2], vwgt[k]);
00435         BNDDelete(nbnd, bndind, bndptr, k);
00436         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00437           kk = adjncy[jj];
00438           if (where[kk] == 2) 
00439             rinfo[kk].edegrees[from] += vwgt[k];
00440         }
00441       }
00442     }
00443 
00444     ASSERT(mincut == pwgts[2]);
00445 
00446     IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00447       printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX", QSIZE: %6"PRIDX"\n", 
00448           mincut, mincutorder, pwgts[0], pwgts[1], nbnd, qsize));
00449 
00450     graph->mincut = mincut;
00451     graph->nbnd   = nbnd;
00452 
00453     if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))
00454       break;
00455   }
00456 
00457   rpqDestroy(queue);
00458 
00459   WCOREPOP;
00460 }
00461 
00462 
00463 /*************************************************************************/
00466 /*************************************************************************/
00467 void FM_2WayNodeRefine2SidedP(ctrl_t *ctrl, graph_t *graph, 
00468           idx_t *hmarker, real_t ubfactor, idx_t npasses)
00469 {
00470   idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
00471   idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
00472   idx_t *mptr, *mind, *moved, *swaps;
00473   rpq_t *queues[2]; 
00474   nrinfo_t *rinfo;
00475   idx_t higain, oldgain, mincut, initcut, mincutorder;  
00476   idx_t pass, to, other, limit;
00477   idx_t badmaxpwgt, mindiff, newdiff;
00478   idx_t u[2], g[2];
00479 
00480   WCOREPUSH;
00481 
00482   nvtxs  = graph->nvtxs;
00483   xadj   = graph->xadj;
00484   adjncy = graph->adjncy;
00485   vwgt   = graph->vwgt;
00486 
00487   bndind = graph->bndind;
00488   bndptr = graph->bndptr;
00489   where  = graph->where;
00490   pwgts  = graph->pwgts;
00491   rinfo  = graph->nrinfo;
00492 
00493   queues[0] = rpqCreate(nvtxs);
00494   queues[1] = rpqCreate(nvtxs);
00495 
00496   moved = iwspacemalloc(ctrl, nvtxs);
00497   swaps = iwspacemalloc(ctrl, nvtxs);
00498   mptr  = iwspacemalloc(ctrl, nvtxs+1);
00499   mind  = iwspacemalloc(ctrl, 2*nvtxs);
00500 
00501   IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00502     printf("Partitions: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
00503 
00504   badmaxpwgt = (idx_t)(ubfactor*gk_max(pwgts[0], pwgts[1]));
00505 
00506   for (pass=0; pass<npasses; pass++) {
00507     iset(nvtxs, -1, moved);
00508     rpqReset(queues[0]);
00509     rpqReset(queues[1]);
00510 
00511     mincutorder = -1;
00512     initcut = mincut = graph->mincut;
00513     nbnd = graph->nbnd;
00514 
00515     /* use the swaps array in place of the traditional perm array to save memory */
00516     irandArrayPermute(nbnd, swaps, nbnd, 1);
00517     for (ii=0; ii<nbnd; ii++) {
00518       i = bndind[swaps[ii]];
00519       ASSERT(where[i] == 2);
00520       if (hmarker[i] == -1) {
00521         rpqInsert(queues[0], i, vwgt[i]-rinfo[i].edegrees[1]);
00522         rpqInsert(queues[1], i, vwgt[i]-rinfo[i].edegrees[0]);
00523         moved[i] = -5;
00524       }
00525       else if (hmarker[i] != 2) {
00526         rpqInsert(queues[hmarker[i]], i, vwgt[i]-rinfo[i].edegrees[(hmarker[i]+1)%2]);
00527         moved[i] = -(10+hmarker[i]);
00528       }
00529     }
00530 
00531     ASSERT(CheckNodeBnd(graph, nbnd));
00532     ASSERT(CheckNodePartitionParams(graph));
00533 
00534     limit = nbnd;
00535 
00536     /******************************************************
00537     * Get into the FM loop
00538     *******************************************************/
00539     mptr[0] = nmind = 0;
00540     mindiff = abs(pwgts[0]-pwgts[1]);
00541     to = (pwgts[0] < pwgts[1] ? 0 : 1);
00542     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00543       u[0] = rpqSeeTopVal(queues[0]);  
00544       u[1] = rpqSeeTopVal(queues[1]);
00545       if (u[0] != -1 && u[1] != -1) {
00546         g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];
00547         g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];
00548 
00549         to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2)); 
00550 
00551         if (pwgts[to]+vwgt[u[to]] > badmaxpwgt) 
00552           to = (to+1)%2;
00553       }
00554       else if (u[0] == -1 && u[1] == -1) {
00555         break;
00556       }
00557       else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
00558         to = 0;
00559       }
00560       else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
00561         to = 1;
00562       }
00563       else
00564         break;
00565 
00566       other = (to+1)%2;
00567 
00568       higain = rpqGetTop(queues[to]);
00569 
00570       /* Delete its matching entry in the other queue */
00571       if (moved[higain] == -5) 
00572         rpqDelete(queues[other], higain);
00573 
00574       ASSERT(bndptr[higain] != -1);
00575 
00576       /* The following check is to ensure we break out if there is a posibility
00577          of over-running the mind array.  */
00578       if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)
00579         break;
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] == -5 || moved[k] == -(10+other)) 
00612             rpqUpdate(queues[other], k, oldgain-vwgt[higain]);
00613         }
00614         else if (where[k] == other) { /* This vertex is pulled into the separator */
00615           ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\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] == -5 || moved[kk] == -(10+to))
00632                 rpqUpdate(queues[to], kk, oldgain+vwgt[k]);
00633             }
00634           }
00635 
00636           /* Insert the new vertex into the priority queue (if it has not been moved). */
00637           if (moved[k] == -1 && (hmarker[k] == -1 || hmarker[k] == to)) {
00638             rpqInsert(queues[to], k, vwgt[k]-edegrees[other]);
00639             moved[k] = -(10+to);
00640           }
00641 #ifdef FULLMOVES  /* this does not work as well as the above partial one */
00642           if (moved[k] == -1) {
00643             if (hmarker[k] == -1) {
00644               rpqInsert(queues[0], k, vwgt[k]-edegrees[1]);
00645               rpqInsert(queues[1], k, vwgt[k]-edegrees[0]);
00646               moved[k] = -5;
00647             }
00648             else if (hmarker[k] != 2) {
00649               rpqInsert(queues[hmarker[k]], k, vwgt[k]-edegrees[(hmarker[k]+1)%2]);
00650               moved[k] = -(10+hmarker[k]);
00651             }
00652           }
00653 #endif
00654         }
00655       }
00656       mptr[nswaps+1] = nmind;
00657 
00658       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
00659             printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] "
00660                    "[%4"PRIDX" %4"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", 
00661                    higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], 
00662                    pwgts[0], pwgts[1], pwgts[2]));
00663 
00664     }
00665 
00666 
00667     /****************************************************************
00668     * Roll back computation 
00669     *****************************************************************/
00670     for (nswaps--; nswaps>mincutorder; nswaps--) {
00671       higain = swaps[nswaps];
00672 
00673       ASSERT(CheckNodePartitionParams(graph));
00674 
00675       to = where[higain];
00676       other = (to+1)%2;
00677       INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
00678       where[higain] = 2;
00679       BNDInsert(nbnd, bndind, bndptr, higain);
00680 
00681       edegrees = rinfo[higain].edegrees;
00682       edegrees[0] = edegrees[1] = 0;
00683       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00684         k = adjncy[j];
00685         if (where[k] == 2) 
00686           rinfo[k].edegrees[to] -= vwgt[higain];
00687         else
00688           edegrees[where[k]] += vwgt[k];
00689       }
00690 
00691       /* Push nodes out of the separator */
00692       for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
00693         k = mind[j];
00694         ASSERT(where[k] == 2);
00695         where[k] = other;
00696         INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
00697         BNDDelete(nbnd, bndind, bndptr, k);
00698         for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
00699           kk = adjncy[jj];
00700           if (where[kk] == 2) 
00701             rinfo[kk].edegrees[other] += vwgt[k];
00702         }
00703       }
00704     }
00705 
00706     ASSERT(mincut == pwgts[2]);
00707 
00708     IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
00709       printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
00710 
00711     graph->mincut = mincut;
00712     graph->nbnd = nbnd;
00713 
00714     if (mincutorder == -1 || mincut >= initcut)
00715       break;
00716   }
00717 
00718   rpqDestroy(queues[0]);
00719   rpqDestroy(queues[1]);
00720 
00721   WCOREPOP;
00722 }
00723
libs/ck-libs/metis/libmetis/parmetis.c
