Charm++: Charm Source Code Documentation

00001 
00011 #include "metislib.h"
00012 
00013 
00014 /*************************************************************************
00015 * This function performs an edge-based FM refinement
00016 **************************************************************************/
00017 void FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
00018 {
00019   if (graph->ncon == 1) 
00020     FM_2WayCutRefine(ctrl, graph, ntpwgts, niter);
00021   else
00022     FM_Mc2WayCutRefine(ctrl, graph, ntpwgts, niter);
00023 }
00024 
00025 
00026 /*************************************************************************/
00028 /*************************************************************************/
00029 void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
00030 {
00031   idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, limit, tmp;
00032   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
00033   idx_t *moved, *swaps, *perm;
00034   rpq_t *queues[2];
00035   idx_t higain, mincut, mindiff, origdiff, initcut, newcut, mincutorder, avgvwgt;
00036   idx_t tpwgts[2];
00037 
00038   WCOREPUSH;
00039 
00040   nvtxs  = graph->nvtxs;
00041   xadj   = graph->xadj;
00042   vwgt   = graph->vwgt;
00043   adjncy = graph->adjncy;
00044   adjwgt = graph->adjwgt;
00045   where  = graph->where;
00046   id     = graph->id;
00047   ed     = graph->ed;
00048   pwgts  = graph->pwgts;
00049   bndptr = graph->bndptr;
00050   bndind = graph->bndind;
00051 
00052   moved = iwspacemalloc(ctrl, nvtxs);
00053   swaps = iwspacemalloc(ctrl, nvtxs);
00054   perm  = iwspacemalloc(ctrl, nvtxs);
00055 
00056   tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
00057   tpwgts[1] = graph->tvwgt[0]-tpwgts[0];
00058   
00059   limit   = gk_min(gk_max(0.01*nvtxs, 15), 100);
00060   avgvwgt = gk_min((pwgts[0]+pwgts[1])/20, 2*(pwgts[0]+pwgts[1])/nvtxs);
00061 
00062   queues[0] = rpqCreate(nvtxs);
00063   queues[1] = rpqCreate(nvtxs);
00064 
00065   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00066       Print2WayRefineStats(ctrl, graph, ntpwgts, 0, -2));
00067 
00068   origdiff = iabs(tpwgts[0]-pwgts[0]);
00069   iset(nvtxs, -1, moved);
00070   for (pass=0; pass<niter; pass++) { /* Do a number of passes */
00071     rpqReset(queues[0]);
00072     rpqReset(queues[1]);
00073 
00074     mincutorder = -1;
00075     newcut = mincut = initcut = graph->mincut;
00076     mindiff = iabs(tpwgts[0]-pwgts[0]);
00077 
00078     ASSERT(ComputeCut(graph, where) == graph->mincut);
00079     ASSERT(CheckBnd(graph));
00080 
00081     /* Insert boundary nodes in the priority queues */
00082     nbnd = graph->nbnd;
00083     irandArrayPermute(nbnd, perm, nbnd, 1);
00084     for (ii=0; ii<nbnd; ii++) {
00085       i = perm[ii];
00086       ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
00087       ASSERT(bndptr[bndind[i]] != -1);
00088       rpqInsert(queues[where[bndind[i]]], bndind[i], ed[bndind[i]]-id[bndind[i]]);
00089     }
00090 
00091     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00092       from = (tpwgts[0]-pwgts[0] < tpwgts[1]-pwgts[1] ? 0 : 1);
00093       to = (from+1)%2;
00094 
00095       if ((higain = rpqGetTop(queues[from])) == -1)
00096         break;
00097       ASSERT(bndptr[higain] != -1);
00098 
00099       newcut -= (ed[higain]-id[higain]);
00100       INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
00101 
00102       if ((newcut < mincut && iabs(tpwgts[0]-pwgts[0]) <= origdiff+avgvwgt) || 
00103           (newcut == mincut && iabs(tpwgts[0]-pwgts[0]) < mindiff)) {
00104         mincut  = newcut;
00105         mindiff = iabs(tpwgts[0]-pwgts[0]);
00106         mincutorder = nswaps;
00107       }
00108       else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
00109         newcut += (ed[higain]-id[higain]);
00110         INC_DEC(pwgts[from], pwgts[to], vwgt[higain]);
00111         break;
00112       }
00113 
00114       where[higain] = to;
00115       moved[higain] = nswaps;
00116       swaps[nswaps] = higain;
00117 
00118       IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, 
00119         printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], newcut, pwgts[0], pwgts[1]));
00120 
00121       /**************************************************************
00122       * Update the id[i]/ed[i] values of the affected nodes
00123       ***************************************************************/
00124       SWAP(id[higain], ed[higain], tmp);
00125       if (ed[higain] == 0 && xadj[higain] < xadj[higain+1]) 
00126         BNDDelete(nbnd, bndind,  bndptr, higain);
00127 
00128       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00129         k = adjncy[j];
00130 
00131         kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00132         INC_DEC(id[k], ed[k], kwgt);
00133 
00134         /* Update its boundary information and queue position */
00135         if (bndptr[k] != -1) { /* If k was a boundary vertex */
00136           if (ed[k] == 0) { /* Not a boundary vertex any more */
00137             BNDDelete(nbnd, bndind, bndptr, k);
00138             if (moved[k] == -1)  /* Remove it if in the queues */
00139               rpqDelete(queues[where[k]], k);
00140           }
00141           else { /* If it has not been moved, update its position in the queue */
00142             if (moved[k] == -1) 
00143               rpqUpdate(queues[where[k]], k, ed[k]-id[k]);
00144           }
00145         }
00146         else {
00147           if (ed[k] > 0) {  /* It will now become a boundary vertex */
00148             BNDInsert(nbnd, bndind, bndptr, k);
00149             if (moved[k] == -1) 
00150               rpqInsert(queues[where[k]], k, ed[k]-id[k]);
00151           }
00152         }
00153       }
00154 
00155     }
00156 
00157 
00158     /****************************************************************
00159     * Roll back computations
00160     *****************************************************************/
00161     for (i=0; i<nswaps; i++)
00162       moved[swaps[i]] = -1;  /* reset moved array */
00163     for (nswaps--; nswaps>mincutorder; nswaps--) {
00164       higain = swaps[nswaps];
00165 
00166       to = where[higain] = (where[higain]+1)%2;
00167       SWAP(id[higain], ed[higain], tmp);
00168       if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
00169         BNDDelete(nbnd, bndind,  bndptr, higain);
00170       else if (ed[higain] > 0 && bndptr[higain] == -1)
00171         BNDInsert(nbnd, bndind,  bndptr, higain);
00172 
00173       INC_DEC(pwgts[to], pwgts[(to+1)%2], vwgt[higain]);
00174       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00175         k = adjncy[j];
00176 
00177         kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00178         INC_DEC(id[k], ed[k], kwgt);
00179 
00180         if (bndptr[k] != -1 && ed[k] == 0)
00181           BNDDelete(nbnd, bndind, bndptr, k);
00182         if (bndptr[k] == -1 && ed[k] > 0)
00183           BNDInsert(nbnd, bndind, bndptr, k);
00184       }
00185     }
00186 
00187     graph->mincut = mincut;
00188     graph->nbnd   = nbnd;
00189 
00190     IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00191         Print2WayRefineStats(ctrl, graph, ntpwgts, 0, mincutorder));
00192 
00193     if (mincutorder <= 0 || mincut == initcut)
00194       break;
00195   }
00196 
00197   rpqDestroy(queues[0]);
00198   rpqDestroy(queues[1]);
00199 
00200   WCOREPOP;
00201 }
00202 
00203 
00204 /*************************************************************************/
00206 /*************************************************************************/
00207 void FM_Mc2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
00208 {
00209   idx_t i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, 
00210         me, limit, tmp, cnum;
00211   idx_t *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *id, *ed, 
00212         *bndptr, *bndind;
00213   idx_t *moved, *swaps, *perm, *qnum;
00214   idx_t higain, mincut, initcut, newcut, mincutorder;
00215   real_t *invtvwgt, *ubfactors, *minbalv, *newbalv;
00216   real_t origbal, minbal, newbal, rgain, ffactor;
00217   rpq_t **queues;
00218 
00219   WCOREPUSH;
00220 
00221   nvtxs    = graph->nvtxs;
00222   ncon     = graph->ncon;
00223   xadj     = graph->xadj;
00224   vwgt     = graph->vwgt;
00225   adjncy   = graph->adjncy;
00226   adjwgt   = graph->adjwgt;
00227   invtvwgt = graph->invtvwgt;
00228   where    = graph->where;
00229   id       = graph->id;
00230   ed       = graph->ed;
00231   pwgts    = graph->pwgts;
00232   bndptr   = graph->bndptr;
00233   bndind   = graph->bndind;
00234 
00235   moved     = iwspacemalloc(ctrl, nvtxs);
00236   swaps     = iwspacemalloc(ctrl, nvtxs);
00237   perm      = iwspacemalloc(ctrl, nvtxs);
00238   qnum      = iwspacemalloc(ctrl, nvtxs);
00239   ubfactors = rwspacemalloc(ctrl, ncon);
00240   newbalv   = rwspacemalloc(ctrl, ncon);
00241   minbalv   = rwspacemalloc(ctrl, ncon);
00242 
00243   limit = gk_min(gk_max(0.01*nvtxs, 25), 150);
00244 
00245 
00246   /* Determine a fudge factor to allow the refinement routines to get out 
00247      of tight balancing constraints. */
00248   ffactor = .5/gk_max(20, nvtxs);
00249 
00250   /* Initialize the queues */
00251   queues = (rpq_t **)wspacemalloc(ctrl, 2*ncon*sizeof(rpq_t *));
00252   for (i=0; i<2*ncon; i++) 
00253     queues[i] = rpqCreate(nvtxs);
00254   for (i=0; i<nvtxs; i++)
00255     qnum[i] = iargmax_nrm(ncon, vwgt+i*ncon, invtvwgt);
00256 
00257   /* Determine the unbalance tolerance for each constraint. The tolerance is
00258      equal to the maximum of the original load imbalance and the user-supplied
00259      allowed tolerance. The rationale behind this approach is to allow the
00260      refinement routine to improve the cut, without having to worry about fixing
00261      load imbalance problems. The load imbalance is addressed by the balancing
00262      routines. */
00263   origbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, ubfactors);
00264   for (i=0; i<ncon; i++) 
00265     ubfactors[i] = (ubfactors[i] > 0 ? ctrl->ubfactors[i]+ubfactors[i] : ctrl->ubfactors[i]);
00266 
00267 
00268   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00269       Print2WayRefineStats(ctrl, graph, ntpwgts, origbal, -2));
00270 
00271   iset(nvtxs, -1, moved);
00272   for (pass=0; pass<niter; pass++) { /* Do a number of passes */
00273     for (i=0; i<2*ncon; i++)  
00274       rpqReset(queues[i]);
00275 
00276     mincutorder = -1;
00277     newcut = mincut = initcut = graph->mincut;
00278 
00279     minbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ubfactors, minbalv);
00280 
00281     ASSERT(ComputeCut(graph, where) == graph->mincut);
00282     ASSERT(CheckBnd(graph));
00283 
00284     /* Insert boundary nodes in the priority queues */
00285     nbnd = graph->nbnd;
00286     irandArrayPermute(nbnd, perm, nbnd/5, 1);
00287     for (ii=0; ii<nbnd; ii++) {
00288       i = bndind[perm[ii]];
00289       ASSERT(ed[i] > 0 || id[i] == 0);
00290       ASSERT(bndptr[i] != -1);
00291       //rgain = 1.0*(ed[i]-id[i])/sqrt(vwgt[i*ncon+qnum[i]]+1);
00292       //rgain = (ed[i]-id[i] > 0 ? 1.0*(ed[i]-id[i])/sqrt(vwgt[i*ncon+qnum[i]]+1) : ed[i]-id[i]);
00293       rgain = ed[i]-id[i];
00294       rpqInsert(queues[2*qnum[i]+where[i]], i, rgain);
00295     }
00296 
00297     for (nswaps=0; nswaps<nvtxs; nswaps++) {
00298       SelectQueue(graph, ctrl->pijbm, ubfactors, queues, &from, &cnum);
00299 
00300       to = (from+1)%2;
00301 
00302       if (from == -1 || (higain = rpqGetTop(queues[2*cnum+from])) == -1)
00303         break;
00304       ASSERT(bndptr[higain] != -1);
00305 
00306       newcut -= (ed[higain]-id[higain]);
00307 
00308       iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+to*ncon,   1);
00309       iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
00310       newbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ubfactors, newbalv);
00311 
00312       if ((newcut < mincut && newbal <= ffactor) || 
00313           (newcut == mincut && (newbal < minbal || 
00314            (newbal == minbal && BetterBalance2Way(ncon, minbalv, newbalv))))) {
00315         mincut      = newcut;
00316         minbal      = newbal;
00317         mincutorder = nswaps;
00318         rcopy(ncon, newbalv, minbalv);
00319       }
00320       else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
00321         newcut += (ed[higain]-id[higain]);
00322         iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
00323         iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+to*ncon,   1);
00324         break;
00325       }
00326 
00327       where[higain] = to;
00328       moved[higain] = nswaps;
00329       swaps[nswaps] = higain;
00330 
00331       if (ctrl->dbglvl&METIS_DBG_MOVEINFO) {
00332         printf("Moved%6"PRIDX" from %"PRIDX"(%"PRIDX") Gain:%5"PRIDX", "
00333             "Cut:%5"PRIDX", NPwgts:", higain, from, cnum, ed[higain]-id[higain], newcut);
00334         for (l=0; l<ncon; l++) 
00335           printf("(%.3"PRREAL" %.3"PRREAL")", pwgts[l]*invtvwgt[l], pwgts[ncon+l]*invtvwgt[l]);
00336         printf(" %+.3"PRREAL" LB: %.3"PRREAL"(%+.3"PRREAL")\n", 
00337             minbal, ComputeLoadImbalance(graph, 2, ctrl->pijbm), newbal);
00338       }
00339 
00340 
00341       /**************************************************************
00342       * Update the id[i]/ed[i] values of the affected nodes
00343       ***************************************************************/
00344       SWAP(id[higain], ed[higain], tmp);
00345       if (ed[higain] == 0 && xadj[higain] < xadj[higain+1]) 
00346         BNDDelete(nbnd, bndind,  bndptr, higain);
00347 
00348       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00349         k = adjncy[j];
00350 
00351         kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00352         INC_DEC(id[k], ed[k], kwgt);
00353 
00354         /* Update its boundary information and queue position */
00355         if (bndptr[k] != -1) { /* If k was a boundary vertex */
00356           if (ed[k] == 0) { /* Not a boundary vertex any more */
00357             BNDDelete(nbnd, bndind, bndptr, k);
00358             if (moved[k] == -1)  /* Remove it if in the queues */
00359               rpqDelete(queues[2*qnum[k]+where[k]], k);
00360           }
00361           else { /* If it has not been moved, update its position in the queue */
00362             if (moved[k] == -1) {
00363               //rgain = 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1);
00364               //rgain = (ed[k]-id[k] > 0 ? 
00365               //              1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1) : ed[k]-id[k]);
00366               rgain = ed[k]-id[k];
00367               rpqUpdate(queues[2*qnum[k]+where[k]], k, rgain);
00368             }
00369           }
00370         }
00371         else {
00372           if (ed[k] > 0) {  /* It will now become a boundary vertex */
00373             BNDInsert(nbnd, bndind, bndptr, k);
00374             if (moved[k] == -1) {
00375               //rgain = 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1);
00376               //rgain = (ed[k]-id[k] > 0 ? 
00377               //              1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1) : ed[k]-id[k]);
00378               rgain = ed[k]-id[k];
00379               rpqInsert(queues[2*qnum[k]+where[k]], k, rgain);
00380             }
00381           }
00382         }
00383       }
00384 
00385     }
00386 
00387 
00388     /****************************************************************
00389     * Roll back computations
00390     *****************************************************************/
00391     for (i=0; i<nswaps; i++)
00392       moved[swaps[i]] = -1;  /* reset moved array */
00393     for (nswaps--; nswaps>mincutorder; nswaps--) {
00394       higain = swaps[nswaps];
00395 
00396       to = where[higain] = (where[higain]+1)%2;
00397       SWAP(id[higain], ed[higain], tmp);
00398       if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
00399         BNDDelete(nbnd, bndind,  bndptr, higain);
00400       else if (ed[higain] > 0 && bndptr[higain] == -1)
00401         BNDInsert(nbnd, bndind,  bndptr, higain);
00402 
00403       iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+to*ncon,         1);
00404       iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+((to+1)%2)*ncon, 1);
00405       for (j=xadj[higain]; j<xadj[higain+1]; j++) {
00406         k = adjncy[j];
00407 
00408         kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
00409         INC_DEC(id[k], ed[k], kwgt);
00410 
00411         if (bndptr[k] != -1 && ed[k] == 0)
00412           BNDDelete(nbnd, bndind, bndptr, k);
00413         if (bndptr[k] == -1 && ed[k] > 0)
00414           BNDInsert(nbnd, bndind, bndptr, k);
00415       }
00416     }
00417 
00418     graph->mincut = mincut;
00419     graph->nbnd   = nbnd;
00420 
00421     IFSET(ctrl->dbglvl, METIS_DBG_REFINE, 
00422         Print2WayRefineStats(ctrl, graph, ntpwgts, minbal, mincutorder));
00423 
00424     if (mincutorder <= 0 || mincut == initcut)
00425       break;
00426   }
00427 
00428   for (i=0; i<2*ncon; i++) 
00429     rpqDestroy(queues[i]);
00430 
00431   WCOREPOP;
00432 }
00433 
00434 
00435 /*************************************************************************/
00438 /*************************************************************************/ 
00439 void SelectQueue(graph_t *graph, real_t *pijbm, real_t *ubfactors, 
00440          rpq_t **queues, idx_t *from, idx_t *cnum)
00441 {
00442   idx_t ncon, i, part;
00443   real_t max, tmp;
00444 
00445   ncon = graph->ncon;
00446 
00447   *from = -1;
00448   *cnum = -1;
00449 
00450   /* First determine the side and the queue, irrespective of the presence of nodes. 
00451      The side & queue is determined based on the most violated balancing constraint. */
00452   for (max=0.0, part=0; part<2; part++) {
00453     for (i=0; i<ncon; i++) {
00454       tmp = graph->pwgts[part*ncon+i]*pijbm[part*ncon+i] - ubfactors[i];
00455       /* the '=' in the test bellow is to ensure that under tight constraints
00456          the partition that is at the max is selected */
00457       if (tmp >= max) { 
00458         max   = tmp;
00459         *from = part;
00460         *cnum = i;
00461       }
00462     }
00463   }
00464 
00465 
00466   if (*from != -1) {
00467     /* in case the desired queue is empty, select a queue from the same side */
00468     if (rpqLength(queues[2*(*cnum)+(*from)]) == 0) {
00469       for (i=0; i<ncon; i++) {
00470         if (rpqLength(queues[2*i+(*from)]) > 0) {
00471           max   = graph->pwgts[(*from)*ncon+i]*pijbm[(*from)*ncon+i] - ubfactors[i];
00472           *cnum = i;
00473           break;
00474         }
00475       }
00476 
00477       for (i++; i<ncon; i++) {
00478         tmp = graph->pwgts[(*from)*ncon+i]*pijbm[(*from)*ncon+i] - ubfactors[i];
00479         if (tmp > max && rpqLength(queues[2*i+(*from)]) > 0) {
00480           max   = tmp;
00481           *cnum = i;
00482         }
00483       }
00484     }
00485 
00486     /*
00487     printf("Selected1 %"PRIDX"(%"PRIDX") -> %"PRIDX" [%5"PRREAL"]\n", 
00488         *from, *cnum, rpqLength(queues[2*(*cnum)+(*from)]), max); 
00489     */
00490   }
00491   else {
00492     /* the partitioning does not violate balancing constraints, in which case select 
00493        a queue based on cut criteria */
00494     for (part=0; part<2; part++) {
00495       for (i=0; i<ncon; i++) {
00496         if (rpqLength(queues[2*i+part]) > 0 && 
00497             (*from == -1 || rpqSeeTopKey(queues[2*i+part]) > max)) {
00498           max   = rpqSeeTopKey(queues[2*i+part]); 
00499           *from = part;
00500           *cnum = i;
00501         }
00502       }
00503     }
00504     /*
00505     printf("Selected2 %"PRIDX"(%"PRIDX") -> %"PRIDX"\n", 
00506         *from, *cnum, rpqLength(queues[2*(*cnum)+(*from)]), max); 
00507     */
00508   }
00509 }
00510 
00511 
00512 /*************************************************************************/
00514 /*************************************************************************/ 
00515 void Print2WayRefineStats(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00516          real_t deltabal, idx_t mincutorder)
00517 {
00518   int i;
00519 
00520   if (mincutorder == -2) {
00521     printf("Parts: ");
00522     printf("Nv-Nb[%5"PRIDX" %5"PRIDX"] ICut: %6"PRIDX, 
00523         graph->nvtxs, graph->nbnd, graph->mincut);
00524     printf(" [");
00525     for (i=0; i<graph->ncon; i++)
00526       printf("(%.3"PRREAL" %.3"PRREAL" T:%.3"PRREAL" %.3"PRREAL")", 
00527           graph->pwgts[i]*graph->invtvwgt[i], 
00528           graph->pwgts[graph->ncon+i]*graph->invtvwgt[i],
00529           ntpwgts[i], ntpwgts[graph->ncon+i]);
00530     printf("] LB: %.3"PRREAL"(%+.3"PRREAL")\n", 
00531         ComputeLoadImbalance(graph, 2, ctrl->pijbm), deltabal);
00532   }
00533   else {
00534     printf("\tMincut: %6"PRIDX" at %5"PRIDX" NBND %6"PRIDX" NPwgts: [", 
00535         graph->mincut, mincutorder, graph->nbnd);
00536     for (i=0; i<graph->ncon; i++)
00537       printf("(%.3"PRREAL" %.3"PRREAL")", 
00538           graph->pwgts[i]*graph->invtvwgt[i], graph->pwgts[graph->ncon+i]*graph->invtvwgt[i]);
00539     printf("] LB: %.3"PRREAL"(%+.3"PRREAL")\n", 
00540         ComputeLoadImbalance(graph, 2, ctrl->pijbm), deltabal);
00541   }
00542 }
00543
libs/ck-libs/metis/libmetis/fm.c
