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: ometis.c 10513 2011-07-07 22:06:03Z karypis $
00013  *
00014  */
00015 
00016 #include "metislib.h"
00017 
00018 
00019 /*************************************************************************/
00042 /*************************************************************************/
00043 int METIS_NodeND(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
00044           idx_t *options, idx_t *perm, idx_t *iperm) 
00045 {
00046   int sigrval=0, renumber=0;
00047   idx_t i, ii, j, l, nnvtxs=0;
00048   graph_t *graph=NULL;
00049   ctrl_t *ctrl;
00050   idx_t *cptr, *cind, *piperm;
00051   int numflag = 0;
00052 
00053   /* set up malloc cleaning code and signal catchers */
00054   if (!gk_malloc_init()) 
00055     return METIS_ERROR_MEMORY;
00056 
00057   gk_sigtrap();
00058 
00059   if ((sigrval = gk_sigcatch()) != 0) 
00060     goto SIGTHROW;
00061 
00062 
00063   /* set up the run time parameters */
00064   ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL);
00065   if (!ctrl) {
00066     gk_siguntrap();
00067     return METIS_ERROR_INPUT;
00068   }
00069 
00070   /* if required, change the numbering to 0 */
00071   if (ctrl->numflag == 1) {
00072     Change2CNumbering(*nvtxs, xadj, adjncy);
00073     renumber = 1;
00074   }
00075 
00076   IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
00077   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));
00078 
00079   /* prune the dense columns */
00080   if (ctrl->pfactor > 0.0) { 
00081     piperm = imalloc(*nvtxs, "OMETIS: piperm");
00082 
00083     graph = PruneGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, piperm, ctrl->pfactor);
00084     if (graph == NULL) {
00085       /* if there was no prunning, cleanup the pfactor */
00086       gk_free((void **)&piperm, LTERM);
00087       ctrl->pfactor = 0.0;
00088     }
00089     else {
00090       nnvtxs = graph->nvtxs;
00091       ctrl->compress = 0;  /* disable compression if prunning took place */
00092     }
00093   }
00094 
00095   /* compress the graph; note that compression only happens if not prunning 
00096      has taken place. */
00097   if (ctrl->compress) { 
00098     cptr = imalloc(*nvtxs+1, "OMETIS: cptr");
00099     cind = imalloc(*nvtxs, "OMETIS: cind");
00100 
00101     graph = CompressGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, cptr, cind);
00102     if (graph == NULL) {
00103       /* if there was no compression, cleanup the compress flag */
00104       gk_free((void **)&cptr, &cind, LTERM);
00105       ctrl->compress = 0; 
00106     }
00107     else {
00108       nnvtxs = graph->nvtxs;
00109       ctrl->cfactor = 1.0*(*nvtxs)/nnvtxs;
00110       if (ctrl->cfactor > 1.5 && ctrl->nseps == 1)
00111         ctrl->nseps = 2;
00112       //ctrl->nseps = (idx_t)(ctrl->cfactor*ctrl->nseps);
00113     }
00114   }
00115 
00116   /* if no prunning and no compression, setup the graph in the normal way. */
00117   if (ctrl->pfactor == 0.0 && ctrl->compress == 0) 
00118     graph = SetupGraph(ctrl, *nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);
00119 
00120   ASSERT(CheckGraph(graph, ctrl->numflag, 1));
00121 
00122   /* allocate workspace memory */
00123   AllocateWorkSpace(ctrl, graph);
00124 
00125   /* do the nested dissection ordering  */
00126   if (ctrl->ccorder) 
00127     MlevelNestedDissectionCC(ctrl, graph, iperm, graph->nvtxs);
00128   else
00129     MlevelNestedDissection(ctrl, graph, iperm, graph->nvtxs);
00130 
00131 
00132   if (ctrl->pfactor > 0.0) { /* Order any prunned vertices */
00133     icopy(nnvtxs, iperm, perm);  /* Use perm as an auxiliary array */
00134     for (i=0; i<nnvtxs; i++)
00135       iperm[piperm[i]] = perm[i];
00136     for (i=nnvtxs; i<*nvtxs; i++)
00137       iperm[piperm[i]] = i;
00138 
00139     gk_free((void **)&piperm, LTERM);
00140   }
00141   else if (ctrl->compress) { /* Uncompress the ordering */
00142     /* construct perm from iperm */
00143     for (i=0; i<nnvtxs; i++)
00144       perm[iperm[i]] = i; 
00145     for (l=ii=0; ii<nnvtxs; ii++) {
00146       i = perm[ii];
00147       for (j=cptr[i]; j<cptr[i+1]; j++)
00148         iperm[cind[j]] = l++;
00149     }
00150 
00151     gk_free((void **)&cptr, &cind, LTERM);
00152   }
00153 
00154   for (i=0; i<*nvtxs; i++)
00155     perm[iperm[i]] = i;
00156 
00157   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->TotalTmr));
00158   IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
00159 
00160   /* clean up */
00161   FreeCtrl(&ctrl);
00162 
00163 SIGTHROW:
00164   /* if required, change the numbering back to 1 */
00165   if (renumber)
00166     Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
00167 
00168   gk_siguntrap();
00169   gk_malloc_cleanup(0);
00170 
00171   return metis_rcode(sigrval);
00172 }
00173 
00174 
00175 /*************************************************************************/
00182 /*************************************************************************/
00183 void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order, 
00184          idx_t lastvtx)
00185 {
00186   idx_t i, j, nvtxs, nbnd;
00187   idx_t *label, *bndind;
00188   graph_t *lgraph, *rgraph;
00189 
00190   nvtxs = graph->nvtxs;
00191 
00192   MlevelNodeBisectionMultiple(ctrl, graph);
00193 
00194   IFSET(ctrl->dbglvl, METIS_DBG_SEPINFO, 
00195       printf("Nvtxs: %6"PRIDX", [%6"PRIDX" %6"PRIDX" %6"PRIDX"]\n", 
00196         graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
00197 
00198 
00199   /* Order the nodes in the separator */
00200   nbnd   = graph->nbnd;
00201   bndind = graph->bndind;
00202   label  = graph->label;
00203   for (i=0; i<nbnd; i++) 
00204     order[label[bndind[i]]] = --lastvtx;
00205 
00206   SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
00207 
00208   /* Free the memory of the top level graph */
00209   FreeGraph(&graph);
00210 
00211   /* Recurse on lgraph first, as its lastvtx depends on rgraph->nvtxs, which
00212      will not be defined upon return from MlevelNestedDissection. */
00213   if (lgraph->nvtxs > MMDSWITCH && lgraph->nedges > 0) 
00214     MlevelNestedDissection(ctrl, lgraph, order, lastvtx-rgraph->nvtxs);
00215   else {
00216     MMDOrder(ctrl, lgraph, order, lastvtx-rgraph->nvtxs); 
00217     FreeGraph(&lgraph);
00218   }
00219   if (rgraph->nvtxs > MMDSWITCH && rgraph->nedges > 0) 
00220     MlevelNestedDissection(ctrl, rgraph, order, lastvtx);
00221   else {
00222     MMDOrder(ctrl, rgraph, order, lastvtx); 
00223     FreeGraph(&rgraph);
00224   }
00225 }
00226 
00227 
00228 /*************************************************************************/
00235 /*************************************************************************/
00236 void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order, 
00237          idx_t lastvtx)
00238 {
00239   idx_t i, j, nvtxs, nbnd, ncmps, rnvtxs, snvtxs;
00240   idx_t *label, *bndind;
00241   idx_t *cptr, *cind;
00242   graph_t **sgraphs;
00243 
00244   nvtxs = graph->nvtxs;
00245 
00246   MlevelNodeBisectionMultiple(ctrl, graph);
00247 
00248   IFSET(ctrl->dbglvl, METIS_DBG_SEPINFO, 
00249       printf("Nvtxs: %6"PRIDX", [%6"PRIDX" %6"PRIDX" %6"PRIDX"]\n", 
00250         graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
00251 
00252   /* Order the nodes in the separator */
00253   nbnd   = graph->nbnd;
00254   bndind = graph->bndind;
00255   label  = graph->label;
00256   for (i=0; i<nbnd; i++) 
00257     order[label[bndind[i]]] = --lastvtx;
00258 
00259   WCOREPUSH;
00260   cptr  = iwspacemalloc(ctrl, nvtxs+1);
00261   cind  = iwspacemalloc(ctrl, nvtxs);
00262   ncmps = FindSepInducedComponents(ctrl, graph, cptr, cind);
00263 
00264   if (ctrl->dbglvl&METIS_DBG_INFO) {
00265     if (ncmps > 2)
00266       printf("  Bisection resulted in %"PRIDX" connected components\n", ncmps);
00267   }
00268   
00269   sgraphs = SplitGraphOrderCC(ctrl, graph, ncmps, cptr, cind);
00270 
00271   WCOREPOP;
00272 
00273   /* Free the memory of the top level graph */
00274   FreeGraph(&graph);
00275 
00276   /* Go and process the subgraphs */
00277   for (rnvtxs=i=0; i<ncmps; i++) {
00278     /* Save the number of vertices in sgraphs[i] because sgraphs[i] is freed 
00279        inside MlevelNestedDissectionCC, and as such it will be undefined. */
00280     snvtxs = sgraphs[i]->nvtxs;
00281 
00282     if (sgraphs[i]->nvtxs > MMDSWITCH && sgraphs[i]->nedges > 0) {
00283       MlevelNestedDissectionCC(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
00284     }
00285     else {
00286       MMDOrder(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
00287       FreeGraph(&sgraphs[i]);
00288     }
00289     rnvtxs += snvtxs;
00290   }
00291 
00292   gk_free((void **)&sgraphs, LTERM);
00293 }
00294 
00295 
00296 /*************************************************************************/
00299 /*************************************************************************/
00300 void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph)
00301 {
00302   idx_t i, mincut;
00303   idx_t *bestwhere;
00304 
00305   /* if the graph is small, just find a single vertex separator */
00306   if (ctrl->nseps == 1 || graph->nvtxs < (ctrl->compress ? 1000 : 2000)) {
00307     MlevelNodeBisectionL2(ctrl, graph, LARGENIPARTS);
00308     return;
00309   }
00310 
00311   WCOREPUSH;
00312 
00313   bestwhere = iwspacemalloc(ctrl, graph->nvtxs);
00314 
00315   mincut = graph->tvwgt[0];
00316   for (i=0; i<ctrl->nseps; i++) {
00317     MlevelNodeBisectionL2(ctrl, graph, LARGENIPARTS);
00318 
00319     if (i == 0 || graph->mincut < mincut) {
00320       mincut = graph->mincut;
00321       if (i < ctrl->nseps-1)
00322         icopy(graph->nvtxs, graph->where, bestwhere);
00323     }
00324 
00325     if (mincut == 0)
00326       break;
00327 
00328     if (i < ctrl->nseps-1) 
00329       FreeRData(graph);
00330   }
00331 
00332   if (mincut != graph->mincut) {
00333     icopy(graph->nvtxs, bestwhere, graph->where);
00334     Compute2WayNodePartitionParams(ctrl, graph);
00335   }
00336 
00337   WCOREPOP;
00338 }
00339 
00340 
00341 /*************************************************************************/
00344 /*************************************************************************/
00345 void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
00346 {
00347   idx_t i, mincut, nruns=5;
00348   graph_t *cgraph; 
00349   idx_t *bestwhere;
00350 
00351   /* if the graph is small, just find a single vertex separator */
00352   if (graph->nvtxs < 5000) {
00353     MlevelNodeBisectionL1(ctrl, graph, niparts);
00354     return;
00355   }
00356 
00357   WCOREPUSH;
00358 
00359   ctrl->CoarsenTo = gk_max(100, graph->nvtxs/30);
00360 
00361   cgraph = CoarsenGraphNlevels(ctrl, graph, 4);
00362 
00363   bestwhere = iwspacemalloc(ctrl, cgraph->nvtxs);
00364 
00365   mincut = graph->tvwgt[0];
00366   for (i=0; i<nruns; i++) {
00367     MlevelNodeBisectionL1(ctrl, cgraph, 0.7*niparts);
00368 
00369     if (i == 0 || cgraph->mincut < mincut) {
00370       mincut = cgraph->mincut;
00371       if (i < nruns-1)
00372         icopy(cgraph->nvtxs, cgraph->where, bestwhere);
00373     }
00374 
00375     if (mincut == 0)
00376       break;
00377 
00378     if (i < nruns-1) 
00379       FreeRData(cgraph);
00380   }
00381 
00382   if (mincut != cgraph->mincut) 
00383     icopy(cgraph->nvtxs, bestwhere, cgraph->where);
00384 
00385   WCOREPOP;
00386 
00387   Refine2WayNode(ctrl, graph, cgraph);
00388 
00389 }
00390 
00391 
00392 /*************************************************************************/
00394 /*************************************************************************/
00395 void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
00396 {
00397   graph_t *cgraph;
00398 
00399   ctrl->CoarsenTo = graph->nvtxs/8;
00400   if (ctrl->CoarsenTo > 100)
00401     ctrl->CoarsenTo = 100;
00402   else if (ctrl->CoarsenTo < 40)
00403     ctrl->CoarsenTo = 40;
00404 
00405   cgraph = CoarsenGraph(ctrl, graph);
00406 
00407   niparts = gk_max(1, (cgraph->nvtxs <= ctrl->CoarsenTo ? niparts/2: niparts));
00408   /*niparts = (cgraph->nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);*/
00409   InitSeparator(ctrl, cgraph, niparts);
00410 
00411   Refine2WayNode(ctrl, graph, cgraph);
00412 }
00413 
00414 
00415 /*************************************************************************/
00421 /*************************************************************************/
00422 void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, 
00423          graph_t **r_rgraph)
00424 {
00425   idx_t i, ii, j, k, l, istart, iend, mypart, nvtxs, snvtxs[3], snedges[3];
00426   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *label, *where, *bndptr, *bndind;
00427   idx_t *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *slabel[2];
00428   idx_t *rename;
00429   idx_t *auxadjncy;
00430   graph_t *lgraph, *rgraph;
00431 
00432   WCOREPUSH;
00433 
00434   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->SplitTmr));
00435 
00436   nvtxs   = graph->nvtxs;
00437   xadj    = graph->xadj;
00438   vwgt    = graph->vwgt;
00439   adjncy  = graph->adjncy;
00440   adjwgt  = graph->adjwgt;
00441   label   = graph->label;
00442   where   = graph->where;
00443   bndptr  = graph->bndptr;
00444   bndind  = graph->bndind;
00445   ASSERT(bndptr != NULL);
00446 
00447   rename = iwspacemalloc(ctrl, nvtxs);
00448   
00449   snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
00450   for (i=0; i<nvtxs; i++) {
00451     k = where[i];
00452     rename[i] = snvtxs[k]++;
00453     snedges[k] += xadj[i+1]-xadj[i];
00454   }
00455 
00456   lgraph      = SetupSplitGraph(graph, snvtxs[0], snedges[0]);
00457   sxadj[0]    = lgraph->xadj;
00458   svwgt[0]    = lgraph->vwgt;
00459   sadjncy[0]  = lgraph->adjncy; 
00460   sadjwgt[0]  = lgraph->adjwgt; 
00461   slabel[0]   = lgraph->label;
00462 
00463   rgraph      = SetupSplitGraph(graph, snvtxs[1], snedges[1]);
00464   sxadj[1]    = rgraph->xadj;
00465   svwgt[1]    = rgraph->vwgt;
00466   sadjncy[1]  = rgraph->adjncy; 
00467   sadjwgt[1]  = rgraph->adjwgt; 
00468   slabel[1]   = rgraph->label;
00469 
00470   /* Go and use bndptr to also mark the boundary nodes in the two partitions */
00471   for (ii=0; ii<graph->nbnd; ii++) {
00472     i = bndind[ii];
00473     for (j=xadj[i]; j<xadj[i+1]; j++)
00474       bndptr[adjncy[j]] = 1;
00475   }
00476 
00477   snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
00478   sxadj[0][0] = sxadj[1][0] = 0;
00479   for (i=0; i<nvtxs; i++) {
00480     if ((mypart = where[i]) == 2)
00481       continue;
00482 
00483     istart = xadj[i];
00484     iend   = xadj[i+1];
00485     if (bndptr[i] == -1) { /* This is an interior vertex */
00486       auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
00487       for(j=istart; j<iend; j++) 
00488         auxadjncy[j] = adjncy[j];
00489       snedges[mypart] += iend-istart;
00490     }
00491     else {
00492       auxadjncy = sadjncy[mypart];
00493       l = snedges[mypart];
00494       for (j=istart; j<iend; j++) {
00495         k = adjncy[j];
00496         if (where[k] == mypart) 
00497           auxadjncy[l++] = k;
00498       }
00499       snedges[mypart] = l;
00500     }
00501 
00502     svwgt[mypart][snvtxs[mypart]]    = vwgt[i];
00503     slabel[mypart][snvtxs[mypart]]   = label[i];
00504     sxadj[mypart][++snvtxs[mypart]]  = snedges[mypart];
00505   }
00506 
00507   for (mypart=0; mypart<2; mypart++) {
00508     iend = snedges[mypart];
00509     iset(iend, 1, sadjwgt[mypart]);
00510 
00511     auxadjncy = sadjncy[mypart];
00512     for (i=0; i<iend; i++) 
00513       auxadjncy[i] = rename[auxadjncy[i]];
00514   }
00515 
00516   lgraph->nvtxs  = snvtxs[0];
00517   lgraph->nedges = snedges[0];
00518   rgraph->nvtxs  = snvtxs[1];
00519   rgraph->nedges = snedges[1];
00520 
00521   SetupGraph_tvwgt(lgraph);
00522   SetupGraph_tvwgt(rgraph);
00523 
00524   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->SplitTmr));
00525 
00526   *r_lgraph = lgraph;
00527   *r_rgraph = rgraph;
00528 
00529   WCOREPOP;
00530 }
00531 
00532 
00533 /*************************************************************************/
00551 /*************************************************************************/
00552 graph_t **SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps, 
00553               idx_t *cptr, idx_t *cind)
00554 {
00555   idx_t i, ii, iii, j, k, l, istart, iend, mypart, nvtxs, snvtxs, snedges;
00556   idx_t *xadj, *vwgt, *adjncy, *adjwgt, *label, *where, *bndptr, *bndind;
00557   idx_t *sxadj, *svwgt, *sadjncy, *sadjwgt, *slabel;
00558   idx_t *rename;
00559   idx_t *auxadjncy;
00560   graph_t **sgraphs;
00561 
00562   WCOREPUSH;
00563 
00564   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->SplitTmr));
00565 
00566   nvtxs   = graph->nvtxs;
00567   xadj    = graph->xadj;
00568   vwgt    = graph->vwgt;
00569   adjncy  = graph->adjncy;
00570   adjwgt  = graph->adjwgt;
00571   label   = graph->label;
00572   where   = graph->where;
00573   bndptr  = graph->bndptr;
00574   bndind  = graph->bndind;
00575   ASSERT(bndptr != NULL);
00576 
00577   /* Go and use bndptr to also mark the boundary nodes in the two partitions */
00578   for (ii=0; ii<graph->nbnd; ii++) {
00579     i = bndind[ii];
00580     for (j=xadj[i]; j<xadj[i+1]; j++)
00581       bndptr[adjncy[j]] = 1;
00582   }
00583 
00584   rename = iwspacemalloc(ctrl, nvtxs);
00585   
00586   sgraphs = (graph_t **)gk_malloc(sizeof(graph_t *)*ncmps, "SplitGraphOrderCC: sgraphs");
00587 
00588   /* Go and split the graph a component at a time */
00589   for (iii=0; iii<ncmps; iii++) {
00590     irandArrayPermute(cptr[iii+1]-cptr[iii], cind+cptr[iii], cptr[iii+1]-cptr[iii], 0);
00591     snvtxs = snedges = 0;
00592     for (j=cptr[iii]; j<cptr[iii+1]; j++) {
00593       i = cind[j];
00594       rename[i] = snvtxs++;
00595       snedges += xadj[i+1]-xadj[i];
00596     }
00597 
00598     sgraphs[iii] = SetupSplitGraph(graph, snvtxs, snedges);
00599 
00600     sxadj    = sgraphs[iii]->xadj;
00601     svwgt    = sgraphs[iii]->vwgt;
00602     sadjncy  = sgraphs[iii]->adjncy;
00603     sadjwgt  = sgraphs[iii]->adjwgt;
00604     slabel   = sgraphs[iii]->label;
00605 
00606     snvtxs = snedges = sxadj[0] = 0;
00607     for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
00608       i = cind[ii];
00609 
00610       istart = xadj[i];
00611       iend   = xadj[i+1];
00612       if (bndptr[i] == -1) { /* This is an interior vertex */
00613         auxadjncy = sadjncy + snedges - istart;
00614         for(j=istart; j<iend; j++) 
00615           auxadjncy[j] = adjncy[j];
00616         snedges += iend-istart;
00617       }
00618       else {
00619         l = snedges;
00620         for (j=istart; j<iend; j++) {
00621           k = adjncy[j];
00622           if (where[k] != 2) 
00623             sadjncy[l++] = k;
00624         }
00625         snedges = l;
00626       }
00627 
00628       svwgt[snvtxs]    = vwgt[i];
00629       slabel[snvtxs]   = label[i];
00630       sxadj[++snvtxs]  = snedges;
00631     }
00632 
00633     iset(snedges, 1, sadjwgt);
00634     for (i=0; i<snedges; i++) 
00635       sadjncy[i] = rename[sadjncy[i]];
00636 
00637     sgraphs[iii]->nvtxs  = snvtxs;
00638     sgraphs[iii]->nedges = snedges;
00639 
00640     SetupGraph_tvwgt(sgraphs[iii]);
00641   }
00642 
00643   IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->SplitTmr));
00644 
00645   WCOREPOP;
00646 
00647   return sgraphs;
00648 }
00649 
00650 
00651 /*************************************************************************/
00654 /*************************************************************************/
00655 void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
00656 {
00657   idx_t i, j, k, nvtxs, nofsub, firstvtx;
00658   idx_t *xadj, *adjncy, *label;
00659   idx_t *perm, *iperm, *head, *qsize, *list, *marker;
00660 
00661   WCOREPUSH;
00662 
00663   nvtxs  = graph->nvtxs;
00664   xadj   = graph->xadj;
00665   adjncy = graph->adjncy;
00666 
00667   /* Relabel the vertices so that it starts from 1 */
00668   k = xadj[nvtxs];
00669   for (i=0; i<k; i++)
00670     adjncy[i]++;
00671   for (i=0; i<nvtxs+1; i++)
00672     xadj[i]++;
00673 
00674   perm   = iwspacemalloc(ctrl, nvtxs+5);
00675   iperm  = iwspacemalloc(ctrl, nvtxs+5);
00676   head   = iwspacemalloc(ctrl, nvtxs+5);
00677   qsize  = iwspacemalloc(ctrl, nvtxs+5);
00678   list   = iwspacemalloc(ctrl, nvtxs+5);
00679   marker = iwspacemalloc(ctrl, nvtxs+5);
00680 
00681   genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker, IDX_MAX, &nofsub);
00682 
00683   label = graph->label;
00684   firstvtx = lastvtx-nvtxs;
00685   for (i=0; i<nvtxs; i++)
00686     order[label[i]] = firstvtx+iperm[i]-1;
00687 
00688   /* Relabel the vertices so that it starts from 0 */
00689   for (i=0; i<nvtxs+1; i++)
00690     xadj[i]--;
00691   k = xadj[nvtxs];
00692   for (i=0; i<k; i++)
00693     adjncy[i]--;
00694 
00695   WCOREPOP;
00696 }
00697 
00698 
00699 
00700 
00701
libs/ck-libs/metis/libmetis/ometis.c
