Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * mpmetis.c
00005  *
00006  * This file contains the top level routines for the multilevel recursive
00007  * bisection algorithm PMETIS.
00008  *
00009  * Started 7/24/97
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 
00019 
00020 /*************************************************************************
00021 * This function is the entry point for PWMETIS that accepts exact weights
00022 * for the target partitions
00023 **************************************************************************/
00024 void METIS_mCPartGraphRecursive(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
00025        idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
00026        int *options, int *edgecut, idxtype *part)
00027 {
00028   int i, j;
00029   GraphType graph;
00030   CtrlType ctrl;
00031 
00032   if (*numflag == 1)
00033     Change2CNumbering(*nvtxs, xadj, adjncy);
00034 
00035   SetUpGraph(&graph, OP_PMETIS, *nvtxs, *ncon, xadj, adjncy, vwgt, adjwgt, *wgtflag);
00036 
00037   if (options[0] == 0) {  /* Use the default parameters */
00038     ctrl.CType  = McPMETIS_CTYPE;
00039     ctrl.IType  = McPMETIS_ITYPE;
00040     ctrl.RType  = McPMETIS_RTYPE;
00041     ctrl.dbglvl = McPMETIS_DBGLVL;
00042   }
00043   else {
00044     ctrl.CType  = options[OPTION_CTYPE];
00045     ctrl.IType  = options[OPTION_ITYPE];
00046     ctrl.RType  = options[OPTION_RTYPE];
00047     ctrl.dbglvl = options[OPTION_DBGLVL];
00048   }
00049   ctrl.optype = OP_PMETIS;
00050   ctrl.CoarsenTo = 100;
00051 
00052   ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
00053 
00054   InitRandom(-1);
00055 
00056   AllocateWorkSpace(&ctrl, &graph, *nparts);
00057 
00058   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00059   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00060 
00061   *edgecut = MCMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, 1.000, 0);
00062 
00063   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00064   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00065 
00066   FreeWorkSpace(&ctrl, &graph);
00067 
00068   if (*numflag == 1)
00069     Change2FNumbering(*nvtxs, xadj, adjncy, part);
00070 }
00071 
00072 
00073 
00074 /*************************************************************************
00075 * This function is the entry point for PWMETIS that accepts exact weights
00076 * for the target partitions
00077 **************************************************************************/
00078 void METIS_mCHPartGraphRecursive(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
00079        idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
00080        floattype *ubvec, int *options, int *edgecut, idxtype *part)
00081 {
00082   int i, j;
00083   GraphType graph;
00084   CtrlType ctrl;
00085   floattype *myubvec;
00086 
00087   if (*numflag == 1)
00088     Change2CNumbering(*nvtxs, xadj, adjncy);
00089 
00090   SetUpGraph(&graph, OP_PMETIS, *nvtxs, *ncon, xadj, adjncy, vwgt, adjwgt, *wgtflag);
00091 
00092   if (options[0] == 0) {  /* Use the default parameters */
00093     ctrl.CType = PMETIS_CTYPE;
00094     ctrl.IType = PMETIS_ITYPE;
00095     ctrl.RType = PMETIS_RTYPE;
00096     ctrl.dbglvl = PMETIS_DBGLVL;
00097   }
00098   else {
00099     ctrl.CType = options[OPTION_CTYPE];
00100     ctrl.IType = options[OPTION_ITYPE];
00101     ctrl.RType = options[OPTION_RTYPE];
00102     ctrl.dbglvl = options[OPTION_DBGLVL];
00103   }
00104   ctrl.optype = OP_PMETIS;
00105   ctrl.CoarsenTo = 100;
00106 
00107   ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
00108 
00109   myubvec = fmalloc(*ncon, "PWMETIS: mytpwgts");
00110   scopy(*ncon, ubvec, myubvec);
00111 
00112   InitRandom(-1);
00113 
00114   AllocateWorkSpace(&ctrl, &graph, *nparts);
00115 
00116   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00117   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00118 
00119   *edgecut = MCHMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, myubvec, 0);
00120 
00121   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00122   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00123 
00124   FreeWorkSpace(&ctrl, &graph);
00125   GKfree(&myubvec, LTERM);
00126 
00127   if (*numflag == 1)
00128     Change2FNumbering(*nvtxs, xadj, adjncy, part);
00129 }
00130 
00131 
00132 
00133 /*************************************************************************
00134 * This function is the entry point for PWMETIS that accepts exact weights
00135 * for the target partitions
00136 **************************************************************************/
00137 void METIS_mCPartGraphRecursiveInternal(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
00138        floattype *nvwgt, idxtype *adjwgt, int *nparts, int *options, int *edgecut, idxtype *part)
00139 {
00140   int i, j;
00141   GraphType graph;
00142   CtrlType ctrl;
00143 
00144   SetUpGraph2(&graph, *nvtxs, *ncon, xadj, adjncy, nvwgt, adjwgt);
00145 
00146   if (options[0] == 0) {  /* Use the default parameters */
00147     ctrl.CType = PMETIS_CTYPE;
00148     ctrl.IType = PMETIS_ITYPE;
00149     ctrl.RType = PMETIS_RTYPE;
00150     ctrl.dbglvl = PMETIS_DBGLVL;
00151   }
00152   else {
00153     ctrl.CType = options[OPTION_CTYPE];
00154     ctrl.IType = options[OPTION_ITYPE];
00155     ctrl.RType = options[OPTION_RTYPE];
00156     ctrl.dbglvl = options[OPTION_DBGLVL];
00157   }
00158   ctrl.optype = OP_PMETIS;
00159   ctrl.CoarsenTo = 100;
00160 
00161   ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
00162 
00163   InitRandom(-1);
00164 
00165   AllocateWorkSpace(&ctrl, &graph, *nparts);
00166 
00167   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00168   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00169 
00170   *edgecut = MCMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, 1.000, 0);
00171 
00172   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00173   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00174 
00175   FreeWorkSpace(&ctrl, &graph);
00176 
00177 }
00178 
00179 
00180 /*************************************************************************
00181 * This function is the entry point for PWMETIS that accepts exact weights
00182 * for the target partitions
00183 **************************************************************************/
00184 void METIS_mCHPartGraphRecursiveInternal(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
00185        floattype *nvwgt, idxtype *adjwgt, int *nparts, floattype *ubvec, int *options, int *edgecut, 
00186        idxtype *part)
00187 {
00188   int i, j;
00189   GraphType graph;
00190   CtrlType ctrl;
00191   floattype *myubvec;
00192 
00193   SetUpGraph2(&graph, *nvtxs, *ncon, xadj, adjncy, nvwgt, adjwgt);
00194 
00195   if (options[0] == 0) {  /* Use the default parameters */
00196     ctrl.CType = PMETIS_CTYPE;
00197     ctrl.IType = PMETIS_ITYPE;
00198     ctrl.RType = PMETIS_RTYPE;
00199     ctrl.dbglvl = PMETIS_DBGLVL;
00200   }
00201   else {
00202     ctrl.CType = options[OPTION_CTYPE];
00203     ctrl.IType = options[OPTION_ITYPE];
00204     ctrl.RType = options[OPTION_RTYPE];
00205     ctrl.dbglvl = options[OPTION_DBGLVL];
00206   }
00207   ctrl.optype = OP_PMETIS;
00208   ctrl.CoarsenTo = 100;
00209 
00210   ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
00211 
00212   myubvec = fmalloc(*ncon, "PWMETIS: mytpwgts");
00213   scopy(*ncon, ubvec, myubvec);
00214 
00215   InitRandom(-1);
00216 
00217   AllocateWorkSpace(&ctrl, &graph, *nparts);
00218 
00219   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00220   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00221 
00222   *edgecut = MCHMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, myubvec, 0);
00223 
00224   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00225   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00226 
00227   FreeWorkSpace(&ctrl, &graph);
00228   GKfree(&myubvec, LTERM);
00229 
00230 }
00231 
00232 
00233 
00234 
00235 /*************************************************************************
00236 * This function takes a graph and produces a bisection of it
00237 **************************************************************************/
00238 int MCMlevelRecursiveBisection(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, 
00239        floattype ubfactor, int fpart)
00240 {
00241   int i, j, nvtxs, ncon, cut;
00242   idxtype *label, *where;
00243   GraphType lgraph, rgraph;
00244   floattype tpwgts[2];
00245 
00246   nvtxs = graph->nvtxs;
00247   if (nvtxs == 0) {
00248     printf("\t***Cannot bisect a graph with 0 vertices!\n\t***You are trying to partition a graph into too many parts!\n");
00249     return 0;
00250   }
00251 
00252   /* Determine the weights of the partitions */
00253   tpwgts[0] = 1.0*(nparts>>1)/(1.0*nparts);
00254   tpwgts[1] = 1.0 - tpwgts[0];
00255 
00256   MCMlevelEdgeBisection(ctrl, graph, tpwgts, ubfactor);
00257   cut = graph->mincut;
00258 
00259   label = graph->label;
00260   where = graph->where;
00261   for (i=0; i<nvtxs; i++)
00262     part[label[i]] = where[i] + fpart;
00263 
00264   if (nparts > 2) 
00265     SplitGraphPart(ctrl, graph, &lgraph, &rgraph);
00266 
00267   /* Free the memory of the top level graph */
00268   GKfree(&graph->gdata, &graph->nvwgt, &graph->rdata, &graph->label, LTERM);
00269 
00270 
00271   /* Do the recursive call */
00272   if (nparts > 3) {
00273     cut += MCMlevelRecursiveBisection(ctrl, &lgraph, nparts/2, part, ubfactor, fpart);
00274     cut += MCMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, ubfactor, fpart+nparts/2);
00275   }
00276   else if (nparts == 3) {
00277     cut += MCMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, ubfactor, fpart+nparts/2);
00278     GKfree(&lgraph.gdata, &lgraph.nvwgt, &lgraph.label, LTERM);
00279   }
00280 
00281   return cut;
00282 
00283 }
00284 
00285 
00286 
00287 /*************************************************************************
00288 * This function takes a graph and produces a bisection of it
00289 **************************************************************************/
00290 int MCHMlevelRecursiveBisection(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, 
00291       floattype *ubvec, int fpart)
00292 {
00293   int i, j, nvtxs, ncon, cut;
00294   idxtype *label, *where;
00295   GraphType lgraph, rgraph;
00296   floattype tpwgts[2], *npwgts, *lubvec, *rubvec;
00297 
00298   lubvec = rubvec = NULL;
00299 
00300   nvtxs = graph->nvtxs;
00301   ncon = graph->ncon;
00302   if (nvtxs == 0) {
00303     printf("\t***Cannot bisect a graph with 0 vertices!\n\t***You are trying to partition a graph into too many parts!\n");
00304     return 0;
00305   }
00306 
00307   /* Determine the weights of the partitions */
00308   tpwgts[0] = 1.0*(nparts>>1)/(1.0*nparts);
00309   tpwgts[1] = 1.0 - tpwgts[0];
00310 
00311   /* For now, relax at the coarsest level only */
00312   if (nparts == 2)
00313     MCHMlevelEdgeBisection(ctrl, graph, tpwgts, ubvec);
00314   else
00315     MCMlevelEdgeBisection(ctrl, graph, tpwgts, 1.000);
00316   cut = graph->mincut;
00317 
00318   label = graph->label;
00319   where = graph->where;
00320   for (i=0; i<nvtxs; i++)
00321     part[label[i]] = where[i] + fpart;
00322 
00323   if (nparts > 2) {
00324     /* Adjust the ubvecs before the split */
00325     npwgts = graph->npwgts;
00326     lubvec = fmalloc(ncon, "MCHMlevelRecursiveBisection");
00327     rubvec = fmalloc(ncon, "MCHMlevelRecursiveBisection");
00328 
00329     for (i=0; i<ncon; i++) {
00330       lubvec[i] = ubvec[i]*tpwgts[0]/npwgts[i];
00331       lubvec[i] = amax(lubvec[i], 1.01);
00332 
00333       rubvec[i] = ubvec[i]*tpwgts[1]/npwgts[ncon+i];
00334       rubvec[i] = amax(rubvec[i], 1.01);
00335     }
00336 
00337     SplitGraphPart(ctrl, graph, &lgraph, &rgraph);
00338   }
00339 
00340   /* Free the memory of the top level graph */
00341   GKfree(&graph->gdata, &graph->nvwgt, &graph->rdata, &graph->label, LTERM);
00342 
00343 
00344   /* Do the recursive call */
00345   if (nparts > 3) {
00346     cut += MCHMlevelRecursiveBisection(ctrl, &lgraph, nparts/2, part, lubvec, fpart);
00347     cut += MCHMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, rubvec, fpart+nparts/2);
00348   }
00349   else if (nparts == 3) {
00350     cut += MCHMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, rubvec, fpart+nparts/2);
00351     GKfree(&lgraph.gdata, &lgraph.nvwgt, &lgraph.label, LTERM);
00352   }
00353 
00354   GKfree(&lubvec, &rubvec, LTERM);
00355 
00356   return cut;
00357 
00358 }
00359 
00360 
00361 
00362 
00363 /*************************************************************************
00364 * This function performs multilevel bisection
00365 **************************************************************************/
00366 void MCMlevelEdgeBisection(CtrlType *ctrl, GraphType *graph, floattype *tpwgts, floattype ubfactor)
00367 {
00368   GraphType *cgraph;
00369 
00370   cgraph = MCCoarsen2Way(ctrl, graph);
00371 
00372   MocInit2WayPartition(ctrl, cgraph, tpwgts, ubfactor);
00373 
00374   MocRefine2Way(ctrl, graph, cgraph, tpwgts, ubfactor); 
00375 
00376 }
00377 
00378 
00379 
00380 /*************************************************************************
00381 * This function performs multilevel bisection
00382 **************************************************************************/
00383 void MCHMlevelEdgeBisection(CtrlType *ctrl, GraphType *graph, floattype *tpwgts, floattype *ubvec)
00384 {
00385   int i;
00386   GraphType *cgraph;
00387 
00388 /*
00389   for (i=0; i<graph->ncon; i++)
00390     printf("%.4f ", ubvec[i]);
00391   printf("\n");
00392 */
00393 
00394   cgraph = MCCoarsen2Way(ctrl, graph);
00395 
00396   MocInit2WayPartition2(ctrl, cgraph, tpwgts, ubvec);
00397 
00398   MocRefine2Way2(ctrl, graph, cgraph, tpwgts, ubvec); 
00399 
00400 }
00401 
00402
libs/ck-libs/parmetis/METISLib/mpmetis.c
