text: /*
   * 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 "metis/metislib.h"
  
  /*************************************************************************/
  /*! This function compresses a graph by merging identical vertices
      The compression should lead to at least 10% reduction. 
  
      The compressed graph that is generated has its adjwgts set to 1.
  
      \returns 1 if compression was performed, otherwise it returns 0.
   
  */
  /**************************************************************************/
  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;
  
  }
  
  
  
  /*************************************************************************/
  /*! This function prunes all the vertices in a graph with degree greater 
      than factor*average. 
  
      \returns the number of vertices that were prunned.
  */
  /*************************************************************************/
  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;
  }
  
  
  
  
  
  
  
  
  
  