Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * kmetis.c
00005  *
00006  * This file contains the top level routines for the multilevel k-way partitioning
00007  * algorithm KMETIS.
00008  *
00009  * Started 7/28/97
00010  * George
00011  *
00012  * $Id$
00013  *
00014  */
00015 
00016 #include <metis.h>
00017 
00018 
00019 /*************************************************************************
00020 * This function is the entry point for KMETIS
00021 **************************************************************************/
00022 void METIS_PartGraphKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00023                          idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
00024                          int *options, int *edgecut, idxtype *part)
00025 {
00026   int i;
00027   floattype *tpwgts;
00028 
00029   tpwgts = fmalloc(*nparts, "KMETIS: tpwgts");
00030   for (i=0; i<*nparts; i++) 
00031     tpwgts[i] = 1.0/(1.0*(*nparts));
00032 
00033   METIS_WPartGraphKway(nvtxs, xadj, adjncy, vwgt, adjwgt, wgtflag, numflag, nparts, 
00034                        tpwgts, options, edgecut, part);
00035 
00036   free(tpwgts);
00037 }
00038 
00039 
00040 /*************************************************************************
00041 * This function is the entry point for KWMETIS
00042 **************************************************************************/
00043 void METIS_WPartGraphKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
00044                           idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
00045                           floattype *tpwgts, int *options, int *edgecut, idxtype *part)
00046 {
00047   int i, j;
00048   GraphType graph;
00049   CtrlType ctrl;
00050 
00051   if (*numflag == 1)
00052     Change2CNumbering(*nvtxs, xadj, adjncy);
00053 
00054   SetUpGraph(&graph, OP_KMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, *wgtflag);
00055 
00056   if (options[0] == 0) {  /* Use the default parameters */
00057     ctrl.CType = KMETIS_CTYPE;
00058     ctrl.IType = KMETIS_ITYPE;
00059     ctrl.RType = KMETIS_RTYPE;
00060     ctrl.dbglvl = KMETIS_DBGLVL;
00061   }
00062   else {
00063     ctrl.CType = options[OPTION_CTYPE];
00064     ctrl.IType = options[OPTION_ITYPE];
00065     ctrl.RType = options[OPTION_RTYPE];
00066     ctrl.dbglvl = options[OPTION_DBGLVL];
00067   }
00068   ctrl.optype = OP_KMETIS;
00069   ctrl.CoarsenTo = amax((*nvtxs)/(40*log2Int(*nparts)), 20*(*nparts));
00070   ctrl.maxvwgt = 1.5*((graph.vwgt ? idxsum(*nvtxs, graph.vwgt) : (*nvtxs))/ctrl.CoarsenTo);
00071 
00072   InitRandom(-1);
00073 
00074   AllocateWorkSpace(&ctrl, &graph, *nparts);
00075 
00076   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00077   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00078 
00079   *edgecut = MlevelKWayPartitioning(&ctrl, &graph, *nparts, part, tpwgts, 1.03);
00080 
00081   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00082   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00083 
00084   FreeWorkSpace(&ctrl, &graph);
00085 
00086   if (*numflag == 1)
00087     Change2FNumbering(*nvtxs, xadj, adjncy, part);
00088 }
00089 
00090 
00091 /*************************************************************************
00092 * This function takes a graph and produces a bisection of it
00093 **************************************************************************/
00094 int MlevelKWayPartitioning(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, floattype *tpwgts, floattype ubfactor)
00095 {
00096   int i, j, nvtxs, tvwgt, tpwgts2[2];
00097   GraphType *cgraph;
00098   int wgtflag=3, numflag=0, options[10], edgecut;
00099 
00100   cgraph = Coarsen2Way(ctrl, graph);
00101 
00102   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
00103   AllocateKWayPartitionMemory(ctrl, cgraph, nparts);
00104 
00105   options[0] = 1; 
00106   options[OPTION_CTYPE] = MATCH_SHEMKWAY;
00107   options[OPTION_ITYPE] = IPART_GGPKL;
00108   options[OPTION_RTYPE] = RTYPE_FM;
00109   options[OPTION_DBGLVL] = 0;
00110 
00111   METIS_WPartGraphRecursive(&cgraph->nvtxs, cgraph->xadj, cgraph->adjncy, cgraph->vwgt, 
00112                             cgraph->adjwgt, &wgtflag, &numflag, &nparts, tpwgts, options, 
00113                             &edgecut, cgraph->where);
00114 
00115   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
00116   IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial %d-way partitioning cut: %d\n", nparts, edgecut));
00117 
00118   IFSET(ctrl->dbglvl, DBG_KWAYPINFO, ComputePartitionInfo(cgraph, nparts, cgraph->where));
00119 
00120   RefineKWay(ctrl, graph, cgraph, nparts, tpwgts, ubfactor);
00121 
00122   idxcopy(graph->nvtxs, graph->where, part);
00123 
00124   GKfree(&graph->gdata, &graph->rdata, LTERM);
00125 
00126   return graph->mincut;
00127 
00128 }
00129
libs/ck-libs/parmetis/METISLib/kmetis.c
