自学教程：C++ AllocateWorkSpace函数代码示例

void METIS_NodeRefine(int nvtxs, idxtype *xadj, idxtype *vwgt, idxtype *adjncy,            idxtype *adjwgt, idxtype *where, idxtype *hmarker, float ubfactor){  GraphType *graph;  CtrlType ctrl;  ctrl.dbglvl    = ONMETIS_DBGLVL;  ctrl.optype    = OP_ONMETIS;  graph = CreateGraph();  SetUpGraph(graph, OP_ONMETIS, nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);  AllocateWorkSpace(&ctrl, graph, 2);  Allocate2WayNodePartitionMemory(&ctrl, graph);  idxcopy(nvtxs, where, graph->where);  Compute2WayNodePartitionParams(&ctrl, graph);  FM_2WayNodeRefine_OneSidedP(&ctrl, graph, hmarker, ubfactor, 10);   /* FM_2WayNodeRefine_TwoSidedP(&ctrl, graph, hmarker, ubfactor, 10); */  FreeWorkSpace(&ctrl, graph);  idxcopy(nvtxs, graph->where, where);  FreeGraph(graph);}

/************************************************************************** This function is the entry point for OEMETIS**************************************************************************/void METIS_EdgeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options,                   idxtype *perm, idxtype *iperm) {  int i, j;  GraphType graph;  CtrlType ctrl;  if (*numflag == 1)    Change2CNumbering(*nvtxs, xadj, adjncy);  SetUpGraph(&graph, OP_OEMETIS, *nvtxs, 1, xadj, adjncy, NULL, NULL, 0);  if (options[0] == 0) {  /* Use the default parameters */    ctrl.CType = OEMETIS_CTYPE;    ctrl.IType = OEMETIS_ITYPE;    ctrl.RType = OEMETIS_RTYPE;    ctrl.dbglvl = OEMETIS_DBGLVL;  }  else {    ctrl.CType = options[OPTION_CTYPE];    ctrl.IType = options[OPTION_ITYPE];    ctrl.RType = options[OPTION_RTYPE];    ctrl.dbglvl = options[OPTION_DBGLVL];  }  ctrl.oflags  = 0;  ctrl.pfactor = -1;  ctrl.nseps   = 1;  ctrl.optype = OP_OEMETIS;  ctrl.CoarsenTo = 20;  ctrl.maxvwgt = 1.5*(idxsum(*nvtxs, graph.vwgt)/ctrl.CoarsenTo);  InitRandom(-1);  AllocateWorkSpace(&ctrl, &graph, 2);  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));  MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, *nvtxs);  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));  for (i=0; i<*nvtxs; i++)    perm[iperm[i]] = i;  FreeWorkSpace(&ctrl, &graph);  if (*numflag == 1)    Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);}

/************************************************************************** This function is the entry point for PWMETIS that accepts exact weights* for the target partitions**************************************************************************/void METIS_WPartGraphRecursive(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,                                idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,                                floattype *tpwgts, int *options, int *edgecut, idxtype *part){  int i, j;  GraphType graph;  CtrlType ctrl;  floattype *mytpwgts;  if (*numflag == 1)    Change2CNumbering(*nvtxs, xadj, adjncy);  SetUpGraph(&graph, OP_PMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, *wgtflag);  if (options[0] == 0) {  /* Use the default parameters */    ctrl.CType = PMETIS_CTYPE;    ctrl.IType = PMETIS_ITYPE;    ctrl.RType = PMETIS_RTYPE;    ctrl.dbglvl = PMETIS_DBGLVL;  }  else {    ctrl.CType = options[OPTION_CTYPE];    ctrl.IType = options[OPTION_ITYPE];    ctrl.RType = options[OPTION_RTYPE];    ctrl.dbglvl = options[OPTION_DBGLVL];  }  ctrl.optype = OP_PMETIS;  ctrl.CoarsenTo = 20;  ctrl.maxvwgt = 1.5*(idxsum(*nvtxs, graph.vwgt)/ctrl.CoarsenTo);  mytpwgts = fmalloc(*nparts, "PWMETIS: mytpwgts");  for (i=0; i<*nparts; i++)     mytpwgts[i] = tpwgts[i];  InitRandom(-1);  AllocateWorkSpace(&ctrl, &graph, *nparts);  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));  *edgecut = MlevelRecursiveBisection(&ctrl, &graph, *nparts, part, mytpwgts, 1.000, 0);  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));  FreeWorkSpace(&ctrl, &graph);  free(mytpwgts);  if (*numflag == 1)    Change2FNumbering(*nvtxs, xadj, adjncy, part);}

/************************************************************************** This function is the entry point for ONWMETIS. It requires weights on the* vertices. It is for the case that the matrix has been pre-compressed.**************************************************************************/void METIS_NodeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,            idxtype *adjwgt, float *ubfactor, int *options, int *sepsize, idxtype *part) {  int i, j, tvwgt, tpwgts[2];  GraphType graph;  CtrlType ctrl;  SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);  tvwgt = idxsum(*nvtxs, graph.vwgt);  if (options[0] == 0) {  /* Use the default parameters */    ctrl.CType  = ONMETIS_CTYPE;    ctrl.IType  = ONMETIS_ITYPE;    ctrl.RType  = ONMETIS_RTYPE;    ctrl.dbglvl = ONMETIS_DBGLVL;  }  else {    ctrl.CType  = options[OPTION_CTYPE];    ctrl.IType  = options[OPTION_ITYPE];    ctrl.RType  = options[OPTION_RTYPE];    ctrl.dbglvl = options[OPTION_DBGLVL];  }  ctrl.oflags    = OFLAG_COMPRESS; /* For by-passing the pre-coarsening for multiple runs */  ctrl.RType     = 2;  /* Standard 1-sided node refinement code */  ctrl.pfactor   = 0;  ctrl.nseps     = 5;  /* This should match NUM_INIT_MSECTIONS in ParMETISLib/defs.h */  ctrl.optype    = OP_ONMETIS;  InitRandom(options[7]);  AllocateWorkSpace(&ctrl, &graph, 2);  /*============================================================   * Perform the bisection   *============================================================*/   tpwgts[0] = tvwgt/2;  tpwgts[1] = tvwgt-tpwgts[0];  MlevelNodeBisectionMultiple(&ctrl, &graph, tpwgts, *ubfactor*.95);  *sepsize = graph.pwgts[2];  idxcopy(*nvtxs, graph.where, part);  GKfree((void **)&graph.gdata, &graph.rdata, &graph.label, LTERM);  FreeWorkSpace(&ctrl, &graph);}

/************************************************************************** This function is the entry point for ONWMETIS. It requires weights on the* vertices. It is for the case that the matrix has been pre-compressed.**************************************************************************/void METIS_NodeComputeSeparator(idxtype *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,            idxtype *adjwgt, idxtype *options, idxtype *sepsize, idxtype *part) {  idxtype i, j, tvwgt, tpwgts[2];  GraphType graph;  CtrlType ctrl;  SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);  tvwgt = idxsum(*nvtxs, graph.vwgt, 1);  if (options[0] == 0) {  /* Use the default parameters */    ctrl.CType = ONMETIS_CTYPE;    ctrl.IType = ONMETIS_ITYPE;    ctrl.RType = ONMETIS_RTYPE;    ctrl.dbglvl = ONMETIS_DBGLVL;  }  else {    ctrl.CType = options[OPTION_CTYPE];    ctrl.IType = options[OPTION_ITYPE];    ctrl.RType = options[OPTION_RTYPE];    ctrl.dbglvl = options[OPTION_DBGLVL];  }  ctrl.oflags  = 0;  ctrl.pfactor = 0;  ctrl.nseps = 3;  ctrl.optype = OP_ONMETIS;  ctrl.CoarsenTo = amin(100, *nvtxs-1);  ctrl.maxvwgt = 1.5*tvwgt/ctrl.CoarsenTo;  InitRandom(options[7]);  AllocateWorkSpace(&ctrl, &graph, 2);  /*============================================================   * Perform the bisection   *============================================================*/   tpwgts[0] = tvwgt/2;  tpwgts[1] = tvwgt-tpwgts[0];  MlevelNodeBisectionMultiple(&ctrl, &graph, tpwgts, 1.02);  *sepsize = graph.pwgts[2];  idxcopy(*nvtxs, graph.where, part);  FreeGraph(&graph, 0);  FreeWorkSpace(&ctrl, &graph);}

/************************************************************************** This function is the entry point for KWMETIS**************************************************************************/void METIS_mCPartGraphKway(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy,                           idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag,                           int *nparts, floattype *rubvec, int *options, int *edgecut,                           idxtype *part){  int i, j;  GraphType graph;  CtrlType ctrl;  if (*numflag == 1)    Change2CNumbering(*nvtxs, xadj, adjncy);  SetUpGraph(&graph, OP_KMETIS, *nvtxs, *ncon, xadj, adjncy, vwgt, adjwgt, *wgtflag);  if (options[0] == 0) {  /* Use the default parameters */    ctrl.CType  = McKMETIS_CTYPE;    ctrl.IType  = McKMETIS_ITYPE;    ctrl.RType  = McKMETIS_RTYPE;    ctrl.dbglvl = McKMETIS_DBGLVL;  }  else {    ctrl.CType  = options[OPTION_CTYPE];    ctrl.IType  = options[OPTION_ITYPE];    ctrl.RType  = options[OPTION_RTYPE];    ctrl.dbglvl = options[OPTION_DBGLVL];  }  ctrl.optype = OP_KMETIS;  ctrl.CoarsenTo = amax((*nvtxs)/(20*log2Int(*nparts)), 30*(*nparts));  ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);  InitRandom(-1);  AllocateWorkSpace(&ctrl, &graph, *nparts);  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));  ASSERT(CheckGraph(&graph));  *edgecut = MCMlevelKWayPartitioning(&ctrl, &graph, *nparts, part, rubvec);  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));  FreeWorkSpace(&ctrl, &graph);  if (*numflag == 1)    Change2FNumbering(*nvtxs, xadj, adjncy, part);}

/************************************************************************** This function is the entry point for KWMETIS with seed specification* in options[7] **************************************************************************/void METIS_WPartGraphKway2(idxtype *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,                           idxtype *adjwgt, idxtype *wgtflag, idxtype *numflag, idxtype *nparts,                           float *tpwgts, idxtype *options, idxtype *edgecut, idxtype *part){  idxtype i, j;  GraphType graph;  CtrlType ctrl;  if (*numflag == 1)    Change2CNumbering(*nvtxs, xadj, adjncy);  SetUpGraph(&graph, OP_KMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, *wgtflag);  if (options[0] == 0) {  /* Use the default parameters */    ctrl.CType = KMETIS_CTYPE;    ctrl.IType = KMETIS_ITYPE;    ctrl.RType = KMETIS_RTYPE;    ctrl.dbglvl = KMETIS_DBGLVL;  }  else {    ctrl.CType = options[OPTION_CTYPE];    ctrl.IType = options[OPTION_ITYPE];    ctrl.RType = options[OPTION_RTYPE];    ctrl.dbglvl = options[OPTION_DBGLVL];  }  ctrl.optype = OP_KMETIS;  ctrl.CoarsenTo = 20*(*nparts);  ctrl.maxvwgt = 1.5*((graph.vwgt ? idxsum(*nvtxs, graph.vwgt, 1) : (*nvtxs))/ctrl.CoarsenTo);  InitRandom(options[7]);  AllocateWorkSpace(&ctrl, &graph, *nparts);  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));  IFSET(ctrl.dbglvl, DBG_TIME, gk_startcputimer(ctrl.TotalTmr));  *edgecut = MlevelKWayPartitioning(&ctrl, &graph, *nparts, part, tpwgts, 1.03);  IFSET(ctrl.dbglvl, DBG_TIME, gk_stopcputimer(ctrl.TotalTmr));  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));  FreeWorkSpace(&ctrl, &graph);  if (*numflag == 1)    Change2FNumbering(*nvtxs, xadj, adjncy, part);}

int METIS_PartGraphKway(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy,           idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts,           real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval,           idx_t *part){  int sigrval=0, renumber=0;  graph_t *graph;  ctrl_t *ctrl;  /* set up malloc cleaning code and signal catchers */  if (!gk_malloc_init())     return METIS_ERROR_MEMORY;  gk_sigtrap();  if ((sigrval = gk_sigcatch()) != 0)    goto SIGTHROW;  /* set up the run parameters */  ctrl = SetupCtrl(METIS_OP_KMETIS, options, *ncon, *nparts, tpwgts, ubvec);  if (!ctrl) {    gk_siguntrap();    return METIS_ERROR_INPUT;  }  /* if required, change the numbering to 0 */  if (ctrl->numflag == 1) {    Change2CNumbering(*nvtxs, xadj, adjncy);    renumber = 1;  }  /* set up the graph */  graph = SetupGraph(ctrl, *nvtxs, *ncon, xadj, adjncy, vwgt, vsize, adjwgt);  /* set up multipliers for making balance computations easier */  SetupKWayBalMultipliers(ctrl, graph);  /* set various run parameters that depend on the graph */  if (ctrl->iptype == METIS_IPTYPE_METISRB) {    ctrl->CoarsenTo = gk_max((*nvtxs)/(40*gk_log2(*nparts)), 30*(*nparts));    ctrl->CoarsenTo = 10*(*nparts);    ctrl->nIparts   = (ctrl->CoarsenTo == 30*(*nparts) ? 4 : 5);  }  else {    ctrl->CoarsenTo = 10*(*nparts);    ctrl->nIparts   = 10;  }  /* take care contiguity requests for disconnected graphs */  if (ctrl->contig && !IsConnected(graph, 0))     gk_errexit(SIGERR, "METIS Error: A contiguous partition is requested for a non-contiguous input graph./n");      /* allocate workspace memory */    AllocateWorkSpace(ctrl, graph);  /* start the partitioning */  IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startwctimer(ctrl->TotalTmr));  *objval = MlevelKWayPartitioning(ctrl, graph, part);  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopwctimer(ctrl->TotalTmr));  IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));  /* clean up */  FreeCtrl(&ctrl);SIGTHROW:  /* if required, change the numbering back to 1 */  if (renumber)    Change2FNumbering(*nvtxs, xadj, adjncy, part);  gk_siguntrap();  gk_malloc_cleanup(0);  return metis_rcode(sigrval);}

idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part){  idx_t i, objval=0, curobj=0, bestobj=0;  real_t curbal=0.0, bestbal=0.0;  graph_t *cgraph;  for (i=0; i<ctrl->ncuts; i++) {    cgraph = CoarsenGraph(ctrl, graph);    IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startwctimer(ctrl->InitPartTmr));    AllocateKWayPartitionMemory(ctrl, cgraph);    /* Compute the initial partitioning */    switch (ctrl->iptype) {      case METIS_IPTYPE_METISRB:        FreeWorkSpace(ctrl); /* Release the work space, for the recursive metis call */        InitKWayPartitioningRB(ctrl, cgraph);        AllocateWorkSpace(ctrl, graph); /* Re-allocate the work space */        break;      case METIS_IPTYPE_GROW:        AllocateRefinementWorkSpace(ctrl, 2*cgraph->nedges);        InitKWayPartitioningGrow(ctrl, cgraph);        break;      default:        gk_errexit(SIGERR, "Unknown iptype: %d/n", ctrl->iptype);    }    IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopwctimer(ctrl->InitPartTmr));    IFSET(ctrl->dbglvl, METIS_DBG_IPART, printf("Initial %"PRIDX /          "-way partitioning cut: %"PRIDX"/n", ctrl->nparts, objval));    RefineKWay(ctrl, graph, cgraph);    switch (ctrl->objtype) {      case METIS_OBJTYPE_CUT:        curobj = graph->mincut;        break;      case METIS_OBJTYPE_VOL:        curobj = graph->minvol;        break;      default:        gk_errexit(SIGERR, "Unknown objtype: %d/n", ctrl->objtype);    }    curbal = ComputeLoadImbalanceDiff(graph, ctrl->nparts, ctrl->pijbm, ctrl->ubfactors);    if (i == 0         || (curbal <= 0.0005 && bestobj > curobj)        || (bestbal > 0.0005 && curbal < bestbal)) {      icopy(graph->nvtxs, graph->where, part);      bestobj = curobj;      bestbal = curbal;    }    FreeRData(graph);    if (bestobj == 0)      break;  }  FreeGraph(&graph);  return bestobj;}

int METIS_NodeND(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,          idx_t *options, idx_t *perm, idx_t *iperm) {  int sigrval=0, renumber=0;  idx_t i, ii, j, l, nnvtxs=0;  graph_t *graph=NULL;  ctrl_t *ctrl;  idx_t *cptr, *cind, *piperm;  int numflag = 0;  /* set up malloc cleaning code and signal catchers */  if (!gk_malloc_init())     return METIS_ERROR_MEMORY;  gk_sigtrap();  if ((sigrval = gk_sigcatch()) != 0)     goto SIGTHROW;  /* set up the run time parameters */  ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL);  if (!ctrl) {    gk_siguntrap();    return METIS_ERROR_INPUT;  }  /* if required, change the numbering to 0 */  if (ctrl->numflag == 1) {    Change2CNumbering(*nvtxs, xadj, adjncy);    renumber = 1;  }  IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));  /* prune the dense columns */  if (ctrl->pfactor > 0.0) {     piperm = imalloc(*nvtxs, "OMETIS: piperm");    graph = PruneGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, piperm, ctrl->pfactor);    if (graph == NULL) {      /* if there was no prunning, cleanup the pfactor */      gk_free((void **)&piperm, LTERM);      ctrl->pfactor = 0.0;    }    else {      nnvtxs = graph->nvtxs;      ctrl->compress = 0;  /* disable compression if prunning took place */    }  }  /* compress the graph; note that compression only happens if not prunning      has taken place. */  if (ctrl->compress) {     cptr = imalloc(*nvtxs+1, "OMETIS: cptr");    cind = imalloc(*nvtxs, "OMETIS: cind");    graph = CompressGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, cptr, cind);    if (graph == NULL) {      /* if there was no compression, cleanup the compress flag */      gk_free((void **)&cptr, &cind, LTERM);      ctrl->compress = 0;     }    else {      nnvtxs = graph->nvtxs;      ctrl->cfactor = 1.0*(*nvtxs)/nnvtxs;      if (ctrl->cfactor > 1.5 && ctrl->nseps == 1)        ctrl->nseps = 2;      //ctrl->nseps = (idx_t)(ctrl->cfactor*ctrl->nseps);    }  }  /* if no prunning and no compression, setup the graph in the normal way. */  if (ctrl->pfactor == 0.0 && ctrl->compress == 0)     graph = SetupGraph(ctrl, *nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);  ASSERT(CheckGraph(graph, ctrl->numflag, 1));  /* allocate workspace memory */  AllocateWorkSpace(ctrl, graph);  /* do the nested dissection ordering  */  if (ctrl->ccorder)     MlevelNestedDissectionCC(ctrl, graph, iperm, graph->nvtxs);  else    MlevelNestedDissection(ctrl, graph, iperm, graph->nvtxs);  if (ctrl->pfactor > 0.0) { /* Order any prunned vertices */    icopy(nnvtxs, iperm, perm);  /* Use perm as an auxiliary array */    for (i=0; i<nnvtxs; i++)      iperm[piperm[i]] = perm[i];    for (i=nnvtxs; i<*nvtxs; i++)      iperm[piperm[i]] = i;    gk_free((void **)&piperm, LTERM);  }  else if (ctrl->compress) { /* Uncompress the ordering */    /* construct perm from iperm *///.........这里部分代码省略.........

/************************************************************************** This function is the entry point for ONCMETIS**************************************************************************/void METIS_NodeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options,                   idxtype *perm, idxtype *iperm) {  int i, ii, j, l, wflag, nflag;  GraphType graph;  CtrlType ctrl;  idxtype *cptr, *cind, *piperm;  if (*numflag == 1)    Change2CNumbering(*nvtxs, xadj, adjncy);  if (options[0] == 0) {  /* Use the default parameters */    ctrl.CType   = ONMETIS_CTYPE;    ctrl.IType   = ONMETIS_ITYPE;    ctrl.RType   = ONMETIS_RTYPE;    ctrl.dbglvl  = ONMETIS_DBGLVL;    ctrl.oflags  = ONMETIS_OFLAGS;    ctrl.pfactor = ONMETIS_PFACTOR;    ctrl.nseps   = ONMETIS_NSEPS;  }  else {    ctrl.CType   = options[OPTION_CTYPE];    ctrl.IType   = options[OPTION_ITYPE];    ctrl.RType   = options[OPTION_RTYPE];    ctrl.dbglvl  = options[OPTION_DBGLVL];    ctrl.oflags  = options[OPTION_OFLAGS];    ctrl.pfactor = options[OPTION_PFACTOR];    ctrl.nseps   = options[OPTION_NSEPS];  }  if (ctrl.nseps < 1)    ctrl.nseps = 1;  ctrl.optype = OP_ONMETIS;  ctrl.CoarsenTo = 100;  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));  InitRandom(-1);  if (ctrl.pfactor > 0) {     /*============================================================    * Prune the dense columns    ==============================================================*/    piperm = idxmalloc(*nvtxs, "ONMETIS: piperm");    PruneGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, piperm, (float)(0.1*ctrl.pfactor));  }  else if (ctrl.oflags&OFLAG_COMPRESS) {    /*============================================================    * Compress the graph     ==============================================================*/    cptr = idxmalloc(*nvtxs+1, "ONMETIS: cptr");    cind = idxmalloc(*nvtxs, "ONMETIS: cind");    CompressGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, cptr, cind);    if (graph.nvtxs >= COMPRESSION_FRACTION*(*nvtxs)) {      ctrl.oflags--; /* We actually performed no compression */      GKfree(&cptr, &cind, LTERM);    }    else if (2*graph.nvtxs < *nvtxs && ctrl.nseps == 1)      ctrl.nseps = 2;  }  else {    SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, NULL, NULL, 0);  }  /*=============================================================  * Do the nested dissection ordering   --=============================================================*/  ctrl.maxvwgt = 1.5*(idxsum(graph.nvtxs, graph.vwgt)/ctrl.CoarsenTo);  AllocateWorkSpace(&ctrl, &graph, 2);  if (ctrl.oflags&OFLAG_CCMP)     MlevelNestedDissectionCC(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, graph.nvtxs);  else    MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, graph.nvtxs);  FreeWorkSpace(&ctrl, &graph);  if (ctrl.pfactor > 0) { /* Order any prunned vertices */    if (graph.nvtxs < *nvtxs) {       idxcopy(graph.nvtxs, iperm, perm);  /* Use perm as an auxiliary array */      for (i=0; i<graph.nvtxs; i++)        iperm[piperm[i]] = perm[i];      for (i=graph.nvtxs; i<*nvtxs; i++)        iperm[piperm[i]] = i;    }    GKfree(&piperm, LTERM);  }  else if (ctrl.oflags&OFLAG_COMPRESS) { /* Uncompress the ordering */    if (graph.nvtxs < COMPRESSION_FRACTION*(*nvtxs)) {       /* construct perm from iperm */      for (i=0; i<graph.nvtxs; i++)//.........这里部分代码省略.........

/*************************************************************************** mexFunction: gateway routine for MATLAB interface.***************************************************************************/void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]){        // Argument checking    if (nrhs != 5)        mexErrMsgIdAndTxt(FUNC_NAME, "Wrong input.");    if (nlhs != 3)        mexErrMsgIdAndTxt(FUNC_NAME, "Wrong output.");        // Input and output variables    idx_t nvtxs = (idx_t) mxGetScalar(nvtxs_in);    idx_t *xadj; GetIdxArray(xadj_in,&xadj);    idx_t *adjncy; GetIdxArray(adjncy_in,&adjncy);    idx_t *vwgt; GetIdxArray(vwgt_in,&vwgt);    idx_t options[METIS_NOPTIONS];    GetOptions(options_in, options);    idx_t *sepidx;    idx_t *lgraphidx;    idx_t *rgraphidx;        // Metis main function    idx_t i, nnvtxs=0;    idx_t ptlgraph, ptrgraph, ptsep;    graph_t *graph=NULL;    ctrl_t *ctrl;    idx_t *piperm;    idx_t snvtxs[3];    idx_t *where;    /* set up malloc cleaning code and signal catchers */    if (!gk_malloc_init())         CheckReturn( METIS_ERROR_MEMORY, FUNC_NAME );    // set up the run time parameters    ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL);    // prune the dense columns    if (ctrl->pfactor > 0.0)    {         piperm = imalloc(nvtxs, "OMETIS: piperm");        graph = PruneGraph(ctrl, nvtxs, xadj, adjncy, vwgt,                piperm, ctrl->pfactor);        if (graph == NULL)        {            // if there was no prunning, cleanup the pfactor            gk_free((void **)&piperm, LTERM);            ctrl->pfactor = 0.0;        }        else        {            nnvtxs = graph->nvtxs;            // disable compression if prunning took place            ctrl->compress = 0;        }    }    // compress the graph    if (ctrl->compress)        ctrl->compress = 0;     // if no prunning and no compression, setup the graph in the normal way.    if (ctrl->pfactor == 0.0 && ctrl->compress == 0)         graph = SetupGraph(ctrl, nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);    ASSERT(CheckGraph(graph, ctrl->numflag, 1));    /* allocate workspace memory */    AllocateWorkSpace(ctrl, graph);    MlevelNodeBisectionMultiple(ctrl, graph);    snvtxs[0] = 0;    snvtxs[1] = 0;    snvtxs[2] = 0;    if (ctrl->pfactor > 0.0)        snvtxs[2] += nvtxs-nnvtxs;    where = graph->where;    for (i=0; i<graph->nvtxs; i++)        snvtxs[where[i]]++;    lgraphidx = (idx_t*) mxCalloc (snvtxs[0], sizeof(idx_t));    rgraphidx = (idx_t*) mxCalloc (snvtxs[1], sizeof(idx_t));    sepidx    = (idx_t*) mxCalloc (snvtxs[2], sizeof(idx_t));    ptlgraph = 0;    ptrgraph = 0;    ptsep    = 0;    if (ctrl->pfactor > 0.0)    {        for (i=0; i<graph->nvtxs; i++)            if (where[i] == 0)                lgraphidx[ptlgraph++] = piperm[i];//.........这里部分代码省略.........