subdomains.c

多层权核k均值算法

      /*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((void **) &cand, (void **) &cand2, LTERM);
}


/*************************************************************************
* 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) {
            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 == myrinfo->ndegrees) {
          myedegrees[myrinfo->ndegrees].pid = to;
          myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
        }
      }

      /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
      if (me != from && me != to) {
        pmat[me*nparts+from] -= adjwgt[j];
        pmat[from*nparts+me] -= adjwgt[j];
        if (pmat[me*nparts+from] == 0) 
          ndoms[me]--;
        if (pmat[from*nparts+me] == 0) 
          ndoms[from]--;

        if (pmat[me*nparts+to] == 0) 
          ndoms[me]++;
        if (pmat[to*nparts+me] == 0) 
          ndoms[to]++;

        pmat[me*nparts+to] += adjwgt[j];
        pmat[to*nparts+me] += adjwgt[j];
      }

      ASSERT(CheckRInfo(myrinfo));
    }

    ASSERT(CheckRInfo(graph->rinfo+i));
  }

  graph->nbnd = nbnd;

}




/*************************************************************************
* This function finds all the connected components induced by the 
* partitioning vector in wgraph->where and tries to push them around to 
* remove some of them
**************************************************************************/
void EliminateComponents(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
{
  int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, other, target, deltawgt;
  idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt;
  idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps;

  nvtxs = graph->nvtxs;
  xadj = graph->xadj;
  adjncy = graph->adjncy;
  vwgt = graph->vwgt;
  adjwgt = graph->adjwgt;

  where = graph->where;
  pwgts = graph->pwgts;

  touched = idxset(nvtxs, 0, idxwspacemalloc(ctrl, nvtxs));
  cptr = idxwspacemalloc(ctrl, nvtxs);
  cind = idxwspacemalloc(ctrl, nvtxs);
  perm = idxwspacemalloc(ctrl, nvtxs);
  todo = idxwspacemalloc(ctrl, nvtxs);
  maxpwgt = idxwspacemalloc(ctrl, nparts);
  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 moves a collection of vertices and updates their rinfo
**************************************************************************/
void MoveGroup(CtrlType *ctrl, GraphType *graph, int nparts, int to, int gid, idxtype *ptr, 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=ptr[gid]; iii<ptr[gid+1]; 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 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) {
            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 == myrinfo->ndegrees) {
          myedegrees[myrinfo->ndegrees].pid = to;
          myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
        }
      }

      ASSERT(CheckRInfo(myrinfo));
    }

    ASSERT(CheckRInfo(graph->rinfo+i));
  }

  graph->nbnd = nbnd;

}