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

//.........这里部分代码省略.........      for (j=0; j<ncon; j++)        flows[j] += (to == me) ? nvwgt[vtx*ncon+j] : -1.0*nvwgt[vtx*ncon+j]; /*      ftmp = sfavg(ncon, flows); */      for (j=0, h=0; h<ncon; h++)        if (fabs(flows[h]) > fabs(flows[j])) j = h;          ftmp = fabs(flows[j]);      if (ftmp < bestflow) {        bestflow = ftmp;        nchanges = 0;      }      else {        changes[nchanges++] = vtx;      }      SWAP(id[vtx], ed[vtx], tmp);      for (j=xadj[vtx]; j<xadj[vtx+1]; j++) {        edge = adjncy[j];        /* must compute oldgain before changing id/ed */        if (myqueue[edge] != -1) {          oldgain = ipc_factor*(float)(ed[edge]-id[edge]);          if (home[edge] == me || home[edge] == you) {            if (where[edge] == home[edge])              oldgain -= redist_factor*(float)vsize[edge];            else              oldgain += redist_factor*(float)vsize[edge];          }        }        tmp = (to == where[edge] ? adjwgt[j] : -adjwgt[j]);        INC_DEC(id[edge], ed[edge], tmp);        if (myqueue[edge] != -1) {          newgain = ipc_factor*(float)(ed[edge]-id[edge]);          if (home[edge] == me || home[edge] == you) {            if (where[edge] == home[edge])              newgain -= redist_factor*(float)vsize[edge];            else              newgain += redist_factor*(float)vsize[edge];          }          FPQueueUpdate(queues+hval[edge]+(nqueues*myqueue[edge]),          map[edge]-ptr[hval[edge]], oldgain, newgain);        }      }    }    /****************************/    /* now go back to best flow */    /****************************/    nswaps -= nchanges;    nmoves -= nchanges;    for (i=0; i<nchanges; i++) {      vtx = changes[i];      from = where[vtx];      where[vtx] = to = (from == me) ? you : me;      SWAP(id[vtx], ed[vtx], tmp);      for (j=xadj[vtx]; j<xadj[vtx+1]; j++) {        edge = adjncy[j];        tmp = (to == where[edge] ? adjwgt[j] : -adjwgt[j]);        INC_DEC(id[edge], ed[edge], tmp);      }

//.........这里部分代码省略.........        j = 0;        if (myedegrees[k].ed-myrinfo->id > 0)          j = 1;        else if (myedegrees[k].ed-myrinfo->id == 0) {          if (/*(iii&7) == 0  ||*/ phtable[myedegrees[k].pid] == 2 || 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 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]);

//.........这里部分代码省略.........      other = cand2[min].val;      /*printf("/tMinOut: %d to %d/n", mypmat[other], other);*/      idxset(nparts, 0, otherpmat);      /* Go and find the vertices in 'other' that are connected in 'me' */      for (nind=0, i=0; i<nvtxs; i++) {        if (where[i] == other) {          for (j=xadj[i]; j<xadj[i+1]; j++) {            if (where[adjncy[j]] == me) {              ind[nind++] = i;              break;            }          }        }      }      /* Go and construct the otherpmat to see where these nind vertices are connected to */      for (cpwgt=0, ii=0; ii<nind; ii++) {        i = ind[ii];        cpwgt += vwgt[i];        for (j=xadj[i]; j<xadj[i+1]; j++)           otherpmat[where[adjncy[j]]] += adjwgt[j];      }      otherpmat[other] = 0;      for (ncand=0, i=0; i<nparts; i++) {        if (otherpmat[i] > 0) {          cand[ncand].key = -otherpmat[i];          cand[ncand++].val = i;        }      }      ikeysort(ncand, cand);      /*        * Go through and the select the first domain that is common with 'me', and       * does not increase the ndoms[target] higher than my ndoms, subject to the       * maxpwgt constraint. Traversal is done from the mostly connected to the least.       */      target = target2 = -1;      for (i=0; i<ncand; i++) {        k = cand[i].val;        if (mypmat[k] > 0) {          if (pwgts[k] + cpwgt > maxpwgt[k])  /* Check if balance will go off */            continue;          for (j=0; j<nparts; j++) {            if (otherpmat[j] > 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0)              break;          }          if (j == nparts) { /* No bad second level effects */            for (nadd=0, j=0; j<nparts; j++) {              if (otherpmat[j] > 0 && pmat[nparts*k+j] == 0)                nadd++;            }            /*printf("/t/tto=%d, nadd=%d, %d/n", k, nadd, ndoms[k]);*/            if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) {              target2 = k;            }            if (nadd == 0) {              target = k;              break;            }          }        }      }      if (target == -1 && target2 != -1)        target = target2;      if (target == -1) {        /* printf("/t/tCould not make the move/n");*/        continue;      }      /*printf("/t/tMoving to %d/n", target);*/      /* Update the partition weights */      INC_DEC(pwgts[target], pwgts[other], cpwgt);      MoveGroupMConn(ctrl, graph, ndoms, pmat, nparts, target, nind, ind);      move = 1;      break;    }    if (move == 0)      break;  }  idxwspacefree(ctrl, nparts);  idxwspacefree(ctrl, nparts);  idxwspacefree(ctrl, nparts);  idxwspacefree(ctrl, nvtxs);  GKfree(&cand, &cand2, LTERM);}

//.........这里部分代码省略.........        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 (myedegrees[k].ed == adjwgt[j])                  myedegrees[k] = myedegrees[--myrinfo->ndegrees];                else                  myedegrees[k].ed -= adjwgt[j];                break;              }            }          }          /* Add contribution to the .ed of 'to' */          if (me != to) {            for (k=0; k<myrinfo->ndegrees; k++) {              if (myedegrees[k].pid == to) {                myedegrees[k].ed += adjwgt[j];                break;              }            }

//.........这里部分代码省略.........              for (h=0; h<ncon; h++) {                lnpwgts[to*ncon+h] += nvwgt[h];                lnpwgts[from*ncon+h] -= nvwgt[h];                gnpwgts[to*ncon+h] += nvwgt[h];                gnpwgts[from*ncon+h] -= nvwgt[h];                movewgts[to*ncon+h] += nvwgt[h];                movewgts[from*ncon+h] -= nvwgt[h];              }              tmp_rinfo[i].ed += tmp_rinfo[i].id-my_edegrees[k].ewgt;              SWAP(tmp_rinfo[i].id, my_edegrees[k].ewgt, j);              if (my_edegrees[k].ewgt == 0) {                tmp_rinfo[i].ndegrees--;                my_edegrees[k].edge = my_edegrees[tmp_rinfo[i].ndegrees].edge;                my_edegrees[k].ewgt = my_edegrees[tmp_rinfo[i].ndegrees].ewgt;              }              else {                my_edegrees[k].edge = from;              }              /* Update the degrees of adjacent vertices */              for (j=xadj[i]; j<xadj[i+1]; j++) {                /* no need to bother about vertices on different pe's */                if (ladjncy[j] >= nvtxs)                  continue;                me = ladjncy[j];                mydomain = tmp_where[me];                myrinfo = tmp_rinfo+me;                your_edegrees = myrinfo->degrees;                if (mydomain == from) {                  INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);                }                else {                  if (mydomain == to) {                    INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);                  }                }                /* Remove contribution from the .ed of 'from' */                if (mydomain != from) {                  for (k=0; k<myrinfo->ndegrees; k++) {                    if (your_edegrees[k].edge == from) {                      if (your_edegrees[k].ewgt == adjwgt[j]) {                        myrinfo->ndegrees--;                        your_edegrees[k].edge = your_edegrees[myrinfo->ndegrees].edge;                        your_edegrees[k].ewgt = your_edegrees[myrinfo->ndegrees].ewgt;                      }                      else {                        your_edegrees[k].ewgt -= adjwgt[j];                      }                      break;                    }                  }                }                /* Add contribution to the .ed of 'to' */                if (mydomain != to) {                  for (k=0; k<myrinfo->ndegrees; k++) {                    if (your_edegrees[k].edge == to) {                      your_edegrees[k].ewgt += adjwgt[j];                      break;                    }                  }

//.........这里部分代码省略.........            }            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];                            rpqInsert(queues[2*qnum[k]+where[k]], k, rgain);                        }                    }                }            }

//.........这里部分代码省略.........      ndirty = dptr;      nclean = nvtxs-dptr;      FastRandomPermute(ndirty, perm, 0);      FastRandomPermute(nclean, perm+ndirty, 0);    }    if (ctrl->mype == 0) {      for (j=nvtxs, k=0, ii=0; ii<nvtxs; ii++) {        i = perm[ii];        if (ed[i] != 0) {          cand[k].key = -ed[i];          cand[k++].val = i;        }        else {          cand[--j].key = 0;          cand[j].val = i;        }      }      ikvsorti(k, cand);    }    for (ii=0; ii<nvtxs/3; ii++) {      i = (ctrl->mype == 0) ? cand[ii].val : perm[ii];      from = where[i];      /* don't move out the last vertex in a subdomain */      if (psize[from] == 1)        continue;      clean = (from == home[i]) ? 1 : 0;      /* only move from top three or dirty vertices */      if (from != first && from != second && from != third && clean)        continue;      /* Scatter the sparse transfer row into the dense tmpvec row */      for (j=rowptr[from]+1; j<rowptr[from+1]; j++)        tmpvec[colind[j]] = transfer[j];      for (j=xadj[i]; j<xadj[i+1]; j++) {        to = where[adjncy[j]];        if (from != to) {          if (tmpvec[to] > (flowFactor * nvwgt[i])) {            tmpvec[to] -= nvwgt[i];            INC_DEC(psize[to], psize[from], 1);            INC_DEC(npwgts[to], npwgts[from], nvwgt[i]);            INC_DEC(load[to], load[from], nvwgt[i]);            where[i] = to;            nswaps++;            /* Update external degrees */            ed[i] = 0;            for (k=xadj[i]; k<xadj[i+1]; k++) {              edge = adjncy[k];              ed[i] += (to != where[edge] ? adjwgt[k] : 0);              if (where[edge] == from)                ed[edge] += adjwgt[k];              if (where[edge] == to)                ed[edge] -= adjwgt[k];            }            break;          }        }      }      /* Gather the dense tmpvec row into the sparse transfer row */      for (j=rowptr[from]+1; j<rowptr[from+1]; j++) {        transfer[j] = tmpvec[colind[j]];        tmpvec[colind[j]] = 0.0;      }      ASSERT(fabs(rsum(nparts, tmpvec, 1)) < .0001)    }    if (l % 2 == 1) {      balance = rmax(nparts, npwgts)*nparts;      if (balance < ubfactor + 0.035)        done = 1;      if (GlobalSESum(ctrl, done) > 0)        break;      noswaps = (nswaps > 0) ? 0 : 1;      if (GlobalSESum(ctrl, noswaps) > ctrl->npes/2)        break;    }  }  graph->mincut = ComputeSerialEdgeCut(graph);  totalv        = Mc_ComputeSerialTotalV(graph, home);  cost          = ctrl->ipc_factor * (real_t)graph->mincut + ctrl->redist_factor * (real_t)totalv;CleanUpAndExit:  gk_free((void **)&solution, (void **)&perm, (void **)&workspace, (void **)&cand, LTERM);  return cost;}

/************************************************************************** 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);//.........这里部分代码省略.........

//.........这里部分代码省略.........      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]);          }        }      }    }    /****************************************************************    * Roll back computations    *****************************************************************/    for (i=0; i<nswaps; i++)      moved[swaps[i]] = -1;  /* reset moved array */    for (nswaps--; nswaps>mincutorder; nswaps--) {      higain = swaps[nswaps];

/************************************************************************** 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];//.........这里部分代码省略.........

//.........这里部分代码省略.........          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[other];              rinfo[kk].edegrees[other] -= vwgt[k];              if (moved[kk] == -5 || moved[kk] == -(10+to))                PQueueUpdate(&parts[to], kk, oldgain, oldgain+vwgt[k]);            }          }          /* Insert the new vertex into the priority queue (if it has not been moved). */          if (moved[k] == -1 && (hmarker[k] == -1 || hmarker[k] == to)) {            PQueueInsert(&parts[to], k, vwgt[k]-edegrees[other]);            moved[k] = -(10+to);          }#ifdef FULLMOVES  /* this does not work as well as the above partial one */          if (moved[k] == -1) {            if (hmarker[k] == -1) {              PQueueInsert(&parts[0], k, vwgt[k]-edegrees[1]);              PQueueInsert(&parts[1], k, vwgt[k]-edegrees[0]);              moved[k] = -5;            }            else if (hmarker[k] != 2) {              PQueueInsert(&parts[hmarker[k]], k, vwgt[k]-edegrees[(hmarker[k]+1)%2]);              moved[k] = -(10+hmarker[k]);            }          }#endif        }      }      mptr[nswaps+1] = nmind;      IFSET(ctrl->dbglvl, DBG_MOVEINFO,            printf("Moved %6d to %3d, Gain: %5d [%5d] [%4d %4d] /t[%5d %5d %5d]/n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));    }    /****************************************************************    * Roll back computation     *****************************************************************/    for (nswaps--; nswaps>mincutorder; nswaps--) {      higain = swaps[nswaps];      ASSERT(CheckNodePartitionParams(graph));      to = where[higain];      other = (to+1)%2;      INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);      where[higain] = 2;      BNDInsert(nbnd, bndind, bndptr, higain);      edegrees = rinfo[higain].edegrees;      edegrees[0] = edegrees[1] = 0;      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2)           rinfo[k].edegrees[to] -= vwgt[higain];        else          edegrees[where[k]] += vwgt[k];      }      /* Push nodes out of the separator */      for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {        k = mind[j];        ASSERT(where[k] == 2);        where[k] = other;        INC_DEC(pwgts[other], pwgts[2], vwgt[k]);        BNDDelete(nbnd, bndind, bndptr, k);        for (jj=xadj[k]; jj<xadj[k+1]; jj++) {          kk = adjncy[jj];          if (where[kk] == 2)             rinfo[kk].edegrees[other] += vwgt[k];        }      }    }    ASSERT(mincut == pwgts[2]);    IFSET(ctrl->dbglvl, DBG_REFINE,      printf("/tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d/n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));    graph->mincut = mincut;    graph->nbnd = nbnd;    if (mincutorder == -1 || mincut >= initcut)      break;  }  PQueueFree(ctrl, &parts[0]);  PQueueFree(ctrl, &parts[1]);  idxwspacefree(ctrl, nvtxs+1);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);}

//.........这里部分代码省略.........        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 */              if (inqueue[kk] == pass)                PQueueUpdateUp(&parts, kk, oldgain, oldgain+vwgt[k]);             }          }          /* Insert the new vertex into the priority queue. Safe due to one-sided moves */          if (hmarker[k] == -1 || hmarker[k] == to) {            PQueueInsert(&parts, k, vwgt[k]-edegrees[from]);            inqueue[k] = pass;          }        }      }      mptr[nswaps+1] = nmind;      IFSET(ctrl->dbglvl, DBG_MOVEINFO,            printf("Moved %6d to %3d, Gain: %5d [%5d] /t[%5d %5d %5d] [%3d %2d]/n",                        higain, to, (vwgt[higain]-rinfo[higain].edegrees[from]), vwgt[higain], pwgts[0], pwgts[1], pwgts[2], nswaps, limit));    }    /****************************************************************    * Roll back computation     *****************************************************************/    for (nswaps--; nswaps>mincutorder; nswaps--) {      higain = swaps[nswaps];      ASSERT(CheckNodePartitionParams(graph));      ASSERT(where[higain] == to);      INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);      where[higain] = 2;      BNDInsert(nbnd, bndind, bndptr, higain);      edegrees = rinfo[higain].edegrees;      edegrees[0] = edegrees[1] = 0;      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2)           rinfo[k].edegrees[to] -= vwgt[higain];        else          edegrees[where[k]] += vwgt[k];      }      /* Push nodes out of the separator */      for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {        k = mind[j];        ASSERT(where[k] == 2);        where[k] = from;        INC_DEC(pwgts[from], pwgts[2], vwgt[k]);        BNDDelete(nbnd, bndind, bndptr, k);        for (jj=xadj[k]; jj<xadj[k+1]; jj++) {          kk = adjncy[jj];          if (where[kk] == 2)             rinfo[kk].edegrees[from] += vwgt[k];        }      }    }    ASSERT(mincut == pwgts[2]);    IFSET(ctrl->dbglvl, DBG_REFINE,      printf("/tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d, QSIZE: %6d/n",           mincut, mincutorder, pwgts[0], pwgts[1], nbnd, qsize));    graph->mincut = mincut;    graph->nbnd   = nbnd;    if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))      break;  }  PQueueFree(ctrl, &parts);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs+1);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);}

/************************************************************************** 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 {//.........这里部分代码省略.........

//.........这里部分代码省略.........          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 {              oldgain = vwgt[kk]-rinfo[kk].edegrees[other];              rinfo[kk].edegrees[other] -= vwgt[k];              if (moved[kk] == -1 || moved[kk] == -(2+to))                PQueueUpdate(&parts[to], kk, oldgain, oldgain+vwgt[k]);            }          }          /* Insert the new vertex into the priority queue. Only one side! */          if (moved[k] == -1) {            PQueueInsert(&parts[to], k, vwgt[k]-edegrees[other]);            moved[k] = -(2+to);          }        }      }      mptr[nswaps+1] = nmind;      IFSET(ctrl->dbglvl, DBG_MOVEINFO,            mprintf("Moved %6D to %3D, Gain: %5D [%5D] [%4D %4D] /t[%5D %5D %5D]/n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));    }    /****************************************************************    * Roll back computation     *****************************************************************/    for (nswaps--; nswaps>mincutorder; nswaps--) {      higain = swaps[nswaps];      ASSERT(CheckNodePartitionParams(graph));      to = where[higain];      other = (to+1)%2;      INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);      where[higain] = 2;      BNDInsert(nbnd, bndind, bndptr, higain);      edegrees = rinfo[higain].edegrees;      edegrees[0] = edegrees[1] = 0;      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2)           rinfo[k].edegrees[to] -= vwgt[higain];        else          edegrees[where[k]] += vwgt[k];      }      /* Push nodes out of the separator */      for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {        k = mind[j];        ASSERT(where[k] == 2);        where[k] = other;        INC_DEC(pwgts[other], pwgts[2], vwgt[k]);        BNDDelete(nbnd, bndind, bndptr, k);        for (jj=xadj[k]; jj<xadj[k+1]; jj++) {          kk = adjncy[jj];          if (where[kk] == 2)             rinfo[kk].edegrees[other] += vwgt[k];        }      }    }    ASSERT(mincut == pwgts[2]);    IFSET(ctrl->dbglvl, DBG_REFINE,      mprintf("/tMinimum sep: %6D at %5D, PWGTS: [%6D %6D], NBND: %6D/n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));    graph->mincut = mincut;    graph->nbnd = nbnd;    if (mincutorder == -1 || mincut >= initcut)      break;  }  PQueueFree(ctrl, &parts[0]);  PQueueFree(ctrl, &parts[1]);  idxwspacefree(ctrl, nvtxs+1);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);}

//.........这里部分代码省略.........             ) {            k = j;          }        }        to = mydegrees[k].edge;        going_home = (myhome == to);        zero_gain = (mydegrees[k].ewgt == myrinfo->id);        fit_in_from = AreAllHVwgtsBelow(ncon,1.0,npwgts+from*ncon,0.0,npwgts+from*ncon,                      maxwgt+from*ncon);        better_balance_ft = IsHBalanceBetterFT(ncon,npwgts+from*ncon,                            npwgts+to*ncon,nvwgt,ubvec);        if (zero_gain &&            !going_home &&            !better_balance_ft &&            fit_in_from)          continue;        /*=====================================================================        * If we got here, we can now move the vertex from 'from' to 'to'         *======================================================================*/        graph->mincut -= mydegrees[k].ewgt-myrinfo->id;        /* Update where, weight, and ID/ED information of the vertex you moved */        saxpy2(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);        saxpy2(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);        where[i] = to;        myrinfo->ed += myrinfo->id-mydegrees[k].ewgt;        SWAP(myrinfo->id, mydegrees[k].ewgt, tmp);        if (mydegrees[k].ewgt == 0) {          myrinfo->ndegrees--;          mydegrees[k].edge = mydegrees[myrinfo->ndegrees].edge;          mydegrees[k].ewgt = mydegrees[myrinfo->ndegrees].ewgt;        }        else          mydegrees[k].edge = from;        /* Update the degrees of adjacent vertices */        for (j=xadj[i]; j<xadj[i+1]; j++) {          ii = adjncy[j];          me = where[ii];          myrinfo = rinfo+ii;          mydegrees = myrinfo->degrees;          if (me == from) {            INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);          }          else {            if (me == to) {              INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);            }          }          /* Remove contribution of the ed from 'from' */          if (me != from) {            for (k=0; k<myrinfo->ndegrees; k++) {              if (mydegrees[k].edge == from) {                if (mydegrees[k].ewgt == adjwgt[j]) {                  myrinfo->ndegrees--;                  mydegrees[k].edge = mydegrees[myrinfo->ndegrees].edge;                  mydegrees[k].ewgt = mydegrees[myrinfo->ndegrees].ewgt;                }                else                  mydegrees[k].ewgt -= adjwgt[j];                break;              }            }          }          /* Add contribution of the ed to 'to' */          if (me != to) {            for (k=0; k<myrinfo->ndegrees; k++) {              if (mydegrees[k].edge == to) {                mydegrees[k].ewgt += adjwgt[j];                break;              }            }            if (k == myrinfo->ndegrees) {              mydegrees[myrinfo->ndegrees].edge = to;              mydegrees[myrinfo->ndegrees++].ewgt = adjwgt[j];            }          }        }        nmoves++;      }    }    if (graph->mincut == oldcut)      break;  }  GKfree((void **)&minwgt, (void **)&maxwgt, (void **)&cand, LTERM);  return;}

//.........这里部分代码省略.........      ***********************************************************/      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);          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 {              oldgain = vwgt[kk]-rinfo[kk].edegrees[other];              rinfo[kk].edegrees[other] -= vwgt[k];              /* Since the moves are one-sided this vertex has not been moved yet */              PQueueUpdateUp(&parts, kk, oldgain, oldgain+vwgt[k]);             }          }          /* Insert the new vertex into the priority queue. Safe due to one-sided moves */          PQueueInsert(&parts, k, vwgt[k]-edegrees[other]);        }      }      mptr[nswaps+1] = nmind;      IFSET(ctrl->dbglvl, DBG_MOVEINFO,            mprintf("Moved %6D to %3D, Gain: %5D [%5D] /t[%5D %5D %5D] [%3D %2D]/n",                        higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain], pwgts[0], pwgts[1], pwgts[2], nswaps, limit));    }    /****************************************************************    * Roll back computation     *****************************************************************/    for (nswaps--; nswaps>mincutorder; nswaps--) {      higain = swaps[nswaps];      ASSERT(CheckNodePartitionParams(graph));      ASSERT(where[higain] == to);      INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);      where[higain] = 2;      BNDInsert(nbnd, bndind, bndptr, higain);      edegrees = rinfo[higain].edegrees;      edegrees[0] = edegrees[1] = 0;      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2)           rinfo[k].edegrees[to] -= vwgt[higain];        else          edegrees[where[k]] += vwgt[k];      }      /* Push nodes out of the separator */      for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {        k = mind[j];        ASSERT(where[k] == 2);        where[k] = other;        INC_DEC(pwgts[other], pwgts[2], vwgt[k]);        BNDDelete(nbnd, bndind, bndptr, k);        for (jj=xadj[k]; jj<xadj[k+1]; jj++) {          kk = adjncy[jj];          if (where[kk] == 2)             rinfo[kk].edegrees[other] += vwgt[k];        }      }    }    ASSERT(mincut == pwgts[2]);    IFSET(ctrl->dbglvl, DBG_REFINE,      mprintf("/tMinimum sep: %6D at %5D, PWGTS: [%6D %6D], NBND: %6D/n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));    graph->mincut = mincut;    graph->nbnd = nbnd;    if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))      break;  }  PQueueFree(ctrl, &parts);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs+1);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);}

//.........这里部分代码省略.........      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    *****************************************************************/    for (i=0; i<nswaps; i++)      moved[swaps[i]] = -1;  /* reset moved array */    for (nswaps--; nswaps>mincutorder; nswaps--) {      higain = swaps[nswaps];      to = where[higain] = (where[higain]+1)%2;

//.........这里部分代码省略.........    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 = 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);    saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);

//.........这里部分代码省略.........    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;}

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++) {//.........这里部分代码省略.........

//.........这里部分代码省略.........    }    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 (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);    saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);    saxpy(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);    }  }  if (ctrl->dbglvl&DBG_REFINE) {    printf("/tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);    for (l=0; l<ncon; l++)      printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);    printf("], LB: %.3f/n", Compute2WayHLoadImbalance(ncon, npwgts, tpwgts));  }  graph->mincut = mincut;  graph->nbnd = nbnd;  for (i=0; i<ncon; i++) {    PQueueFree(ctrl, &parts[i][0]);    PQueueFree(ctrl, &parts[i][1]);  }  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);}

//.........这里部分代码省略.........      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) {          for (k=0; k<myrinfo->ndegrees; k++) {            if (myedegrees[k].pid == from) {              if (myedegrees[k].ed == adjwgt[j])                myedegrees[k] = myedegrees[--myrinfo->ndegrees];              else                myedegrees[k].ed -= adjwgt[j];              break;            }          }        }        /* Add contribution to the .ed of 'to' */        if (me != to) {          for (k=0; k<myrinfo->ndegrees; k++) {            if (myedegrees[k].pid == to) {              myedegrees[k].ed += adjwgt[j];              break;            }          }

//.........这里部分代码省略.........            }            if (k == myndegrees)                continue;  /* break out if you did not find a candidate */            for (j=k+1; j<myndegrees; j++) {                to = myedegrees[j].pid;                if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||                        (myedegrees[j].ed == myedegrees[k].ed &&                         itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))                    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);                }

//.........这里部分代码省略.........  cpvec = idxwspacemalloc(ctrl, nparts);  npcmps = idxset(nparts, 0, idxwspacemalloc(ctrl, nparts));  for (i=0; i<nvtxs; i++)     perm[i] = todo[i] = i;  /* Find the connected componends induced by the partition */  ncmps = -1;  first = last = 0;  nleft = nvtxs;  while (nleft > 0) {    if (first == last) { /* Find another starting vertex */      cptr[++ncmps] = first;      ASSERT(touched[todo[0]] == 0);      i = todo[0];      cind[last++] = i;      touched[i] = 1;      me = where[i];      npcmps[me]++;    }    i = cind[first++];    k = perm[i];    j = todo[k] = todo[--nleft];    perm[j] = k;    for (j=xadj[i]; j<xadj[i+1]; j++) {      k = adjncy[j];      if (where[k] == me && !touched[k]) {        cind[last++] = k;        touched[k] = 1;      }    }  }  cptr[++ncmps] = first;  /* printf("I found %d components, for this %d-way partition/n", ncmps, nparts); */  if (ncmps > nparts) { /* There are more components than processors */    /* First determine the max allowed load imbalance */    tvwgt = idxsum(nparts, pwgts);    for (i=0; i<nparts; i++)      maxpwgt[i] = ubfactor*tpwgts[i]*tvwgt;    deltawgt = 5;    for (i=0; i<ncmps; i++) {      me = where[cind[cptr[i]]];  /* Get the domain of this component */      if (npcmps[me] == 1)        continue;  /* Skip it because it is contigous */      /*printf("Trying to move %d from %d/n", i, me); */      /* Determine the weight of the block to be moved and abort if too high */      for (cwgt=0, j=cptr[i]; j<cptr[i+1]; j++)         cwgt += vwgt[cind[j]];      if (cwgt > .30*pwgts[me])        continue;  /* Skip the component if it is over 30% of the weight */      /* Determine the connectivity */      idxset(nparts, 0, cpvec);      for (j=cptr[i]; j<cptr[i+1]; j++) {        ii = cind[j];        for (jj=xadj[ii]; jj<xadj[ii+1]; jj++)           cpvec[where[adjncy[jj]]] += adjwgt[jj];      }      cpvec[me] = 0;      target = -1;      for (j=0; j<nparts; j++) {        if (cpvec[j] > 0 && (cwgt < deltawgt || pwgts[j] + cwgt < maxpwgt[j])) {          if (target == -1 || cpvec[target] < cpvec[j])            target = j;        }      }      /* printf("/tMoving it to %d [%d]/n", target, cpvec[target]);*/      if (target != -1) {        /* Assign all the vertices of 'me' to 'target' and update data structures */        INC_DEC(pwgts[target], pwgts[me], cwgt);        npcmps[me]--;        MoveGroup(ctrl, graph, nparts, target, i, cptr, cind);      }    }  }  idxwspacefree(ctrl, nparts);  idxwspacefree(ctrl, nparts);  idxwspacefree(ctrl, nparts);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);  idxwspacefree(ctrl, nvtxs);}

/************************************************************************** This function takes a graph and produces a bisection by using a region* growing algorithm. The resulting partition is returned in* graph->where**************************************************************************/void GrowBisectionNode(CtrlType *ctrl, GraphType *graph, float ubfactor){  int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], tpwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *bndind;  idxtype *queue, *touched, *gain, *bestwhere;  nvtxs = graph->nvtxs;  xadj = graph->xadj;  vwgt = graph->vwgt;  adjncy = graph->adjncy;  adjwgt = graph->adjwgt;  bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");  queue = idxmalloc(nvtxs, "BisectGraph: queue");  touched = idxmalloc(nvtxs, "BisectGraph: touched");  tpwgts[0] = idxsum(nvtxs, vwgt);  tpwgts[1] = tpwgts[0]/2;  tpwgts[0] -= tpwgts[1];  maxpwgt[0] = ubfactor*tpwgts[0];  maxpwgt[1] = ubfactor*tpwgts[1];  minpwgt[0] = (1.0/ubfactor)*tpwgts[0];  minpwgt[1] = (1.0/ubfactor)*tpwgts[1];  /* Allocate memory for graph->rdata. Allocate sufficient memory for both edge and node */  graph->rdata = idxmalloc(5*nvtxs+3, "GrowBisectionNode: graph->rdata");  graph->pwgts    = graph->rdata;  graph->where    = graph->rdata + 3;  graph->bndptr   = graph->rdata + nvtxs + 3;  graph->bndind   = graph->rdata + 2*nvtxs + 3;  graph->nrinfo   = (NRInfoType *)(graph->rdata + 3*nvtxs + 3);  graph->id       = graph->rdata + 3*nvtxs + 3;  graph->ed       = graph->rdata + 4*nvtxs + 3;    where = graph->where;  bndind = graph->bndind;  nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);  bestcut = tpwgts[0]+tpwgts[1];  for (nbfs++; nbfs>0; nbfs--) {    idxset(nvtxs, 0, touched);    pwgts[1] = tpwgts[0]+tpwgts[1];    pwgts[0] = 0;    idxset(nvtxs, 1, where);    queue[0] = RandomInRange(nvtxs);    touched[queue[0]] = 1;    first = 0; last = 1;    nleft = nvtxs-1;    drain = 0;    /* Start the BFS from queue to get a partition */    if (nbfs >= 1) {      for (;;) {        if (first == last) { /* Empty. Disconnected graph! */          if (nleft == 0 || drain)            break;            k = RandomInRange(nleft);          for (i=0; i<nvtxs; i++) {            if (touched[i] == 0) {              if (k == 0)                break;              else                k--;            }          }          queue[0] = i;          touched[i] = 1;          first = 0; last = 1;;          nleft--;        }        i = queue[first++];        if (pwgts[1]-vwgt[i] < minpwgt[1]) {          drain = 1;          continue;        }        where[i] = 0;        INC_DEC(pwgts[0], pwgts[1], vwgt[i]);        if (pwgts[1] <= maxpwgt[1])          break;        drain = 0;        for (j=xadj[i]; j<xadj[i+1]; j++) {          k = adjncy[j];          if (touched[k] == 0) {            queue[last++] = k;            touched[k] = 1;            nleft--;//.........这里部分代码省略.........

//.........这里部分代码省略.........        if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])           k = j;      }      to = myedegrees[k].pid;      if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->id < 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 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);        }

/************************************************************************** This function takes a graph and produces a bisection by using a region* growing algorithm. The resulting partition is returned in* graph->where**************************************************************************/void GrowBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor){  int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where;  idxtype *queue, *touched, *gain, *bestwhere;  nvtxs = graph->nvtxs;  xadj = graph->xadj;  vwgt = graph->vwgt;  adjncy = graph->adjncy;  adjwgt = graph->adjwgt;  Allocate2WayPartitionMemory(ctrl, graph);  where = graph->where;  bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");  queue = idxmalloc(nvtxs, "BisectGraph: queue");  touched = idxmalloc(nvtxs, "BisectGraph: touched");  ASSERTP(tpwgts[0]+tpwgts[1] == idxsum(nvtxs, vwgt), ("%d %d/n", tpwgts[0]+tpwgts[1], idxsum(nvtxs, vwgt)));  maxpwgt[0] = ubfactor*tpwgts[0];  maxpwgt[1] = ubfactor*tpwgts[1];  minpwgt[0] = (1.0/ubfactor)*tpwgts[0];  minpwgt[1] = (1.0/ubfactor)*tpwgts[1];  nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);  bestcut = idxsum(nvtxs, graph->adjwgtsum)+1;  /* The +1 is for the 0 edges case */  for (; nbfs>0; nbfs--) {    idxset(nvtxs, 0, touched);    pwgts[1] = tpwgts[0]+tpwgts[1];    pwgts[0] = 0;    idxset(nvtxs, 1, where);    queue[0] = RandomInRange(nvtxs);    touched[queue[0]] = 1;    first = 0; last = 1;    nleft = nvtxs-1;    drain = 0;    /* Start the BFS from queue to get a partition */    for (;;) {      if (first == last) { /* Empty. Disconnected graph! */        if (nleft == 0 || drain)          break;        k = RandomInRange(nleft);        for (i=0; i<nvtxs; i++) {          if (touched[i] == 0) {            if (k == 0)              break;            else              k--;          }        }        queue[0] = i;        touched[i] = 1;        first = 0; last = 1;;        nleft--;      }      i = queue[first++];      if (pwgts[0] > 0 && pwgts[1]-vwgt[i] < minpwgt[1]) {        drain = 1;        continue;      }      where[i] = 0;      INC_DEC(pwgts[0], pwgts[1], vwgt[i]);      if (pwgts[1] <= maxpwgt[1])        break;      drain = 0;      for (j=xadj[i]; j<xadj[i+1]; j++) {        k = adjncy[j];        if (touched[k] == 0) {          queue[last++] = k;          touched[k] = 1;          nleft--;        }      }    }    /* Check to see if we hit any bad limiting cases */    if (pwgts[1] == 0) {       i = RandomInRange(nvtxs);      where[i] = 1;      INC_DEC(pwgts[1], pwgts[0], vwgt[i]);    }    /*************************************************************//.........这里部分代码省略.........

/************************************************************************** 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) {//.........这里部分代码省略.........

//.........这里部分代码省略.........      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);          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], iend=xadj[k+1]; jj<iend; jj++) {            kk = adjncy[jj];            if (where[kk] != 2)               edegrees[where[kk]] += vwgt[kk];            else {              rinfo[kk].edegrees[other] -= vwgt[k];              /* Since the moves are one-sided this vertex has not been moved yet */              rpqUpdate(queue, kk, vwgt[kk]-rinfo[kk].edegrees[other]);             }          }          /* Insert the new vertex into the priority queue. Safe due to one-sided moves */          rpqInsert(queue, k, vwgt[k]-edegrees[other]);        }      }      mptr[nswaps+1] = nmind;      IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopwctimer(ctrl->Aux1Tmr));      IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,            printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] /t[%5"PRIDX" %5"PRIDX" %5"PRIDX"] [%3"PRIDX" %2"PRIDX"]/n",                 higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain],                 pwgts[0], pwgts[1], pwgts[2], nswaps, limit));    }    IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopwctimer(ctrl->Aux3Tmr));    /****************************************************************    * Roll back computation     *****************************************************************/    IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startwctimer(ctrl->Aux2Tmr));    for (nswaps--; nswaps>mincutorder; nswaps--) {      higain = swaps[nswaps];      ASSERT(CheckNodePartitionParams(graph));      ASSERT(where[higain] == to);      INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);      where[higain] = 2;      BNDInsert(nbnd, bndind, bndptr, higain);      edegrees = rinfo[higain].edegrees;      edegrees[0] = edegrees[1] = 0;      for (j=xadj[higain]; j<xadj[higain+1]; j++) {        k = adjncy[j];        if (where[k] == 2)           rinfo[k].edegrees[to] -= vwgt[higain];        else          edegrees[where[k]] += vwgt[k];      }      /* Push nodes out of the separator */      for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {        k = mind[j];        ASSERT(where[k] == 2);        where[k] = other;        INC_DEC(pwgts[other], pwgts[2], vwgt[k]);        BNDDelete(nbnd, bndind, bndptr, k);        for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {          kk = adjncy[jj];          if (where[kk] == 2)             rinfo[kk].edegrees[other] += vwgt[k];        }      }    }    IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopwctimer(ctrl->Aux2Tmr));    ASSERT(mincut == pwgts[2]);    IFSET(ctrl->dbglvl, METIS_DBG_REFINE,      printf("/tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"/n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));    graph->mincut = mincut;    graph->nbnd   = nbnd;    if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))      break;  }  rpqDestroy(queue);  WCOREPOP;}