Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * initpart.c
00005  *
00006  * This file contains code that performs the initial partition of the
00007  * coarsest graph
00008  *
00009  * Started 7/23/97
00010  * George
00011  *
00012  */
00013 
00014 #include "metislib.h"
00015 
00016 /*************************************************************************/
00018 /*************************************************************************/
00019 void Init2WayPartition(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00020          idx_t niparts) 
00021 {
00022   mdbglvl_et dbglvl;
00023 
00024   ASSERT(graph->tvwgt[0] >= 0);
00025 
00026   dbglvl = ctrl->dbglvl;
00027   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, ctrl->dbglvl -= METIS_DBG_REFINE);
00028   IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, ctrl->dbglvl -= METIS_DBG_MOVEINFO);
00029 
00030   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
00031 
00032   switch (ctrl->iptype) {
00033     case METIS_IPTYPE_RANDOM:
00034       if (graph->ncon == 1)
00035         RandomBisection(ctrl, graph, ntpwgts, niparts);
00036       else
00037         McRandomBisection(ctrl, graph, ntpwgts, niparts);
00038       break;
00039 
00040     case METIS_IPTYPE_GROW:
00041       if (graph->nedges == 0)
00042         if (graph->ncon == 1)
00043           RandomBisection(ctrl, graph, ntpwgts, niparts);
00044         else
00045           McRandomBisection(ctrl, graph, ntpwgts, niparts);
00046       else
00047         if (graph->ncon == 1)
00048           GrowBisection(ctrl, graph, ntpwgts, niparts);
00049         else
00050           McGrowBisection(ctrl, graph, ntpwgts, niparts);
00051       break;
00052 
00053     default:
00054       gk_errexit(SIGERR, "Unknown initial partition type: %d\n", ctrl->iptype);
00055   }
00056 
00057   IFSET(ctrl->dbglvl, METIS_DBG_IPART, printf("Initial Cut: %"PRIDX"\n", graph->mincut));
00058   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
00059   ctrl->dbglvl = dbglvl;
00060 
00061 }
00062 
00063 
00064 /*************************************************************************/
00066 /*************************************************************************/
00067 void InitSeparator(ctrl_t *ctrl, graph_t *graph, idx_t niparts) 
00068 {
00069   real_t ntpwgts[2] = {0.5, 0.5};
00070   mdbglvl_et dbglvl;
00071 
00072   dbglvl = ctrl->dbglvl;
00073   IFSET(ctrl->dbglvl, METIS_DBG_REFINE, ctrl->dbglvl -= METIS_DBG_REFINE);
00074   IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, ctrl->dbglvl -= METIS_DBG_MOVEINFO);
00075 
00076   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
00077 
00078   /* this is required for the cut-based part of the refinement */
00079   Setup2WayBalMultipliers(ctrl, graph, ntpwgts);
00080 
00081   switch (ctrl->iptype) {
00082     case METIS_IPTYPE_EDGE:
00083       if (graph->nedges == 0)
00084         RandomBisection(ctrl, graph, ntpwgts, niparts);
00085       else
00086         GrowBisection(ctrl, graph, ntpwgts, niparts);
00087 
00088       Compute2WayPartitionParams(ctrl, graph);
00089       ConstructSeparator(ctrl, graph);
00090       break;
00091 
00092     case METIS_IPTYPE_NODE:
00093       GrowBisectionNode(ctrl, graph, ntpwgts, niparts);
00094       break;
00095 
00096     default:
00097       gk_errexit(SIGERR, "Unkown iptype of %"PRIDX"\n", ctrl->iptype);
00098   }
00099 
00100   IFSET(ctrl->dbglvl, METIS_DBG_IPART, printf("Initial Sep: %"PRIDX"\n", graph->mincut));
00101   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
00102 
00103   ctrl->dbglvl = dbglvl;
00104 
00105 }
00106 
00107 
00108 /*************************************************************************/
00113 /*************************************************************************/
00114 void RandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00115          idx_t niparts)
00116 {
00117   idx_t i, ii, j, k, nvtxs, pwgts[2], zeromaxpwgt, from, me, 
00118         bestcut=0, icut, mincut, inbfs;
00119   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where;
00120   idx_t *perm, *bestwhere;
00121 
00122   WCOREPUSH;
00123 
00124   nvtxs  = graph->nvtxs;
00125   xadj   = graph->xadj;
00126   vwgt   = graph->vwgt;
00127   adjncy = graph->adjncy;
00128   adjwgt = graph->adjwgt;
00129 
00130   Allocate2WayPartitionMemory(ctrl, graph);
00131   where = graph->where;
00132 
00133   bestwhere = iwspacemalloc(ctrl, nvtxs);
00134   perm      = iwspacemalloc(ctrl, nvtxs);
00135 
00136   zeromaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*ntpwgts[0];
00137 
00138   for (inbfs=0; inbfs<niparts; inbfs++) {
00139     iset(nvtxs, 1, where);
00140 
00141     if (inbfs > 0) {
00142       irandArrayPermute(nvtxs, perm, nvtxs/2, 1);
00143       pwgts[1] = graph->tvwgt[0];
00144       pwgts[0] = 0;
00145 
00146       for (ii=0; ii<nvtxs; ii++) {
00147         i = perm[ii];
00148         if (pwgts[0]+vwgt[i] < zeromaxpwgt) {
00149           where[i] = 0;
00150           pwgts[0] += vwgt[i];
00151           pwgts[1] -= vwgt[i];
00152           if (pwgts[0] > zeromaxpwgt)
00153             break;
00154         }
00155       }
00156     }
00157 
00158     /* Do some partition refinement  */
00159     Compute2WayPartitionParams(ctrl, graph);
00160     /* printf("IPART: %3"PRIDX" [%5"PRIDX" %5"PRIDX"] [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); */
00161 
00162     Balance2Way(ctrl, graph, ntpwgts);
00163     /* printf("BPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
00164 
00165     FM_2WayRefine(ctrl, graph, ntpwgts, 4);
00166     /* printf("RPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
00167 
00168     if (inbfs==0 || bestcut > graph->mincut) {
00169       bestcut = graph->mincut;
00170       icopy(nvtxs, where, bestwhere);
00171       if (bestcut == 0)
00172         break;
00173     }
00174   }
00175 
00176   graph->mincut = bestcut;
00177   icopy(nvtxs, bestwhere, where);
00178 
00179   WCOREPOP;
00180 }
00181 
00182 
00183 /*************************************************************************/
00188 /*************************************************************************/
00189 void GrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00190          idx_t niparts)
00191 {
00192   idx_t i, j, k, nvtxs, drain, nleft, first, last, 
00193         pwgts[2], oneminpwgt, onemaxpwgt, 
00194         from, me, bestcut=0, icut, mincut, inbfs;
00195   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where;
00196   idx_t *queue, *touched, *gain, *bestwhere;
00197 
00198   WCOREPUSH;
00199 
00200   nvtxs  = graph->nvtxs;
00201   xadj   = graph->xadj;
00202   vwgt   = graph->vwgt;
00203   adjncy = graph->adjncy;
00204   adjwgt = graph->adjwgt;
00205 
00206   Allocate2WayPartitionMemory(ctrl, graph);
00207   where = graph->where;
00208 
00209   bestwhere = iwspacemalloc(ctrl, nvtxs);
00210   queue     = iwspacemalloc(ctrl, nvtxs);
00211   touched   = iwspacemalloc(ctrl, nvtxs);
00212 
00213   onemaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*ntpwgts[1];
00214   oneminpwgt = (1.0/ctrl->ubfactors[0])*graph->tvwgt[0]*ntpwgts[1];
00215 
00216   for (inbfs=0; inbfs<niparts; inbfs++) {
00217     iset(nvtxs, 1, where);
00218 
00219     iset(nvtxs, 0, touched);
00220 
00221     pwgts[1] = graph->tvwgt[0];
00222     pwgts[0] = 0;
00223 
00224 
00225     queue[0] = irandInRange(nvtxs);
00226     touched[queue[0]] = 1;
00227     first = 0; 
00228     last  = 1;
00229     nleft = nvtxs-1;
00230     drain = 0;
00231 
00232     /* Start the BFS from queue to get a partition */
00233     for (;;) {
00234       if (first == last) { /* Empty. Disconnected graph! */
00235         if (nleft == 0 || drain)
00236           break;
00237 
00238         k = irandInRange(nleft);
00239         for (i=0; i<nvtxs; i++) {
00240           if (touched[i] == 0) {
00241             if (k == 0)
00242               break;
00243             else
00244               k--;
00245           }
00246         }
00247 
00248         queue[0]   = i;
00249         touched[i] = 1;
00250         first      = 0; 
00251         last       = 1;
00252         nleft--;
00253       }
00254 
00255       i = queue[first++];
00256       if (pwgts[0] > 0 && pwgts[1]-vwgt[i] < oneminpwgt) {
00257         drain = 1;
00258         continue;
00259       }
00260 
00261       where[i] = 0;
00262       INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
00263       if (pwgts[1] <= onemaxpwgt)
00264         break;
00265 
00266       drain = 0;
00267       for (j=xadj[i]; j<xadj[i+1]; j++) {
00268         k = adjncy[j];
00269         if (touched[k] == 0) {
00270           queue[last++] = k;
00271           touched[k] = 1;
00272           nleft--;
00273         }
00274       }
00275     }
00276 
00277     /* Check to see if we hit any bad limiting cases */
00278     if (pwgts[1] == 0) 
00279       where[irandInRange(nvtxs)] = 1;
00280     if (pwgts[0] == 0) 
00281       where[irandInRange(nvtxs)] = 0;
00282 
00283     /*************************************************************
00284     * Do some partition refinement 
00285     **************************************************************/
00286     Compute2WayPartitionParams(ctrl, graph);
00287     /*
00288     printf("IPART: %3"PRIDX" [%5"PRIDX" %5"PRIDX"] [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", 
00289         graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); 
00290     */
00291 
00292     Balance2Way(ctrl, graph, ntpwgts);
00293     /*
00294     printf("BPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0],
00295         graph->pwgts[1], graph->mincut); 
00296     */
00297 
00298     FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
00299     /*
00300     printf("RPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0], 
00301         graph->pwgts[1], graph->mincut);
00302     */
00303 
00304     if (inbfs == 0 || bestcut > graph->mincut) {
00305       bestcut = graph->mincut;
00306       icopy(nvtxs, where, bestwhere);
00307       if (bestcut == 0)
00308         break;
00309     }
00310   }
00311 
00312   graph->mincut = bestcut;
00313   icopy(nvtxs, bestwhere, where);
00314 
00315   WCOREPOP;
00316 }
00317 
00318 
00319 /*************************************************************************/
00324 /**************************************************************************/
00325 void McRandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00326          idx_t niparts)
00327 {
00328   idx_t i, ii, j, k, nvtxs, ncon, from, bestcut=0, mincut, inbfs, qnum;
00329   idx_t *bestwhere, *where, *perm, *counts;
00330   idx_t *vwgt;
00331 
00332   WCOREPUSH;
00333 
00334   nvtxs = graph->nvtxs;
00335   ncon  = graph->ncon;
00336   vwgt  = graph->vwgt;
00337 
00338   Allocate2WayPartitionMemory(ctrl, graph);
00339   where = graph->where;
00340 
00341   bestwhere = iwspacemalloc(ctrl, nvtxs);
00342   perm      = iwspacemalloc(ctrl, nvtxs);
00343   counts    = iwspacemalloc(ctrl, ncon);
00344 
00345   for (inbfs=0; inbfs<2*niparts; inbfs++) {
00346     irandArrayPermute(nvtxs, perm, nvtxs/2, 1);
00347     iset(ncon, 0, counts);
00348 
00349     /* partition by spliting the queues randomly */
00350     for (ii=0; ii<nvtxs; ii++) {
00351       i        = perm[ii];
00352       qnum     = iargmax(ncon, vwgt+i*ncon);
00353       where[i] = (counts[qnum]++)%2;
00354     }
00355 
00356     Compute2WayPartitionParams(ctrl, graph);
00357 
00358     FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
00359     Balance2Way(ctrl, graph, ntpwgts);
00360     FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
00361     Balance2Way(ctrl, graph, ntpwgts);
00362     FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
00363 
00364     if (inbfs == 0 || bestcut >= graph->mincut) {
00365       bestcut = graph->mincut;
00366       icopy(nvtxs, where, bestwhere);
00367       if (bestcut == 0)
00368         break;
00369     }
00370   }
00371 
00372   graph->mincut = bestcut;
00373   icopy(nvtxs, bestwhere, where);
00374 
00375   WCOREPOP;
00376 }
00377 
00378 
00379 /*************************************************************************/
00384 /*************************************************************************/
00385 void McGrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00386          idx_t niparts)
00387 {
00388   idx_t i, j, k, nvtxs, ncon, from, bestcut=0, mincut, inbfs;
00389   idx_t *bestwhere, *where;
00390 
00391   WCOREPUSH;
00392 
00393   nvtxs = graph->nvtxs;
00394 
00395   Allocate2WayPartitionMemory(ctrl, graph);
00396   where = graph->where;
00397 
00398   bestwhere = iwspacemalloc(ctrl, nvtxs);
00399 
00400   for (inbfs=0; inbfs<2*niparts; inbfs++) {
00401     iset(nvtxs, 1, where);
00402     where[irandInRange(nvtxs)] = 0;
00403 
00404     Compute2WayPartitionParams(ctrl, graph);
00405 
00406     Balance2Way(ctrl, graph, ntpwgts);
00407     FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
00408     Balance2Way(ctrl, graph, ntpwgts);
00409     FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
00410 
00411     if (inbfs == 0 || bestcut >= graph->mincut) {
00412       bestcut = graph->mincut;
00413       icopy(nvtxs, where, bestwhere);
00414       if (bestcut == 0)
00415         break;
00416     }
00417   }
00418 
00419   graph->mincut = bestcut;
00420   icopy(nvtxs, bestwhere, where);
00421 
00422   WCOREPOP;
00423 }
00424 
00425 
00426 /*************************************************************************/
00427 /* This function takes a graph and produces a tri-section into left, right,
00428    and separator using a region growing algorithm. The resulting separator
00429    is refined using node FM.
00430    The resulting partition is returned in graph->where.
00431 */
00432 /**************************************************************************/
00433 void GrowBisectionNode(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00434          idx_t niparts)
00435 {
00436   idx_t i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], oneminpwgt, 
00437         onemaxpwgt, from, me, bestcut=0, icut, mincut, inbfs;
00438   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *bndind;
00439   idx_t *queue, *touched, *gain, *bestwhere;
00440 
00441   WCOREPUSH;
00442 
00443   nvtxs  = graph->nvtxs;
00444   xadj   = graph->xadj;
00445   vwgt   = graph->vwgt;
00446   adjncy = graph->adjncy;
00447   adjwgt = graph->adjwgt;
00448 
00449   bestwhere = iwspacemalloc(ctrl, nvtxs);
00450   queue     = iwspacemalloc(ctrl, nvtxs);
00451   touched   = iwspacemalloc(ctrl, nvtxs);
00452 
00453   onemaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*0.5;
00454   oneminpwgt = (1.0/ctrl->ubfactors[0])*graph->tvwgt[0]*0.5;
00455 
00456 
00457   /* Allocate refinement memory. Allocate sufficient memory for both edge and node */
00458   graph->pwgts  = imalloc(3, "GrowBisectionNode: pwgts");
00459   graph->where  = imalloc(nvtxs, "GrowBisectionNode: where");
00460   graph->bndptr = imalloc(nvtxs, "GrowBisectionNode: bndptr");
00461   graph->bndind = imalloc(nvtxs, "GrowBisectionNode: bndind");
00462   graph->id     = imalloc(nvtxs, "GrowBisectionNode: id");
00463   graph->ed     = imalloc(nvtxs, "GrowBisectionNode: ed");
00464   graph->nrinfo = (nrinfo_t *)gk_malloc(nvtxs*sizeof(nrinfo_t), "GrowBisectionNode: nrinfo");
00465   
00466   where  = graph->where;
00467   bndind = graph->bndind;
00468 
00469   for (inbfs=0; inbfs<niparts; inbfs++) {
00470     iset(nvtxs, 1, where);
00471     iset(nvtxs, 0, touched);
00472 
00473     pwgts[1] = graph->tvwgt[0];
00474     pwgts[0] = 0;
00475 
00476     queue[0] = irandInRange(nvtxs);
00477     touched[queue[0]] = 1;
00478     first = 0; last = 1;
00479     nleft = nvtxs-1;
00480     drain = 0;
00481 
00482     /* Start the BFS from queue to get a partition */
00483     for (;;) {
00484       if (first == last) { /* Empty. Disconnected graph! */
00485         if (nleft == 0 || drain)
00486           break;
00487   
00488         k = irandInRange(nleft);
00489         for (i=0; i<nvtxs; i++) { /* select the kth untouched vertex */
00490           if (touched[i] == 0) {
00491             if (k == 0)
00492               break;
00493             else
00494               k--;
00495           }
00496         }
00497 
00498         queue[0]   = i;
00499         touched[i] = 1;
00500         first      = 0; 
00501         last       = 1;
00502         nleft--;
00503       }
00504 
00505       i = queue[first++];
00506       if (pwgts[1]-vwgt[i] < oneminpwgt) {
00507         drain = 1;
00508         continue;
00509       }
00510 
00511       where[i] = 0;
00512       INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
00513       if (pwgts[1] <= onemaxpwgt)
00514         break;
00515 
00516       drain = 0;
00517       for (j=xadj[i]; j<xadj[i+1]; j++) {
00518         k = adjncy[j];
00519         if (touched[k] == 0) {
00520           queue[last++] = k;
00521           touched[k] = 1;
00522           nleft--;
00523         }
00524       }
00525     }
00526 
00527     /*************************************************************
00528     * Do some partition refinement 
00529     **************************************************************/
00530     Compute2WayPartitionParams(ctrl, graph);
00531     Balance2Way(ctrl, graph, ntpwgts);
00532     FM_2WayRefine(ctrl, graph, ntpwgts, 4);
00533 
00534     /* Construct and refine the vertex separator */
00535     for (i=0; i<graph->nbnd; i++) {
00536       j = bndind[i];
00537       if (xadj[j+1]-xadj[j] > 0) /* ignore islands */
00538         where[j] = 2;
00539     }
00540 
00541     Compute2WayNodePartitionParams(ctrl, graph); 
00542     FM_2WayNodeRefine2Sided(ctrl, graph, 1);
00543     FM_2WayNodeRefine1Sided(ctrl, graph, 4);
00544 
00545     /*
00546     printf("ISep: [%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"] %"PRIDX"\n", 
00547         inbfs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut); 
00548     */
00549     
00550     if (inbfs == 0 || bestcut > graph->mincut) {
00551       bestcut = graph->mincut;
00552       icopy(nvtxs, where, bestwhere);
00553     }
00554   }
00555 
00556   graph->mincut = bestcut;
00557   icopy(nvtxs, bestwhere, where);
00558 
00559   WCOREPOP;
00560 }
00561 
00562 
00563 /*************************************************************************/
00564 /* This function takes a graph and produces a tri-section into left, right,
00565    and separator using a region growing algorithm. The resulting separator
00566    is refined using node FM.
00567    The resulting partition is returned in graph->where.
00568 */
00569 /**************************************************************************/
00570 void GrowBisectionNode2(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00571          idx_t niparts)
00572 {
00573   idx_t i, j, k, nvtxs, bestcut=0, mincut, inbfs;
00574   idx_t *xadj, *where, *bndind, *bestwhere;
00575 
00576   WCOREPUSH;
00577 
00578   nvtxs  = graph->nvtxs;
00579   xadj   = graph->xadj;
00580 
00581   /* Allocate refinement memory. Allocate sufficient memory for both edge and node */
00582   graph->pwgts  = imalloc(3, "GrowBisectionNode: pwgts");
00583   graph->where  = imalloc(nvtxs, "GrowBisectionNode: where");
00584   graph->bndptr = imalloc(nvtxs, "GrowBisectionNode: bndptr");
00585   graph->bndind = imalloc(nvtxs, "GrowBisectionNode: bndind");
00586   graph->id     = imalloc(nvtxs, "GrowBisectionNode: id");
00587   graph->ed     = imalloc(nvtxs, "GrowBisectionNode: ed");
00588   graph->nrinfo = (nrinfo_t *)gk_malloc(nvtxs*sizeof(nrinfo_t), "GrowBisectionNode: nrinfo");
00589   
00590   bestwhere = iwspacemalloc(ctrl, nvtxs);
00591 
00592   where  = graph->where;
00593   bndind = graph->bndind;
00594 
00595   for (inbfs=0; inbfs<niparts; inbfs++) {
00596     iset(nvtxs, 1, where);
00597     if (inbfs > 0)
00598       where[irandInRange(nvtxs)] = 0;
00599 
00600     Compute2WayPartitionParams(ctrl, graph);
00601     General2WayBalance(ctrl, graph, ntpwgts);
00602     FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
00603 
00604     /* Construct and refine the vertex separator */
00605     for (i=0; i<graph->nbnd; i++) {
00606       j = bndind[i];
00607       if (xadj[j+1]-xadj[j] > 0) /* ignore islands */
00608         where[j] = 2;
00609     }
00610 
00611     Compute2WayNodePartitionParams(ctrl, graph); 
00612     FM_2WayNodeRefine2Sided(ctrl, graph, 4);
00613 
00614     /*
00615     printf("ISep: [%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"] %"PRIDX"\n", 
00616         inbfs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut); 
00617     */
00618 
00619     if (inbfs == 0 || bestcut > graph->mincut) {
00620       bestcut = graph->mincut;
00621       icopy(nvtxs, where, bestwhere);
00622     }
00623   }
00624 
00625   graph->mincut = bestcut;
00626   icopy(nvtxs, bestwhere, where);
00627 
00628   WCOREPOP;
00629 }
00630
libs/ck-libs/metis/libmetis/initpart.c
