ometis.c

多层权核k均值算法

* bisections and selects the best.
**************************************************************************/
void MlevelNodeBisectionMultiple(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
{
  int i, nvtxs, cnvtxs, mincut, tmp;
  GraphType *cgraph; 
  idxtype *bestwhere;

  if (ctrl->nseps == 1 || graph->nvtxs < (ctrl->oflags&OFLAG_COMPRESS ? 1000 : 2000)) {
    MlevelNodeBisection(ctrl, graph, tpwgts, ubfactor);
    return;
  }

  nvtxs = graph->nvtxs;

  if (ctrl->oflags&OFLAG_COMPRESS) { /* Multiple separators at the original graph */
    bestwhere = idxmalloc(nvtxs, "MlevelNodeBisection2: bestwhere");
    mincut = nvtxs;

    for (i=ctrl->nseps; i>0; i--) {
      MlevelNodeBisection(ctrl, graph, tpwgts, ubfactor);

      /* printf("%5d ", cgraph->mincut); */

      if (graph->mincut < mincut) {
        mincut = graph->mincut;
        idxcopy(nvtxs, graph->where, bestwhere);
      }

      GKfree((void**) &graph->rdata, LTERM);
    
      if (mincut == 0)
        break;
    }
    /* printf("[%5d]\n", mincut); */

    Allocate2WayNodePartitionMemory(ctrl, graph);
    idxcopy(nvtxs, bestwhere, graph->where);
    free(bestwhere);

    Compute2WayNodePartitionParams(ctrl, graph);
  }
  else {  /* Coarsen it a bit */
    ctrl->CoarsenTo = nvtxs-1;

    cgraph = Coarsen2Way(ctrl, graph);

    cnvtxs = cgraph->nvtxs;

    bestwhere = idxmalloc(cnvtxs, "MlevelNodeBisection2: bestwhere");
    mincut = nvtxs;

    for (i=ctrl->nseps; i>0; i--) {
      ctrl->CType += 20; /* This is a hack. Look at coarsen.c */
      MlevelNodeBisection(ctrl, cgraph, tpwgts, ubfactor);

      /* printf("%5d ", cgraph->mincut); */

      if (cgraph->mincut < mincut) {
        mincut = cgraph->mincut;
        idxcopy(cnvtxs, cgraph->where, bestwhere);
      }

      GKfree((void**) &cgraph->rdata, LTERM);
    
      if (mincut == 0)
        break;
    }
    /* printf("[%5d]\n", mincut); */

    Allocate2WayNodePartitionMemory(ctrl, cgraph);
    idxcopy(cnvtxs, bestwhere, cgraph->where);
    free(bestwhere);

    Compute2WayNodePartitionParams(ctrl, cgraph);

    Refine2WayNode(ctrl, graph, cgraph, ubfactor);
  }

}

/*************************************************************************
* This function performs multilevel bisection
**************************************************************************/
void MlevelNodeBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
{
  GraphType *cgraph;

  ctrl->CoarsenTo = graph->nvtxs/8;
  if (ctrl->CoarsenTo > 100)
    ctrl->CoarsenTo = 100;
  else if (ctrl->CoarsenTo < 40)
    ctrl->CoarsenTo = 40;
  ctrl->maxvwgt = (int) 1.5*((tpwgts[0]+tpwgts[1])/ctrl->CoarsenTo);

  cgraph = Coarsen2Way(ctrl, graph);

  switch (ctrl->IType) {
    case IPART_GGPKL:
      Init2WayPartition(ctrl, cgraph, tpwgts, ubfactor);

      IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SepTmr));

      Compute2WayPartitionParams(ctrl, cgraph);
      ConstructSeparator(ctrl, cgraph, ubfactor);

      IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SepTmr));
      break;
    case IPART_GGPKLNODE:
      InitSeparator(ctrl, cgraph, ubfactor);
      break;
  }

  Refine2WayNode(ctrl, graph, cgraph, ubfactor);

}




/*************************************************************************
* This function takes a graph and a bisection and splits it into two graphs.
* This function relies on the fact that adjwgt is all equal to 1.
**************************************************************************/
void SplitGraphOrder(CtrlType *ctrl, GraphType *graph, GraphType *lgraph, GraphType *rgraph)
{
  int i, ii, j, k, l, istart, iend, mypart, nvtxs, snvtxs[3], snedges[3];
  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr, *bndind;
  idxtype *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *sadjwgtsum[2], *slabel[2];
  idxtype *rename;
  idxtype *auxadjncy, *auxadjwgt;

  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SplitTmr));

  nvtxs = graph->nvtxs;
  xadj = graph->xadj;
  vwgt = graph->vwgt;
  adjncy = graph->adjncy;
  adjwgt = graph->adjwgt;
  adjwgtsum = graph->adjwgtsum;
  label = graph->label;
  where = graph->where;
  bndptr = graph->bndptr;
  bndind = graph->bndind;
  ASSERT(bndptr != NULL);

  rename = idxwspacemalloc(ctrl, nvtxs);
  
  snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
  for (i=0; i<nvtxs; i++) {
    k = where[i];
    rename[i] = snvtxs[k]++;
    snedges[k] += xadj[i+1]-xadj[i];
  }

  SetUpSplitGraph(graph, lgraph, snvtxs[0], snedges[0]);
  sxadj[0] = lgraph->xadj;
  svwgt[0] = lgraph->vwgt;
  sadjwgtsum[0] = lgraph->adjwgtsum;
  sadjncy[0] = lgraph->adjncy; 
  sadjwgt[0] = lgraph->adjwgt; 
  slabel[0] = lgraph->label;

  SetUpSplitGraph(graph, rgraph, snvtxs[1], snedges[1]);
  sxadj[1] = rgraph->xadj;
  svwgt[1] = rgraph->vwgt;
  sadjwgtsum[1] = rgraph->adjwgtsum;
  sadjncy[1] = rgraph->adjncy; 
  sadjwgt[1] = rgraph->adjwgt; 
  slabel[1] = rgraph->label;

  /* Go and use bndptr to also mark the boundary nodes in the two partitions */
  for (ii=0; ii<graph->nbnd; ii++) {
    i = bndind[ii];
    for (j=xadj[i]; j<xadj[i+1]; j++)
      bndptr[adjncy[j]] = 1;
  }

  snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
  sxadj[0][0] = sxadj[1][0] = 0;
  for (i=0; i<nvtxs; i++) {
    if ((mypart = where[i]) == 2)
      continue;

    istart = xadj[i];
    iend = xadj[i+1];
    if (bndptr[i] == -1) { /* This is an interior vertex */
      auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
      for(j=istart; j<iend; j++) 
        auxadjncy[j] = adjncy[j];
      snedges[mypart] += iend-istart;
    }
    else {
      auxadjncy = sadjncy[mypart];
      l = snedges[mypart];
      for (j=istart; j<iend; j++) {
        k = adjncy[j];
        if (where[k] == mypart) 
          auxadjncy[l++] = k;
      }
      snedges[mypart] = l;
    }

    svwgt[mypart][snvtxs[mypart]] = vwgt[i];
    sadjwgtsum[mypart][snvtxs[mypart]] = snedges[mypart]-sxadj[mypart][snvtxs[mypart]];
    slabel[mypart][snvtxs[mypart]] = label[i];
    sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
  }

  for (mypart=0; mypart<2; mypart++) {
    iend = snedges[mypart];
    idxset(iend, 1, sadjwgt[mypart]);

    auxadjncy = sadjncy[mypart];
    for (i=0; i<iend; i++) 
      auxadjncy[i] = rename[auxadjncy[i]];
  }

  lgraph->nvtxs = snvtxs[0];
  lgraph->nedges = snedges[0];
  rgraph->nvtxs = snvtxs[1];
  rgraph->nedges = snedges[1];

  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SplitTmr));

  idxwspacefree(ctrl, nvtxs);

}

/*************************************************************************
* This function uses MMD to order the graph. The vertices are numbered
* from lastvtx downwards
**************************************************************************/
void MMDOrder(CtrlType *ctrl, GraphType *graph, idxtype *order, int lastvtx)
{
  int i, j, k, nvtxs, nofsub, firstvtx;
  idxtype *xadj, *adjncy, *label;
  idxtype *perm, *iperm, *head, *qsize, *list, *marker;

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

  /* Relabel the vertices so that it starts from 1 */
  k = xadj[nvtxs];
  for (i=0; i<k; i++)
    adjncy[i]++;
  for (i=0; i<nvtxs+1; i++)
    xadj[i]++;

  perm = idxmalloc(6*(nvtxs+5), "MMDOrder: perm");
  iperm = perm + nvtxs + 5;
  head = iperm + nvtxs + 5;
  qsize = head + nvtxs + 5;
  list = qsize + nvtxs + 5;
  marker = list + nvtxs + 5;

  genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker, MAXIDX, &nofsub);

  label = graph->label;
  firstvtx = lastvtx-nvtxs;
  for (i=0; i<nvtxs; i++)
    order[label[i]] = firstvtx+iperm[i]-1;

  free(perm);

  /* Relabel the vertices so that it starts from 0 */
  for (i=0; i<nvtxs+1; i++)
    xadj[i]--;
  k = xadj[nvtxs];
  for (i=0; i<k; i++)
    adjncy[i]--;
}


/*************************************************************************
* This function takes a graph and a bisection and splits it into two graphs.
* It relies on the fact that adjwgt is all set to 1.
**************************************************************************/
int SplitGraphOrderCC(CtrlType *ctrl, GraphType *graph, GraphType *sgraphs, int ncmps, idxtype *cptr, idxtype *cind)
{
  int i, ii, iii, j, k, l, istart, iend, mypart, nvtxs, snvtxs, snedges;
  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr, *bndind;
  idxtype *sxadj, *svwgt, *sadjncy, *sadjwgt, *sadjwgtsum, *slabel;
  idxtype *rename;
  idxtype *auxadjncy, *auxadjwgt;

  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SplitTmr));

  nvtxs = graph->nvtxs;
  xadj = graph->xadj;
  vwgt = graph->vwgt;
  adjncy = graph->adjncy;
  adjwgt = graph->adjwgt;
  adjwgtsum = graph->adjwgtsum;
  label = graph->label;
  where = graph->where;
  bndptr = graph->bndptr;
  bndind = graph->bndind;
  ASSERT(bndptr != NULL);

  /* Go and use bndptr to also mark the boundary nodes in the two partitions */
  for (ii=0; ii<graph->nbnd; ii++) {
    i = bndind[ii];
    for (j=xadj[i]; j<xadj[i+1]; j++)
      bndptr[adjncy[j]] = 1;
  }

  rename = idxwspacemalloc(ctrl, nvtxs);
  
  /* Go and split the graph a component at a time */
  for (iii=0; iii<ncmps; iii++) {
    RandomPermute(cptr[iii+1]-cptr[iii], cind+cptr[iii], 0);
    snvtxs = snedges = 0;
    for (j=cptr[iii]; j<cptr[iii+1]; j++) {
      i = cind[j];
      rename[i] = snvtxs++;
      snedges += xadj[i+1]-xadj[i];
    }

    SetUpSplitGraph(graph, sgraphs+iii, snvtxs, snedges);
    sxadj = sgraphs[iii].xadj;
    svwgt = sgraphs[iii].vwgt;
    sadjwgtsum = sgraphs[iii].adjwgtsum;
    sadjncy = sgraphs[iii].adjncy;
    sadjwgt = sgraphs[iii].adjwgt;
    slabel = sgraphs[iii].label;

    snvtxs = snedges = sxadj[0] = 0;
    for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
      i = cind[ii];

      istart = xadj[i];
      iend = xadj[i+1];
      if (bndptr[i] == -1) { /* This is an interior vertex */
        auxadjncy = sadjncy + snedges - istart;
        auxadjwgt = sadjwgt + snedges - istart;
        for(j=istart; j<iend; j++) 
          auxadjncy[j] = adjncy[j];
        snedges += iend-istart;
      }
      else {
        l = snedges;
        for (j=istart; j<iend; j++) {
          k = adjncy[j];
          if (where[k] != 2) 
            sadjncy[l++] = k;
        }
        snedges = l;
      }

      svwgt[snvtxs] = vwgt[i];
      sadjwgtsum[snvtxs] = snedges-sxadj[snvtxs];
      slabel[snvtxs] = label[i];
      sxadj[++snvtxs] = snedges;
    }

    idxset(snedges, 1, sadjwgt);
    for (i=0; i<snedges; i++) 
      sadjncy[i] = rename[sadjncy[i]];

    sgraphs[iii].nvtxs = snvtxs;
    sgraphs[iii].nedges = snedges;
    sgraphs[iii].ncon = 1;

    if (snvtxs < MMDSWITCH)
      sgraphs[iii].adjwgt = NULL;  /* A marker to call MMD on the driver */
  }

  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SplitTmr));

  idxwspacefree(ctrl, nvtxs);

  return ncmps;

}