debug.c

/*
 * Copyright 1997, Regents of the University of Minnesota
 *
 * debug.c
 *
 * This file contains code that performs self debuging
 *
 * 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;
  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)];

  printf("%zu => %"PRIDX"\n", iargmax(nparts, cuts), 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;

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