Cloned library METIS with extra build files for internal package management.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 

464 lines
12 KiB

/*
* Copyright 1997, Regents of the University of Minnesota
*
* debug.c
*
* This file contains code that performs self debugging
*
* Started 7/24/97
* George
*
*/
#include "metislib.h"
/*************************************************************************/
/*! This function computes the total edgecut
*/
/*************************************************************************/
idx_t ComputeCut(graph_t *graph, idx_t *where)
{
idx_t i, j, cut;
if (graph->adjwgt == NULL) {
for (cut=0, i=0; i<graph->nvtxs; i++) {
for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
if (where[i] != where[graph->adjncy[j]])
cut++;
}
}
else {
for (cut=0, i=0; i<graph->nvtxs; i++) {
for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
if (where[i] != where[graph->adjncy[j]])
cut += graph->adjwgt[j];
}
}
return cut/2;
}
/*************************************************************************/
/*! This function computes the total volume
*/
/*************************************************************************/
idx_t ComputeVolume(graph_t *graph, idx_t *where)
{
idx_t i, j, k, me, nvtxs, nparts, totalv;
idx_t *xadj, *adjncy, *vsize, *marker;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
adjncy = graph->adjncy;
vsize = graph->vsize;
nparts = where[iargmax(nvtxs, where,1)]+1;
marker = ismalloc(nparts, -1, "ComputeVolume: marker");
totalv = 0;
for (i=0; i<nvtxs; i++) {
marker[where[i]] = i;
for (j=xadj[i]; j<xadj[i+1]; j++) {
k = where[adjncy[j]];
if (marker[k] != i) {
marker[k] = i;
totalv += (vsize ? vsize[i] : 1);
}
}
}
gk_free((void **)&marker, LTERM);
return totalv;
}
/*************************************************************************/
/*! This function computes the cut given the graph and a where vector
*/
/*************************************************************************/
idx_t ComputeMaxCut(graph_t *graph, idx_t nparts, idx_t *where)
{
idx_t i, j, maxcut;
idx_t *cuts;
cuts = ismalloc(nparts, 0, "ComputeMaxCut: cuts");
if (graph->adjwgt == NULL) {
for (i=0; i<graph->nvtxs; i++) {
for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
if (where[i] != where[graph->adjncy[j]])
cuts[where[i]]++;
}
}
else {
for (i=0; i<graph->nvtxs; i++) {
for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
if (where[i] != where[graph->adjncy[j]])
cuts[where[i]] += graph->adjwgt[j];
}
}
maxcut = cuts[iargmax(nparts, cuts,1)];
printf("%zu => %"PRIDX"\n", iargmax(nparts, cuts,1), maxcut);
gk_free((void **)&cuts, LTERM);
return maxcut;
}
/*************************************************************************/
/*! This function checks whether or not the boundary information is correct
*/
/*************************************************************************/
idx_t CheckBnd(graph_t *graph)
{
idx_t i, j, nvtxs, nbnd;
idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
adjncy = graph->adjncy;
where = graph->where;
bndptr = graph->bndptr;
bndind = graph->bndind;
for (nbnd=0, i=0; i<nvtxs; i++) {
if (xadj[i+1]-xadj[i] == 0)
nbnd++; /* Islands are considered to be boundary vertices */
for (j=xadj[i]; j<xadj[i+1]; j++) {
if (where[i] != where[adjncy[j]]) {
nbnd++;
ASSERT(bndptr[i] != -1);
ASSERT(bndind[bndptr[i]] == i);
break;
}
}
}
ASSERTP(nbnd == graph->nbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, graph->nbnd));
return 1;
}
/*************************************************************************/
/*! This function checks whether or not the boundary information is correct
*/
/*************************************************************************/
idx_t CheckBnd2(graph_t *graph)
{
idx_t i, j, nvtxs, nbnd, id, ed;
idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
adjncy = graph->adjncy;
where = graph->where;
bndptr = graph->bndptr;
bndind = graph->bndind;
for (nbnd=0, i=0; i<nvtxs; i++) {
id = ed = 0;
for (j=xadj[i]; j<xadj[i+1]; j++) {
if (where[i] != where[adjncy[j]])
ed += graph->adjwgt[j];
else
id += graph->adjwgt[j];
}
if (ed - id >= 0 && xadj[i] < xadj[i+1]) {
nbnd++;
ASSERTP(bndptr[i] != -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", i, id, ed));
ASSERT(bndind[bndptr[i]] == i);
}
}
ASSERTP(nbnd == graph->nbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, graph->nbnd));
return 1;
}
/*************************************************************************/
/*! This function checks whether or not the boundary information is correct
*/
/*************************************************************************/
idx_t CheckNodeBnd(graph_t *graph, idx_t onbnd)
{
idx_t i, j, nvtxs, nbnd;
idx_t *xadj, *adjncy, *where, *bndptr, *bndind;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
adjncy = graph->adjncy;
where = graph->where;
bndptr = graph->bndptr;
bndind = graph->bndind;
for (nbnd=0, i=0; i<nvtxs; i++) {
if (where[i] == 2)
nbnd++;
}
ASSERTP(nbnd == onbnd, ("%"PRIDX" %"PRIDX"\n", nbnd, onbnd));
for (i=0; i<nvtxs; i++) {
if (where[i] != 2) {
ASSERTP(bndptr[i] == -1, ("%"PRIDX" %"PRIDX"\n", i, bndptr[i]));
}
else {
ASSERTP(bndptr[i] != -1, ("%"PRIDX" %"PRIDX"\n", i, bndptr[i]));
}
}
return 1;
}
/*************************************************************************/
/*! This function checks whether or not the rinfo of a vertex is consistent
*/
/*************************************************************************/
idx_t CheckRInfo(ctrl_t *ctrl, ckrinfo_t *rinfo)
{
idx_t i, j;
cnbr_t *nbrs;
ASSERT(ctrl->nbrpoolcpos >= 0);
ASSERT(rinfo->nnbrs < ctrl->nparts);
nbrs = ctrl->cnbrpool + rinfo->inbr;
for (i=0; i<rinfo->nnbrs; i++) {
for (j=i+1; j<rinfo->nnbrs; j++)
ASSERTP(nbrs[i].pid != nbrs[j].pid,
("%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n",
i, j, nbrs[i].pid, nbrs[j].pid));
}
return 1;
}
/*************************************************************************/
/*! This function checks the correctness of the NodeFM data structures
*/
/*************************************************************************/
idx_t CheckNodePartitionParams(graph_t *graph)
{
idx_t i, j, k, l, nvtxs, me, other;
idx_t *xadj, *adjncy, *adjwgt, *vwgt, *where;
idx_t edegrees[2], pwgts[3];
nvtxs = graph->nvtxs;
xadj = graph->xadj;
vwgt = graph->vwgt;
adjncy = graph->adjncy;
adjwgt = graph->adjwgt;
where = graph->where;
/*------------------------------------------------------------
/ Compute now the separator external degrees
/------------------------------------------------------------*/
pwgts[0] = pwgts[1] = pwgts[2] = 0;
for (i=0; i<nvtxs; i++) {
me = where[i];
pwgts[me] += vwgt[i];
if (me == 2) { /* If it is on the separator do some computations */
edegrees[0] = edegrees[1] = 0;
for (j=xadj[i]; j<xadj[i+1]; j++) {
other = where[adjncy[j]];
if (other != 2)
edegrees[other] += vwgt[adjncy[j]];
}
if (edegrees[0] != graph->nrinfo[i].edegrees[0] ||
edegrees[1] != graph->nrinfo[i].edegrees[1]) {
printf("Something wrong with edegrees: %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n",
i, edegrees[0], edegrees[1],
graph->nrinfo[i].edegrees[0], graph->nrinfo[i].edegrees[1]);
return 0;
}
}
}
if (pwgts[0] != graph->pwgts[0] ||
pwgts[1] != graph->pwgts[1] ||
pwgts[2] != graph->pwgts[2]) {
printf("Something wrong with part-weights: %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n", pwgts[0], pwgts[1], pwgts[2], graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]);
return 0;
}
return 1;
}
/*************************************************************************/
/*! This function checks if the separator is indeed a separator
*/
/*************************************************************************/
idx_t IsSeparable(graph_t *graph)
{
idx_t i, j, nvtxs, other;
idx_t *xadj, *adjncy, *where;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
adjncy = graph->adjncy;
where = graph->where;
for (i=0; i<nvtxs; i++) {
if (where[i] == 2)
continue;
other = (where[i]+1)%2;
for (j=xadj[i]; j<xadj[i+1]; j++) {
ASSERTP(where[adjncy[j]] != other,
("%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n",
i, where[i], adjncy[j], where[adjncy[j]], xadj[i+1]-xadj[i],
xadj[adjncy[j]+1]-xadj[adjncy[j]]));
}
}
return 1;
}
/*************************************************************************/
/*! This function recomputes the vrinfo fields and checks them against
those in the graph->vrinfo structure */
/*************************************************************************/
void CheckKWayVolPartitionParams(ctrl_t *ctrl, graph_t *graph)
{
idx_t i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
idx_t *xadj, *vsize, *adjncy, *pwgts, *where, *bndind, *bndptr;
vkrinfo_t *rinfo, *myrinfo, *orinfo, tmprinfo;
vnbr_t *mynbrs, *onbrs, *tmpnbrs;
WCOREPUSH;
nvtxs = graph->nvtxs;
xadj = graph->xadj;
vsize = graph->vsize;
adjncy = graph->adjncy;
where = graph->where;
rinfo = graph->vkrinfo;
tmpnbrs = (vnbr_t *)wspacemalloc(ctrl, ctrl->nparts*sizeof(vnbr_t));
/*------------------------------------------------------------
/ Compute now the iv/ev degrees
/------------------------------------------------------------*/
for (i=0; i<nvtxs; i++) {
me = where[i];
myrinfo = rinfo+i;
mynbrs = ctrl->vnbrpool + myrinfo->inbr;
for (k=0; k<myrinfo->nnbrs; k++)
tmpnbrs[k] = mynbrs[k];
tmprinfo.nnbrs = myrinfo->nnbrs;
tmprinfo.nid = myrinfo->nid;
tmprinfo.ned = myrinfo->ned;
myrinfo = &tmprinfo;
mynbrs = tmpnbrs;
for (k=0; k<myrinfo->nnbrs; k++)
mynbrs[k].gv = 0;
for (j=xadj[i]; j<xadj[i+1]; j++) {
ii = adjncy[j];
other = where[ii];
orinfo = rinfo+ii;
onbrs = ctrl->vnbrpool + orinfo->inbr;
if (me == other) {
/* Find which domains 'i' is connected and 'ii' is not and update their gain */
for (k=0; k<myrinfo->nnbrs; k++) {
pid = mynbrs[k].pid;
for (kk=0; kk<orinfo->nnbrs; kk++) {
if (onbrs[kk].pid == pid)
break;
}
if (kk == orinfo->nnbrs)
mynbrs[k].gv -= vsize[ii];
}
}
else {
/* Find the orinfo[me].ed and see if I'm the only connection */
for (k=0; k<orinfo->nnbrs; k++) {
if (onbrs[k].pid == me)
break;
}
if (onbrs[k].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
for (k=0; k<myrinfo->nnbrs; k++) {
if (mynbrs[k].pid == other) {
mynbrs[k].gv += vsize[ii];
break;
}
}
/* Increase the gains for all the common domains between 'i' and 'ii' */
for (k=0; k<myrinfo->nnbrs; k++) {
if ((pid = mynbrs[k].pid) == other)
continue;
for (kk=0; kk<orinfo->nnbrs; kk++) {
if (onbrs[kk].pid == pid) {
mynbrs[k].gv += vsize[ii];
break;
}
}
}
}
else {
/* Find which domains 'i' is connected and 'ii' is not and update their gain */
for (k=0; k<myrinfo->nnbrs; k++) {
if ((pid = mynbrs[k].pid) == other)
continue;
for (kk=0; kk<orinfo->nnbrs; kk++) {
if (onbrs[kk].pid == pid)
break;
}
if (kk == orinfo->nnbrs)
mynbrs[k].gv -= vsize[ii];
}
}
}
}
myrinfo = rinfo+i;
mynbrs = ctrl->vnbrpool + myrinfo->inbr;
for (k=0; k<myrinfo->nnbrs; k++) {
pid = mynbrs[k].pid;
for (kk=0; kk<tmprinfo.nnbrs; kk++) {
if (tmpnbrs[kk].pid == pid) {
if (tmpnbrs[kk].gv != mynbrs[k].gv)
printf("[%8"PRIDX" %8"PRIDX" %8"PRIDX" %+8"PRIDX" %+8"PRIDX"]\n",
i, where[i], pid, mynbrs[k].gv, tmpnbrs[kk].gv);
break;
}
}
}
}
WCOREPOP;
}