Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * ometis.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 * This function is the entry point for OEMETIS
00021 **************************************************************************/
00022 void METIS_EdgeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options, 
00023                   idxtype *perm, idxtype *iperm) 
00024 {
00025   int i, j;
00026   GraphType graph;
00027   CtrlType ctrl;
00028 
00029   if (*numflag == 1)
00030     Change2CNumbering(*nvtxs, xadj, adjncy);
00031 
00032   SetUpGraph(&graph, OP_OEMETIS, *nvtxs, 1, xadj, adjncy, NULL, NULL, 0);
00033 
00034   if (options[0] == 0) {  /* Use the default parameters */
00035     ctrl.CType = OEMETIS_CTYPE;
00036     ctrl.IType = OEMETIS_ITYPE;
00037     ctrl.RType = OEMETIS_RTYPE;
00038     ctrl.dbglvl = OEMETIS_DBGLVL;
00039   }
00040   else {
00041     ctrl.CType = options[OPTION_CTYPE];
00042     ctrl.IType = options[OPTION_ITYPE];
00043     ctrl.RType = options[OPTION_RTYPE];
00044     ctrl.dbglvl = options[OPTION_DBGLVL];
00045   }
00046   ctrl.oflags  = 0;
00047   ctrl.pfactor = -1;
00048   ctrl.nseps   = 1;
00049 
00050   ctrl.optype = OP_OEMETIS;
00051   ctrl.CoarsenTo = 20;
00052   ctrl.maxvwgt = 1.5*(idxsum(*nvtxs, graph.vwgt)/ctrl.CoarsenTo);
00053 
00054   InitRandom(-1);
00055 
00056   AllocateWorkSpace(&ctrl, &graph, 2);
00057 
00058   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00059   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00060 
00061   MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, *nvtxs);
00062 
00063   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00064   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00065 
00066   for (i=0; i<*nvtxs; i++)
00067     perm[iperm[i]] = i;
00068 
00069   FreeWorkSpace(&ctrl, &graph);
00070 
00071   if (*numflag == 1)
00072     Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
00073 }
00074 
00075 
00076 /*************************************************************************
00077 * This function is the entry point for ONCMETIS
00078 **************************************************************************/
00079 void METIS_NodeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options, 
00080                   idxtype *perm, idxtype *iperm) 
00081 {
00082   int i, ii, j, l, wflag, nflag;
00083   GraphType graph;
00084   CtrlType ctrl;
00085   idxtype *cptr, *cind, *piperm;
00086 
00087   if (*numflag == 1)
00088     Change2CNumbering(*nvtxs, xadj, adjncy);
00089 
00090   if (options[0] == 0) {  /* Use the default parameters */
00091     ctrl.CType   = ONMETIS_CTYPE;
00092     ctrl.IType   = ONMETIS_ITYPE;
00093     ctrl.RType   = ONMETIS_RTYPE;
00094     ctrl.dbglvl  = ONMETIS_DBGLVL;
00095     ctrl.oflags  = ONMETIS_OFLAGS;
00096     ctrl.pfactor = ONMETIS_PFACTOR;
00097     ctrl.nseps   = ONMETIS_NSEPS;
00098   }
00099   else {
00100     ctrl.CType   = options[OPTION_CTYPE];
00101     ctrl.IType   = options[OPTION_ITYPE];
00102     ctrl.RType   = options[OPTION_RTYPE];
00103     ctrl.dbglvl  = options[OPTION_DBGLVL];
00104     ctrl.oflags  = options[OPTION_OFLAGS];
00105     ctrl.pfactor = options[OPTION_PFACTOR];
00106     ctrl.nseps   = options[OPTION_NSEPS];
00107   }
00108   if (ctrl.nseps < 1)
00109     ctrl.nseps = 1;
00110 
00111   ctrl.optype = OP_ONMETIS;
00112   ctrl.CoarsenTo = 100;
00113 
00114   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00115   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00116 
00117   InitRandom(-1);
00118 
00119   if (ctrl.pfactor > 0) { 
00120     /*============================================================
00121     * Prune the dense columns
00122     ==============================================================*/
00123     piperm = idxmalloc(*nvtxs, "ONMETIS: piperm");
00124 
00125     PruneGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, piperm, (floattype)(0.1*ctrl.pfactor));
00126   }
00127   else if (ctrl.oflags&OFLAG_COMPRESS) {
00128     /*============================================================
00129     * Compress the graph 
00130     ==============================================================*/
00131     cptr = idxmalloc(*nvtxs+1, "ONMETIS: cptr");
00132     cind = idxmalloc(*nvtxs, "ONMETIS: cind");
00133 
00134     CompressGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, cptr, cind);
00135 
00136     if (graph.nvtxs >= COMPRESSION_FRACTION*(*nvtxs)) {
00137       ctrl.oflags--; /* We actually performed no compression */
00138       GKfree(&cptr, &cind, LTERM);
00139     }
00140     else if (2*graph.nvtxs < *nvtxs && ctrl.nseps == 1)
00141       ctrl.nseps = 2;
00142   }
00143   else {
00144     SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, NULL, NULL, 0);
00145   }
00146 
00147 
00148   /*=============================================================
00149   * Do the nested dissection ordering 
00150   --=============================================================*/
00151   ctrl.maxvwgt = 1.5*(idxsum(graph.nvtxs, graph.vwgt)/ctrl.CoarsenTo);
00152   AllocateWorkSpace(&ctrl, &graph, 2);
00153 
00154   if (ctrl.oflags&OFLAG_CCMP) 
00155     MlevelNestedDissectionCC(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, graph.nvtxs);
00156   else
00157     MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, graph.nvtxs);
00158 
00159   FreeWorkSpace(&ctrl, &graph);
00160 
00161   if (ctrl.pfactor > 0) { /* Order any prunned vertices */
00162     if (graph.nvtxs < *nvtxs) { 
00163       idxcopy(graph.nvtxs, iperm, perm);  /* Use perm as an auxiliary array */
00164       for (i=0; i<graph.nvtxs; i++)
00165         iperm[piperm[i]] = perm[i];
00166       for (i=graph.nvtxs; i<*nvtxs; i++)
00167         iperm[piperm[i]] = i;
00168     }
00169 
00170     GKfree(&piperm, LTERM);
00171   }
00172   else if (ctrl.oflags&OFLAG_COMPRESS) { /* Uncompress the ordering */
00173     if (graph.nvtxs < COMPRESSION_FRACTION*(*nvtxs)) { 
00174       /* construct perm from iperm */
00175       for (i=0; i<graph.nvtxs; i++)
00176         perm[iperm[i]] = i; 
00177       for (l=ii=0; ii<graph.nvtxs; ii++) {
00178         i = perm[ii];
00179         for (j=cptr[i]; j<cptr[i+1]; j++)
00180           iperm[cind[j]] = l++;
00181       }
00182     }
00183 
00184     GKfree(&cptr, &cind, LTERM);
00185   }
00186 
00187 
00188   for (i=0; i<*nvtxs; i++)
00189     perm[iperm[i]] = i;
00190 
00191   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00192   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00193 
00194   if (*numflag == 1)
00195     Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
00196 
00197 }
00198 
00199 
00200 /*************************************************************************
00201 * This function is the entry point for ONWMETIS. It requires weights on the
00202 * vertices. It is for the case that the matrix has been pre-compressed.
00203 **************************************************************************/
00204 void METIS_NodeWND(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, int *numflag, 
00205                    int *options, idxtype *perm, idxtype *iperm) 
00206 {
00207   int i, j, tvwgt;
00208   GraphType graph;
00209   CtrlType ctrl;
00210 
00211   if (*numflag == 1)
00212     Change2CNumbering(*nvtxs, xadj, adjncy);
00213 
00214   SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, NULL, 2);
00215 
00216   if (options[0] == 0) {  /* Use the default parameters */
00217     ctrl.CType = ONMETIS_CTYPE;
00218     ctrl.IType = ONMETIS_ITYPE;
00219     ctrl.RType = ONMETIS_RTYPE;
00220     ctrl.dbglvl = ONMETIS_DBGLVL;
00221   }
00222   else {
00223     ctrl.CType = options[OPTION_CTYPE];
00224     ctrl.IType = options[OPTION_ITYPE];
00225     ctrl.RType = options[OPTION_RTYPE];
00226     ctrl.dbglvl = options[OPTION_DBGLVL];
00227   }
00228 
00229   ctrl.oflags  = OFLAG_COMPRESS;
00230   ctrl.pfactor = 0;
00231   ctrl.nseps = 2;
00232   ctrl.optype = OP_ONMETIS;
00233   ctrl.CoarsenTo = 100;
00234   ctrl.maxvwgt = 1.5*(idxsum(*nvtxs, graph.vwgt)/ctrl.CoarsenTo);
00235 
00236   InitRandom(-1);
00237 
00238   AllocateWorkSpace(&ctrl, &graph, 2);
00239 
00240   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00241   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00242 
00243   MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, *nvtxs);
00244 
00245   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00246   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
00247 
00248   for (i=0; i<*nvtxs; i++)
00249     perm[iperm[i]] = i;
00250 
00251   FreeWorkSpace(&ctrl, &graph);
00252 
00253   if (*numflag == 1)
00254     Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
00255 }
00256 
00257 
00258 
00259 
00260 /*************************************************************************
00261 * This function takes a graph and produces a bisection of it
00262 **************************************************************************/
00263 void MlevelNestedDissection(CtrlType *ctrl, GraphType *graph, idxtype *order, floattype ubfactor, int lastvtx)
00264 {
00265   int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2];
00266   idxtype *label, *bndind;
00267   GraphType lgraph, rgraph;
00268 
00269   nvtxs = graph->nvtxs;
00270 
00271   /* Determine the weights of the partitions */
00272   tvwgt = idxsum(nvtxs, graph->vwgt);
00273   tpwgts2[0] = tvwgt/2;
00274   tpwgts2[1] = tvwgt-tpwgts2[0];
00275 
00276   switch (ctrl->optype) {
00277     case OP_OEMETIS:
00278       MlevelEdgeBisection(ctrl, graph, tpwgts2, ubfactor);
00279 
00280       IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SepTmr));
00281       ConstructMinCoverSeparator(ctrl, graph, ubfactor);
00282       IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SepTmr));
00283 
00284       break;
00285     case OP_ONMETIS:
00286       MlevelNodeBisectionMultiple(ctrl, graph, tpwgts2, ubfactor);
00287 
00288       IFSET(ctrl->dbglvl, DBG_SEPINFO, printf("Nvtxs: %6d, [%6d %6d %6d]\n", graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
00289 
00290       break;
00291   }
00292 
00293   /* Order the nodes in the separator */
00294   nbnd = graph->nbnd;
00295   bndind = graph->bndind;
00296   label = graph->label;
00297   for (i=0; i<nbnd; i++) 
00298     order[label[bndind[i]]] = --lastvtx;
00299 
00300   SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
00301 
00302   /* Free the memory of the top level graph */
00303   GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
00304 
00305   if (rgraph.nvtxs > MMDSWITCH) 
00306     MlevelNestedDissection(ctrl, &rgraph, order, ubfactor, lastvtx);
00307   else {
00308     MMDOrder(ctrl, &rgraph, order, lastvtx); 
00309     GKfree(&rgraph.gdata, &rgraph.rdata, &rgraph.label, LTERM);
00310   }
00311   if (lgraph.nvtxs > MMDSWITCH) 
00312     MlevelNestedDissection(ctrl, &lgraph, order, ubfactor, lastvtx-rgraph.nvtxs);
00313   else {
00314     MMDOrder(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs); 
00315     GKfree(&lgraph.gdata, &lgraph.rdata, &lgraph.label, LTERM);
00316   }
00317 }
00318 
00319 
00320 /*************************************************************************
00321 * This function takes a graph and produces a bisection of it
00322 **************************************************************************/
00323 void MlevelNestedDissectionCC(CtrlType *ctrl, GraphType *graph, idxtype *order, floattype ubfactor, int lastvtx)
00324 {
00325   int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2], nsgraphs, ncmps, rnvtxs;
00326   idxtype *label, *bndind;
00327   idxtype *cptr, *cind;
00328   GraphType *sgraphs;
00329 
00330   nvtxs = graph->nvtxs;
00331 
00332   /* Determine the weights of the partitions */
00333   tvwgt = idxsum(nvtxs, graph->vwgt);
00334   tpwgts2[0] = tvwgt/2;
00335   tpwgts2[1] = tvwgt-tpwgts2[0];
00336 
00337   MlevelNodeBisectionMultiple(ctrl, graph, tpwgts2, ubfactor);
00338   IFSET(ctrl->dbglvl, DBG_SEPINFO, printf("Nvtxs: %6d, [%6d %6d %6d]\n", graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
00339 
00340   /* Order the nodes in the separator */
00341   nbnd = graph->nbnd;
00342   bndind = graph->bndind;
00343   label = graph->label;
00344   for (i=0; i<nbnd; i++) 
00345     order[label[bndind[i]]] = --lastvtx;
00346 
00347   cptr  = idxmalloc(nvtxs+1, "MlevelNestedDissectionCC: cptr");
00348   cind  = idxmalloc(nvtxs, "MlevelNestedDissectionCC: cind");
00349   ncmps = FindComponents(ctrl, graph, cptr, cind);
00350 
00351 /*
00352   if (ncmps > 2)
00353     printf("[%5d] has %3d components\n", nvtxs, ncmps);
00354 */
00355 
00356   sgraphs = (GraphType *)GKmalloc(ncmps*sizeof(GraphType), "MlevelNestedDissectionCC: sgraphs");
00357 
00358   nsgraphs = SplitGraphOrderCC(ctrl, graph, sgraphs, ncmps, cptr, cind);
00359 
00360   GKfree(&cptr, &cind, LTERM);
00361 
00362   /* Free the memory of the top level graph */
00363   GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
00364 
00365   /* Go and process the subgraphs */
00366   for (rnvtxs=i=0; i<nsgraphs; i++) {
00367     if (sgraphs[i].adjwgt == NULL) {
00368       MMDOrder(ctrl, sgraphs+i, order, lastvtx-rnvtxs);
00369       GKfree(&sgraphs[i].gdata, &sgraphs[i].label, LTERM);
00370     }
00371     else {
00372       MlevelNestedDissectionCC(ctrl, sgraphs+i, order, ubfactor, lastvtx-rnvtxs);
00373     }
00374     rnvtxs += sgraphs[i].nvtxs;
00375   }
00376 
00377   free(sgraphs);
00378 }
00379 
00380 
00381 
00382 /*************************************************************************
00383 * This function performs multilevel bisection. It performs multiple 
00384 * bisections and selects the best.
00385 **************************************************************************/
00386 void MlevelNodeBisectionMultiple(CtrlType *ctrl, GraphType *graph, int *tpwgts, floattype ubfactor)
00387 {
00388   int i, nvtxs, cnvtxs, mincut, tmp;
00389   GraphType *cgraph; 
00390   idxtype *bestwhere;
00391 
00392   if (ctrl->nseps == 1 || graph->nvtxs < (ctrl->oflags&OFLAG_COMPRESS ? 1000 : 2000)) {
00393     MlevelNodeBisection(ctrl, graph, tpwgts, ubfactor);
00394     return;
00395   }
00396 
00397   nvtxs = graph->nvtxs;
00398 
00399   if (ctrl->oflags&OFLAG_COMPRESS) { /* Multiple separators at the original graph */
00400     bestwhere = idxmalloc(nvtxs, "MlevelNodeBisection2: bestwhere");
00401     mincut = nvtxs;
00402 
00403     for (i=ctrl->nseps; i>0; i--) {
00404       MlevelNodeBisection(ctrl, graph, tpwgts, ubfactor);
00405 
00406       /* printf("%5d ", cgraph->mincut); */
00407 
00408       if (graph->mincut < mincut) {
00409         mincut = graph->mincut;
00410         idxcopy(nvtxs, graph->where, bestwhere);
00411       }
00412 
00413       GKfree(&graph->rdata, LTERM);
00414     
00415       if (mincut == 0)
00416         break;
00417     }
00418     /* printf("[%5d]\n", mincut); */
00419 
00420     Allocate2WayNodePartitionMemory(ctrl, graph);
00421     idxcopy(nvtxs, bestwhere, graph->where);
00422     free(bestwhere);
00423 
00424     Compute2WayNodePartitionParams(ctrl, graph);
00425   }
00426   else {  /* Coarsen it a bit */
00427     ctrl->CoarsenTo = nvtxs-1;
00428 
00429     cgraph = Coarsen2Way(ctrl, graph);
00430 
00431     cnvtxs = cgraph->nvtxs;
00432 
00433     bestwhere = idxmalloc(cnvtxs, "MlevelNodeBisection2: bestwhere");
00434     mincut = nvtxs;
00435 
00436     for (i=ctrl->nseps; i>0; i--) {
00437       ctrl->CType += 20; /* This is a hack. Look at coarsen.c */
00438       MlevelNodeBisection(ctrl, cgraph, tpwgts, ubfactor);
00439 
00440       /* printf("%5d ", cgraph->mincut); */
00441 
00442       if (cgraph->mincut < mincut) {
00443         mincut = cgraph->mincut;
00444         idxcopy(cnvtxs, cgraph->where, bestwhere);
00445       }
00446 
00447       GKfree(&cgraph->rdata, LTERM);
00448     
00449       if (mincut == 0)
00450         break;
00451     }
00452     /* printf("[%5d]\n", mincut); */
00453 
00454     Allocate2WayNodePartitionMemory(ctrl, cgraph);
00455     idxcopy(cnvtxs, bestwhere, cgraph->where);
00456     free(bestwhere);
00457 
00458     Compute2WayNodePartitionParams(ctrl, cgraph);
00459 
00460     Refine2WayNode(ctrl, graph, cgraph, ubfactor);
00461   }
00462 
00463 }
00464 
00465 /*************************************************************************
00466 * This function performs multilevel bisection
00467 **************************************************************************/
00468 void MlevelNodeBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, floattype ubfactor)
00469 {
00470   GraphType *cgraph;
00471 
00472   ctrl->CoarsenTo = graph->nvtxs/8;
00473   if (ctrl->CoarsenTo > 100)
00474     ctrl->CoarsenTo = 100;
00475   else if (ctrl->CoarsenTo < 40)
00476     ctrl->CoarsenTo = 40;
00477   ctrl->maxvwgt = 1.5*((tpwgts[0]+tpwgts[1])/ctrl->CoarsenTo);
00478 
00479   cgraph = Coarsen2Way(ctrl, graph);
00480 
00481   switch (ctrl->IType) {
00482     case IPART_GGPKL:
00483       Init2WayPartition(ctrl, cgraph, tpwgts, ubfactor);
00484 
00485       IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SepTmr));
00486 
00487       Compute2WayPartitionParams(ctrl, cgraph);
00488       ConstructSeparator(ctrl, cgraph, ubfactor);
00489 
00490       IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SepTmr));
00491       break;
00492     case IPART_GGPKLNODE:
00493       InitSeparator(ctrl, cgraph, ubfactor);
00494       break;
00495   }
00496 
00497   Refine2WayNode(ctrl, graph, cgraph, ubfactor);
00498 
00499 }
00500 
00501 
00502 
00503 
00504 /*************************************************************************
00505 * This function takes a graph and a bisection and splits it into two graphs.
00506 * This function relies on the fact that adjwgt is all equal to 1.
00507 **************************************************************************/
00508 void SplitGraphOrder(CtrlType *ctrl, GraphType *graph, GraphType *lgraph, GraphType *rgraph)
00509 {
00510   int i, ii, j, k, l, istart, iend, mypart, nvtxs, snvtxs[3], snedges[3];
00511   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr, *bndind;
00512   idxtype *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *sadjwgtsum[2], *slabel[2];
00513   idxtype *rename;
00514   idxtype *auxadjncy, *auxadjwgt;
00515 
00516   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SplitTmr));
00517 
00518   nvtxs = graph->nvtxs;
00519   xadj = graph->xadj;
00520   vwgt = graph->vwgt;
00521   adjncy = graph->adjncy;
00522   adjwgt = graph->adjwgt;
00523   adjwgtsum = graph->adjwgtsum;
00524   label = graph->label;
00525   where = graph->where;
00526   bndptr = graph->bndptr;
00527   bndind = graph->bndind;
00528   ASSERT(bndptr != NULL);
00529 
00530   rename = idxwspacemalloc(ctrl, nvtxs);
00531   
00532   snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
00533   for (i=0; i<nvtxs; i++) {
00534     k = where[i];
00535     rename[i] = snvtxs[k]++;
00536     snedges[k] += xadj[i+1]-xadj[i];
00537   }
00538 
00539   SetUpSplitGraph(graph, lgraph, snvtxs[0], snedges[0]);
00540   sxadj[0] = lgraph->xadj;
00541   svwgt[0] = lgraph->vwgt;
00542   sadjwgtsum[0] = lgraph->adjwgtsum;
00543   sadjncy[0] = lgraph->adjncy; 
00544   sadjwgt[0] = lgraph->adjwgt; 
00545   slabel[0] = lgraph->label;
00546 
00547   SetUpSplitGraph(graph, rgraph, snvtxs[1], snedges[1]);
00548   sxadj[1] = rgraph->xadj;
00549   svwgt[1] = rgraph->vwgt;
00550   sadjwgtsum[1] = rgraph->adjwgtsum;
00551   sadjncy[1] = rgraph->adjncy; 
00552   sadjwgt[1] = rgraph->adjwgt; 
00553   slabel[1] = rgraph->label;
00554 
00555   /* Go and use bndptr to also mark the boundary nodes in the two partitions */
00556   for (ii=0; ii<graph->nbnd; ii++) {
00557     i = bndind[ii];
00558     for (j=xadj[i]; j<xadj[i+1]; j++)
00559       bndptr[adjncy[j]] = 1;
00560   }
00561 
00562   snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
00563   sxadj[0][0] = sxadj[1][0] = 0;
00564   for (i=0; i<nvtxs; i++) {
00565     if ((mypart = where[i]) == 2)
00566       continue;
00567 
00568     istart = xadj[i];
00569     iend = xadj[i+1];
00570     if (bndptr[i] == -1) { /* This is an interior vertex */
00571       auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
00572       for(j=istart; j<iend; j++) 
00573         auxadjncy[j] = adjncy[j];
00574       snedges[mypart] += iend-istart;
00575     }
00576     else {
00577       auxadjncy = sadjncy[mypart];
00578       l = snedges[mypart];
00579       for (j=istart; j<iend; j++) {
00580         k = adjncy[j];
00581         if (where[k] == mypart) 
00582           auxadjncy[l++] = k;
00583       }
00584       snedges[mypart] = l;
00585     }
00586 
00587     svwgt[mypart][snvtxs[mypart]] = vwgt[i];
00588     sadjwgtsum[mypart][snvtxs[mypart]] = snedges[mypart]-sxadj[mypart][snvtxs[mypart]];
00589     slabel[mypart][snvtxs[mypart]] = label[i];
00590     sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
00591   }
00592 
00593   for (mypart=0; mypart<2; mypart++) {
00594     iend = snedges[mypart];
00595     idxset(iend, 1, sadjwgt[mypart]);
00596 
00597     auxadjncy = sadjncy[mypart];
00598     for (i=0; i<iend; i++) 
00599       auxadjncy[i] = rename[auxadjncy[i]];
00600   }
00601 
00602   lgraph->nvtxs = snvtxs[0];
00603   lgraph->nedges = snedges[0];
00604   rgraph->nvtxs = snvtxs[1];
00605   rgraph->nedges = snedges[1];
00606 
00607   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SplitTmr));
00608 
00609   idxwspacefree(ctrl, nvtxs);
00610 
00611 }
00612 
00613 /*************************************************************************
00614 * This function uses MMD to order the graph. The vertices are numbered
00615 * from lastvtx downwards
00616 **************************************************************************/
00617 void MMDOrder(CtrlType *ctrl, GraphType *graph, idxtype *order, int lastvtx)
00618 {
00619   int i, j, k, nvtxs, nofsub, firstvtx;
00620   idxtype *xadj, *adjncy, *label;
00621   idxtype *perm, *iperm, *head, *qsize, *list, *marker;
00622 
00623   nvtxs = graph->nvtxs;
00624   xadj = graph->xadj;
00625   adjncy = graph->adjncy;
00626 
00627   /* Relabel the vertices so that it starts from 1 */
00628   k = xadj[nvtxs];
00629   for (i=0; i<k; i++)
00630     adjncy[i]++;
00631   for (i=0; i<nvtxs+1; i++)
00632     xadj[i]++;
00633 
00634   perm = idxmalloc(6*(nvtxs+5), "MMDOrder: perm");
00635   iperm = perm + nvtxs + 5;
00636   head = iperm + nvtxs + 5;
00637   qsize = head + nvtxs + 5;
00638   list = qsize + nvtxs + 5;
00639   marker = list + nvtxs + 5;
00640 
00641   genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker, MAXIDX, &nofsub);
00642 
00643   label = graph->label;
00644   firstvtx = lastvtx-nvtxs;
00645   for (i=0; i<nvtxs; i++)
00646     order[label[i]] = firstvtx+iperm[i]-1;
00647 
00648   free(perm);
00649 
00650   /* Relabel the vertices so that it starts from 0 */
00651   for (i=0; i<nvtxs+1; i++)
00652     xadj[i]--;
00653   k = xadj[nvtxs];
00654   for (i=0; i<k; i++)
00655     adjncy[i]--;
00656 }
00657 
00658 
00659 /*************************************************************************
00660 * This function takes a graph and a bisection and splits it into two graphs.
00661 * It relies on the fact that adjwgt is all set to 1.
00662 **************************************************************************/
00663 int SplitGraphOrderCC(CtrlType *ctrl, GraphType *graph, GraphType *sgraphs, int ncmps, idxtype *cptr, idxtype *cind)
00664 {
00665   int i, ii, iii, j, k, l, istart, iend, mypart, nvtxs, snvtxs, snedges;
00666   idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr, *bndind;
00667   idxtype *sxadj, *svwgt, *sadjncy, *sadjwgt, *sadjwgtsum, *slabel;
00668   idxtype *rename;
00669   idxtype *auxadjncy, *auxadjwgt;
00670 
00671   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SplitTmr));
00672 
00673   nvtxs = graph->nvtxs;
00674   xadj = graph->xadj;
00675   vwgt = graph->vwgt;
00676   adjncy = graph->adjncy;
00677   adjwgt = graph->adjwgt;
00678   adjwgtsum = graph->adjwgtsum;
00679   label = graph->label;
00680   where = graph->where;
00681   bndptr = graph->bndptr;
00682   bndind = graph->bndind;
00683   ASSERT(bndptr != NULL);
00684 
00685   /* Go and use bndptr to also mark the boundary nodes in the two partitions */
00686   for (ii=0; ii<graph->nbnd; ii++) {
00687     i = bndind[ii];
00688     for (j=xadj[i]; j<xadj[i+1]; j++)
00689       bndptr[adjncy[j]] = 1;
00690   }
00691 
00692   rename = idxwspacemalloc(ctrl, nvtxs);
00693   
00694   /* Go and split the graph a component at a time */
00695   for (iii=0; iii<ncmps; iii++) {
00696     RandomPermute(cptr[iii+1]-cptr[iii], cind+cptr[iii], 0);
00697     snvtxs = snedges = 0;
00698     for (j=cptr[iii]; j<cptr[iii+1]; j++) {
00699       i = cind[j];
00700       rename[i] = snvtxs++;
00701       snedges += xadj[i+1]-xadj[i];
00702     }
00703 
00704     SetUpSplitGraph(graph, sgraphs+iii, snvtxs, snedges);
00705     sxadj = sgraphs[iii].xadj;
00706     svwgt = sgraphs[iii].vwgt;
00707     sadjwgtsum = sgraphs[iii].adjwgtsum;
00708     sadjncy = sgraphs[iii].adjncy;
00709     sadjwgt = sgraphs[iii].adjwgt;
00710     slabel = sgraphs[iii].label;
00711 
00712     snvtxs = snedges = sxadj[0] = 0;
00713     for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
00714       i = cind[ii];
00715 
00716       istart = xadj[i];
00717       iend = xadj[i+1];
00718       if (bndptr[i] == -1) { /* This is an interior vertex */
00719         auxadjncy = sadjncy + snedges - istart;
00720         auxadjwgt = sadjwgt + snedges - istart;
00721         for(j=istart; j<iend; j++) 
00722           auxadjncy[j] = adjncy[j];
00723         snedges += iend-istart;
00724       }
00725       else {
00726         l = snedges;
00727         for (j=istart; j<iend; j++) {
00728           k = adjncy[j];
00729           if (where[k] != 2) 
00730             sadjncy[l++] = k;
00731         }
00732         snedges = l;
00733       }
00734 
00735       svwgt[snvtxs] = vwgt[i];
00736       sadjwgtsum[snvtxs] = snedges-sxadj[snvtxs];
00737       slabel[snvtxs] = label[i];
00738       sxadj[++snvtxs] = snedges;
00739     }
00740 
00741     idxset(snedges, 1, sadjwgt);
00742     for (i=0; i<snedges; i++) 
00743       sadjncy[i] = rename[sadjncy[i]];
00744 
00745     sgraphs[iii].nvtxs = snvtxs;
00746     sgraphs[iii].nedges = snedges;
00747     sgraphs[iii].ncon = 1;
00748 
00749     if (snvtxs < MMDSWITCH)
00750       sgraphs[iii].adjwgt = NULL;  /* A marker to call MMD on the driver */
00751   }
00752 
00753   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SplitTmr));
00754 
00755   idxwspacefree(ctrl, nvtxs);
00756 
00757   return ncmps;
00758 
00759 }
00760 
00761 
00762 
00763 
00764
libs/ck-libs/parmetis/METISLib/ometis.c
