Charm++: Charm Source Code Documentation

00001 
00011 #include "metislib.h"
00012 
00013 
00014 
00015 /*************************************************************************/
00016 /* Top-level routine for k-way partitioning refinement. This routine just
00017    calls the appropriate refinement routine based on the objectives and
00018    constraints. */
00019 /*************************************************************************/
00020 void Greedy_KWayOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00021          real_t ffactor, idx_t omode)
00022 {
00023   switch (ctrl->objtype) {
00024     case METIS_OBJTYPE_CUT:
00025       if (graph->ncon == 1)
00026         Greedy_KWayCutOptimize(ctrl, graph, niter, ffactor, omode);
00027       else
00028         Greedy_McKWayCutOptimize(ctrl, graph, niter, ffactor, omode);
00029       break;
00030 
00031     case METIS_OBJTYPE_VOL:
00032       if (graph->ncon == 1)
00033         Greedy_KWayVolOptimize(ctrl, graph, niter, ffactor, omode);
00034       else
00035         Greedy_McKWayVolOptimize(ctrl, graph, niter, ffactor, omode);
00036       break;
00037 
00038     default:
00039       gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
00040   }
00041 }
00042 
00043 
00044 /*************************************************************************/
00059 /**************************************************************************/
00060 void Greedy_KWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00061          real_t ffactor, idx_t omode)
00062 {
00063   /* Common variables to all types of kway-refinement/balancing routines */
00064   idx_t i, ii, iii, j, k, l, pass, nvtxs, nparts, gain; 
00065   idx_t from, me, to, oldcut, vwgt;
00066   idx_t *xadj, *adjncy, *adjwgt;
00067   idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
00068   idx_t nmoved, nupd, *vstatus, *updptr, *updind;
00069   idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
00070   idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
00071   idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
00072 
00073   /* Edgecut-specific/different variables */
00074   idx_t nbnd, oldnnbrs;
00075   rpq_t *queue;
00076   real_t rgain;
00077   ckrinfo_t *myrinfo;
00078   cnbr_t *mynbrs;
00079 
00080   WCOREPUSH;
00081 
00082   /* Link the graph fields */
00083   nvtxs  = graph->nvtxs;
00084   xadj   = graph->xadj;
00085   adjncy = graph->adjncy;
00086   adjwgt = graph->adjwgt;
00087 
00088   bndind = graph->bndind;
00089   bndptr = graph->bndptr;
00090 
00091   where = graph->where;
00092   pwgts = graph->pwgts;
00093   
00094   nparts = ctrl->nparts;
00095 
00096   /* Setup the weight intervals of the various subdomains */
00097   minwgt  = iwspacemalloc(ctrl, nparts);
00098   maxwgt  = iwspacemalloc(ctrl, nparts);
00099   itpwgts = iwspacemalloc(ctrl, nparts);
00100 
00101   for (i=0; i<nparts; i++) {
00102     itpwgts[i] = ctrl->tpwgts[i]*graph->tvwgt[0];
00103     maxwgt[i]  = ctrl->tpwgts[i]*graph->tvwgt[0]*ctrl->ubfactors[0];
00104     minwgt[i]  = ctrl->tpwgts[i]*graph->tvwgt[0]*(1.0/ctrl->ubfactors[0]);
00105   }
00106 
00107   perm = iwspacemalloc(ctrl, nvtxs);
00108 
00109 
00110   /* This stores the valid target subdomains. It is used when ctrl->minconn to
00111      control the subdomains to which moves are allowed to be made. 
00112      When ctrl->minconn is false, the default values of 2 allow all moves to
00113      go through and it does not interfere with the zero-gain move selection. */
00114   safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
00115 
00116   if (ctrl->minconn) {
00117     ComputeSubDomainGraph(ctrl, graph);
00118 
00119     nads    = ctrl->nads;
00120     adids   = ctrl->adids;
00121     adwgts  = ctrl->adwgts;
00122     doms    = iset(nparts, 0, ctrl->pvec1);
00123   }
00124 
00125 
00126   /* Setup updptr, updind like boundary info to keep track of the vertices whose
00127      vstatus's need to be reset at the end of the inner iteration */
00128   vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
00129   updptr  = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
00130   updind  = iwspacemalloc(ctrl, nvtxs);
00131 
00132   if (ctrl->contig) {
00133     /* The arrays that will be used for limited check of articulation points */
00134     bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
00135     bfsind = iwspacemalloc(ctrl, nvtxs);
00136     bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
00137   }
00138 
00139   if (ctrl->dbglvl&METIS_DBG_REFINE) {
00140      printf("%s: [%6"PRIDX" %6"PRIDX"]-[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL"," 
00141             " Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %6"PRIDX,
00142             (omode == OMODE_REFINE ? "GRC" : "GBC"),
00143             pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts), minwgt[0], maxwgt[0], 
00144             ComputeLoadImbalance(graph, nparts, ctrl->pijbm), 
00145             graph->nvtxs, graph->nbnd, graph->mincut);
00146      if (ctrl->minconn) 
00147        printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
00148      printf("\n");
00149   }
00150 
00151   queue = rpqCreate(nvtxs);
00152 
00153   /*=====================================================================
00154   * The top-level refinement loop 
00155   *======================================================================*/
00156   for (pass=0; pass<niter; pass++) {
00157     ASSERT(ComputeCut(graph, where) == graph->mincut);
00158 
00159     if (omode == OMODE_BALANCE) {
00160       /* Check to see if things are out of balance, given the tolerance */
00161       for (i=0; i<nparts; i++) {
00162         if (pwgts[i] > maxwgt[i])
00163           break;
00164       }
00165       if (i == nparts) /* Things are balanced. Return right away */
00166         break;
00167     }
00168 
00169     oldcut = graph->mincut;
00170     nbnd   = graph->nbnd;
00171     nupd   = 0;
00172 
00173     if (ctrl->minconn)
00174       maxndoms = imax(nparts, nads);
00175 
00176     /* Insert the boundary vertices in the priority queue */
00177     irandArrayPermute(nbnd, perm, nbnd/4, 1);
00178     for (ii=0; ii<nbnd; ii++) {
00179       i = bndind[perm[ii]];
00180       rgain = (graph->ckrinfo[i].nnbrs > 0 ? 
00181                1.0*graph->ckrinfo[i].ed/sqrt(graph->ckrinfo[i].nnbrs) : 0.0) 
00182                - graph->ckrinfo[i].id;
00183       rpqInsert(queue, i, rgain);
00184       vstatus[i] = VPQSTATUS_PRESENT;
00185       ListInsert(nupd, updind, updptr, i);
00186     }
00187 
00188     /* Start extracting vertices from the queue and try to move them */
00189     for (nmoved=0, iii=0;;iii++) {
00190       if ((i = rpqGetTop(queue)) == -1) 
00191         break;
00192       vstatus[i] = VPQSTATUS_EXTRACTED;
00193 
00194       myrinfo = graph->ckrinfo+i;
00195       mynbrs  = ctrl->cnbrpool + myrinfo->inbr;
00196 
00197       from = where[i];
00198       vwgt = graph->vwgt[i];
00199 
00200       /* Prevent moves that make 'from' domain underbalanced */
00201       if (omode == OMODE_REFINE) {
00202         if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from]) 
00203           continue;   
00204       }
00205       else { /* OMODE_BALANCE */
00206         if (pwgts[from]-vwgt < minwgt[from]) 
00207           continue;   
00208       }
00209 
00210       if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
00211         continue;
00212 
00213       if (ctrl->minconn)
00214         SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
00215 
00216       /* Find the most promising subdomain to move to */
00217       if (omode == OMODE_REFINE) {
00218         for (k=myrinfo->nnbrs-1; k>=0; k--) {
00219           if (!safetos[to=mynbrs[k].pid])
00220             continue;
00221           gain = mynbrs[k].ed-myrinfo->id; 
00222           if (gain >= 0 && pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain)  
00223             break;
00224         }
00225         if (k < 0)
00226           continue;  /* break out if you did not find a candidate */
00227 
00228         for (j=k-1; j>=0; j--) {
00229           if (!safetos[to=mynbrs[j].pid])
00230             continue;
00231           gain = mynbrs[j].ed-myrinfo->id; 
00232           if ((mynbrs[j].ed > mynbrs[k].ed && pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain) 
00233               ||
00234               (mynbrs[j].ed == mynbrs[k].ed && 
00235                itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid]))
00236             k = j;
00237         }
00238 
00239         to = mynbrs[k].pid;
00240 
00241         gain = mynbrs[k].ed-myrinfo->id;
00242         if (!(gain > 0 
00243               || (gain == 0  
00244                   && (pwgts[from] >= maxwgt[from] 
00245                       || itpwgts[to]*pwgts[from] > itpwgts[from]*(pwgts[to]+vwgt) 
00246                       || (iii%2 == 0 && safetos[to] == 2)
00247                      )
00248                  )
00249              )
00250            )
00251           continue;
00252       }
00253       else {  /* OMODE_BALANCE */
00254         for (k=myrinfo->nnbrs-1; k>=0; k--) {
00255           if (!safetos[to=mynbrs[k].pid])
00256             continue;
00257           if (pwgts[to]+vwgt <= maxwgt[to] || 
00258               itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from]) 
00259             break;
00260         }
00261         if (k < 0)
00262           continue;  /* break out if you did not find a candidate */
00263 
00264         for (j=k-1; j>=0; j--) {
00265           if (!safetos[to=mynbrs[j].pid])
00266             continue;
00267           if (itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid]) 
00268             k = j;
00269         }
00270 
00271         to = mynbrs[k].pid;
00272 
00273         if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && 
00274             mynbrs[k].ed-myrinfo->id < 0) 
00275           continue;
00276       }
00277 
00278 
00279 
00280       /*=====================================================================
00281       * If we got here, we can now move the vertex from 'from' to 'to' 
00282       *======================================================================*/
00283       graph->mincut -= mynbrs[k].ed-myrinfo->id;
00284       nmoved++;
00285 
00286       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
00287           printf("\t\tMoving %6"PRIDX" to %3"PRIDX". Gain: %4"PRIDX". Cut: %6"PRIDX"\n", 
00288               i, to, mynbrs[k].ed-myrinfo->id, graph->mincut));
00289 
00290       /* Update the subdomain connectivity information */
00291       if (ctrl->minconn) {
00292         /* take care of i's move itself */
00293         UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->id-mynbrs[k].ed, &maxndoms);
00294 
00295         /* take care of the adjancent vertices */
00296         for (j=xadj[i]; j<xadj[i+1]; j++) {
00297           me = where[adjncy[j]];
00298           if (me != from && me != to) {
00299             UpdateEdgeSubDomainGraph(ctrl, from, me, -adjwgt[j], &maxndoms);
00300             UpdateEdgeSubDomainGraph(ctrl, to, me, adjwgt[j], &maxndoms);
00301           }
00302         }
00303       }
00304 
00305       /* Update ID/ED and BND related information for the moved vertex */
00306       INC_DEC(pwgts[to], pwgts[from], vwgt);
00307       UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd, 
00308           bndptr, bndind, bndtype);
00309       
00310       /* Update the degrees of adjacent vertices */
00311       for (j=xadj[i]; j<xadj[i+1]; j++) {
00312         ii = adjncy[j];
00313         me = where[ii];
00314         myrinfo = graph->ckrinfo+ii;
00315 
00316         oldnnbrs = myrinfo->nnbrs;
00317 
00318         UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me, 
00319             from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, bndtype);
00320 
00321         UpdateQueueInfo(queue, vstatus, ii, me, from, to, myrinfo, oldnnbrs, 
00322             nupd, updptr, updind, bndtype);
00323 
00324         ASSERT(myrinfo->nnbrs <= xadj[ii+1]-xadj[ii]);
00325       }
00326     }
00327 
00328     graph->nbnd = nbnd;
00329 
00330     /* Reset the vstatus and associated data structures */
00331     for (i=0; i<nupd; i++) {
00332       ASSERT(updptr[updind[i]] != -1);
00333       ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
00334       vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
00335       updptr[updind[i]]  = -1;
00336     }
00337 
00338     if (ctrl->dbglvl&METIS_DBG_REFINE) {
00339        printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
00340               " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
00341               pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts),
00342               ComputeLoadImbalance(graph, nparts, ctrl->pijbm), 
00343               graph->nbnd, nmoved, graph->mincut, ComputeVolume(graph, where));
00344        if (ctrl->minconn) 
00345          printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
00346        printf("\n");
00347     }
00348 
00349     if (nmoved == 0 || (omode == OMODE_REFINE && graph->mincut == oldcut))
00350       break;
00351   }
00352 
00353   rpqDestroy(queue);
00354 
00355   WCOREPOP;
00356 }
00357 
00358 
00359 /*************************************************************************/
00369 /**************************************************************************/
00370 void Greedy_KWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00371          real_t ffactor, idx_t omode)
00372 {
00373   /* Common variables to all types of kway-refinement/balancing routines */
00374   idx_t i, ii, iii, j, k, l, pass, nvtxs, nparts, gain; 
00375   idx_t from, me, to, oldcut, vwgt;
00376   idx_t *xadj, *adjncy;
00377   idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
00378   idx_t nmoved, nupd, *vstatus, *updptr, *updind;
00379   idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
00380   idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
00381   idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
00382 
00383   /* Volume-specific/different variables */
00384   ipq_t *queue;
00385   idx_t oldvol, xgain;
00386   idx_t *vmarker, *pmarker, *modind;
00387   vkrinfo_t *myrinfo;
00388   vnbr_t *mynbrs;
00389 
00390   WCOREPUSH;
00391 
00392   /* Link the graph fields */
00393   nvtxs  = graph->nvtxs;
00394   xadj   = graph->xadj;
00395   adjncy = graph->adjncy;
00396   bndptr = graph->bndptr;
00397   bndind = graph->bndind;
00398   where  = graph->where;
00399   pwgts  = graph->pwgts;
00400   
00401   nparts = ctrl->nparts;
00402 
00403   /* Setup the weight intervals of the various subdomains */
00404   minwgt  = iwspacemalloc(ctrl, nparts);
00405   maxwgt  = iwspacemalloc(ctrl, nparts);
00406   itpwgts = iwspacemalloc(ctrl, nparts);
00407 
00408   for (i=0; i<nparts; i++) {
00409     itpwgts[i] = ctrl->tpwgts[i]*graph->tvwgt[0];
00410     maxwgt[i]  = ctrl->tpwgts[i]*graph->tvwgt[0]*ctrl->ubfactors[0];
00411     minwgt[i]  = ctrl->tpwgts[i]*graph->tvwgt[0]*(1.0/ctrl->ubfactors[0]);
00412   }
00413 
00414   perm = iwspacemalloc(ctrl, nvtxs);
00415 
00416 
00417   /* This stores the valid target subdomains. It is used when ctrl->minconn to
00418      control the subdomains to which moves are allowed to be made. 
00419      When ctrl->minconn is false, the default values of 2 allow all moves to
00420      go through and it does not interfere with the zero-gain move selection. */
00421   safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
00422 
00423   if (ctrl->minconn) {
00424     ComputeSubDomainGraph(ctrl, graph);
00425 
00426     nads    = ctrl->nads;
00427     adids   = ctrl->adids;
00428     adwgts  = ctrl->adwgts;
00429     doms    = iset(nparts, 0, ctrl->pvec1);
00430   }
00431 
00432 
00433   /* Setup updptr, updind like boundary info to keep track of the vertices whose
00434      vstatus's need to be reset at the end of the inner iteration */
00435   vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
00436   updptr  = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
00437   updind  = iwspacemalloc(ctrl, nvtxs);
00438 
00439   if (ctrl->contig) {
00440     /* The arrays that will be used for limited check of articulation points */
00441     bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
00442     bfsind = iwspacemalloc(ctrl, nvtxs);
00443     bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
00444   }
00445 
00446   /* Vol-refinement specific working arrays */
00447   modind  = iwspacemalloc(ctrl, nvtxs);
00448   vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
00449   pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
00450 
00451   if (ctrl->dbglvl&METIS_DBG_REFINE) {
00452      printf("%s: [%6"PRIDX" %6"PRIDX"]-[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL
00453          ", Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %5"PRIDX", Vol: %5"PRIDX,
00454          (omode == OMODE_REFINE ? "GRV" : "GBV"),
00455          pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts), minwgt[0], maxwgt[0], 
00456          ComputeLoadImbalance(graph, nparts, ctrl->pijbm), 
00457          graph->nvtxs, graph->nbnd, graph->mincut, graph->minvol);
00458      if (ctrl->minconn) 
00459        printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
00460      printf("\n");
00461   }
00462 
00463   queue = ipqCreate(nvtxs);
00464 
00465 
00466   /*=====================================================================
00467   * The top-level refinement loop 
00468   *======================================================================*/
00469   for (pass=0; pass<niter; pass++) {
00470     ASSERT(ComputeVolume(graph, where) == graph->minvol);
00471 
00472     if (omode == OMODE_BALANCE) {
00473       /* Check to see if things are out of balance, given the tolerance */
00474       for (i=0; i<nparts; i++) {
00475         if (pwgts[i] > maxwgt[i])
00476           break;
00477       }
00478       if (i == nparts) /* Things are balanced. Return right away */
00479         break;
00480     }
00481 
00482     oldcut = graph->mincut;
00483     oldvol = graph->minvol;
00484     nupd   = 0;
00485 
00486     if (ctrl->minconn)
00487       maxndoms = imax(nparts, nads);
00488 
00489     /* Insert the boundary vertices in the priority queue */
00490     irandArrayPermute(graph->nbnd, perm, graph->nbnd/4, 1);
00491     for (ii=0; ii<graph->nbnd; ii++) {
00492       i = bndind[perm[ii]];
00493       ipqInsert(queue, i, graph->vkrinfo[i].gv);
00494       vstatus[i] = VPQSTATUS_PRESENT;
00495       ListInsert(nupd, updind, updptr, i);
00496     }
00497 
00498     /* Start extracting vertices from the queue and try to move them */
00499     for (nmoved=0, iii=0;;iii++) {
00500       if ((i = ipqGetTop(queue)) == -1) 
00501         break;
00502       vstatus[i] = VPQSTATUS_EXTRACTED;
00503 
00504       myrinfo = graph->vkrinfo+i;
00505       mynbrs  = ctrl->vnbrpool + myrinfo->inbr;
00506 
00507       from = where[i];
00508       vwgt = graph->vwgt[i];
00509 
00510       /* Prevent moves that make 'from' domain underbalanced */
00511       if (omode == OMODE_REFINE) {
00512         if (myrinfo->nid > 0 && pwgts[from]-vwgt < minwgt[from]) 
00513           continue;
00514       }
00515       else { /* OMODE_BALANCE */
00516         if (pwgts[from]-vwgt < minwgt[from]) 
00517           continue;
00518       }
00519 
00520       if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
00521         continue;
00522 
00523       if (ctrl->minconn)
00524         SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
00525 
00526       xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? graph->vsize[i] : 0);
00527 
00528       /* Find the most promising subdomain to move to */
00529       if (omode == OMODE_REFINE) {
00530         for (k=myrinfo->nnbrs-1; k>=0; k--) {
00531           if (!safetos[to=mynbrs[k].pid])
00532             continue;
00533           gain = mynbrs[k].gv + xgain;
00534           if (gain >= 0 && pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain)  
00535             break;
00536         }
00537         if (k < 0)
00538           continue;  /* break out if you did not find a candidate */
00539 
00540         for (j=k-1; j>=0; j--) {
00541           if (!safetos[to=mynbrs[j].pid])
00542             continue;
00543           gain = mynbrs[j].gv + xgain;
00544           if ((mynbrs[j].gv > mynbrs[k].gv && 
00545                pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain) 
00546               ||
00547               (mynbrs[j].gv == mynbrs[k].gv && 
00548                mynbrs[j].ned > mynbrs[k].ned &&
00549                pwgts[to]+vwgt <= maxwgt[to]) 
00550               ||
00551               (mynbrs[j].gv == mynbrs[k].gv && 
00552                mynbrs[j].ned == mynbrs[k].ned &&
00553                itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
00554              )
00555             k = j;
00556         }
00557         to = mynbrs[k].pid;
00558 
00559         ASSERT(xgain+mynbrs[k].gv >= 0);
00560 
00561         j = 0;
00562         if (xgain+mynbrs[k].gv > 0 || mynbrs[k].ned-myrinfo->nid > 0)
00563           j = 1;
00564         else if (mynbrs[k].ned-myrinfo->nid == 0) {
00565           if ((iii%2 == 0 && safetos[to] == 2) || 
00566               pwgts[from] >= maxwgt[from] || 
00567               itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
00568             j = 1;
00569         }
00570         if (j == 0)
00571           continue;
00572       }
00573       else { /* OMODE_BALANCE */
00574         for (k=myrinfo->nnbrs-1; k>=0; k--) {
00575           if (!safetos[to=mynbrs[k].pid])
00576             continue;
00577           if (pwgts[to]+vwgt <= maxwgt[to] || 
00578               itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])  
00579             break;
00580         }
00581         if (k < 0)
00582           continue;  /* break out if you did not find a candidate */
00583 
00584         for (j=k-1; j>=0; j--) {
00585           if (!safetos[to=mynbrs[j].pid])
00586             continue;
00587           if (itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
00588             k = j;
00589         }
00590         to = mynbrs[k].pid;
00591 
00592         if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && 
00593             (xgain+mynbrs[k].gv < 0 || 
00594              (xgain+mynbrs[k].gv == 0 &&  mynbrs[k].ned-myrinfo->nid < 0))
00595            )
00596           continue;
00597       }
00598           
00599           
00600       /*=====================================================================
00601       * If we got here, we can now move the vertex from 'from' to 'to' 
00602       *======================================================================*/
00603       INC_DEC(pwgts[to], pwgts[from], vwgt);
00604       graph->mincut -= mynbrs[k].ned-myrinfo->nid;
00605       graph->minvol -= (xgain+mynbrs[k].gv);
00606       where[i] = to;
00607       nmoved++;
00608 
00609       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
00610           printf("\t\tMoving %6"PRIDX" from %3"PRIDX" to %3"PRIDX". "
00611                  "Gain: [%4"PRIDX" %4"PRIDX"]. Cut: %6"PRIDX", Vol: %6"PRIDX"\n", 
00612               i, from, to, xgain+mynbrs[k].gv, mynbrs[k].ned-myrinfo->nid, 
00613               graph->mincut, graph->minvol));
00614 
00615       /* Update the subdomain connectivity information */
00616       if (ctrl->minconn) {
00617         /* take care of i's move itself */
00618         UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->nid-mynbrs[k].ned, &maxndoms);
00619 
00620         /* take care of the adjancent vertices */
00621         for (j=xadj[i]; j<xadj[i+1]; j++) {
00622           me = where[adjncy[j]];
00623           if (me != from && me != to) {
00624             UpdateEdgeSubDomainGraph(ctrl, from, me, -1, &maxndoms);
00625             UpdateEdgeSubDomainGraph(ctrl, to, me, 1, &maxndoms);
00626           }
00627         }
00628       }
00629 
00630       /* Update the id/ed/gains/bnd/queue of potentially affected nodes */
00631       KWayVolUpdate(ctrl, graph, i, from, to, queue, vstatus, &nupd, updptr, 
00632           updind, bndtype, vmarker, pmarker, modind);
00633 
00634       /*CheckKWayVolPartitionParams(ctrl, graph); */
00635     }
00636 
00637 
00638     /* Reset the vstatus and associated data structures */
00639     for (i=0; i<nupd; i++) {
00640       ASSERT(updptr[updind[i]] != -1);
00641       ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
00642       vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
00643       updptr[updind[i]]  = -1;
00644     }
00645 
00646     if (ctrl->dbglvl&METIS_DBG_REFINE) {
00647        printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
00648               " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
00649               pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts),
00650               ComputeLoadImbalance(graph, nparts, ctrl->pijbm), 
00651               graph->nbnd, nmoved, graph->mincut, graph->minvol);
00652        if (ctrl->minconn) 
00653          printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
00654        printf("\n");
00655     }
00656 
00657     if (nmoved == 0 || 
00658         (omode == OMODE_REFINE && graph->minvol == oldvol && graph->mincut == oldcut))
00659       break;
00660   }
00661 
00662   ipqDestroy(queue);
00663 
00664   WCOREPOP;
00665 }
00666 
00667 
00668 /*************************************************************************/
00683 /**************************************************************************/
00684 void Greedy_McKWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00685          real_t ffactor, idx_t omode)
00686 {
00687   /* Common variables to all types of kway-refinement/balancing routines */
00688   idx_t i, ii, iii, j, k, l, pass, nvtxs, ncon, nparts, gain; 
00689   idx_t from, me, to, cto, oldcut;
00690   idx_t *xadj, *vwgt, *adjncy, *adjwgt;
00691   idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt;
00692   idx_t nmoved, nupd, *vstatus, *updptr, *updind;
00693   idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
00694   idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
00695   idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
00696   real_t *ubfactors, *pijbm;
00697   real_t origbal;
00698 
00699   /* Edgecut-specific/different variables */
00700   idx_t nbnd, oldnnbrs;
00701   rpq_t *queue;
00702   real_t rgain;
00703   ckrinfo_t *myrinfo;
00704   cnbr_t *mynbrs;
00705 
00706   WCOREPUSH;
00707 
00708   /* Link the graph fields */
00709   nvtxs  = graph->nvtxs;
00710   ncon   = graph->ncon;
00711   xadj   = graph->xadj;
00712   vwgt   = graph->vwgt;
00713   adjncy = graph->adjncy;
00714   adjwgt = graph->adjwgt;
00715 
00716   bndind = graph->bndind;
00717   bndptr = graph->bndptr;
00718 
00719   where = graph->where;
00720   pwgts = graph->pwgts;
00721   
00722   nparts = ctrl->nparts;
00723   pijbm  = ctrl->pijbm;
00724 
00725 
00726   /* Determine the ubfactors. The method used is different based on omode. 
00727      When OMODE_BALANCE, the ubfactors are those supplied by the user. 
00728      When OMODE_REFINE, the ubfactors are the max of the current partition
00729      and the user-specified ones. */
00730   ubfactors = rwspacemalloc(ctrl, ncon);
00731   ComputeLoadImbalanceVec(graph, nparts, pijbm, ubfactors);
00732   origbal = rvecmaxdiff(ncon, ubfactors, ctrl->ubfactors);
00733   if (omode == OMODE_BALANCE) {
00734     rcopy(ncon, ctrl->ubfactors, ubfactors);
00735   }
00736   else {
00737     for (i=0; i<ncon; i++)
00738       ubfactors[i] = (ubfactors[i] > ctrl->ubfactors[i] ? ubfactors[i] : ctrl->ubfactors[i]);
00739   }
00740 
00741 
00742   /* Setup the weight intervals of the various subdomains */
00743   minwgt  = iwspacemalloc(ctrl, nparts*ncon);
00744   maxwgt  = iwspacemalloc(ctrl, nparts*ncon);
00745 
00746   for (i=0; i<nparts; i++) {
00747     for (j=0; j<ncon; j++) {
00748       maxwgt[i*ncon+j]  = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*ubfactors[j];
00749       /*minwgt[i*ncon+j]  = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*(.9/ubfactors[j]);*/
00750       minwgt[i*ncon+j]  = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*.2;
00751     }
00752   }
00753 
00754   perm = iwspacemalloc(ctrl, nvtxs);
00755 
00756 
00757   /* This stores the valid target subdomains. It is used when ctrl->minconn to
00758      control the subdomains to which moves are allowed to be made. 
00759      When ctrl->minconn is false, the default values of 2 allow all moves to
00760      go through and it does not interfere with the zero-gain move selection. */
00761   safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
00762 
00763   if (ctrl->minconn) {
00764     ComputeSubDomainGraph(ctrl, graph);
00765 
00766     nads    = ctrl->nads;
00767     adids   = ctrl->adids;
00768     adwgts  = ctrl->adwgts;
00769     doms    = iset(nparts, 0, ctrl->pvec1);
00770   }
00771 
00772 
00773   /* Setup updptr, updind like boundary info to keep track of the vertices whose
00774      vstatus's need to be reset at the end of the inner iteration */
00775   vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
00776   updptr  = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
00777   updind  = iwspacemalloc(ctrl, nvtxs);
00778 
00779   if (ctrl->contig) {
00780     /* The arrays that will be used for limited check of articulation points */
00781     bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
00782     bfsind = iwspacemalloc(ctrl, nvtxs);
00783     bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
00784   }
00785 
00786   if (ctrl->dbglvl&METIS_DBG_REFINE) {
00787      printf("%s: [%6"PRIDX" %6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL"(%.3"PRREAL")," 
00788             " Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %6"PRIDX", (%"PRIDX")",
00789             (omode == OMODE_REFINE ? "GRC" : "GBC"),
00790             imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts), imax(nparts*ncon, maxwgt),
00791             ComputeLoadImbalance(graph, nparts, pijbm), origbal,
00792             graph->nvtxs, graph->nbnd, graph->mincut, niter);
00793      if (ctrl->minconn) 
00794        printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
00795      printf("\n");
00796   }
00797 
00798   queue = rpqCreate(nvtxs);
00799 
00800 
00801   /*=====================================================================
00802   * The top-level refinement loop 
00803   *======================================================================*/
00804   for (pass=0; pass<niter; pass++) {
00805     ASSERT(ComputeCut(graph, where) == graph->mincut);
00806 
00807     /* In balancing mode, exit as soon as balance is reached */
00808     if (omode == OMODE_BALANCE && IsBalanced(ctrl, graph, 0)) 
00809       break;
00810     
00811     oldcut = graph->mincut;
00812     nbnd   = graph->nbnd;
00813     nupd   = 0;
00814 
00815     if (ctrl->minconn)
00816       maxndoms = imax(nparts, nads);
00817 
00818     /* Insert the boundary vertices in the priority queue */
00819     irandArrayPermute(nbnd, perm, nbnd/4, 1);
00820     for (ii=0; ii<nbnd; ii++) {
00821       i = bndind[perm[ii]];
00822       rgain = (graph->ckrinfo[i].nnbrs > 0 ? 
00823                1.0*graph->ckrinfo[i].ed/sqrt(graph->ckrinfo[i].nnbrs) : 0.0) 
00824                - graph->ckrinfo[i].id;
00825       rpqInsert(queue, i, rgain);
00826       vstatus[i] = VPQSTATUS_PRESENT;
00827       ListInsert(nupd, updind, updptr, i);
00828     }
00829 
00830     /* Start extracting vertices from the queue and try to move them */
00831     for (nmoved=0, iii=0;;iii++) {
00832       if ((i = rpqGetTop(queue)) == -1) 
00833         break;
00834       vstatus[i] = VPQSTATUS_EXTRACTED;
00835 
00836       myrinfo = graph->ckrinfo+i;
00837       mynbrs  = ctrl->cnbrpool + myrinfo->inbr;
00838 
00839       from = where[i];
00840 
00841       /* Prevent moves that make 'from' domain underbalanced */
00842       if (omode == OMODE_REFINE) {
00843         if (myrinfo->id > 0 && 
00844             !ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon))
00845           continue;   
00846       }
00847       else { /* OMODE_BALANCE */
00848         if (!ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon)) 
00849           continue;   
00850       }
00851 
00852       if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
00853         continue;
00854 
00855       if (ctrl->minconn)
00856         SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
00857 
00858       /* Find the most promising subdomain to move to */
00859       if (omode == OMODE_REFINE) {
00860         for (k=myrinfo->nnbrs-1; k>=0; k--) {
00861           if (!safetos[to=mynbrs[k].pid])
00862             continue;
00863           gain = mynbrs[k].ed-myrinfo->id; 
00864           if (gain >= 0 && ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
00865             break;
00866         }
00867         if (k < 0)
00868           continue;  /* break out if you did not find a candidate */
00869 
00870         cto = to;
00871         for (j=k-1; j>=0; j--) {
00872           if (!safetos[to=mynbrs[j].pid])
00873             continue;
00874           if ((mynbrs[j].ed > mynbrs[k].ed && 
00875                ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
00876               ||
00877               (mynbrs[j].ed == mynbrs[k].ed && 
00878                BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors, 
00879                    1, pwgts+cto*ncon, pijbm+cto*ncon,
00880                    1, pwgts+to*ncon, pijbm+to*ncon))) {
00881             k   = j;
00882             cto = to;
00883           }
00884         }
00885         to = cto;
00886 
00887         gain = mynbrs[k].ed-myrinfo->id;
00888         if (!(gain > 0 
00889               || (gain == 0  
00890                   && (BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
00891                              -1, pwgts+from*ncon, pijbm+from*ncon,
00892                              +1, pwgts+to*ncon, pijbm+to*ncon)
00893                       || (iii%2 == 0 && safetos[to] == 2)
00894                      )
00895                  )
00896              )
00897            )
00898           continue;
00899       }
00900       else {  /* OMODE_BALANCE */
00901         for (k=myrinfo->nnbrs-1; k>=0; k--) {
00902           if (!safetos[to=mynbrs[k].pid])
00903             continue;
00904           if (ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon) || 
00905               BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
00906                   -1, pwgts+from*ncon, pijbm+from*ncon,
00907                   +1, pwgts+to*ncon, pijbm+to*ncon))
00908             break;
00909         }
00910         if (k < 0)
00911           continue;  /* break out if you did not find a candidate */
00912 
00913         cto = to;
00914         for (j=k-1; j>=0; j--) {
00915           if (!safetos[to=mynbrs[j].pid])
00916             continue;
00917           if (BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors, 
00918                    1, pwgts+cto*ncon, pijbm+cto*ncon,
00919                    1, pwgts+to*ncon, pijbm+to*ncon)) {
00920             k   = j;
00921             cto = to;
00922           }
00923         }
00924         to = cto;
00925 
00926         if (mynbrs[k].ed-myrinfo->id < 0 &&
00927             !BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
00928                   -1, pwgts+from*ncon, pijbm+from*ncon,
00929                   +1, pwgts+to*ncon, pijbm+to*ncon))
00930           continue;
00931       }
00932 
00933 
00934 
00935       /*=====================================================================
00936       * If we got here, we can now move the vertex from 'from' to 'to' 
00937       *======================================================================*/
00938       graph->mincut -= mynbrs[k].ed-myrinfo->id;
00939       nmoved++;
00940 
00941       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
00942           printf("\t\tMoving %6"PRIDX" to %3"PRIDX". Gain: %4"PRIDX". Cut: %6"PRIDX"\n", 
00943               i, to, mynbrs[k].ed-myrinfo->id, graph->mincut));
00944 
00945       /* Update the subdomain connectivity information */
00946       if (ctrl->minconn) {
00947         /* take care of i's move itself */
00948         UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->id-mynbrs[k].ed, &maxndoms);
00949 
00950         /* take care of the adjancent vertices */
00951         for (j=xadj[i]; j<xadj[i+1]; j++) {
00952           me = where[adjncy[j]];
00953           if (me != from && me != to) {
00954             UpdateEdgeSubDomainGraph(ctrl, from, me, -adjwgt[j], &maxndoms);
00955             UpdateEdgeSubDomainGraph(ctrl, to, me, adjwgt[j], &maxndoms);
00956           }
00957         }
00958       }
00959 
00960       /* Update ID/ED and BND related information for the moved vertex */
00961       iaxpy(ncon,  1, vwgt+i*ncon, 1, pwgts+to*ncon,   1);
00962       iaxpy(ncon, -1, vwgt+i*ncon, 1, pwgts+from*ncon, 1);
00963       UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, 
00964           nbnd, bndptr, bndind, bndtype);
00965       
00966       /* Update the degrees of adjacent vertices */
00967       for (j=xadj[i]; j<xadj[i+1]; j++) {
00968         ii = adjncy[j];
00969         me = where[ii];
00970         myrinfo = graph->ckrinfo+ii;
00971 
00972         oldnnbrs = myrinfo->nnbrs;
00973 
00974         UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me, 
00975             from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, bndtype);
00976 
00977         UpdateQueueInfo(queue, vstatus, ii, me, from, to, myrinfo, oldnnbrs, 
00978             nupd, updptr, updind, bndtype);
00979 
00980         ASSERT(myrinfo->nnbrs <= xadj[ii+1]-xadj[ii]);
00981       }
00982     }
00983 
00984     graph->nbnd = nbnd;
00985 
00986     /* Reset the vstatus and associated data structures */
00987     for (i=0; i<nupd; i++) {
00988       ASSERT(updptr[updind[i]] != -1);
00989       ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
00990       vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
00991       updptr[updind[i]]  = -1;
00992     }
00993 
00994     if (ctrl->dbglvl&METIS_DBG_REFINE) {
00995        printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
00996               " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
00997               imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts), 
00998               ComputeLoadImbalance(graph, nparts, pijbm), 
00999               graph->nbnd, nmoved, graph->mincut, ComputeVolume(graph, where));
01000        if (ctrl->minconn) 
01001          printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
01002        printf("\n");
01003     }
01004 
01005     if (nmoved == 0 || (omode == OMODE_REFINE && graph->mincut == oldcut))
01006       break;
01007   }
01008 
01009   rpqDestroy(queue);
01010 
01011   WCOREPOP;
01012 }
01013 
01014 
01015 /*************************************************************************/
01025 /**************************************************************************/
01026 void Greedy_McKWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
01027          real_t ffactor, idx_t omode)
01028 {
01029   /* Common variables to all types of kway-refinement/balancing routines */
01030   idx_t i, ii, iii, j, k, l, pass, nvtxs, ncon, nparts, gain; 
01031   idx_t from, me, to, cto, oldcut;
01032   idx_t *xadj, *vwgt, *adjncy;
01033   idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt;
01034   idx_t nmoved, nupd, *vstatus, *updptr, *updind;
01035   idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
01036   idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
01037   idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
01038   real_t *ubfactors, *pijbm;
01039   real_t origbal;
01040 
01041   /* Volume-specific/different variables */
01042   ipq_t *queue;
01043   idx_t oldvol, xgain;
01044   idx_t *vmarker, *pmarker, *modind;
01045   vkrinfo_t *myrinfo;
01046   vnbr_t *mynbrs;
01047 
01048   WCOREPUSH;
01049 
01050   /* Link the graph fields */
01051   nvtxs  = graph->nvtxs;
01052   ncon   = graph->ncon;
01053   xadj   = graph->xadj;
01054   vwgt   = graph->vwgt;
01055   adjncy = graph->adjncy;
01056   bndptr = graph->bndptr;
01057   bndind = graph->bndind;
01058   where  = graph->where;
01059   pwgts  = graph->pwgts;
01060   
01061   nparts = ctrl->nparts;
01062   pijbm  = ctrl->pijbm;
01063 
01064 
01065   /* Determine the ubfactors. The method used is different based on omode. 
01066      When OMODE_BALANCE, the ubfactors are those supplied by the user. 
01067      When OMODE_REFINE, the ubfactors are the max of the current partition
01068      and the user-specified ones. */
01069   ubfactors = rwspacemalloc(ctrl, ncon);
01070   ComputeLoadImbalanceVec(graph, nparts, pijbm, ubfactors);
01071   origbal = rvecmaxdiff(ncon, ubfactors, ctrl->ubfactors);
01072   if (omode == OMODE_BALANCE) {
01073     rcopy(ncon, ctrl->ubfactors, ubfactors);
01074   }
01075   else {
01076     for (i=0; i<ncon; i++)
01077       ubfactors[i] = (ubfactors[i] > ctrl->ubfactors[i] ? ubfactors[i] : ctrl->ubfactors[i]);
01078   }
01079 
01080 
01081   /* Setup the weight intervals of the various subdomains */
01082   minwgt  = iwspacemalloc(ctrl, nparts*ncon);
01083   maxwgt  = iwspacemalloc(ctrl, nparts*ncon);
01084 
01085   for (i=0; i<nparts; i++) {
01086     for (j=0; j<ncon; j++) {
01087       maxwgt[i*ncon+j]  = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*ubfactors[j];
01088       /*minwgt[i*ncon+j]  = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*(.9/ubfactors[j]); */
01089       minwgt[i*ncon+j]  = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*.2;
01090     }
01091   }
01092 
01093   perm = iwspacemalloc(ctrl, nvtxs);
01094 
01095 
01096   /* This stores the valid target subdomains. It is used when ctrl->minconn to
01097      control the subdomains to which moves are allowed to be made. 
01098      When ctrl->minconn is false, the default values of 2 allow all moves to
01099      go through and it does not interfere with the zero-gain move selection. */
01100   safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
01101 
01102   if (ctrl->minconn) {
01103     ComputeSubDomainGraph(ctrl, graph);
01104 
01105     nads    = ctrl->nads;
01106     adids   = ctrl->adids;
01107     adwgts  = ctrl->adwgts;
01108     doms    = iset(nparts, 0, ctrl->pvec1);
01109   }
01110 
01111 
01112   /* Setup updptr, updind like boundary info to keep track of the vertices whose
01113      vstatus's need to be reset at the end of the inner iteration */
01114   vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
01115   updptr  = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
01116   updind  = iwspacemalloc(ctrl, nvtxs);
01117 
01118   if (ctrl->contig) {
01119     /* The arrays that will be used for limited check of articulation points */
01120     bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
01121     bfsind = iwspacemalloc(ctrl, nvtxs);
01122     bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
01123   }
01124 
01125   /* Vol-refinement specific working arrays */
01126   modind  = iwspacemalloc(ctrl, nvtxs);
01127   vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
01128   pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
01129 
01130   if (ctrl->dbglvl&METIS_DBG_REFINE) {
01131      printf("%s: [%6"PRIDX" %6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL"(%.3"PRREAL"),"
01132          ", Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %5"PRIDX", Vol: %5"PRIDX", (%"PRIDX")",
01133          (omode == OMODE_REFINE ? "GRV" : "GBV"),
01134          imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts), imax(nparts*ncon, maxwgt),
01135          ComputeLoadImbalance(graph, nparts, pijbm), origbal,
01136          graph->nvtxs, graph->nbnd, graph->mincut, graph->minvol, niter);
01137      if (ctrl->minconn) 
01138        printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
01139      printf("\n");
01140   }
01141 
01142   queue = ipqCreate(nvtxs);
01143 
01144 
01145   /*=====================================================================
01146   * The top-level refinement loop 
01147   *======================================================================*/
01148   for (pass=0; pass<niter; pass++) {
01149     ASSERT(ComputeVolume(graph, where) == graph->minvol);
01150 
01151     /* In balancing mode, exit as soon as balance is reached */
01152     if (omode == OMODE_BALANCE && IsBalanced(ctrl, graph, 0))
01153       break;
01154 
01155     oldcut = graph->mincut;
01156     oldvol = graph->minvol;
01157     nupd   = 0;
01158 
01159     if (ctrl->minconn)
01160       maxndoms = imax(nparts, nads);
01161 
01162     /* Insert the boundary vertices in the priority queue */
01163     irandArrayPermute(graph->nbnd, perm, graph->nbnd/4, 1);
01164     for (ii=0; ii<graph->nbnd; ii++) {
01165       i = bndind[perm[ii]];
01166       ipqInsert(queue, i, graph->vkrinfo[i].gv);
01167       vstatus[i] = VPQSTATUS_PRESENT;
01168       ListInsert(nupd, updind, updptr, i);
01169     }
01170 
01171     /* Start extracting vertices from the queue and try to move them */
01172     for (nmoved=0, iii=0;;iii++) {
01173       if ((i = ipqGetTop(queue)) == -1) 
01174         break;
01175       vstatus[i] = VPQSTATUS_EXTRACTED;
01176 
01177       myrinfo = graph->vkrinfo+i;
01178       mynbrs  = ctrl->vnbrpool + myrinfo->inbr;
01179 
01180       from = where[i];
01181 
01182       /* Prevent moves that make 'from' domain underbalanced */
01183       if (omode == OMODE_REFINE) {
01184         if (myrinfo->nid > 0 &&
01185             !ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon))
01186           continue;
01187       }
01188       else { /* OMODE_BALANCE */
01189         if (!ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon))
01190           continue;
01191       }
01192 
01193       if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
01194         continue;
01195 
01196       if (ctrl->minconn)
01197         SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
01198 
01199       xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? graph->vsize[i] : 0);
01200 
01201       /* Find the most promising subdomain to move to */
01202       if (omode == OMODE_REFINE) {
01203         for (k=myrinfo->nnbrs-1; k>=0; k--) {
01204           if (!safetos[to=mynbrs[k].pid])
01205             continue;
01206           gain = mynbrs[k].gv + xgain;
01207           if (gain >= 0 && ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
01208             break;
01209         }
01210         if (k < 0)
01211           continue;  /* break out if you did not find a candidate */
01212 
01213         cto = to;
01214         for (j=k-1; j>=0; j--) {
01215           if (!safetos[to=mynbrs[j].pid])
01216             continue;
01217           gain = mynbrs[j].gv + xgain;
01218           if ((mynbrs[j].gv > mynbrs[k].gv && 
01219                ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
01220               ||
01221               (mynbrs[j].gv == mynbrs[k].gv && 
01222                mynbrs[j].ned > mynbrs[k].ned &&
01223                ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
01224               ||
01225               (mynbrs[j].gv == mynbrs[k].gv && 
01226                mynbrs[j].ned == mynbrs[k].ned &&
01227                BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
01228                    1, pwgts+cto*ncon, pijbm+cto*ncon,
01229                    1, pwgts+to*ncon, pijbm+to*ncon))) {
01230             k   = j;
01231             cto = to;
01232           }
01233         }
01234         to = cto;
01235 
01236         j = 0;
01237         if (xgain+mynbrs[k].gv > 0 || mynbrs[k].ned-myrinfo->nid > 0)
01238           j = 1;
01239         else if (mynbrs[k].ned-myrinfo->nid == 0) {
01240           if ((iii%2 == 0 && safetos[to] == 2) ||
01241               BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
01242                   -1, pwgts+from*ncon, pijbm+from*ncon,
01243                   +1, pwgts+to*ncon, pijbm+to*ncon))
01244             j = 1;
01245         }
01246         if (j == 0)
01247           continue;
01248       }
01249       else { /* OMODE_BALANCE */
01250         for (k=myrinfo->nnbrs-1; k>=0; k--) {
01251           if (!safetos[to=mynbrs[k].pid])
01252             continue;
01253           if (ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon) ||
01254               BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
01255                   -1, pwgts+from*ncon, pijbm+from*ncon,
01256                   +1, pwgts+to*ncon, pijbm+to*ncon))
01257             break;
01258         }
01259         if (k < 0)
01260           continue;  /* break out if you did not find a candidate */
01261 
01262         cto = to;
01263         for (j=k-1; j>=0; j--) {
01264           if (!safetos[to=mynbrs[j].pid])
01265             continue;
01266           if (BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
01267                   1, pwgts+cto*ncon, pijbm+cto*ncon,
01268                   1, pwgts+to*ncon, pijbm+to*ncon)) {
01269             k   = j;
01270             cto = to;
01271           }
01272         }
01273         to = cto;
01274 
01275         if ((xgain+mynbrs[k].gv < 0 || 
01276              (xgain+mynbrs[k].gv == 0 && mynbrs[k].ned-myrinfo->nid < 0))
01277             &&
01278             !BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
01279                  -1, pwgts+from*ncon, pijbm+from*ncon,
01280                  +1, pwgts+to*ncon, pijbm+to*ncon))
01281           continue;
01282       }
01283           
01284           
01285       /*=====================================================================
01286       * If we got here, we can now move the vertex from 'from' to 'to' 
01287       *======================================================================*/
01288       graph->mincut -= mynbrs[k].ned-myrinfo->nid;
01289       graph->minvol -= (xgain+mynbrs[k].gv);
01290       where[i] = to;
01291       nmoved++;
01292 
01293       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
01294           printf("\t\tMoving %6"PRIDX" from %3"PRIDX" to %3"PRIDX". "
01295                  "Gain: [%4"PRIDX" %4"PRIDX"]. Cut: %6"PRIDX", Vol: %6"PRIDX"\n", 
01296               i, from, to, xgain+mynbrs[k].gv, mynbrs[k].ned-myrinfo->nid, 
01297               graph->mincut, graph->minvol));
01298 
01299       /* Update the subdomain connectivity information */
01300       if (ctrl->minconn) {
01301         /* take care of i's move itself */
01302         UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->nid-mynbrs[k].ned, &maxndoms);
01303 
01304         /* take care of the adjancent vertices */
01305         for (j=xadj[i]; j<xadj[i+1]; j++) {
01306           me = where[adjncy[j]];
01307           if (me != from && me != to) {
01308             UpdateEdgeSubDomainGraph(ctrl, from, me, -1, &maxndoms);
01309             UpdateEdgeSubDomainGraph(ctrl, to, me, 1, &maxndoms);
01310           }
01311         }
01312       }
01313 
01314       /* Update pwgts */
01315       iaxpy(ncon,  1, vwgt+i*ncon, 1, pwgts+to*ncon,   1);
01316       iaxpy(ncon, -1, vwgt+i*ncon, 1, pwgts+from*ncon, 1);
01317 
01318       /* Update the id/ed/gains/bnd/queue of potentially affected nodes */
01319       KWayVolUpdate(ctrl, graph, i, from, to, queue, vstatus, &nupd, updptr, 
01320           updind, bndtype, vmarker, pmarker, modind);
01321 
01322       /*CheckKWayVolPartitionParams(ctrl, graph); */
01323     }
01324 
01325 
01326     /* Reset the vstatus and associated data structures */
01327     for (i=0; i<nupd; i++) {
01328       ASSERT(updptr[updind[i]] != -1);
01329       ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
01330       vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
01331       updptr[updind[i]]  = -1;
01332     }
01333 
01334     if (ctrl->dbglvl&METIS_DBG_REFINE) {
01335        printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
01336               " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
01337               imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts), 
01338               ComputeLoadImbalance(graph, nparts, pijbm), 
01339               graph->nbnd, nmoved, graph->mincut, graph->minvol);
01340        if (ctrl->minconn) 
01341          printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
01342        printf("\n");
01343     }
01344 
01345     if (nmoved == 0 || 
01346         (omode == OMODE_REFINE && graph->minvol == oldvol && graph->mincut == oldcut))
01347       break;
01348   }
01349 
01350   ipqDestroy(queue);
01351 
01352   WCOREPOP;
01353 }
01354 
01355 
01356 /*************************************************************************/
01360 /*************************************************************************/
01361 idx_t IsArticulationNode(idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where,
01362           idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk)
01363 {
01364   idx_t ii, j, k=0, head, tail, nhits, tnhits, from, BFSDEPTH=5;
01365 
01366   from = where[i];
01367 
01368   /* Determine if the vertex is safe to move from a contiguity standpoint */
01369   for (tnhits=0, j=xadj[i]; j<xadj[i+1]; j++) {
01370     if (where[adjncy[j]] == from) {
01371       ASSERT(bfsmrk[adjncy[j]] == 0);
01372       ASSERT(bfslvl[adjncy[j]] == 0);
01373       bfsmrk[k=adjncy[j]] = 1;
01374       tnhits++;
01375     }
01376   }
01377 
01378   /* Easy cases */
01379   if (tnhits == 0)
01380     return 0;
01381   if (tnhits == 1) {
01382     bfsmrk[k] = 0;
01383     return 0;
01384   }
01385 
01386   ASSERT(bfslvl[i] == 0);
01387   bfslvl[i] = 1;
01388 
01389   bfsind[0] = k; /* That was the last one from the previous loop */
01390   bfslvl[k] = 1;
01391   bfsmrk[k] = 0;
01392   head = 0;
01393   tail = 1;
01394 
01395   /* Do a limited BFS traversal to see if you can get to all the other nodes */
01396   for (nhits=1; head<tail; ) {
01397     ii = bfsind[head++];
01398     for (j=xadj[ii]; j<xadj[ii+1]; j++) {
01399       if (where[k=adjncy[j]] == from) {
01400         if (bfsmrk[k]) {
01401           bfsmrk[k] = 0;
01402           if (++nhits == tnhits)
01403             break;
01404         }
01405         if (bfslvl[k] == 0 && bfslvl[ii] < BFSDEPTH) {
01406           bfsind[tail++] = k;
01407           bfslvl[k] = bfslvl[ii]+1;
01408         }
01409       }
01410     }
01411     if (nhits == tnhits)
01412       break;
01413   }
01414 
01415   /* Reset the various BFS related arrays */
01416   bfslvl[i] = 0;
01417   for (j=0; j<tail; j++)
01418     bfslvl[bfsind[j]] = 0;
01419 
01420 
01421   /* Reset the bfsmrk array for the next vertex when has not already being cleared */
01422   if (nhits < tnhits) {
01423     for (j=xadj[i]; j<xadj[i+1]; j++) 
01424       if (where[adjncy[j]] == from) 
01425         bfsmrk[adjncy[j]] = 0;
01426   }
01427 
01428   return (nhits != tnhits);
01429 }
01430 
01431 
01432 /*************************************************************************/
01459 /*************************************************************************/
01460 void KWayVolUpdate(ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from, 
01461          idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr, 
01462          idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker, 
01463          idx_t *modind)
01464 {
01465   idx_t i, ii, iii, j, jj, k, kk, l, u, nmod, other, me, myidx; 
01466   idx_t *xadj, *vsize, *adjncy, *where;
01467   vkrinfo_t *myrinfo, *orinfo;
01468   vnbr_t *mynbrs, *onbrs;
01469 
01470   xadj   = graph->xadj;
01471   adjncy = graph->adjncy;
01472   vsize  = graph->vsize;
01473   where  = graph->where;
01474 
01475   myrinfo = graph->vkrinfo+v;
01476   mynbrs  = ctrl->vnbrpool + myrinfo->inbr;
01477 
01478 
01479   /*======================================================================
01480    * Remove the contributions on the gain made by 'v'. 
01481    *=====================================================================*/
01482   for (k=0; k<myrinfo->nnbrs; k++)
01483     pmarker[mynbrs[k].pid] = k;
01484   pmarker[from] = k;
01485 
01486   myidx = pmarker[to];  /* Keep track of the index in mynbrs of the 'to' domain */
01487 
01488   for (j=xadj[v]; j<xadj[v+1]; j++) {
01489     ii     = adjncy[j];
01490     other  = where[ii];
01491     orinfo = graph->vkrinfo+ii;
01492     onbrs  = ctrl->vnbrpool + orinfo->inbr;
01493 
01494     if (other == from) {
01495       for (k=0; k<orinfo->nnbrs; k++) {
01496         if (pmarker[onbrs[k].pid] == -1) 
01497           onbrs[k].gv += vsize[v];
01498       }
01499     }
01500     else {
01501       ASSERT(pmarker[other] != -1);
01502 
01503       if (mynbrs[pmarker[other]].ned > 1) {
01504         for (k=0; k<orinfo->nnbrs; k++) {
01505           if (pmarker[onbrs[k].pid] == -1) 
01506             onbrs[k].gv += vsize[v];
01507         }
01508       }
01509       else { /* There is only one connection */
01510         for (k=0; k<orinfo->nnbrs; k++) {
01511           if (pmarker[onbrs[k].pid] != -1) 
01512             onbrs[k].gv -= vsize[v];
01513         }
01514       }
01515     }
01516   }
01517 
01518   for (k=0; k<myrinfo->nnbrs; k++)
01519     pmarker[mynbrs[k].pid] = -1;
01520   pmarker[from] = -1;
01521 
01522 
01523   /*======================================================================
01524    * Update the id/ed of vertex 'v'
01525    *=====================================================================*/
01526   if (myidx == -1) {
01527     myidx = myrinfo->nnbrs++;
01528     ASSERT(myidx < xadj[v+1]-xadj[v]);
01529     mynbrs[myidx].ned = 0;
01530   }
01531   myrinfo->ned += myrinfo->nid-mynbrs[myidx].ned;
01532   SWAP(myrinfo->nid, mynbrs[myidx].ned, j);
01533   if (mynbrs[myidx].ned == 0) 
01534     mynbrs[myidx] = mynbrs[--myrinfo->nnbrs];
01535   else
01536     mynbrs[myidx].pid = from;
01537 
01538 
01539   /*======================================================================
01540    * Update the degrees of adjacent vertices and their volume gains
01541    *=====================================================================*/
01542   vmarker[v] = 1;
01543   modind[0]  = v;
01544   nmod       = 1;
01545   for (j=xadj[v]; j<xadj[v+1]; j++) {
01546     ii = adjncy[j];
01547     me = where[ii];
01548 
01549     if (!vmarker[ii]) {  /* The marking is done for boundary and max gv calculations */
01550       vmarker[ii] = 2;
01551       modind[nmod++] = ii;
01552     }
01553 
01554     myrinfo = graph->vkrinfo+ii;
01555     if (myrinfo->inbr == -1) 
01556       myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[ii+1]-xadj[ii]+1);
01557     mynbrs = ctrl->vnbrpool + myrinfo->inbr;
01558 
01559     if (me == from) {
01560       INC_DEC(myrinfo->ned, myrinfo->nid, 1);
01561     } 
01562     else if (me == to) {
01563       INC_DEC(myrinfo->nid, myrinfo->ned, 1);
01564     }
01565 
01566     /* Remove the edgeweight from the 'pid == from' entry of the vertex */
01567     if (me != from) {
01568       for (k=0; k<myrinfo->nnbrs; k++) {
01569         if (mynbrs[k].pid == from) {
01570           if (mynbrs[k].ned == 1) {
01571             mynbrs[k] = mynbrs[--myrinfo->nnbrs];
01572             vmarker[ii] = 1;  /* You do a complete .gv calculation */
01573 
01574             /* All vertices adjacent to 'ii' need to be updated */
01575             for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
01576               u      = adjncy[jj];
01577               other  = where[u];
01578               orinfo = graph->vkrinfo+u;
01579               onbrs  = ctrl->vnbrpool + orinfo->inbr;
01580 
01581               for (kk=0; kk<orinfo->nnbrs; kk++) {
01582                 if (onbrs[kk].pid == from) {
01583                   onbrs[kk].gv -= vsize[ii];
01584                   if (!vmarker[u]) { /* Need to update boundary etc */
01585                     vmarker[u]      = 2;
01586                     modind[nmod++] = u;
01587                   }
01588                   break;
01589                 }
01590               }
01591             }
01592           }
01593           else {
01594             mynbrs[k].ned--;
01595 
01596             /* Update the gv due to single 'ii' connection to 'from' */
01597             if (mynbrs[k].ned == 1) {
01598               /* find the vertex 'u' that 'ii' was connected into 'from' */
01599               for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
01600                 u     = adjncy[jj];
01601                 other = where[u];
01602 
01603                 if (other == from) {
01604                   orinfo = graph->vkrinfo+u;
01605                   onbrs  = ctrl->vnbrpool + orinfo->inbr;
01606 
01607                   /* The following is correct because domains in common
01608                      between ii and u will lead to a reduction over the
01609                      previous gain, whereas domains only in u but not in
01610                      ii, will lead to no change as opposed to the earlier
01611                      increase */
01612                   for (kk=0; kk<orinfo->nnbrs; kk++) 
01613                     onbrs[kk].gv += vsize[ii];
01614 
01615                   if (!vmarker[u]) { /* Need to update boundary etc */
01616                     vmarker[u]     = 2;
01617                     modind[nmod++] = u;
01618                   }
01619                   break;  
01620                 }
01621               }
01622             }
01623           }
01624           break; 
01625         }
01626       }
01627     }
01628 
01629 
01630     /* Add the edgeweight to the 'pid == to' entry of the vertex */
01631     if (me != to) {
01632       for (k=0; k<myrinfo->nnbrs; k++) {
01633         if (mynbrs[k].pid == to) {
01634           mynbrs[k].ned++;
01635 
01636           /* Update the gv due to non-single 'ii' connection to 'to' */
01637           if (mynbrs[k].ned == 2) {
01638             /* find the vertex 'u' that 'ii' was connected into 'to' */
01639             for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
01640               u     = adjncy[jj];
01641               other = where[u];
01642 
01643               if (u != v && other == to) {
01644                 orinfo = graph->vkrinfo+u;
01645                 onbrs  = ctrl->vnbrpool + orinfo->inbr;
01646                 for (kk=0; kk<orinfo->nnbrs; kk++) 
01647                   onbrs[kk].gv -= vsize[ii];
01648 
01649                 if (!vmarker[u]) { /* Need to update boundary etc */
01650                   vmarker[u]      = 2;
01651                   modind[nmod++] = u;
01652                 }
01653                 break;  
01654               }
01655             }
01656           }
01657           break;
01658         }
01659       }
01660 
01661       if (k == myrinfo->nnbrs) {
01662         mynbrs[myrinfo->nnbrs].pid   = to;
01663         mynbrs[myrinfo->nnbrs++].ned = 1;
01664         vmarker[ii] = 1;  /* You do a complete .gv calculation */
01665 
01666         /* All vertices adjacent to 'ii' need to be updated */
01667         for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
01668           u      = adjncy[jj];
01669           other  = where[u];
01670           orinfo = graph->vkrinfo+u;
01671           onbrs  = ctrl->vnbrpool + orinfo->inbr;
01672 
01673           for (kk=0; kk<orinfo->nnbrs; kk++) {
01674             if (onbrs[kk].pid == to) {
01675               onbrs[kk].gv += vsize[ii];
01676               if (!vmarker[u]) { /* Need to update boundary etc */
01677                 vmarker[u] = 2;
01678                 modind[nmod++] = u;
01679               }
01680               break;
01681             }
01682           }
01683         }
01684       }
01685     }
01686 
01687     ASSERT(myrinfo->nnbrs <= xadj[ii+1]-xadj[ii]);
01688   }
01689 
01690 
01691   /*======================================================================
01692    * Add the contributions on the volume gain due to 'v'
01693    *=====================================================================*/
01694   myrinfo = graph->vkrinfo+v;
01695   mynbrs  = ctrl->vnbrpool + myrinfo->inbr;
01696   for (k=0; k<myrinfo->nnbrs; k++)
01697     pmarker[mynbrs[k].pid] = k;
01698   pmarker[to] = k;
01699 
01700   for (j=xadj[v]; j<xadj[v+1]; j++) {
01701     ii     = adjncy[j];
01702     other  = where[ii];
01703     orinfo = graph->vkrinfo+ii;
01704     onbrs  = ctrl->vnbrpool + orinfo->inbr;
01705 
01706     if (other == to) {
01707       for (k=0; k<orinfo->nnbrs; k++) {
01708         if (pmarker[onbrs[k].pid] == -1) 
01709           onbrs[k].gv -= vsize[v];
01710       }
01711     }
01712     else {
01713       ASSERT(pmarker[other] != -1);
01714 
01715       if (mynbrs[pmarker[other]].ned > 1) {
01716         for (k=0; k<orinfo->nnbrs; k++) {
01717           if (pmarker[onbrs[k].pid] == -1) 
01718             onbrs[k].gv -= vsize[v];
01719         }
01720       }
01721       else { /* There is only one connection */
01722         for (k=0; k<orinfo->nnbrs; k++) {
01723           if (pmarker[onbrs[k].pid] != -1) 
01724             onbrs[k].gv += vsize[v];
01725         }
01726       }
01727     }
01728   }
01729   for (k=0; k<myrinfo->nnbrs; k++)
01730     pmarker[mynbrs[k].pid] = -1;
01731   pmarker[to] = -1;
01732 
01733 
01734   /*======================================================================
01735    * Recompute the volume information of the 'hard' nodes, and update the
01736    * max volume gain for all the modified vertices and the priority queue
01737    *=====================================================================*/
01738   for (iii=0; iii<nmod; iii++) {
01739     i  = modind[iii];
01740     me = where[i];
01741 
01742     myrinfo = graph->vkrinfo+i;
01743     mynbrs  = ctrl->vnbrpool + myrinfo->inbr;
01744 
01745     if (vmarker[i] == 1) {  /* Only complete gain updates go through */
01746       for (k=0; k<myrinfo->nnbrs; k++) 
01747         mynbrs[k].gv = 0;
01748 
01749       for (j=xadj[i]; j<xadj[i+1]; j++) {
01750         ii     = adjncy[j];
01751         other  = where[ii];
01752         orinfo = graph->vkrinfo+ii;
01753         onbrs  = ctrl->vnbrpool + orinfo->inbr;
01754 
01755         for (kk=0; kk<orinfo->nnbrs; kk++) 
01756           pmarker[onbrs[kk].pid] = kk;
01757         pmarker[other] = 1;
01758 
01759         if (me == other) {
01760           /* Find which domains 'i' is connected and 'ii' is not and update their gain */
01761           for (k=0; k<myrinfo->nnbrs; k++) {
01762             if (pmarker[mynbrs[k].pid] == -1)
01763               mynbrs[k].gv -= vsize[ii];
01764           }
01765         }
01766         else {
01767           ASSERT(pmarker[me] != -1);
01768 
01769           /* I'm the only connection of 'ii' in 'me' */
01770           if (onbrs[pmarker[me]].ned == 1) { 
01771             /* Increase the gains for all the common domains between 'i' and 'ii' */
01772             for (k=0; k<myrinfo->nnbrs; k++) {
01773               if (pmarker[mynbrs[k].pid] != -1) 
01774                 mynbrs[k].gv += vsize[ii];
01775             }
01776           }
01777           else {
01778             /* Find which domains 'i' is connected and 'ii' is not and update their gain */
01779             for (k=0; k<myrinfo->nnbrs; k++) {
01780               if (pmarker[mynbrs[k].pid] == -1) 
01781                 mynbrs[k].gv -= vsize[ii];
01782             }
01783           }
01784         }
01785 
01786         for (kk=0; kk<orinfo->nnbrs; kk++) 
01787           pmarker[onbrs[kk].pid] = -1;
01788         pmarker[other] = -1;
01789   
01790       }
01791     }
01792 
01793     /* Compute the overall gv for that node */
01794     myrinfo->gv = IDX_MIN;
01795     for (k=0; k<myrinfo->nnbrs; k++) {
01796       if (mynbrs[k].gv > myrinfo->gv)
01797         myrinfo->gv = mynbrs[k].gv;
01798     }
01799 
01800     /* Add the xtra gain due to id == 0 */
01801     if (myrinfo->ned > 0 && myrinfo->nid == 0)
01802       myrinfo->gv += vsize[i];
01803 
01804 
01805     /*======================================================================
01806      * Maintain a consistent boundary
01807      *=====================================================================*/
01808     if (bndtype == BNDTYPE_REFINE) {
01809       if (myrinfo->gv >= 0 && graph->bndptr[i] == -1)
01810         BNDInsert(graph->nbnd, graph->bndind, graph->bndptr, i);
01811 
01812       if (myrinfo->gv < 0 && graph->bndptr[i] != -1)
01813         BNDDelete(graph->nbnd, graph->bndind, graph->bndptr, i);
01814     }
01815     else {
01816       if (myrinfo->ned > 0 && graph->bndptr[i] == -1)
01817         BNDInsert(graph->nbnd, graph->bndind, graph->bndptr, i);
01818 
01819       if (myrinfo->ned == 0 && graph->bndptr[i] != -1)
01820         BNDDelete(graph->nbnd, graph->bndind, graph->bndptr, i);
01821     }
01822 
01823 
01824     /*======================================================================
01825      * Update the priority queue appropriately (if allowed)
01826      *=====================================================================*/
01827     if (queue != NULL) {
01828       if (vstatus[i] != VPQSTATUS_EXTRACTED) {
01829         if (graph->bndptr[i] != -1) { /* In-boundary vertex */
01830           if (vstatus[i] == VPQSTATUS_PRESENT) {
01831             ipqUpdate(queue, i, myrinfo->gv);
01832           }
01833           else {
01834             ipqInsert(queue, i, myrinfo->gv);
01835             vstatus[i] = VPQSTATUS_PRESENT;
01836             ListInsert(*r_nupd, updind, updptr, i);
01837           }
01838         }
01839         else { /* Off-boundary vertex */
01840           if (vstatus[i] == VPQSTATUS_PRESENT) {
01841             ipqDelete(queue, i);
01842             vstatus[i] = VPQSTATUS_NOTPRESENT;
01843             ListDelete(*r_nupd, updind, updptr, i);
01844           }
01845         }
01846       }
01847     }
01848   
01849     vmarker[i] = 0;
01850   }
01851 }
01852
libs/ck-libs/metis/libmetis/kwayfm.c
