Charm++: Charm Source Code Documentation

00001 
00011 #include "metislib.h"
00012 
00013 
00014 /*************************************************************************/
00016 /*************************************************************************/
00017 void RefineKWay(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph)
00018 {
00019   idx_t i, nlevels, contig=ctrl->contig;
00020   graph_t *ptr;
00021 
00022   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->UncoarsenTmr));
00023 
00024   /* Determine how many levels are there */
00025   for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++); 
00026 
00027   /* Compute the parameters of the coarsest graph */
00028   ComputeKWayPartitionParams(ctrl, graph);
00029 
00030   /* Try to minimize the sub-domain connectivity */
00031   if (ctrl->minconn) 
00032     EliminateSubDomainEdges(ctrl, graph);
00033   
00034   /* Deal with contiguity constraints at the beginning */
00035   if (contig && FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts) { 
00036     EliminateComponents(ctrl, graph);
00037 
00038     ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
00039     Greedy_KWayOptimize(ctrl, graph, 5, 0, OMODE_BALANCE); 
00040 
00041     ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
00042     Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE); 
00043 
00044     ctrl->contig = 0;
00045   }
00046 
00047   /* Refine each successively finer graph */
00048   for (i=0; ;i++) {
00049     if (ctrl->minconn && i == nlevels/2) 
00050       EliminateSubDomainEdges(ctrl, graph);
00051 
00052     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->RefTmr));
00053 
00054     if (2*i >= nlevels && !IsBalanced(ctrl, graph, .02)) {
00055       ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
00056       Greedy_KWayOptimize(ctrl, graph, 1, 0, OMODE_BALANCE); 
00057       ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
00058     }
00059 
00060     Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 5.0, OMODE_REFINE); 
00061 
00062     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->RefTmr));
00063 
00064     /* Deal with contiguity constraints in the middle */
00065     if (contig && i == nlevels/2) {
00066       if (FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts) {
00067         EliminateComponents(ctrl, graph);
00068 
00069         if (!IsBalanced(ctrl, graph, .02)) {
00070           ctrl->contig = 1;
00071           ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
00072           Greedy_KWayOptimize(ctrl, graph, 5, 0, OMODE_BALANCE); 
00073   
00074           ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
00075           Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE); 
00076           ctrl->contig = 0;
00077         }
00078       }
00079     }
00080 
00081     if (graph == orggraph)
00082       break;
00083 
00084     graph = graph->finer;
00085 
00086     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->ProjectTmr));
00087     ASSERT(graph->vwgt != NULL);
00088 
00089     ProjectKWayPartition(ctrl, graph);
00090     IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->ProjectTmr));
00091   }
00092 
00093   /* Deal with contiguity requirement at the end */
00094   ctrl->contig = contig;
00095   if (contig && FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts) 
00096     EliminateComponents(ctrl, graph);
00097 
00098   if (!IsBalanced(ctrl, graph, 0.0)) {
00099     ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
00100     Greedy_KWayOptimize(ctrl, graph, 10, 0, OMODE_BALANCE); 
00101 
00102     ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
00103     Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE); 
00104   }
00105 
00106   if (ctrl->contig) 
00107     ASSERT(FindPartitionInducedComponents(graph, graph->where, NULL, NULL) == ctrl->nparts);
00108 
00109   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->UncoarsenTmr));
00110 }
00111 
00112 
00113 /*************************************************************************/
00115 /*************************************************************************/
00116 void AllocateKWayPartitionMemory(ctrl_t *ctrl, graph_t *graph)
00117 {
00118 
00119   graph->pwgts  = imalloc(ctrl->nparts*graph->ncon, "AllocateKWayPartitionMemory: pwgts");
00120   graph->where  = imalloc(graph->nvtxs,  "AllocateKWayPartitionMemory: where");
00121   graph->bndptr = imalloc(graph->nvtxs,  "AllocateKWayPartitionMemory: bndptr");
00122   graph->bndind = imalloc(graph->nvtxs,  "AllocateKWayPartitionMemory: bndind");
00123 
00124   switch (ctrl->objtype) {
00125     case METIS_OBJTYPE_CUT:
00126       graph->ckrinfo  = (ckrinfo_t *)gk_malloc(graph->nvtxs*sizeof(ckrinfo_t), 
00127                           "AllocateKWayPartitionMemory: ckrinfo");
00128       break;
00129 
00130     case METIS_OBJTYPE_VOL:
00131       graph->vkrinfo = (vkrinfo_t *)gk_malloc(graph->nvtxs*sizeof(vkrinfo_t), 
00132                           "AllocateKWayVolPartitionMemory: vkrinfo");
00133 
00134       /* This is to let the cut-based -minconn and -contig large-scale graph
00135          changes to go through */
00136       graph->ckrinfo = (ckrinfo_t *)graph->vkrinfo;
00137       break;
00138 
00139     default:
00140       gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
00141   }
00142 
00143 }
00144 
00145 
00146 /*************************************************************************/
00148 /**************************************************************************/
00149 void ComputeKWayPartitionParams(ctrl_t *ctrl, graph_t *graph)
00150 {
00151   idx_t i, j, k, l, nvtxs, ncon, nparts, nbnd, mincut, me, other;
00152   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
00153 
00154   nparts = ctrl->nparts;
00155 
00156   nvtxs  = graph->nvtxs;
00157   ncon   = graph->ncon;
00158   xadj   = graph->xadj;
00159   vwgt   = graph->vwgt;
00160   adjncy = graph->adjncy;
00161   adjwgt = graph->adjwgt;
00162 
00163   where  = graph->where;
00164   pwgts  = iset(nparts*ncon, 0, graph->pwgts);
00165   bndind = graph->bndind;
00166   bndptr = iset(nvtxs, -1, graph->bndptr);
00167 
00168   nbnd = mincut = 0;
00169 
00170   /* Compute pwgts */
00171   if (ncon == 1) {
00172     for (i=0; i<nvtxs; i++) {
00173       ASSERT(where[i] >= 0 && where[i] < nparts);
00174       pwgts[where[i]] += vwgt[i];
00175     }
00176   }
00177   else {
00178     for (i=0; i<nvtxs; i++) {
00179       me = where[i];
00180       for (j=0; j<ncon; j++)
00181         pwgts[me*ncon+j] += vwgt[i*ncon+j];
00182     }
00183   }
00184 
00185   /* Compute the required info for refinement */
00186   switch (ctrl->objtype) {
00187     case METIS_OBJTYPE_CUT:
00188       {
00189         ckrinfo_t *myrinfo;
00190         cnbr_t *mynbrs;
00191 
00192         memset(graph->ckrinfo, 0, sizeof(ckrinfo_t)*nvtxs);
00193         cnbrpoolReset(ctrl);
00194 
00195         for (i=0; i<nvtxs; i++) {
00196           me      = where[i];
00197           myrinfo = graph->ckrinfo+i;
00198 
00199           for (j=xadj[i]; j<xadj[i+1]; j++) {
00200             if (me == where[adjncy[j]])
00201               myrinfo->id += adjwgt[j];
00202             else
00203               myrinfo->ed += adjwgt[j];
00204           }
00205 
00206           /* Time to compute the particular external degrees */
00207           if (myrinfo->ed > 0) {
00208             mincut += myrinfo->ed;
00209 
00210             myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
00211             mynbrs        = ctrl->cnbrpool + myrinfo->inbr;
00212 
00213             for (j=xadj[i]; j<xadj[i+1]; j++) {
00214               other = where[adjncy[j]];
00215               if (me != other) {
00216                 for (k=0; k<myrinfo->nnbrs; k++) {
00217                   if (mynbrs[k].pid == other) {
00218                     mynbrs[k].ed += adjwgt[j];
00219                     break;
00220                   }
00221                 }
00222                 if (k == myrinfo->nnbrs) {
00223                   mynbrs[k].pid = other;
00224                   mynbrs[k].ed  = adjwgt[j];
00225                   myrinfo->nnbrs++;
00226                 }
00227               }
00228             }
00229 
00230             ASSERT(myrinfo->nnbrs <= xadj[i+1]-xadj[i]);
00231 
00232             /* Only ed-id>=0 nodes are considered to be in the boundary */
00233             if (myrinfo->ed-myrinfo->id >= 0)
00234               BNDInsert(nbnd, bndind, bndptr, i);
00235           }
00236           else {
00237             myrinfo->inbr = -1;
00238           }
00239         }
00240 
00241         graph->mincut = mincut/2;
00242         graph->nbnd   = nbnd;
00243 
00244       }
00245       ASSERT(CheckBnd2(graph));
00246       break;
00247 
00248     case METIS_OBJTYPE_VOL:
00249       {
00250         vkrinfo_t *myrinfo;
00251         vnbr_t *mynbrs;
00252 
00253         memset(graph->vkrinfo, 0, sizeof(vkrinfo_t)*nvtxs);
00254         vnbrpoolReset(ctrl);
00255 
00256         /* Compute now the id/ed degrees */
00257         for (i=0; i<nvtxs; i++) {
00258           me      = where[i];
00259           myrinfo = graph->vkrinfo+i;
00260       
00261           for (j=xadj[i]; j<xadj[i+1]; j++) {
00262             if (me == where[adjncy[j]]) 
00263               myrinfo->nid++;
00264             else 
00265               myrinfo->ned++;
00266           }
00267       
00268           /* Time to compute the particular external degrees */
00269           if (myrinfo->ned > 0) { 
00270             mincut += myrinfo->ned;
00271 
00272             myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
00273             mynbrs        = ctrl->vnbrpool + myrinfo->inbr;
00274 
00275             for (j=xadj[i]; j<xadj[i+1]; j++) {
00276               other = where[adjncy[j]];
00277               if (me != other) {
00278                 for (k=0; k<myrinfo->nnbrs; k++) {
00279                   if (mynbrs[k].pid == other) {
00280                     mynbrs[k].ned++;
00281                     break;
00282                   }
00283                 }
00284                 if (k == myrinfo->nnbrs) {
00285                   mynbrs[k].gv  = 0;
00286                   mynbrs[k].pid = other;
00287                   mynbrs[k].ned = 1;
00288                   myrinfo->nnbrs++;
00289                 }
00290               }
00291             }
00292             ASSERT(myrinfo->nnbrs <= xadj[i+1]-xadj[i]);
00293           }
00294           else {
00295             myrinfo->inbr = -1;
00296           }
00297         }
00298         graph->mincut = mincut/2;
00299       
00300         ComputeKWayVolGains(ctrl, graph);
00301       }
00302       ASSERT(graph->minvol == ComputeVolume(graph, graph->where));
00303       break;
00304     default:
00305       gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
00306   }
00307 
00308 }
00309 
00310 
00311 /*************************************************************************/
00314 /*************************************************************************/
00315 void ProjectKWayPartition(ctrl_t *ctrl, graph_t *graph)
00316 {
00317   idx_t i, j, k, nvtxs, nbnd, nparts, me, other, istart, iend, tid, ted;
00318   idx_t *xadj, *adjncy, *adjwgt;
00319   idx_t *cmap, *where, *bndptr, *bndind, *cwhere, *htable;
00320   graph_t *cgraph;
00321 
00322   WCOREPUSH;
00323 
00324   nparts = ctrl->nparts;
00325 
00326   cgraph = graph->coarser;
00327   cwhere = cgraph->where;
00328 
00329   nvtxs   = graph->nvtxs;
00330   cmap    = graph->cmap;
00331   xadj    = graph->xadj;
00332   adjncy  = graph->adjncy;
00333   adjwgt  = graph->adjwgt;
00334 
00335   AllocateKWayPartitionMemory(ctrl, graph);
00336 
00337   where  = graph->where;
00338   bndind = graph->bndind;
00339   bndptr = iset(nvtxs, -1, graph->bndptr);
00340 
00341   htable = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
00342 
00343   /* Compute the required info for refinement */
00344   switch (ctrl->objtype) {
00345     case METIS_OBJTYPE_CUT:
00346       ASSERT(CheckBnd2(cgraph));
00347       {
00348         ckrinfo_t *myrinfo;
00349         cnbr_t *mynbrs;
00350 
00351         /* go through and project partition and compute id/ed for the nodes */
00352         for (i=0; i<nvtxs; i++) {
00353           k        = cmap[i];
00354           where[i] = cwhere[k];
00355           cmap[i]  = cgraph->ckrinfo[k].ed;  /* For optimization */
00356         }
00357 
00358         memset(graph->ckrinfo, 0, sizeof(ckrinfo_t)*nvtxs);
00359         cnbrpoolReset(ctrl);
00360 
00361         for (nbnd=0, i=0; i<nvtxs; i++) {
00362           istart = xadj[i];
00363           iend   = xadj[i+1];
00364 
00365           myrinfo = graph->ckrinfo+i;
00366 
00367           if (cmap[i] == 0) { /* Interior node. Note that cmap[i] = crinfo[cmap[i]].ed */
00368             for (tid=0, j=istart; j<iend; j++) 
00369               tid += adjwgt[j];
00370 
00371             myrinfo->id   = tid;
00372             myrinfo->inbr = -1;
00373           }
00374           else { /* Potentially an interface node */
00375             myrinfo->inbr = cnbrpoolGetNext(ctrl, iend-istart+1);
00376             mynbrs        = ctrl->cnbrpool + myrinfo->inbr;
00377 
00378             me = where[i];
00379             for (tid=0, ted=0, j=istart; j<iend; j++) {
00380               other = where[adjncy[j]];
00381               if (me == other) {
00382                 tid += adjwgt[j];
00383               }
00384               else {
00385                 ted += adjwgt[j];
00386                 if ((k = htable[other]) == -1) {
00387                   htable[other]               = myrinfo->nnbrs;
00388                   mynbrs[myrinfo->nnbrs].pid  = other;
00389                   mynbrs[myrinfo->nnbrs++].ed = adjwgt[j];
00390                 }
00391                 else {
00392                   mynbrs[k].ed += adjwgt[j];
00393                 }
00394               }
00395             }
00396             myrinfo->id = tid;
00397             myrinfo->ed = ted;
00398       
00399             /* Remove space for edegrees if it was interior */
00400             if (ted == 0) { 
00401               ctrl->nbrpoolcpos -= iend-istart+1;
00402               myrinfo->inbr      = -1;
00403             }
00404             else {
00405               if (ted-tid >= 0) 
00406                 BNDInsert(nbnd, bndind, bndptr, i); 
00407       
00408               for (j=0; j<myrinfo->nnbrs; j++)
00409                 htable[mynbrs[j].pid] = -1;
00410             }
00411           }
00412         }
00413       
00414         graph->nbnd = nbnd;
00415 
00416       }
00417       ASSERT(CheckBnd2(graph));
00418       break;
00419 
00420     case METIS_OBJTYPE_VOL:
00421       {
00422         vkrinfo_t *myrinfo;
00423         vnbr_t *mynbrs;
00424 
00425         ASSERT(cgraph->minvol == ComputeVolume(cgraph, cgraph->where));
00426 
00427         /* go through and project partition and compute id/ed for the nodes */
00428         for (i=0; i<nvtxs; i++) {
00429           k        = cmap[i];
00430           where[i] = cwhere[k];
00431           cmap[i]  = cgraph->vkrinfo[k].ned;  /* For optimization */
00432         }
00433 
00434         memset(graph->vkrinfo, 0, sizeof(vkrinfo_t)*nvtxs);
00435         vnbrpoolReset(ctrl);
00436 
00437         for (i=0; i<nvtxs; i++) {
00438           istart = xadj[i];
00439           iend   = xadj[i+1];
00440           myrinfo = graph->vkrinfo+i;
00441 
00442           if (cmap[i] == 0) { /* Note that cmap[i] = crinfo[cmap[i]].ed */
00443             myrinfo->nid  = iend-istart;
00444             myrinfo->inbr = -1;
00445           }
00446           else { /* Potentially an interface node */
00447             myrinfo->inbr = vnbrpoolGetNext(ctrl, iend-istart+1);
00448             mynbrs        = ctrl->vnbrpool + myrinfo->inbr;
00449 
00450             me = where[i];
00451             for (tid=0, ted=0, j=istart; j<iend; j++) {
00452               other = where[adjncy[j]];
00453               if (me == other) {
00454                 tid++;
00455               }
00456               else {
00457                 ted++;
00458                 if ((k = htable[other]) == -1) {
00459                   htable[other]                = myrinfo->nnbrs;
00460                   mynbrs[myrinfo->nnbrs].gv    = 0;
00461                   mynbrs[myrinfo->nnbrs].pid   = other;
00462                   mynbrs[myrinfo->nnbrs++].ned = 1;
00463                 }
00464                 else {
00465                   mynbrs[k].ned++;
00466                 }
00467               }
00468             }
00469             myrinfo->nid = tid;
00470             myrinfo->ned = ted;
00471       
00472             /* Remove space for edegrees if it was interior */
00473             if (ted == 0) { 
00474               ctrl->nbrpoolcpos -= iend-istart+1;
00475               myrinfo->inbr = -1;
00476             }
00477             else {
00478               for (j=0; j<myrinfo->nnbrs; j++)
00479                 htable[mynbrs[j].pid] = -1;
00480             }
00481           }
00482         }
00483       
00484         ComputeKWayVolGains(ctrl, graph);
00485 
00486         ASSERT(graph->minvol == ComputeVolume(graph, graph->where));
00487       }
00488       break;
00489 
00490     default:
00491       gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
00492   }
00493 
00494   graph->mincut = cgraph->mincut;
00495   icopy(nparts*graph->ncon, cgraph->pwgts, graph->pwgts);
00496 
00497   FreeGraph(&graph->coarser);
00498   graph->coarser = NULL;
00499 
00500   WCOREPOP;
00501 }
00502 
00503 
00504 /*************************************************************************/
00506 /*************************************************************************/
00507 void ComputeKWayBoundary(ctrl_t *ctrl, graph_t *graph, idx_t bndtype)
00508 {
00509   idx_t i, nvtxs, nbnd;
00510   idx_t *bndind, *bndptr;
00511 
00512   nvtxs  = graph->nvtxs;
00513   bndind = graph->bndind;
00514   bndptr = iset(nvtxs, -1, graph->bndptr);
00515 
00516   nbnd = 0;
00517 
00518   switch (ctrl->objtype) {
00519     case METIS_OBJTYPE_CUT:
00520       /* Compute the boundary */
00521       if (bndtype == BNDTYPE_REFINE) {
00522         for (i=0; i<nvtxs; i++) {
00523           if (graph->ckrinfo[i].ed-graph->ckrinfo[i].id >= 0) 
00524             BNDInsert(nbnd, bndind, bndptr, i);
00525         }
00526       }
00527       else { /* BNDTYPE_BALANCE */
00528         for (i=0; i<nvtxs; i++) {
00529           if (graph->ckrinfo[i].ed > 0) 
00530             BNDInsert(nbnd, bndind, bndptr, i);
00531         }
00532       }
00533       break;
00534 
00535     case METIS_OBJTYPE_VOL:
00536       /* Compute the boundary */
00537       if (bndtype == BNDTYPE_REFINE) {
00538         for (i=0; i<nvtxs; i++) {
00539           if (graph->vkrinfo[i].gv >= 0)
00540             BNDInsert(nbnd, bndind, bndptr, i);
00541         }
00542       }
00543       else { /* BNDTYPE_BALANCE */
00544         for (i=0; i<nvtxs; i++) {
00545           if (graph->vkrinfo[i].ned > 0) 
00546             BNDInsert(nbnd, bndind, bndptr, i);
00547         }
00548       }
00549       break;
00550 
00551     default:
00552       gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
00553   }
00554 
00555   graph->nbnd = nbnd;
00556 }
00557 
00558 
00559 /*************************************************************************/
00561 /*************************************************************************/
00562 void ComputeKWayVolGains(ctrl_t *ctrl, graph_t *graph)
00563 {
00564   idx_t i, ii, j, k, l, nvtxs, nparts, me, other, pid; 
00565   idx_t *xadj, *vsize, *adjncy, *adjwgt, *where, 
00566         *bndind, *bndptr, *ophtable;
00567   vkrinfo_t *myrinfo, *orinfo;
00568   vnbr_t *mynbrs, *onbrs;
00569 
00570   WCOREPUSH;
00571 
00572   nparts = ctrl->nparts;
00573 
00574   nvtxs  = graph->nvtxs;
00575   xadj   = graph->xadj;
00576   vsize  = graph->vsize;
00577   adjncy = graph->adjncy;
00578   adjwgt = graph->adjwgt;
00579 
00580   where  = graph->where;
00581   bndind = graph->bndind;
00582   bndptr = iset(nvtxs, -1, graph->bndptr);
00583 
00584   ophtable = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
00585 
00586   /* Compute the volume gains */
00587   graph->minvol = graph->nbnd = 0;
00588   for (i=0; i<nvtxs; i++) {
00589     myrinfo     = graph->vkrinfo+i;
00590     myrinfo->gv = IDX_MIN;
00591 
00592     if (myrinfo->nnbrs > 0) {
00593       me     = where[i];
00594       mynbrs = ctrl->vnbrpool + myrinfo->inbr;
00595 
00596       graph->minvol += myrinfo->nnbrs*vsize[i];
00597 
00598       for (j=xadj[i]; j<xadj[i+1]; j++) {
00599         ii     = adjncy[j];
00600         other  = where[ii];
00601         orinfo = graph->vkrinfo+ii;
00602         onbrs  = ctrl->vnbrpool + orinfo->inbr;
00603 
00604         for (k=0; k<orinfo->nnbrs; k++) 
00605           ophtable[onbrs[k].pid] = k;
00606         ophtable[other] = 1;  /* this is to simplify coding */
00607 
00608         if (me == other) {
00609           /* Find which domains 'i' is connected to but 'ii' is not 
00610              and update their gain */
00611           for (k=0; k<myrinfo->nnbrs; k++) {
00612             if (ophtable[mynbrs[k].pid] == -1)
00613               mynbrs[k].gv -= vsize[ii];
00614           }
00615         }
00616         else {
00617           ASSERT(ophtable[me] != -1);
00618 
00619           if (onbrs[ophtable[me]].ned == 1) { 
00620             /* I'm the only connection of 'ii' in 'me' */
00621             /* Increase the gains for all the common domains between 'i' and 'ii' */
00622             for (k=0; k<myrinfo->nnbrs; k++) {
00623               if (ophtable[mynbrs[k].pid] != -1) 
00624                 mynbrs[k].gv += vsize[ii];
00625             }
00626           }
00627           else {
00628             /* Find which domains 'i' is connected to and 'ii' is not 
00629                and update their gain */
00630             for (k=0; k<myrinfo->nnbrs; k++) {
00631               if (ophtable[mynbrs[k].pid] == -1) 
00632                 mynbrs[k].gv -= vsize[ii];
00633             }
00634           }
00635         }
00636 
00637         /* Reset the marker vector */
00638         for (k=0; k<orinfo->nnbrs; k++) 
00639           ophtable[onbrs[k].pid] = -1;
00640         ophtable[other] = -1;
00641       }
00642 
00643       /* Compute the max vgain */
00644       for (k=0; k<myrinfo->nnbrs; k++) {
00645         if (mynbrs[k].gv > myrinfo->gv)
00646           myrinfo->gv = mynbrs[k].gv;
00647       }
00648 
00649       /* Add the extra gain due to id == 0 */
00650       if (myrinfo->ned > 0 && myrinfo->nid == 0)
00651         myrinfo->gv += vsize[i];
00652     }
00653 
00654     if (myrinfo->gv >= 0)
00655       BNDInsert(graph->nbnd, bndind, bndptr, i);
00656   }
00657 
00658   WCOREPOP;
00659 }
00660 
00661 
00662 /*************************************************************************/
00665 /*************************************************************************/
00666 int IsBalanced(ctrl_t *ctrl, graph_t *graph, real_t ffactor)
00667 {
00668   return 
00669     (ComputeLoadImbalanceDiff(graph, ctrl->nparts, ctrl->pijbm, ctrl->ubfactors) 
00670          <= ffactor);
00671 }
00672
libs/ck-libs/metis/libmetis/kwayrefine.c
