Charm++: Charm Source Code Documentation

00001 
00013 #include "metislib.h"
00014 
00015 
00016 /*************************************************************************/
00090 /*************************************************************************/
00091 int METIS_PartGraphRecursive(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, 
00092           idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, 
00093           idx_t *nparts, real_t *tpwgts, real_t *ubvec, idx_t *options, 
00094           idx_t *objval, idx_t *part)
00095 {
00096   int sigrval=0, renumber=0;
00097   graph_t *graph;
00098   ctrl_t *ctrl;
00099 
00100   /* set up malloc cleaning code and signal catchers */
00101   if (!gk_malloc_init()) 
00102     return METIS_ERROR_MEMORY;
00103 
00104   gk_sigtrap();
00105 
00106   if ((sigrval = gk_sigcatch()) != 0) 
00107     goto SIGTHROW;
00108 
00109 
00110   /* set up the run parameters */
00111   ctrl = SetupCtrl(METIS_OP_PMETIS, options, *ncon, *nparts, tpwgts, ubvec);
00112   if (!ctrl) {
00113     gk_siguntrap();
00114     return METIS_ERROR_INPUT;
00115   }
00116 
00117   /* if required, change the numbering to 0 */
00118   if (ctrl->numflag == 1) {
00119     Change2CNumbering(*nvtxs, xadj, adjncy);
00120     renumber = 1;
00121   }
00122 
00123   /* set up the graph */
00124   graph = SetupGraph(ctrl, *nvtxs, *ncon, xadj, adjncy, vwgt, vsize, adjwgt);
00125 
00126   /* allocate workspace memory */
00127   AllocateWorkSpace(ctrl, graph);
00128 
00129   /* start the partitioning */
00130   IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
00131   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));
00132 
00133   *objval = MlevelRecursiveBisection(ctrl, graph, *nparts, part, ctrl->tpwgts, 0);
00134 
00135   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->TotalTmr));
00136   IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
00137 
00138   /* clean up */
00139   FreeCtrl(&ctrl);
00140 
00141 SIGTHROW:
00142   /* if required, change the numbering back to 1 */
00143   if (renumber)
00144     Change2FNumbering(*nvtxs, xadj, adjncy, part);
00145 
00146   gk_siguntrap();
00147   gk_malloc_cleanup(0);
00148 
00149   return metis_rcode(sigrval);
00150 }
00151 
00152 
00153 /*************************************************************************/
00156 /*************************************************************************/
00157 idx_t MlevelRecursiveBisection(ctrl_t *ctrl, graph_t *graph, idx_t nparts, 
00158           idx_t *part, real_t *tpwgts, idx_t fpart)
00159 {
00160   idx_t i, j, nvtxs, ncon, objval;
00161   idx_t *label, *where;
00162   graph_t *lgraph, *rgraph;
00163   real_t wsum, *tpwgts2;
00164 
00165   if ((nvtxs = graph->nvtxs) == 0) {
00166     printf("\t***Cannot bisect a graph with 0 vertices!\n"
00167            "\t***You are trying to partition a graph into too many parts!\n");
00168     return 0;
00169   }
00170 
00171   ncon = graph->ncon;
00172 
00173   /* determine the weights of the two partitions as a function of the weight of the
00174      target partition weights */
00175   WCOREPUSH;
00176   tpwgts2 = rwspacemalloc(ctrl, 2*ncon);
00177   for (i=0; i<ncon; i++) {
00178     tpwgts2[i]      = rsum((nparts>>1), tpwgts+i, ncon);
00179     tpwgts2[ncon+i] = 1.0 - tpwgts2[i];
00180   }
00181 
00182   /* perform the bisection */
00183   objval = MultilevelBisect(ctrl, graph, tpwgts2);
00184 
00185   WCOREPOP;
00186 
00187   label = graph->label;
00188   where = graph->where;
00189   for (i=0; i<nvtxs; i++)
00190     part[label[i]] = where[i] + fpart;
00191 
00192   if (nparts > 2) 
00193     SplitGraphPart(ctrl, graph, &lgraph, &rgraph);
00194 
00195   /* Free the memory of the top level graph */
00196   FreeGraph(&graph);
00197 
00198   /* Scale the fractions in the tpwgts according to the true weight */
00199   for (i=0; i<ncon; i++) {
00200     wsum = rsum((nparts>>1), tpwgts+i, ncon);
00201     rscale((nparts>>1), 1.0/wsum, tpwgts+i, ncon);
00202     rscale(nparts-(nparts>>1), 1.0/(1.0-wsum), tpwgts+(nparts>>1)*ncon+i, ncon);
00203   }
00204 
00205   /* Do the recursive call */
00206   if (nparts > 3) {
00207     objval += MlevelRecursiveBisection(ctrl, lgraph, (nparts>>1), part, 
00208                tpwgts, fpart);
00209     objval += MlevelRecursiveBisection(ctrl, rgraph, nparts-(nparts>>1), part, 
00210                tpwgts+(nparts>>1)*ncon, fpart+(nparts>>1));
00211   }
00212   else if (nparts == 3) {
00213     FreeGraph(&lgraph);
00214     objval += MlevelRecursiveBisection(ctrl, rgraph, nparts-(nparts>>1), part, 
00215                tpwgts+(nparts>>1)*ncon, fpart+(nparts>>1));
00216   }
00217 
00218 
00219   return objval;
00220 }
00221 
00222 
00223 /*************************************************************************/
00225 /*************************************************************************/
00226 idx_t MultilevelBisect(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts)
00227 {
00228   idx_t i, niparts, bestobj=0, curobj=0, *bestwhere=NULL;
00229   graph_t *cgraph;
00230   real_t bestbal=0.0, curbal=0.0;
00231 
00232   Setup2WayBalMultipliers(ctrl, graph, tpwgts);
00233 
00234   WCOREPUSH;
00235 
00236   if (ctrl->ncuts > 1)
00237     bestwhere = iwspacemalloc(ctrl, graph->nvtxs);
00238 
00239   for (i=0; i<ctrl->ncuts; i++) {
00240     cgraph = CoarsenGraph(ctrl, graph);
00241 
00242     niparts = (cgraph->nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
00243     Init2WayPartition(ctrl, cgraph, tpwgts, niparts);
00244 
00245     Refine2Way(ctrl, graph, cgraph, tpwgts);
00246 
00247     curobj = graph->mincut;
00248     curbal = ComputeLoadImbalanceDiff(graph, 2, ctrl->pijbm, ctrl->ubfactors);
00249 
00250     if (i == 0  
00251         || (curbal <= 0.0005 && bestobj > curobj) 
00252         || (bestbal > 0.0005 && curbal < bestbal)) {
00253       bestobj = curobj;
00254       bestbal = curbal;
00255       if (i < ctrl->ncuts-1)
00256         icopy(graph->nvtxs, graph->where, bestwhere);
00257     }
00258 
00259     if (bestobj == 0)
00260       break;
00261 
00262     if (i < ctrl->ncuts-1)
00263       FreeRData(graph);
00264   }
00265 
00266   if (bestobj != curobj) {
00267     icopy(graph->nvtxs, bestwhere, graph->where);
00268     Compute2WayPartitionParams(ctrl, graph);
00269   }
00270 
00271   WCOREPOP;
00272 
00273   return bestobj;
00274 }
00275 
00276 
00277 /*************************************************************************/
00279 /*************************************************************************/
00280 void SplitGraphPart(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, 
00281          graph_t **r_rgraph)
00282 {
00283   idx_t i, j, k, l, istart, iend, mypart, nvtxs, ncon, snvtxs[2], snedges[2];
00284   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *label, *where, *bndptr;
00285   idx_t *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *slabel[2];
00286   idx_t *rename;
00287   idx_t *auxadjncy, *auxadjwgt;
00288   graph_t *lgraph, *rgraph;
00289 
00290   WCOREPUSH;
00291 
00292   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->SplitTmr));
00293 
00294   nvtxs   = graph->nvtxs;
00295   ncon    = graph->ncon;
00296   xadj    = graph->xadj;
00297   vwgt    = graph->vwgt;
00298   adjncy  = graph->adjncy;
00299   adjwgt  = graph->adjwgt;
00300   label   = graph->label;
00301   where   = graph->where;
00302   bndptr  = graph->bndptr;
00303 
00304   ASSERT(bndptr != NULL);
00305 
00306   rename = iwspacemalloc(ctrl, nvtxs);
00307   
00308   snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
00309   for (i=0; i<nvtxs; i++) {
00310     k = where[i];
00311     rename[i] = snvtxs[k]++;
00312     snedges[k] += xadj[i+1]-xadj[i];
00313   }
00314 
00315   lgraph      = SetupSplitGraph(graph, snvtxs[0], snedges[0]);
00316   sxadj[0]    = lgraph->xadj;
00317   svwgt[0]    = lgraph->vwgt;
00318   sadjncy[0]  = lgraph->adjncy;     
00319   sadjwgt[0]  = lgraph->adjwgt; 
00320   slabel[0]   = lgraph->label;
00321 
00322   rgraph      = SetupSplitGraph(graph, snvtxs[1], snedges[1]);
00323   sxadj[1]    = rgraph->xadj;
00324   svwgt[1]    = rgraph->vwgt;
00325   sadjncy[1]  = rgraph->adjncy;     
00326   sadjwgt[1]  = rgraph->adjwgt; 
00327   slabel[1]   = rgraph->label;
00328 
00329   snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
00330   sxadj[0][0] = sxadj[1][0] = 0;
00331   for (i=0; i<nvtxs; i++) {
00332     mypart = where[i];
00333 
00334     istart = xadj[i];
00335     iend = xadj[i+1];
00336     if (bndptr[i] == -1) { /* This is an interior vertex */
00337       auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
00338       auxadjwgt = sadjwgt[mypart] + snedges[mypart] - istart;
00339       for(j=istart; j<iend; j++) {
00340         auxadjncy[j] = adjncy[j];
00341         auxadjwgt[j] = adjwgt[j]; 
00342       }
00343       snedges[mypart] += iend-istart;
00344     }
00345     else {
00346       auxadjncy = sadjncy[mypart];
00347       auxadjwgt = sadjwgt[mypart];
00348       l = snedges[mypart];
00349       for (j=istart; j<iend; j++) {
00350         k = adjncy[j];
00351         if (where[k] == mypart) {
00352           auxadjncy[l] = k;
00353           auxadjwgt[l++] = adjwgt[j]; 
00354         }
00355       }
00356       snedges[mypart] = l;
00357     }
00358 
00359     /* copy vertex weights */
00360     for (k=0; k<ncon; k++)
00361       svwgt[mypart][snvtxs[mypart]*ncon+k] = vwgt[i*ncon+k];
00362 
00363     slabel[mypart][snvtxs[mypart]]   = label[i];
00364     sxadj[mypart][++snvtxs[mypart]]  = snedges[mypart];
00365   }
00366 
00367   for (mypart=0; mypart<2; mypart++) {
00368     iend = sxadj[mypart][snvtxs[mypart]];
00369     auxadjncy = sadjncy[mypart];
00370     for (i=0; i<iend; i++) 
00371       auxadjncy[i] = rename[auxadjncy[i]];
00372   }
00373 
00374   lgraph->nedges = snedges[0];
00375   rgraph->nedges = snedges[1];
00376 
00377   SetupGraph_tvwgt(lgraph);
00378   SetupGraph_tvwgt(rgraph);
00379 
00380   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->SplitTmr));
00381 
00382   *r_lgraph = lgraph;
00383   *r_rgraph = rgraph;
00384 
00385   WCOREPOP;
00386 }
00387
libs/ck-libs/metis/libmetis/pmetis.c
