/*
* Copyright 1997, Regents of the University of Minnesota
*
* kwayvolrefine.c
*
* This file contains the driving routines for multilevel k-way refinement
*
* Started 7/28/97
* George
*
* $Id: kwayvolrefine.c,v 1.2 1998/11/30 16:13:57 karypis Exp $
*/
#include <metis.h>
/*************************************************************************
* This function is the entry point of refinement
**************************************************************************/
void RefineVolKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, long nparts,
float *tpwgts, float ubfactor)
{
long i, nlevels;
GraphType *ptr;
IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
/* Take care any non-contiguity */
if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
ComputeVolKWayPartitionParams(ctrl, graph, nparts);
EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
EliminateVolSubDomainEdges(ctrl, graph, nparts, tpwgts);
EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
}
/* Determine how many levels are there */
for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
/* Compute the parameters of the coarsest graph */
ComputeVolKWayPartitionParams(ctrl, graph, nparts);
for (i=0; ;i++) {
/*PrintSubDomainGraph(graph, nparts, graph->where);*/
MALLOC_CHECK(NULL);
IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
switch (ctrl->RType) {
case RTYPE_KWAYRANDOM:
Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1);
break;
case RTYPE_KWAYRANDOM_MCONN:
Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1);
break;
}
ComputeVolKWayBoundary(ctrl, graph, nparts);
}
switch (ctrl->RType) {
case RTYPE_KWAYRANDOM:
Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
break;
case RTYPE_KWAYRANDOM_MCONN:
Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
break;
}
IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
if (graph == orggraph)
break;
GKfree(&graph->gdata, LTERM); /* Deallocate the graph related arrays */
graph = graph->finer;
IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
ProjectVolKWayPartition(ctrl, graph, nparts);
IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
}
if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
switch (ctrl->RType) {
case RTYPE_KWAYRANDOM:
Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8);
Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
break;
case RTYPE_KWAYRANDOM_MCONN:
Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8);
Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
break;
}
}
EliminateVolComponents(ctrl, graph, nparts, tpwgts, ubfactor);
IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
}
/*************************************************************************
* This function allocates memory for k-way edge refinement
**************************************************************************/
void AllocateVolKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, long nparts)
{
long nvtxs, pad64;
nvtxs = graph->nvtxs;
pad64 = (3*nvtxs+nparts)%2;
graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(VRInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateVolKWayPartitionMemory: rdata");
graph->pwgts = graph->rdata;
graph->where = graph->rdata + nparts;
graph->bndptr = graph->rdata + nvtxs + nparts;
graph->bndind = graph->rdata + 2*nvtxs + nparts;
graph->vrinfo = (VRInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
}
/*************************************************************************
* This function computes the initial id/ed
**************************************************************************/
void ComputeVolKWayPartitionParams(CtrlType *ctrl, GraphType *graph, long nparts)
{
long i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where;
VRInfoType *rinfo, *myrinfo, *orinfo;
VEDegreeType *myedegrees, *oedegrees;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
vwgt = graph->vwgt;
adjncy = graph->adjncy;
adjwgt = graph->adjwgt;
where = graph->where;
pwgts = idxset(nparts, 0, graph->pwgts);
rinfo = graph->vrinfo;
/*------------------------------------------------------------
/ Compute now the id/ed degrees
/------------------------------------------------------------*/
ctrl->wspace.cdegree = 0;
mincut = 0;
for (i=0; i<nvtxs; i++) {
me = where[i];
pwgts[me] += vwgt[i];
myrinfo = rinfo+i;
myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
myrinfo->edegrees = NULL;
for (j=xadj[i]; j<xadj[i+1]; j++) {
if (me == where[adjncy[j]]) {
myrinfo->id += adjwgt[j];
myrinfo->nid++;
}
}
myrinfo->ed = graph->adjwgtsum[i] - myrinfo->id;
mincut += myrinfo->ed;
/* Time to compute the particular external degrees */
if (myrinfo->ed > 0) {
myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
for (j=xadj[i]; j<xadj[i+1]; j++) {
other = where[adjncy[j]];
if (me != other) {
for (k=0; k<myrinfo->ndegrees; k++) {
if (myedegrees[k].pid == other) {
myedegrees[k].ed += adjwgt[j];
myedegrees[k].ned++;
break;
}
}
if (k == myrinfo->ndegrees) {
myedegrees[myrinfo->ndegrees].gv = 0;
myedegrees[myrinfo->ndegrees].pid = other;
myedegrees[myrinfo->ndegrees].ed = adjwgt[j];
myedegrees[myrinfo->ndegrees++].ned = 1;
}
}
}
ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
}
}
graph->mincut = mincut/2;
ComputeKWayVolGains(ctrl, graph, nparts);
}
/*************************************************************************
* This function computes the initial id/ed
**************************************************************************/
void ComputeKWayVolGains(CtrlType *ctrl, GraphType *graph, long nparts)
{
long i, ii, j, k, kk, l, nvtxs, me, other, pid, myndegrees;
idxtype *xadj, *vsize, *adjncy, *adjwgt, *where, *bndind, *bndptr, *ophtable;
VRInfoType *rinfo, *myrinfo, *orinfo;
VEDegreeType *myedegrees, *oedegrees;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
vsize = graph->vsize;
adjncy = graph->adjncy;
adjwgt = graph->adjwgt;
where = graph->where;
bndind = graph->bndind;
bndptr = idxset(nvtxs, -1, graph->bndptr);
rinfo = graph->vrinfo;
ophtable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
/*------------------------------------------------------------
/ Compute now the iv/ev degrees
/------------------------------------------------------------*/
graph->minvol = graph->nbnd = 0;
for (i=0; i<nvtxs; i++) {
myrinfo = rinfo+i;
myrinfo->gv = -MAXIDX;
if (myrinfo->ndegrees > 0) {
me = where[i];
myedegrees = myrinfo->edegrees;
myndegrees = myrinfo->ndegrees;
graph->minvol += myndegrees*vsize[i];
for (j=xadj[i]; j<xadj[i+1]; j++) {
ii = adjncy[j];
other = where[ii];
orinfo = rinfo+ii;
oedegrees = orinfo->edegrees;
for (k=0; k<orinfo->ndegrees; k++)
ophtable[oedegrees[k].pid] = k;
ophtable[other] = 1; /* this is to simplify coding */
if (me == other) {
/* Find which domains 'i' is connected and 'ii' is not and update their gain */
for (k=0; k<myndegrees; k++) {
if (ophtable[myedegrees[k].pid] == -1)
myedegrees[k].gv -= vsize[ii];
}
}
else {
ASSERT(ophtable[me] != -1);
if (oedegrees[ophtable[me]].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
/* Increase the gains for all the common domains between 'i' and 'ii' */
for (k=0; k<myndegrees; k++) {
if (ophtable[myedegrees[k].pid] != -1)
myedegrees[k].gv += vsize[ii];
}
}
else {
/* Find which domains 'i' is connected and 'ii' is not and update their gain */
for (k=0; k<myndegrees; k++) {
if (ophtable[myedegrees[k].pid] == -1)
myedegrees[k].gv -= vsize[ii];
}
}
}
for (kk=0; kk<orinfo->ndegrees; kk++)
ophtable[oedegrees[kk].pid] = -1;
ophtable[other] = -1;
}
/* Compute the max vgain */
for (k=0; k<myndegrees; k++) {
if (myedegrees[k].gv > myrinfo->gv)
myrinfo->gv = myedegrees[k].gv;
}
}
if (myrinfo->ed > 0 && myrinfo->id == 0)
myrinfo->gv += vsize[i];
if (myrinfo->gv >= 0 || myrinfo->ed-myrinfo->id >= 0)
BNDInsert(graph->nbnd, bndind, bndptr, i);
}
idxwspacefree(ctrl, nparts);
}
/*************************************************************************
* This function projects a partition, and at the same time computes the
* parameters for refinement.
**************************************************************************/
void ProjectVolKWayPartition(CtrlType *ctrl, GraphType *graph, long nparts)
{
long i, j, k, nvtxs, me, other, istart, iend, ndegrees;
idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
idxtype *cmap, *where;
idxtype *cwhere;
GraphType *cgraph;
VRInfoType *crinfo, *rinfo, *myrinfo;
VEDegreeType *myedegrees;
idxtype *htable;
cgraph = graph->coarser;
cwhere = cgraph->where;
crinfo = cgraph->vrinfo;
nvtxs = graph->nvtxs;
cmap = graph->cmap;
xadj = graph->xadj;
adjncy = graph->adjncy;
adjwgt = graph->adjwgt;
adjwgtsum = graph->adjwgtsum;
AllocateVolKWayPartitionMemory(ctrl, graph, nparts);
where = graph->where;
rinfo = graph->vrinfo;
/* Go through and project partition and compute id/ed for the nodes */
for (i=0; i<nvtxs; i++) {
k = cmap[i];
where[i] = cwhere[k];
cmap[i] = crinfo[k].ed; /* For optimization */
}
htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
ctrl->wspace.cdegree = 0;
for (i=0; i<nvtxs; i++) {
me = where[i];
myrinfo = rinfo+i;
myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
myrinfo->edegrees = NULL;
myrinfo->id = adjwgtsum[i];
myrinfo->nid = xadj[i+1]-xadj[i];
if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
istart = xadj[i];
iend = xadj[i+1];
myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
ctrl->wspace.cdegree += iend-istart;
ndegrees = 0;
for (j=istart; j<iend; j++) {
other = where[adjncy[j]];
if (me != other) {
myrinfo->ed += adjwgt[j];
myrinfo->nid--;
if ((k = htable[other]) == -1) {
htable[other] = ndegrees;
myedegrees[ndegrees].gv = 0;
myedegrees[ndegrees].pid = other;
myedegrees[ndegrees].ed = adjwgt[j];
myedegrees[ndegrees++].ned = 1;
}
else {
myedegrees[k].ed += adjwgt[j];
myedegrees[k].ned++;
}
}
}
myrinfo->id -= myrinfo->ed;
/* Remove space for edegrees if it was interior */
if (myrinfo->ed == 0) {
myrinfo->edegrees = NULL;
ctrl->wspace.cdegree -= iend-istart;
}
else {
myrinfo->ndegrees = ndegrees;
for (j=0; j<ndegrees; j++)
htable[myedegrees[j].pid] = -1;
}
}
}
ComputeKWayVolGains(ctrl, graph, nparts);
idxcopy(nparts, cgraph->pwgts, graph->pwgts);
graph->mincut = cgraph->mincut;
FreeGraph(graph->coarser);
graph->coarser = NULL;
idxwspacefree(ctrl, nparts);
}
/*************************************************************************
* This function computes the boundary definition for balancing
**************************************************************************/
void ComputeVolKWayBoundary(CtrlType *ctrl, GraphType *graph, long nparts)
{
long i, nvtxs, nbnd;
idxtype *bndind, *bndptr;
nvtxs = graph->nvtxs;
bndind = graph->bndind;
bndptr = idxset(nvtxs, -1, graph->bndptr);
/*------------------------------------------------------------
/ Compute the new boundary
/------------------------------------------------------------*/
nbnd = 0;
for (i=0; i<nvtxs; i++) {
if (graph->vrinfo[i].gv >=0 || graph->vrinfo[i].ed-graph->vrinfo[i].id >= 0)
BNDInsert(nbnd, bndind, bndptr, i);
}
graph->nbnd = nbnd;
}
/*************************************************************************
* This function computes the boundary definition for balancing
**************************************************************************/
void ComputeVolKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, long nparts)
{
long i, nvtxs, nbnd;
idxtype *bndind, *bndptr;
nvtxs = graph->nvtxs;
bndind = graph->bndind;
bndptr = idxset(nvtxs, -1, graph->bndptr);
/*------------------------------------------------------------
/ Compute the new boundary
/------------------------------------------------------------*/
nbnd = 0;
for (i=0; i<nvtxs; i++) {
if (graph->vrinfo[i].ed > 0)
BNDInsert(nbnd, bndind, bndptr, i);
}
graph->nbnd = nbnd;
}
syntax highlighted by Code2HTML, v. 0.9.1