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

//.........这里部分代码省略.........        u[1] = PQueueSeeMax(&parts[1]);        if (u[0] != -1 && u[1] != -1) {          g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];          g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];          to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2));         }      }      other = (to+1)%2;      if ((higain = PQueueGetMax(&parts[to])) == -1)        break;      if (moved[higain] == -1) /* Delete if it was in the separator originally */        PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);      ASSERT(bndptr[higain] != -1);      pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);      newdiff = idxtype_abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));      if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {        mincut = pwgts[2];        mincutorder = nswaps;        mindiff = newdiff;      }      else {        if (nswaps - mincutorder > limit) {          pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);          break; /* No further improvement, break out */        }      }      BNDDelete(nbnd, bndind, bndptr, higain);      pwgts[to] += vwgt[higain];      where[higain] = to;      moved[higain] = nswaps;      swaps[nswaps] = higain;        /**********************************************************      * Update the degrees of the affected nodes      ***********************************************************/      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */          oldgain = vwgt[k]-rinfo[k].edegrees[to];          rinfo[k].edegrees[to] += vwgt[higain];          if (moved[k] == -1 || moved[k] == -(2+other))            PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);        }        else if (where[k] == other) { /* This vertex is pulled into the separator */          ASSERTP(bndptr[k] == -1, ("%d %d %d/n", k, bndptr[k], where[k]));          BNDInsert(nbnd, bndind, bndptr, k);          mind[nmind++] = k;  /* Keep track for rollback */          where[k] = 2;          pwgts[other] -= vwgt[k];          edegrees = rinfo[k].edegrees;          edegrees[0] = edegrees[1] = 0;          for (jj=xadj[k]; jj<xadj[k+1]; jj++) {            kk = adjncy[jj];            if (where[kk] != 2)               edegrees[where[kk]] += vwgt[kk];            else {

/************************************************************************** This function performs a node-based FM refinement. This is the * one-way version **************************************************************************/void FM_2WayNodeRefine_OneSided(CtrlType *ctrl, GraphType *graph, float ubfactor, idxtype npasses){  idxtype i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;  idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;  idxtype *mptr, *mind, *swaps, *perm;  PQueueType parts;   NRInfoType *rinfo;  idxtype higain, oldgain, mincut, initcut, mincutorder;	  idxtype pass, to, other, limit;  idxtype badmaxpwgt, mindiff, newdiff;  nvtxs = graph->nvtxs;  xadj = graph->xadj;  adjncy = graph->adjncy;  vwgt = graph->vwgt;  bndind = graph->bndind;  bndptr = graph->bndptr;  where = graph->where;  pwgts = graph->pwgts;  rinfo = graph->nrinfo;  PQueueInit(ctrl, &parts, nvtxs, ComputeMaxNodeGain(nvtxs, xadj, adjncy, vwgt));  perm  = idxwspacemalloc(ctrl, nvtxs);  swaps = idxwspacemalloc(ctrl, nvtxs);  mptr  = idxwspacemalloc(ctrl, nvtxs+1);  mind  = idxwspacemalloc(ctrl, nvtxs);  IFSET(ctrl->dbglvl, DBG_REFINE,    mprintf("Partitions-N1: [%6D %6D] Nv-Nb[%6D %6D]. ISep: %6D/n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));  badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2])/2);  to = (pwgts[0] < pwgts[1] ? 1 : 0);  for (pass=0; pass<npasses; pass++) {    other = to;     to = (to+1)%2;    PQueueReset(&parts);    mincutorder = -1;    initcut = mincut = graph->mincut;    nbnd = graph->nbnd;    RandomPermute(nbnd, perm, 1);    for (ii=0; ii<nbnd; ii++) {      i = bndind[perm[ii]];      ASSERT(where[i] == 2);      PQueueInsert(&parts, i, vwgt[i]-rinfo[i].edegrees[other]);    }    ASSERT(CheckNodeBnd(graph, nbnd));    ASSERT(CheckNodePartitionParams(graph));    limit = (ctrl->oflags&OFLAG_COMPRESS ? amin(5*nbnd, 400) : amin(2*nbnd, 300));    /******************************************************    * Get into the FM loop    *******************************************************/    mptr[0] = nmind = 0;    mindiff = idxtype_abs(pwgts[0]-pwgts[1]);    for (nswaps=0; nswaps<nvtxs; nswaps++) {      if ((higain = PQueueGetMax(&parts)) == -1)        break;      ASSERT(bndptr[higain] != -1);      if (pwgts[to]+vwgt[higain] > badmaxpwgt)        break;  /* No point going any further. Balance will be bad */      pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);      newdiff = idxtype_abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));      if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {        mincut = pwgts[2];        mincutorder = nswaps;        mindiff = newdiff;      }      else {        if (nswaps - mincutorder > limit) {          pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);          break; /* No further improvement, break out */        }      }      BNDDelete(nbnd, bndind, bndptr, higain);      pwgts[to] += vwgt[higain];      where[higain] = to;      swaps[nswaps] = higain;        /**********************************************************      * Update the degrees of the affected nodes      ***********************************************************///.........这里部分代码省略.........

//.........这里部分代码省略.........      /*=====================================================================      * If we got here, we can now move the vertex from 'from' to 'to'       *======================================================================*/      graph->mincut -= myedegrees[k].ed-myrinfo->id;      IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("/t/tMoving %6d to %3d. Gain: %4d. Cut: %6d/n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));      /* Update pmat to reflect the move of 'i' */      pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);      pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);      if (pmat[from*nparts+to] == 0) {        ndoms[from]--;        if (ndoms[from]+1 == maxndoms)          maxndoms = ndoms[idxamax(nparts, ndoms)];      }      if (pmat[to*nparts+from] == 0) {        ndoms[to]--;        if (ndoms[to]+1 == maxndoms)          maxndoms = ndoms[idxamax(nparts, ndoms)];      }      /* Update where, weight, and ID/ED information of the vertex you moved */      where[i] = to;      INC_DEC(pwgts[to], pwgts[from], vwgt);      myrinfo->ed += myrinfo->id-myedegrees[k].ed;      SWAP(myrinfo->id, myedegrees[k].ed, j);      if (myedegrees[k].ed == 0)         myedegrees[k] = myedegrees[--myrinfo->ndegrees];      else        myedegrees[k].pid = from;      if (myrinfo->ed == 0)        BNDDelete(nbnd, bndind, bndptr, i);      /* Update the degrees of adjacent vertices */      for (j=xadj[i]; j<xadj[i+1]; j++) {        ii = adjncy[j];        me = where[ii];        myrinfo = graph->rinfo+ii;        if (myrinfo->edegrees == NULL) {          myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;          ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];        }        myedegrees = myrinfo->edegrees;        ASSERT(CheckRInfo(myrinfo));        oldgain = (myrinfo->ed-myrinfo->id);        if (me == from) {          INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);          if (myrinfo->ed > 0 && bndptr[ii] == -1)            BNDInsert(nbnd, bndind, bndptr, ii);        }        else if (me == to) {          INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);          if (myrinfo->ed == 0 && bndptr[ii] != -1)            BNDDelete(nbnd, bndind, bndptr, ii);        }        /* Remove contribution from the .ed of 'from' */        if (me != from) {

void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter){  idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind, iend;  idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;  idx_t *mptr, *mind, *swaps;  rpq_t *queue;   nrinfo_t *rinfo;  idx_t higain, mincut, initcut, mincutorder;	  idx_t pass, to, other, limit;  idx_t badmaxpwgt, mindiff, newdiff;  real_t mult;  WCOREPUSH;  nvtxs  = graph->nvtxs;  xadj   = graph->xadj;  adjncy = graph->adjncy;  vwgt   = graph->vwgt;  bndind = graph->bndind;  bndptr = graph->bndptr;  where  = graph->where;  pwgts  = graph->pwgts;  rinfo  = graph->nrinfo;  queue = rpqCreate(nvtxs);  swaps = iwspacemalloc(ctrl, nvtxs);  mptr  = iwspacemalloc(ctrl, nvtxs+1);  mind  = iwspacemalloc(ctrl, 2*nvtxs);  mult = 0.5*ctrl->ubfactors[0];  badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,    printf("Partitions-N1: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"/n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));  to = (pwgts[0] < pwgts[1] ? 1 : 0);  for (pass=0; pass<2*niter; pass++) {  /* the 2*niter is for the two sides */    other = to;     to    = (to+1)%2;    rpqReset(queue);    mincutorder = -1;    initcut = mincut = graph->mincut;    nbnd = graph->nbnd;    /* use the swaps array in place of the traditional perm array to save memory */    my_irandArrayPermute_r(nbnd, swaps, nbnd, 1, &ctrl->curseed);    for (ii=0; ii<nbnd; ii++) {      i = bndind[swaps[ii]];      ASSERT(where[i] == 2);      rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);    }    ASSERT(CheckNodeBnd(graph, nbnd));    ASSERT(CheckNodePartitionParams(graph));    limit = (ctrl->compress ? gk_min(5*nbnd, 500) : gk_min(3*nbnd, 300));    /******************************************************    * Get into the FM loop    *******************************************************/    IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startwctimer(ctrl->Aux3Tmr));    mptr[0] = nmind = 0;    mindiff = iabs(pwgts[0]-pwgts[1]);    for (nswaps=0; nswaps<nvtxs; nswaps++) {      if ((higain = rpqGetTop(queue)) == -1)        break;      ASSERT(bndptr[higain] != -1);      /* The following check is to ensure we break out if there is a posibility         of over-running the mind array.  */      if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)         break;      if (pwgts[to]+vwgt[higain] > badmaxpwgt)         break;  /* No point going any further. Balance will be bad */      pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);      newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));      if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {        mincut      = pwgts[2];        mincutorder = nswaps;        mindiff     = newdiff;      }      else {        if (nswaps - mincutorder > 3*limit ||             (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {          pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);          break; /* No further improvement, break out */        }      }      BNDDelete(nbnd, bndind, bndptr, higain);      pwgts[to]     += vwgt[higain];      where[higain]  = to;//.........这里部分代码省略.........

void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter){    idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, limit, tmp;    idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;    idx_t *moved, *swaps, *perm;    rpq_t *queues[2];    idx_t higain, mincut, mindiff, origdiff, initcut, newcut, mincutorder, avgvwgt;    idx_t tpwgts[2];    WCOREPUSH;    nvtxs  = graph->nvtxs;    xadj   = graph->xadj;    vwgt   = graph->vwgt;    adjncy = graph->adjncy;    adjwgt = graph->adjwgt;    where  = graph->where;    id     = graph->id;    ed     = graph->ed;    pwgts  = graph->pwgts;    bndptr = graph->bndptr;    bndind = graph->bndind;    moved = iwspacemalloc(ctrl, nvtxs);    swaps = iwspacemalloc(ctrl, nvtxs);    perm  = iwspacemalloc(ctrl, nvtxs);    tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];    tpwgts[1] = graph->tvwgt[0]-tpwgts[0];    limit   = gk_min(gk_max(0.01*nvtxs, 15), 100);    avgvwgt = gk_min((pwgts[0]+pwgts[1])/20, 2*(pwgts[0]+pwgts[1])/nvtxs);    queues[0] = rpqCreate(nvtxs);    queues[1] = rpqCreate(nvtxs);    IFSET(ctrl->dbglvl, METIS_DBG_REFINE,          Print2WayRefineStats(ctrl, graph, ntpwgts, 0, -2));    origdiff = iabs(tpwgts[0]-pwgts[0]);    iset(nvtxs, -1, moved);    for (pass=0; pass<niter; pass++) { /* Do a number of passes */        rpqReset(queues[0]);        rpqReset(queues[1]);        mincutorder = -1;        newcut = mincut = initcut = graph->mincut;        mindiff = iabs(tpwgts[0]-pwgts[0]);        ASSERT(ComputeCut(graph, where) == graph->mincut);        ASSERT(CheckBnd(graph));        /* Insert boundary nodes in the priority queues */        nbnd = graph->nbnd;        irandArrayPermute(nbnd, perm, nbnd, 1);        for (ii=0; ii<nbnd; ii++) {            i = perm[ii];            ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);            ASSERT(bndptr[bndind[i]] != -1);            rpqInsert(queues[where[bndind[i]]], bndind[i], ed[bndind[i]]-id[bndind[i]]);        }        for (nswaps=0; nswaps<nvtxs; nswaps++) {            from = (tpwgts[0]-pwgts[0] < tpwgts[1]-pwgts[1] ? 0 : 1);            to = (from+1)%2;            if ((higain = rpqGetTop(queues[from])) == -1)                break;            ASSERT(bndptr[higain] != -1);            newcut -= (ed[higain]-id[higain]);            INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);            if ((newcut < mincut && iabs(tpwgts[0]-pwgts[0]) <= origdiff+avgvwgt) ||                    (newcut == mincut && iabs(tpwgts[0]-pwgts[0]) < mindiff)) {                mincut  = newcut;                mindiff = iabs(tpwgts[0]-pwgts[0]);                mincutorder = nswaps;            }            else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */                newcut += (ed[higain]-id[higain]);                INC_DEC(pwgts[from], pwgts[to], vwgt[higain]);                break;            }            where[higain] = to;            moved[higain] = nswaps;            swaps[nswaps] = higain;            IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,                  printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]/n", higain, from, ed[higain]-id[higain], vwgt[higain], newcut, pwgts[0], pwgts[1]));            /**************************************************************            * Update the id[i]/ed[i] values of the affected nodes            ***************************************************************/            SWAP(id[higain], ed[higain], tmp);            if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])                BNDDelete(nbnd, bndind,  bndptr, higain);            for (j=xadj[higain]; j<xadj[higain+1]; j++) {//.........这里部分代码省略.........

//.........这里部分代码省略.........        j++;      if (!AreAllHVwgtsAbove(ncon, 1.0, npwgts+to*ncon, 0.0, nvwgt, minwgt+to*ncon) &&          AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon))        j++;      if (j == 0)        continue;/* DELETE      if (myedegrees[k].ed-myrinfo->id < 0 &&           AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, maxwgt+from*ncon) &&          AreAllHVwgtsAbove(ncon, 1.0, npwgts+to*ncon, 0.0, nvwgt, minwgt+to*ncon) &&          AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon))        continue;*/      /*=====================================================================      * If we got here, we can now move the vertex from 'from' to 'to'       *======================================================================*/      graph->mincut -= myedegrees[k].ed-myrinfo->id;      IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("/t/tMoving %6d to %3d. Gain: %4d. Cut: %6d/n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));      /* Update where, weight, and ID/ED information of the vertex you moved */      saxpy(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);      saxpy(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);      where[i] = to;      myrinfo->ed += myrinfo->id-myedegrees[k].ed;      SWAP(myrinfo->id, myedegrees[k].ed, j);      if (myedegrees[k].ed == 0)         myedegrees[k] = myedegrees[--myrinfo->ndegrees];      else        myedegrees[k].pid = from;      if (myrinfo->ed == 0)        BNDDelete(nbnd, bndind, bndptr, i);      /* Update the degrees of adjacent vertices */      for (j=xadj[i]; j<xadj[i+1]; j++) {        ii = adjncy[j];        me = where[ii];        myrinfo = graph->rinfo+ii;        if (myrinfo->edegrees == NULL) {          myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;          ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];        }        myedegrees = myrinfo->edegrees;        ASSERT(CheckRInfo(myrinfo));        oldgain = (myrinfo->ed-myrinfo->id);        if (me == from) {          INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);          if (myrinfo->ed > 0 && bndptr[ii] == -1)            BNDInsert(nbnd, bndind, bndptr, ii);        }        else if (me == to) {          INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);          if (myrinfo->ed == 0 && bndptr[ii] != -1)            BNDDelete(nbnd, bndind, bndptr, ii);        }        /* Remove contribution from the .ed of 'from' */        if (me != from) {

/************************************************************************** This function performs an edge-based FM refinement**************************************************************************/void FM_2WayEdgeRefine(CtrlType *ctrl, GraphType *graph, int *tpwgts, int npasses){  int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, limit, tmp;  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;  idxtype *moved, *swaps, *perm;  PQueueType parts[2];  int higain, oldgain, mincut, mindiff, origdiff, initcut, newcut, mincutorder, avgvwgt;  nvtxs = graph->nvtxs;  xadj = graph->xadj;  vwgt = graph->vwgt;  adjncy = graph->adjncy;  adjwgt = graph->adjwgt;  where = graph->where;  id = graph->id;  ed = graph->ed;  pwgts = graph->pwgts;  bndptr = graph->bndptr;  bndind = graph->bndind;  moved = idxwspacemalloc(ctrl, nvtxs);  swaps = idxwspacemalloc(ctrl, nvtxs);  perm = idxwspacemalloc(ctrl, nvtxs);  limit = (int) amin(amax(0.01*nvtxs, 15), 100);  avgvwgt = amin((pwgts[0]+pwgts[1])/20, 2*(pwgts[0]+pwgts[1])/nvtxs);  tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];  PQueueInit(ctrl, &parts[0], nvtxs, tmp);  PQueueInit(ctrl, &parts[1], nvtxs, tmp);  IFSET(ctrl->dbglvl, DBG_REFINE,      printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d/n",             pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));  origdiff = abs(tpwgts[0]-pwgts[0]);  idxset(nvtxs, -1, moved);  for (pass=0; pass<npasses; pass++) { /* Do a number of passes */    PQueueReset(&parts[0]);    PQueueReset(&parts[1]);    mincutorder = -1;    newcut = mincut = initcut = graph->mincut;    mindiff = abs(tpwgts[0]-pwgts[0]);    ASSERT(ComputeCut(graph, where) == graph->mincut);    ASSERT(CheckBnd(graph));    /* Insert boundary nodes in the priority queues */    nbnd = graph->nbnd;    RandomPermute(nbnd, perm, 1);    for (ii=0; ii<nbnd; ii++) {      i = perm[ii];      ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);      ASSERT(bndptr[bndind[i]] != -1);      PQueueInsert(&parts[where[bndind[i]]], bndind[i], ed[bndind[i]]-id[bndind[i]]);    }    for (nswaps=0; nswaps<nvtxs; nswaps++) {      from = (tpwgts[0]-pwgts[0] < tpwgts[1]-pwgts[1] ? 0 : 1);      to = (from+1)%2;      if ((higain = PQueueGetMax(&parts[from])) == -1)        break;      ASSERT(bndptr[higain] != -1);      newcut -= (ed[higain]-id[higain]);      INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);      if ((newcut < mincut && abs(tpwgts[0]-pwgts[0]) <= origdiff+avgvwgt) ||           (newcut == mincut && abs(tpwgts[0]-pwgts[0]) < mindiff)) {        mincut = newcut;        mindiff = abs(tpwgts[0]-pwgts[0]);        mincutorder = nswaps;      }      else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */        newcut += (ed[higain]-id[higain]);        INC_DEC(pwgts[from], pwgts[to], vwgt[higain]);        break;      }      where[higain] = to;      moved[higain] = nswaps;      swaps[nswaps] = higain;      IFSET(ctrl->dbglvl, DBG_MOVEINFO,         printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]/n", higain, from, ed[higain]-id[higain], vwgt[higain], newcut, pwgts[0], pwgts[1]));      /**************************************************************      * Update the id[i]/ed[i] values of the affected nodes      ***************************************************************/      SWAP(id[higain], ed[higain], tmp);      if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])         BNDDelete(nbnd, bndind,  bndptr, higain);      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];//.........这里部分代码省略.........

//.........这里部分代码省略.........    }    else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */      newcut += (ed[higain]-id[higain]);      saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);      saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);      break;    }    where[higain] = to;    moved[higain] = nswaps;    swaps[nswaps] = higain;    if (ctrl->dbglvl&DBG_MOVEINFO) {      printf("Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);      for (i=0; i<ncon; i++)         printf("(%.3f, %.3f) ", npwgts[i], npwgts[ncon+i]);      Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, tvec);      printf(", LB: ");      for (i=0; i<ncon; i++)         printf("%.3f ", tvec[i]);      if (mincutorder == nswaps)        printf(" */n");      else        printf("/n");    }    /**************************************************************    * Update the id[i]/ed[i] values of the affected nodes    ***************************************************************/    SWAP(id[higain], ed[higain], tmp);    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])       BNDDelete(nbnd, bndind,  bndptr, higain);    if (ed[higain] > 0 && bndptr[higain] == -1)      BNDInsert(nbnd, bndind,  bndptr, higain);    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      oldgain = ed[k]-id[k];      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);      INC_DEC(id[k], ed[k], kwgt);      /* Update the queue position */      if (moved[k] == -1)        PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-id[k]);      /* Update its boundary information */      if (ed[k] == 0 && bndptr[k] != -1)         BNDDelete(nbnd, bndind, bndptr, k);      else if (ed[k] > 0 && bndptr[k] == -1)          BNDInsert(nbnd, bndind, bndptr, k);    }     }  /****************************************************************  * Roll back computations  *****************************************************************/  for (i=0; i<nswaps; i++)    moved[swaps[i]] = -1;  /* reset moved array */  for (nswaps--; nswaps>mincutorder; nswaps--) {    higain = swaps[nswaps];

//.........这里部分代码省略.........        to = 0;      }      else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {        to = 1;      }      else        break;      other = (to+1)%2;      higain = PQueueGetMax(&parts[to]);      /* Delete its matching entry in the other queue */      if (moved[higain] == -5)         PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);      ASSERT(bndptr[higain] != -1);      pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);      newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));      if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {        mincut      = pwgts[2];        mincutorder = nswaps;        mindiff     = newdiff;      }      else {        if (nswaps - mincutorder > limit) {          pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);          break; /* No further improvement, break out */        }      }      BNDDelete(nbnd, bndind, bndptr, higain);      pwgts[to] += vwgt[higain];      where[higain] = to;      moved[higain] = nswaps;      swaps[nswaps] = higain;        /**********************************************************      * Update the degrees of the affected nodes      ***********************************************************/      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */          oldgain = vwgt[k]-rinfo[k].edegrees[to];          rinfo[k].edegrees[to] += vwgt[higain];          if (moved[k] == -5 || moved[k] == -(10+other))             PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);        }        else if (where[k] == other) { /* This vertex is pulled into the separator */          ASSERTP(bndptr[k] == -1, ("%d %d %d/n", k, bndptr[k], where[k]));          BNDInsert(nbnd, bndind, bndptr, k);          mind[nmind++] = k;  /* Keep track for rollback */          where[k] = 2;          pwgts[other] -= vwgt[k];          edegrees = rinfo[k].edegrees;          edegrees[0] = edegrees[1] = 0;          for (jj=xadj[k]; jj<xadj[k+1]; jj++) {            kk = adjncy[jj];            if (where[kk] != 2)               edegrees[where[kk]] += vwgt[kk];            else {

//.........这里部分代码省略.........                                (newbal == minbal && BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {        mincut = newcut;        minbal = newbal;        mincutorder = nswaps;        for (i=0; i<ncon; i++)          mindiff[i] = fabs(tpwgts[0]-npwgts[i]);      }      else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */        newcut += (ed[higain]-id[higain]);        saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);        saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);        break;      }      where[higain] = to;      moved[higain] = nswaps;      swaps[nswaps] = higain;/*      if (ctrl->dbglvl&DBG_MOVEINFO) {        printf("Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);        for (l=0; l<ncon; l++)           printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);        printf(", %.3f LB: %.3f/n", minbal, newbal);      }*/      /**************************************************************      * Update the id[i]/ed[i] values of the affected nodes      ***************************************************************/      SWAP(id[higain], ed[higain], tmp);      if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])         BNDDelete(nbnd, bndind,  bndptr, higain);      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        oldgain = ed[k]-id[k];        kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);        INC_DEC(id[k], ed[k], kwgt);        /* Update its boundary information and queue position */        if (bndptr[k] != -1) { /* If k was a boundary vertex */          if (ed[k] == 0) { /* Not a boundary vertex any more */            BNDDelete(nbnd, bndind, bndptr, k);            if (moved[k] == -1)  /* Remove it if in the queues */              PQueueDelete(&parts[qnum[k]][where[k]], k, oldgain);          }          else { /* If it has not been moved, update its position in the queue */            if (moved[k] == -1)              PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-id[k]);          }        }        else {          if (ed[k] > 0) {  /* It will now become a boundary vertex */            BNDInsert(nbnd, bndind, bndptr, k);            if (moved[k] == -1)               PQueueInsert(&parts[qnum[k]][where[k]], k, ed[k]-id[k]);          }        }      }    }

//.........这里部分代码省略.........    for (nswaps=0; nswaps<nvtxs; nswaps++) {      if ((higain = PQueueGetMax(&parts)) == -1)         break;      inqueue[higain] = -1;      ASSERT(bndptr[higain] != -1);      if (pwgts[to]+vwgt[higain] > badmaxpwgt) { /* Skip this vertex */        if (nbad++ > limit)           break;         else {          nswaps--;          continue;          }      }      pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[from]);      newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[from]-rinfo[higain].edegrees[from]));      if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {        mincut      = pwgts[2];        mincutorder = nswaps;        mindiff     = newdiff;        nbad        = 0;      }      else {        if (nbad++ > limit) {          pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[from]);          break; /* No further improvement, break out */        }      }      BNDDelete(nbnd, bndind, bndptr, higain);      pwgts[to] += vwgt[higain];      where[higain] = to;      swaps[nswaps] = higain;        /**********************************************************      * Update the degrees of the affected nodes      ***********************************************************/      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */          rinfo[k].edegrees[to] += vwgt[higain];        }        else if (where[k] == from) { /* This vertex is pulled into the separator */          ASSERTP(bndptr[k] == -1, ("%d %d %d/n", k, bndptr[k], where[k]));          BNDInsert(nbnd, bndind, bndptr, k);          mind[nmind++] = k;  /* Keep track for rollback */          where[k]      = 2;          pwgts[from]  -= vwgt[k];          edegrees = rinfo[k].edegrees;          edegrees[0] = edegrees[1] = 0;          for (jj=xadj[k]; jj<xadj[k+1]; jj++) {            kk = adjncy[jj];            if (where[kk] != 2)               edegrees[where[kk]] += vwgt[kk];            else {              oldgain = vwgt[kk]-rinfo[kk].edegrees[from];              rinfo[kk].edegrees[from] -= vwgt[k];              /* Update the gain of this node if it was skipped */

/************************************************************************** This function balances two partitions by moving boundary nodes* from the domain that is overweight to the one that is underweight.**************************************************************************/void Bnd2WayBalance(CtrlType *ctrl, GraphType *graph, int *tpwgts){  int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;  idxtype *moved, *perm;  PQueueType parts;  int higain, oldgain, mincut, mindiff;  nvtxs = graph->nvtxs;  xadj = graph->xadj;  vwgt = graph->vwgt;  adjncy = graph->adjncy;  adjwgt = graph->adjwgt;  where = graph->where;  id = graph->id;  ed = graph->ed;  pwgts = graph->pwgts;  bndptr = graph->bndptr;  bndind = graph->bndind;  moved = idxwspacemalloc(ctrl, nvtxs);  perm = idxwspacemalloc(ctrl, nvtxs);  /* Determine from which domain you will be moving data */  mindiff = abs(tpwgts[0]-pwgts[0]);  from = (pwgts[0] < tpwgts[0] ? 1 : 0);  to = (from+1)%2;  IFSET(ctrl->dbglvl, DBG_REFINE,      printf("Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d [B]/n",             pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));  tmp = graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)];  PQueueInit(ctrl, &parts, nvtxs, tmp);  idxset(nvtxs, -1, moved);  ASSERT(ComputeCut(graph, where) == graph->mincut);  ASSERT(CheckBnd(graph));  /* Insert the boundary nodes of the proper partition whose size is OK in the priority queue */  nbnd = graph->nbnd;  RandomPermute(nbnd, perm, 1);  for (ii=0; ii<nbnd; ii++) {    i = perm[ii];    ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);    ASSERT(bndptr[bndind[i]] != -1);    if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)      PQueueInsert(&parts, bndind[i], ed[bndind[i]]-id[bndind[i]]);  }  mincut = graph->mincut;  for (nswaps=0; nswaps<nvtxs; nswaps++) {    if ((higain = PQueueGetMax(&parts)) == -1)      break;    ASSERT(bndptr[higain] != -1);    if (pwgts[to]+vwgt[higain] > tpwgts[to])      break;    mincut -= (ed[higain]-id[higain]);    INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);    where[higain] = to;    moved[higain] = nswaps;    IFSET(ctrl->dbglvl, DBG_MOVEINFO,       printf("Moved %6d from %d. [%3d %3d] %5d [%4d %4d]/n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));    /**************************************************************    * Update the id[i]/ed[i] values of the affected nodes    ***************************************************************/    SWAP(id[higain], ed[higain], tmp);    if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])       BNDDelete(nbnd, bndind,  bndptr, higain);    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      oldgain = ed[k]-id[k];      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);      INC_DEC(id[k], ed[k], kwgt);      /* Update its boundary information and queue position */      if (bndptr[k] != -1) { /* If k was a boundary vertex */        if (ed[k] == 0) { /* Not a boundary vertex any more */          BNDDelete(nbnd, bndind, bndptr, k);          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)  /* Remove it if in the queues */            PQueueDelete(&parts, k, oldgain);        }        else { /* If it has not been moved, update its position in the queue */          if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)            PQueueUpdate(&parts, k, oldgain, ed[k]-id[k]);        }      }      else {//.........这里部分代码省略.........

void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph){  idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, gain;  idx_t badmaxpwgt, higain, oldgain, to, other;  idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;  idx_t *perm, *moved;  rpq_t *queue;   nrinfo_t *rinfo;  real_t mult;  nvtxs  = graph->nvtxs;  xadj   = graph->xadj;  adjncy = graph->adjncy;  vwgt   = graph->vwgt;  bndind = graph->bndind;  bndptr = graph->bndptr;  where  = graph->where;  pwgts  = graph->pwgts;  rinfo  = graph->nrinfo;  mult = 0.5*ctrl->ubfactors[0];  badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));  if (gk_max(pwgts[0], pwgts[1]) < badmaxpwgt)    return;  if (iabs(pwgts[0]-pwgts[1]) < 3*graph->tvwgt[0]/nvtxs)    return;  WCOREPUSH;  to    = (pwgts[0] < pwgts[1] ? 0 : 1);   other = (to+1)%2;  queue = rpqCreate(nvtxs);  perm  = iwspacemalloc(ctrl, nvtxs);  moved = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,    printf("Partitions: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX" [B]/n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));  nbnd = graph->nbnd;  my_irandArrayPermute_r(nbnd, perm, nbnd, 1, &ctrl->curseed);  for (ii=0; ii<nbnd; ii++) {    i = bndind[perm[ii]];    ASSERT(where[i] == 2);    rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);  }  ASSERT(CheckNodeBnd(graph, nbnd));  ASSERT(CheckNodePartitionParams(graph));  /******************************************************  * Get into the FM loop  *******************************************************/  for (nswaps=0; nswaps<nvtxs; nswaps++) {    if ((higain = rpqGetTop(queue)) == -1)      break;    moved[higain] = 1;    gain = vwgt[higain]-rinfo[higain].edegrees[other];    badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));    /* break if other is now underwight */    if (pwgts[to] > pwgts[other])      break;    /* break if balance is achieved and no +ve or zero gain */    if (gain < 0 && pwgts[other] < badmaxpwgt)       break;    /* skip this vertex if it will violate balance on the other side */    if (pwgts[to]+vwgt[higain] > badmaxpwgt)       continue;    ASSERT(bndptr[higain] != -1);    pwgts[2] -= gain;    BNDDelete(nbnd, bndind, bndptr, higain);    pwgts[to] += vwgt[higain];    where[higain] = to;    IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,          printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %3"PRIDX", /t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]/n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));    /**********************************************************    * Update the degrees of the affected nodes    ***********************************************************/    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */        rinfo[k].edegrees[to] += vwgt[higain];      }      else if (where[k] == other) { /* This vertex is pulled into the separator */        ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"/n", k, bndptr[k], where[k]));        BNDInsert(nbnd, bndind, bndptr, k);//.........这里部分代码省略.........

/************************************************************************** This function performs a node-based FM refinement **************************************************************************/void FM_2WayNodeBalance(CtrlType *ctrl, GraphType *graph, float ubfactor){  idxtype i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps;  idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;  idxtype *perm, *moved;  PQueueType parts;   NRInfoType *rinfo;  idxtype higain, oldgain;	  idxtype pass, to, other;  nvtxs = graph->nvtxs;  xadj = graph->xadj;  adjncy = graph->adjncy;  vwgt = graph->vwgt;  bndind = graph->bndind;  bndptr = graph->bndptr;  where = graph->where;  pwgts = graph->pwgts;  rinfo = graph->nrinfo;  if (idxtype_abs(pwgts[0]-pwgts[1]) < (int)((ubfactor-1.0)*(pwgts[0]+pwgts[1])))    return;  if (idxtype_abs(pwgts[0]-pwgts[1]) < 3*idxsum(nvtxs, vwgt, 1)/nvtxs)    return;  to = (pwgts[0] < pwgts[1] ? 0 : 1);   other = (to+1)%2;  PQueueInit(ctrl, &parts, nvtxs, ComputeMaxNodeGain(nvtxs, xadj, adjncy, vwgt));  perm = idxwspacemalloc(ctrl, nvtxs);  moved = idxset(nvtxs, -1, idxwspacemalloc(ctrl, nvtxs));  IFSET(ctrl->dbglvl, DBG_REFINE,    mprintf("Partitions: [%6D %6D] Nv-Nb[%6D %6D]. ISep: %6D [B]/n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));  nbnd = graph->nbnd;  RandomPermute(nbnd, perm, 1);  for (ii=0; ii<nbnd; ii++) {    i = bndind[perm[ii]];    ASSERT(where[i] == 2);    PQueueInsert(&parts, i, vwgt[i]-rinfo[i].edegrees[other]);  }  ASSERT(CheckNodeBnd(graph, nbnd));  ASSERT(CheckNodePartitionParams(graph));  /******************************************************  * Get into the FM loop  *******************************************************/  for (nswaps=0; nswaps<nvtxs; nswaps++) {    if ((higain = PQueueGetMax(&parts)) == -1)      break;    moved[higain] = 1;    if (pwgts[other] - rinfo[higain].edegrees[other] < (pwgts[0]+pwgts[1])/2)       continue;#ifdef XXX    if (pwgts[other] - rinfo[higain].edegrees[other] < pwgts[to]+vwgt[higain])       break;#endif    ASSERT(bndptr[higain] != -1);    pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);    BNDDelete(nbnd, bndind, bndptr, higain);    pwgts[to] += vwgt[higain];    where[higain] = to;    IFSET(ctrl->dbglvl, DBG_MOVEINFO,          mprintf("Moved %6D to %3D, Gain: %3D, /t[%5D %5D %5D]/n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));    /**********************************************************    * Update the degrees of the affected nodes    ***********************************************************/    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */        rinfo[k].edegrees[to] += vwgt[higain];      }      else if (where[k] == other) { /* This vertex is pulled into the separator */        ASSERTP(bndptr[k] == -1, ("%d %d %d/n", k, bndptr[k], where[k]));        BNDInsert(nbnd, bndind, bndptr, k);        where[k] = 2;        pwgts[other] -= vwgt[k];        edegrees = rinfo[k].edegrees;        edegrees[0] = edegrees[1] = 0;        for (jj=xadj[k]; jj<xadj[k+1]; jj++) {          kk = adjncy[jj];          if (where[kk] != 2)             edegrees[where[kk]] += vwgt[kk];//.........这里部分代码省略.........

/************************************************************************** This function balances two partitions by moving the highest gain* (including negative gain) vertices to the other domain.* It is used only when tha unbalance is due to non contigous* subdomains. That is, the are no boundary vertices.* It moves vertices from the domain that is overweight to the one that* is underweight.**************************************************************************/void Mc_Serial_Init2WayBalance(GraphType *graph, float *tpwgts){  int i, ii, j, k;  int kwgt, nvtxs, nbnd, ncon, nswaps, from, to, cnum, tmp;  idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;  idxtype *qnum;  float *nvwgt, *npwgts;  FPQueueType parts[MAXNCON][2];  int higain, oldgain, mincut;  KeyValueType *cand;  nvtxs = graph->nvtxs;  ncon = graph->ncon;  xadj = graph->xadj;  adjncy = graph->adjncy;  nvwgt = graph->nvwgt;  adjwgt = graph->adjwgt;  where = graph->where;  id = graph->sendind;  ed = graph->recvind;  npwgts = graph->gnpwgts;  bndptr = graph->sendptr;  bndind = graph->recvptr;  qnum = idxmalloc(nvtxs, "qnum");  cand = (KeyValueType *)GKmalloc(nvtxs*sizeof(KeyValueType), "cand");  /* This is called for initial partitioning so we know from where to pick nodes */  from = 1;  to = (from+1)%2;  for (i=0; i<ncon; i++) {    FPQueueInit(&parts[i][0], nvtxs);    FPQueueInit(&parts[i][1], nvtxs);  }  /* Compute the queues in which each vertex will be assigned to */  for (i=0; i<nvtxs; i++)    qnum[i] = samax(ncon, nvwgt+i*ncon);  for (i=0; i<nvtxs; i++) {    cand[i].key = id[i]-ed[i];    cand[i].val = i;  }  ikeysort(nvtxs, cand);  /* Insert the nodes of the proper partition in the appropriate priority queue */  for (ii=0; ii<nvtxs; ii++) {    i = cand[ii].val;    if (where[i] == from) {      if (ed[i] > 0)        FPQueueInsert(&parts[qnum[i]][0], i, (float)(ed[i]-id[i]));      else        FPQueueInsert(&parts[qnum[i]][1], i, (float)(ed[i]-id[i]));    }  }  mincut = graph->mincut;  nbnd = graph->gnvtxs;  for (nswaps=0; nswaps<nvtxs; nswaps++) {    if (Serial_AreAnyVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, tpwgts+from*ncon))      break;    if ((cnum = Serial_SelectQueueOneWay(ncon, npwgts, tpwgts, from, parts)) == -1)      break;    if ((higain = FPQueueGetMax(&parts[cnum][0])) == -1)      higain = FPQueueGetMax(&parts[cnum][1]);    mincut -= (ed[higain]-id[higain]);    saxpy2(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);    saxpy2(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);    where[higain] = to;    /**************************************************************    * Update the id[i]/ed[i] values of the affected nodes    ***************************************************************/    SWAP(id[higain], ed[higain], tmp);    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])      BNDDelete(nbnd, bndind,  bndptr, higain);    if (ed[higain] > 0 && bndptr[higain] == -1)      BNDInsert(nbnd, bndind,  bndptr, higain);    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      oldgain = ed[k]-id[k];      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);      INC_DEC(id[k], ed[k], kwgt);//.........这里部分代码省略.........

//.........这里部分代码省略.........        break;      saxpy2(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);      saxpy2(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);      newcut -= (ed[higain]-id[higain]);      newbal = Serial_Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);      if ((newcut < mincut && newbal-origbal <= .00001) ||          (newcut == mincut && (newbal < minbal ||                                (newbal == minbal && Serial_BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {        mincut = newcut;        minbal = newbal;        mincutorder = nswaps;        for (i=0; i<ncon; i++)          mindiff[i] = fabs(tpwgts[i]-npwgts[i]);      }      else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */        newcut += (ed[higain]-id[higain]);        saxpy2(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);        saxpy2(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);        break;      }      where[higain] = to;      moved[higain] = nswaps;      swaps[nswaps] = higain;      /**************************************************************      * Update the id[i]/ed[i] values of the affected nodes      ***************************************************************/      SWAP(id[higain], ed[higain], tmp);      if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])        BNDDelete(nbnd, bndind,  bndptr, higain);      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        oldgain = ed[k]-id[k];        kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);        INC_DEC(id[k], ed[k], kwgt);        /* Update its boundary information and queue position */        if (bndptr[k] != -1) { /* If k was a boundary vertex */          if (ed[k] == 0) { /* Not a boundary vertex any more */            BNDDelete(nbnd, bndind, bndptr, k);            if (moved[k] == -1)  /* Remove it if in the queues */              FPQueueDelete(&parts[qnum[k]][where[k]], k);          }          else { /* If it has not been moved, update its position in the queue */            if (moved[k] == -1)              FPQueueUpdate(&parts[qnum[k]][where[k]], k, (float)oldgain, (float)(ed[k]-id[k]));          }        }        else {          if (ed[k] > 0) {  /* It will now become a boundary vertex */            BNDInsert(nbnd, bndind, bndptr, k);            if (moved[k] == -1)              FPQueueInsert(&parts[qnum[k]][where[k]], k, (float)(ed[k]-id[k]));          }        }      }    }    /****************************************************************    * Roll back computations

//.........这里部分代码省略.........                    (newcut == mincut && (newbal < minbal ||                                          (newbal == minbal && BetterBalance2Way(ncon, minbalv, newbalv))))) {                mincut      = newcut;                minbal      = newbal;                mincutorder = nswaps;                rcopy(ncon, newbalv, minbalv);            }            else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */                newcut += (ed[higain]-id[higain]);                iaxpy(ncon,  1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);                iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+to*ncon,   1);                break;            }            where[higain] = to;            moved[higain] = nswaps;            swaps[nswaps] = higain;            if (ctrl->dbglvl&METIS_DBG_MOVEINFO) {                printf("Moved%6"PRIDX" from %"PRIDX"(%"PRIDX") Gain:%5"PRIDX", "                       "Cut:%5"PRIDX", NPwgts:", higain, from, cnum, ed[higain]-id[higain], newcut);                for (l=0; l<ncon; l++)                    printf("(%.3"PRREAL" %.3"PRREAL")", pwgts[l]*invtvwgt[l], pwgts[ncon+l]*invtvwgt[l]);                printf(" %+.3"PRREAL" LB: %.3"PRREAL"(%+.3"PRREAL")/n",                       minbal, ComputeLoadImbalance(graph, 2, ctrl->pijbm), newbal);            }            /**************************************************************            * Update the id[i]/ed[i] values of the affected nodes            ***************************************************************/            SWAP(id[higain], ed[higain], tmp);            if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])                BNDDelete(nbnd, bndind,  bndptr, higain);            for (j=xadj[higain]; j<xadj[higain+1]; j++) {                k = adjncy[j];                kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);                INC_DEC(id[k], ed[k], kwgt);                /* Update its boundary information and queue position */                if (bndptr[k] != -1) { /* If k was a boundary vertex */                    if (ed[k] == 0) { /* Not a boundary vertex any more */                        BNDDelete(nbnd, bndind, bndptr, k);                        if (moved[k] == -1)  /* Remove it if in the queues */                            rpqDelete(queues[2*qnum[k]+where[k]], k);                    }                    else { /* If it has not been moved, update its position in the queue */                        if (moved[k] == -1) {                            //rgain = 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1);                            //rgain = (ed[k]-id[k] > 0 ?                            //              1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1) : ed[k]-id[k]);                            rgain = ed[k]-id[k];                            rpqUpdate(queues[2*qnum[k]+where[k]], k, rgain);                        }                    }                }                else {                    if (ed[k] > 0) {  /* It will now become a boundary vertex */                        BNDInsert(nbnd, bndind, bndptr, k);                        if (moved[k] == -1) {                            //rgain = 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1);                            //rgain = (ed[k]-id[k] > 0 ?                            //              1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1) : ed[k]-id[k]);                            rgain = ed[k]-id[k];

//.........这里部分代码省略.........    Serial_SelectQueue(ncon, npwgts, tpwgts, &from, &cnum, parts);    to = (from+1)%2;    if (from == -1 || (higain = FPQueueGetMax(&parts[cnum][from])) == -1)      break;    saxpy2(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);    saxpy2(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);    newcut -= (ed[higain]-id[higain]);    newbal = Serial_Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);    if (newbal < minbal || (newbal == minbal &&        (newcut < mincut || (newcut == mincut &&          Serial_BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {      mincut = newcut;      minbal = newbal;      mincutorder = nswaps;      for (i=0; i<ncon; i++)        mindiff[i] = fabs(tpwgts[i]-npwgts[i]);    }    else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */      newcut += (ed[higain]-id[higain]);      saxpy2(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);      saxpy2(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);      break;    }    where[higain] = to;    moved[higain] = nswaps;    swaps[nswaps] = higain;    /**************************************************************    * Update the id[i]/ed[i] values of the affected nodes    ***************************************************************/    SWAP(id[higain], ed[higain], tmp);    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])      BNDDelete(nbnd, bndind,  bndptr, higain);    if (ed[higain] > 0 && bndptr[higain] == -1)      BNDInsert(nbnd, bndind,  bndptr, higain);    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      oldgain = ed[k]-id[k];      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);      INC_DEC(id[k], ed[k], kwgt);      /* Update the queue position */      if (moved[k] == -1)        FPQueueUpdate(&parts[qnum[k]][where[k]], k, (float)(oldgain), (float)(ed[k]-id[k]));      /* Update its boundary information */      if (ed[k] == 0 && bndptr[k] != -1)        BNDDelete(nbnd, bndind, bndptr, k);      else if (ed[k] > 0 && bndptr[k] == -1)        BNDInsert(nbnd, bndind, bndptr, k);    }  }  /****************************************************************  * Roll back computations  *****************************************************************/  for (nswaps--; nswaps>mincutorder; nswaps--) {    higain = swaps[nswaps];    to = where[higain] = (where[higain]+1)%2;    SWAP(id[higain], ed[higain], tmp);    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])      BNDDelete(nbnd, bndind,  bndptr, higain);    else if (ed[higain] > 0 && bndptr[higain] == -1)      BNDInsert(nbnd, bndind,  bndptr, higain);    saxpy2(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);    saxpy2(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);      INC_DEC(id[k], ed[k], kwgt);      if (bndptr[k] != -1 && ed[k] == 0)        BNDDelete(nbnd, bndind, bndptr, k);      if (bndptr[k] == -1 && ed[k] > 0)        BNDInsert(nbnd, bndind, bndptr, k);    }  }  graph->mincut = mincut;  graph->gnvtxs = nbnd;  for (i=0; i<ncon; i++) {    FPQueueFree(&parts[i][0]);    FPQueueFree(&parts[i][1]);  }  GKfree((void **)&cand, (void **)&qnum, (void **)&moved, (void **)&swaps, LTERM);  return;}

//.........这里部分代码省略.........               (AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon) ||                IsHBalanceBetterFT(ncon, nparts, npwgts+from*ncon, npwgts+to*ncon, nvwgt, ubvec))) ||              (myedegrees[j].ed == myedegrees[k].ed &&                IsHBalanceBetterTT(ncon, nparts, npwgts+myedegrees[k].pid*ncon, npwgts+to*ncon, nvwgt, ubvec)))            k = j;        }        to = myedegrees[k].pid;        if (myedegrees[k].ed-myrinfo->id == 0             && !IsHBalanceBetterFT(ncon, nparts, npwgts+from*ncon, npwgts+to*ncon, nvwgt, ubvec)            && AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, npwgts+from*ncon, maxwgt+from*ncon))           continue;        /*=====================================================================        * If we got here, we can now move the vertex from 'from' to 'to'         *======================================================================*/        graph->mincut -= myedegrees[k].ed-myrinfo->id;        IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("/t/tMoving %6d to %3d. Gain: %4d. Cut: %6d/n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));        /* Update where, weight, and ID/ED information of the vertex you moved */        saxpy(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);        saxpy(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);        where[i] = to;        myrinfo->ed += myrinfo->id-myedegrees[k].ed;        SWAP(myrinfo->id, myedegrees[k].ed, j);        if (myedegrees[k].ed == 0)           myedegrees[k] = myedegrees[--myrinfo->ndegrees];        else          myedegrees[k].pid = from;        if (myrinfo->ed-myrinfo->id < 0)          BNDDelete(nbnd, bndind, bndptr, i);        /* Update the degrees of adjacent vertices */        for (j=xadj[i]; j<xadj[i+1]; j++) {          ii = adjncy[j];          me = where[ii];          myrinfo = graph->rinfo+ii;          if (myrinfo->edegrees == NULL) {            myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;            ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];          }          myedegrees = myrinfo->edegrees;          ASSERT(CheckRInfo(myrinfo));          if (me == from) {            INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);            if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)              BNDInsert(nbnd, bndind, bndptr, ii);          }          else if (me == to) {            INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);            if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)              BNDDelete(nbnd, bndind, bndptr, ii);          }          /* Remove contribution from the .ed of 'from' */          if (me != from) {            for (k=0; k<myrinfo->ndegrees; k++) {              if (myedegrees[k].pid == from) {

//.........这里部分代码省略.........    if (newbal < minbal || (newbal == minbal &&         (newcut < mincut || (newcut == mincut && BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {      mincut = newcut;      minbal = newbal;      mincutorder = nswaps;      for (i=0; i<ncon; i++)        mindiff[i] = fabs(tpwgts[0]-npwgts[i]);    }    else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */      newcut += (ed[higain]-id[higain]);      saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);      saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);      break;    }    where[higain] = to;    moved[higain] = nswaps;    swaps[nswaps] = higain;    if (ctrl->dbglvl&DBG_MOVEINFO) {      printf("Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);      for (l=0; l<ncon; l++)         printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);      printf(", %.3f LB: %.3f/n", minbal, newbal);    }    /**************************************************************    * Update the id[i]/ed[i] values of the affected nodes    ***************************************************************/    SWAP(id[higain], ed[higain], tmp);    if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])       BNDDelete(nbnd, bndind,  bndptr, higain);    if (ed[higain] > 0 && bndptr[higain] == -1)      BNDInsert(nbnd, bndind,  bndptr, higain);    for (j=xadj[higain]; j<xadj[higain+1]; j++) {      k = adjncy[j];      oldgain = ed[k]-id[k];      kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);      INC_DEC(id[k], ed[k], kwgt);      /* Update the queue position */      if (moved[k] == -1)        PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-id[k]);      /* Update its boundary information */      if (ed[k] == 0 && bndptr[k] != -1)         BNDDelete(nbnd, bndind, bndptr, k);      else if (ed[k] > 0 && bndptr[k] == -1)          BNDInsert(nbnd, bndind, bndptr, k);    }  }  /****************************************************************  * Roll back computations  *****************************************************************/  for (nswaps--; nswaps>mincutorder; nswaps--) {    higain = swaps[nswaps];    to = where[higain] = (where[higain]+1)%2;    SWAP(id[higain], ed[higain], tmp);

//.........这里部分代码省略.........                  /*=====================================================================        * If we got here, we can now move the vertex from 'from' to 'to'         *======================================================================*/        graph->mincut -= myedegrees[k].ed-myrinfo->id;        IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("/t/tMoving %6d to %3d. Gain: %4d. Cut: %6d/n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));        /* Update pmat to reflect the move of 'i' */        pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);        pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);        if (pmat[from*nparts+to] == 0) {          ndoms[from]--;          if (ndoms[from]+1 == maxndoms)            maxndoms = ndoms[idxamax(nparts, ndoms)];        }        if (pmat[to*nparts+from] == 0) {          ndoms[to]--;          if (ndoms[to]+1 == maxndoms)            maxndoms = ndoms[idxamax(nparts, ndoms)];        }        /* Update where, weight, and ID/ED information of the vertex you moved */        where[i] = to;        INC_DEC(pwgts[to], pwgts[from], vwgt);        myrinfo->ed += myrinfo->id-myedegrees[k].ed;        SWAP(myrinfo->id, myedegrees[k].ed, j);        if (myedegrees[k].ed == 0)           myedegrees[k] = myedegrees[--myrinfo->ndegrees];        else          myedegrees[k].pid = from;        if (myrinfo->ed-myrinfo->id < 0)          BNDDelete(nbnd, bndind, bndptr, i);        /* Update the degrees of adjacent vertices */        for (j=xadj[i]; j<xadj[i+1]; j++) {          ii = adjncy[j];          me = where[ii];          myrinfo = graph->rinfo+ii;          if (myrinfo->edegrees == NULL) {            myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;            ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];          }          myedegrees = myrinfo->edegrees;          ASSERT(CheckRInfo(myrinfo));          if (me == from) {            INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);            if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)              BNDInsert(nbnd, bndind, bndptr, ii);          }          else if (me == to) {            INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);            if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)              BNDDelete(nbnd, bndind, bndptr, ii);          }          /* Remove contribution from the .ed of 'from' */          if (me != from) {            for (k=0; k<myrinfo->ndegrees; k++) {              if (myedegrees[k].pid == from) {

//.........这里部分代码省略.........                    k = j;            }            to = myedegrees[k].pid;            j = 0;            if (myedegrees[k].ed-myrinfo->id > 0)                j = 1;            else if (myedegrees[k].ed-myrinfo->id == 0) {                if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])                    j = 1;            }            if (j == 0)                continue;            /*=====================================================================            * If we got here, we can now move the vertex from 'from' to 'to'            *======================================================================*/            graph->mincut -= myedegrees[k].ed-myrinfo->id;            IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("/t/tMoving %6d to %3d. Gain: %4d. Cut: %6d/n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));            /* Update where, weight, and ID/ED information of the vertex you moved */            where[i] = to;            INC_DEC(pwgts[to], pwgts[from], vwgt);            myrinfo->ed += myrinfo->id-myedegrees[k].ed;            SWAP(myrinfo->id, myedegrees[k].ed, j);            if (myedegrees[k].ed == 0)                myedegrees[k] = myedegrees[--myrinfo->ndegrees];            else                myedegrees[k].pid = from;            if (myrinfo->ed < myrinfo->id)                BNDDelete(nbnd, bndind, bndptr, i);            /* Update the degrees of adjacent vertices */            for (j=xadj[i]; j<xadj[i+1]; j++) {                ii = adjncy[j];                me = where[ii];                myrinfo = graph->rinfo+ii;                if (myrinfo->edegrees == NULL) {                    myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;                    ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];                }                myedegrees = myrinfo->edegrees;                ASSERT(CheckRInfo(myrinfo));                oldgain = (myrinfo->ed-myrinfo->id);                if (me == from) {                    INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);                    if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)                        BNDInsert(nbnd, bndind, bndptr, ii);                }                else if (me == to) {                    INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);                    if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)                        BNDDelete(nbnd, bndind, bndptr, ii);                }                /* Remove contribution from the .ed of 'from' */                if (me != from) {

/************************************************************************** This function moves a collection of vertices and updates their rinfo**************************************************************************/void MoveGroupMConn(CtrlType *ctrl, GraphType *graph, idxtype *ndoms, idxtype *pmat,                    int nparts, int to, int nind, idxtype *ind){  int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees;   int from, me;  idxtype *xadj, *adjncy, *adjwgt;  idxtype *where, *bndptr, *bndind;  EDegreeType *myedegrees;  RInfoType *myrinfo;  nvtxs = graph->nvtxs;  xadj = graph->xadj;  adjncy = graph->adjncy;  adjwgt = graph->adjwgt;  where = graph->where;  bndptr = graph->bndptr;  bndind = graph->bndind;  nbnd = graph->nbnd;  for (iii=0; iii<nind; iii++) {    i = ind[iii];    from = where[i];    myrinfo = graph->rinfo+i;    if (myrinfo->edegrees == NULL) {      myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;      ctrl->wspace.cdegree += xadj[i+1]-xadj[i];      myrinfo->ndegrees = 0;    }    myedegrees = myrinfo->edegrees;    /* find the location of 'to' in myrinfo or create it if it is not there */    for (k=0; k<myrinfo->ndegrees; k++) {      if (myedegrees[k].pid == to)        break;    }    if (k == myrinfo->ndegrees) {      myedegrees[k].pid = to;      myedegrees[k].ed = 0;      myrinfo->ndegrees++;    }    graph->mincut -= myedegrees[k].ed-myrinfo->id;    /* Update pmat to reflect the move of 'i' */    pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);    pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);    if (pmat[from*nparts+to] == 0)       ndoms[from]--;    if (pmat[to*nparts+from] == 0)       ndoms[to]--;    /* Update where, weight, and ID/ED information of the vertex you moved */    where[i] = to;    myrinfo->ed += myrinfo->id-myedegrees[k].ed;    SWAP(myrinfo->id, myedegrees[k].ed, j);    if (myedegrees[k].ed == 0)       myedegrees[k] = myedegrees[--myrinfo->ndegrees];    else      myedegrees[k].pid = from;    if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1)      BNDDelete(nbnd, bndind, bndptr, i);    /* Update the degrees of adjacent vertices */    for (j=xadj[i]; j<xadj[i+1]; j++) {      ii = adjncy[j];      me = where[ii];      myrinfo = graph->rinfo+ii;      if (myrinfo->edegrees == NULL) {        myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;        ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];      }      myedegrees = myrinfo->edegrees;      ASSERT(CheckRInfo(myrinfo));      if (me == from) {        INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);        if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)          BNDInsert(nbnd, bndind, bndptr, ii);      }      else if (me == to) {        INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);        if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)          BNDDelete(nbnd, bndind, bndptr, ii);      }      /* Remove contribution from the .ed of 'from' */      if (me != from) {        for (k=0; k<myrinfo->ndegrees; k++) {          if (myedegrees[k].pid == from) {//.........这里部分代码省略.........

//.........这里部分代码省略.........      }      else        break;      other = (to+1)%2;      higain = rpqGetTop(queues[to]);      if (moved[higain] == -1) /* Delete if it was in the separator originally */        rpqDelete(queues[other], higain);      ASSERT(bndptr[higain] != -1);      /* The following check is to ensure we break out if there is a posibility         of over-running the mind array.  */      if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)         break;      pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);      newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));      if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {        mincut = pwgts[2];        mincutorder = nswaps;        mindiff = newdiff;      }      else {        if (nswaps - mincutorder > 2*limit ||             (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {          pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);          break; /* No further improvement, break out */        }      }      BNDDelete(nbnd, bndind, bndptr, higain);      pwgts[to] += vwgt[higain];      where[higain] = to;      moved[higain] = nswaps;      swaps[nswaps] = higain;        /**********************************************************      * Update the degrees of the affected nodes      ***********************************************************/      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */          oldgain = vwgt[k]-rinfo[k].edegrees[to];          rinfo[k].edegrees[to] += vwgt[higain];          if (moved[k] == -1 || moved[k] == -(2+other))            rpqUpdate(queues[other], k, oldgain-vwgt[higain]);        }        else if (where[k] == other) { /* This vertex is pulled into the separator */          ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"/n", k, bndptr[k], where[k]));          BNDInsert(nbnd, bndind, bndptr, k);          mind[nmind++] = k;  /* Keep track for rollback */          where[k] = 2;          pwgts[other] -= vwgt[k];          edegrees = rinfo[k].edegrees;          edegrees[0] = edegrees[1] = 0;          for (jj=xadj[k]; jj<xadj[k+1]; jj++) {            kk = adjncy[jj];            if (where[kk] != 2)               edegrees[where[kk]] += vwgt[kk];            else {