compress.c

Go to the documentation of this file.

/*
 * Copyright 1997, Regents of the University of Minnesota
 *
 * compress.c
 *
 * This file contains code for compressing nodes with identical adjacency
 * structure and for prunning dense columns
 *
 * Started 9/17/97
 * George
 */
 
#include "metislib.h"
 
/*************************************************************************/
/**************************************************************************/
graph_t *CompressGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, 
             idx_t *vwgt, idx_t *cptr, idx_t *cind)
{
  idx_t i, ii, iii, j, jj, k, l, cnvtxs, cnedges;
  idx_t *cxadj, *cadjncy, *cvwgt, *mark, *map;
  ikv_t *keys;
  graph_t *graph=NULL;
 
  mark = ismalloc(nvtxs, -1, "CompressGraph: mark");
  map  = ismalloc(nvtxs, -1, "CompressGraph: map");
  keys = ikvmalloc(nvtxs, "CompressGraph: keys");
 
  /* Compute a key for each adjacency list */
  for (i=0; i<nvtxs; i++) {
    k = 0;
    for (j=xadj[i]; j<xadj[i+1]; j++)
      k += adjncy[j];
    keys[i].key = k+i; /* Add the diagonal entry as well */
    keys[i].val = i;
  }
 
  ikvsorti(nvtxs, keys);
 
  l = cptr[0] = 0;
  for (cnvtxs=i=0; i<nvtxs; i++) {
    ii = keys[i].val;
    if (map[ii] == -1) {
      mark[ii] = i;  /* Add the diagonal entry */
      for (j=xadj[ii]; j<xadj[ii+1]; j++) 
        mark[adjncy[j]] = i;
 
      map[ii]   = cnvtxs;
      cind[l++] = ii;
 
      for (j=i+1; j<nvtxs; j++) {
        iii = keys[j].val;
 
        if (keys[i].key != keys[j].key || xadj[ii+1]-xadj[ii] != xadj[iii+1]-xadj[iii])
          break; /* Break if keys or degrees are different */
 
        if (map[iii] == -1) { /* Do a comparison if iii has not been mapped */ 
          for (jj=xadj[iii]; jj<xadj[iii+1]; jj++) {
            if (mark[adjncy[jj]] != i)
              break;
          }
 
          if (jj == xadj[iii+1]) { /* Identical adjacency structure */
            map[iii]  = cnvtxs;
            cind[l++] = iii;
          }
        }
      }
 
      cptr[++cnvtxs] = l;
    }
  }
 
  IFSET(ctrl->dbglvl, METIS_DBG_INFO, 
        printf("  Compression: reduction in # of vertices: %"PRIDX".\n", nvtxs-cnvtxs)); 
 
 
  if (cnvtxs < COMPRESSION_FRACTION*nvtxs) {
    /* Sufficient compression is possible, so go ahead and create the 
       compressed graph */
 
    graph = CreateGraph();
 
    cnedges = 0;
    for (i=0; i<cnvtxs; i++) {
      ii = cind[cptr[i]];
      cnedges += xadj[ii+1]-xadj[ii];
    }
 
    /* Allocate memory for the compressed graph */
    cxadj   = graph->xadj   = imalloc(cnvtxs+1, "CompressGraph: xadj");
    cvwgt   = graph->vwgt   = ismalloc(cnvtxs, 0, "CompressGraph: vwgt");
    cadjncy = graph->adjncy = imalloc(cnedges, "CompressGraph: adjncy");
              graph->adjwgt = ismalloc(cnedges, 1, "CompressGraph: adjwgt");
 
    /* Now go and compress the graph */
    iset(nvtxs, -1, mark);
    l = cxadj[0] = 0;
    for (i=0; i<cnvtxs; i++) {
      mark[i] = i;  /* Remove any dioganal entries in the compressed graph */
      for (j=cptr[i]; j<cptr[i+1]; j++) {
        ii = cind[j];
 
        /* accumulate the vertex weights of the consistuent vertices */
        cvwgt[i] += (vwgt == NULL ? 1 : vwgt[ii]);
 
        /* generate the combined adjancency list */
        for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
          k = map[adjncy[jj]];
          if (mark[k] != i) {
            mark[k] = i;
            cadjncy[l++] = k;
          }
        }
      }
      cxadj[i+1] = l;
    }
 
    graph->nvtxs  = cnvtxs;
    graph->nedges = l;
    graph->ncon   = 1;
 
    SetupGraph_tvwgt(graph);
    SetupGraph_label(graph);
  }
 
  gk_free((void **)&keys, &map, &mark, LTERM);
 
  return graph;
 
}
 
 
 
/*************************************************************************/
/*************************************************************************/
graph_t *PruneGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, 
             idx_t *vwgt, idx_t *iperm, real_t factor)
{
  idx_t i, j, k, l, nlarge, pnvtxs, pnedges;
  idx_t *pxadj, *padjncy, *padjwgt, *pvwgt;
  idx_t *perm;
  graph_t *graph=NULL;
 
  perm = imalloc(nvtxs, "PruneGraph: perm");
 
  factor = factor*xadj[nvtxs]/nvtxs;
 
  pnvtxs = pnedges = nlarge = 0;
  for (i=0; i<nvtxs; i++) {
    if (xadj[i+1]-xadj[i] < factor) {
      perm[i] = pnvtxs;
      iperm[pnvtxs++] = i;
      pnedges += xadj[i+1]-xadj[i];
    }
    else {
      perm[i] = nvtxs - ++nlarge;
      iperm[nvtxs-nlarge] = i;
    }
  }
 
  IFSET(ctrl->dbglvl, METIS_DBG_INFO, 
        printf("  Pruned %"PRIDX" of %"PRIDX" vertices.\n", nlarge, nvtxs)); 
 
 
  if (nlarge > 0 && nlarge < nvtxs) {  
    /* Prunning is possible, so go ahead and create the prunned graph */
    graph = CreateGraph();
 
    /* Allocate memory for the prunned graph*/
    pxadj   = graph->xadj   = imalloc(pnvtxs+1, "PruneGraph: xadj");
    pvwgt   = graph->vwgt   = imalloc(pnvtxs, "PruneGraph: vwgt");
    padjncy = graph->adjncy = imalloc(pnedges, "PruneGraph: adjncy");
              graph->adjwgt = ismalloc(pnedges, 1, "PruneGraph: adjwgt");
 
    pxadj[0] = pnedges = l = 0;
    for (i=0; i<nvtxs; i++) {
      if (xadj[i+1]-xadj[i] < factor) {
        pvwgt[l] = (vwgt == NULL ? 1 : vwgt[i]);
        
        for (j=xadj[i]; j<xadj[i+1]; j++) {
          k = perm[adjncy[j]];
          if (k < pnvtxs) 
            padjncy[pnedges++] = k;
        }
        pxadj[++l] = pnedges;
      }
    }
 
    graph->nvtxs  = pnvtxs;
    graph->nedges = pnedges;
    graph->ncon   = 1;
 
    SetupGraph_tvwgt(graph);
    SetupGraph_label(graph);
  }
  else if (nlarge > 0 && nlarge == nvtxs) {  
    IFSET(ctrl->dbglvl, METIS_DBG_INFO, 
          printf("  Pruning is ignored as it removes all vertices.\n"));
    nlarge = 0;
  }
 
 
  gk_free((void **)&perm, LTERM);
 
  return graph;
}