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
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;
|
|
}
|
|
|
|
|
|
|