/* 
  * 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 
  * 
  * $Id: compress.c,v 1.1 1998/11/27 17:59:12 karypis Exp $ 
  */ 

 #include <metis.h> 

 /************************************************************************* 
 * This function compresses a graph by merging identical vertices 
 * The compression should lead to at least 10% reduction. 
 **************************************************************************/ 
 void CompressGraph(CtrlType *ctrl, GraphType *graph, long nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *cptr, idxtype *cind) 
 { 
   long i, ii, iii, j, jj, k, l, cnvtxs, cnedges; 
   idxtype *cxadj, *cadjncy, *cvwgt, *mark, *map; 
   KeyValueType *keys; 

   mark = idxsmalloc(nvtxs, -1, "CompressGraph: mark"); 
   map = idxsmalloc(nvtxs, -1, "CompressGraph: map"); 
   keys = (KeyValueType *)GKmalloc(nvtxs*sizeof(KeyValueType), "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; 
   } 

   ikeysort(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; 

       cind[l++] = ii; 
       map[ii] = cnvtxs; 

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

   /* printf("Original: %6ld, Compressed: %6ld\n", nvtxs, cnvtxs); */ 


   InitGraph(graph); 

   if (cnvtxs >= COMPRESSION_FRACTION*nvtxs) { 
     graph->nvtxs = nvtxs; 
     graph->nedges = xadj[nvtxs]; 
     graph->ncon = 1; 
     graph->xadj = xadj; 
     graph->adjncy = adjncy; 

     graph->gdata = idxmalloc(3*nvtxs+graph->nedges, "CompressGraph: gdata"); 
     graph->vwgt         = graph->gdata; 
     graph->adjwgtsum    = graph->gdata+nvtxs; 
     graph->cmap         = graph->gdata+2*nvtxs; 
     graph->adjwgt       = graph->gdata+3*nvtxs; 

     idxset(nvtxs, 1, graph->vwgt); 
     idxset(graph->nedges, 1, graph->adjwgt); 
     for (i=0; i<nvtxs; i++) 
       graph->adjwgtsum[i] = xadj[i+1]-xadj[i]; 

     graph->label = idxmalloc(nvtxs, "CompressGraph: label"); 
     for (i=0; i<nvtxs; i++) 
       graph->label[i] = i; 
   } 
   else { /* Ok, form the compressed graph  */ 
     cnedges = 0; 
     for (i=0; i<cnvtxs; i++) { 
       ii = cind[cptr[i]]; 
       cnedges += xadj[ii+1]-xadj[ii]; 
     } 

     /* Allocate memory for the compressed graph*/ 
     graph->gdata = idxmalloc(4*cnvtxs+1 + 2*cnedges, "CompressGraph: gdata"); 
     cxadj = graph->xadj         = graph->gdata; 
     cvwgt = graph->vwgt         = graph->gdata + cnvtxs+1; 
     graph->adjwgtsum            = graph->gdata + 2*cnvtxs+1; 
     graph->cmap                 = graph->gdata + 3*cnvtxs+1; 
     cadjncy = graph->adjncy     = graph->gdata + 4*cnvtxs+1; 
     graph->adjwgt               = graph->gdata + 4*cnvtxs+1 + cnedges; 

     /* Now go and compress the graph */ 
     idxset(nvtxs, -1, mark); 
     l = cxadj[0] = 0; 
     for (i=0; i<cnvtxs; i++) { 
       cvwgt[i] = cptr[i+1]-cptr[i]; 
       mark[i] = i;  /* Remove any dioganal entries in the compressed graph */ 
       for (j=cptr[i]; j<cptr[i+1]; j++) { 
         ii = cind[j]; 
         for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) { 
           k = map[adjncy[jj]]; 
           if (mark[k] != i)  
             cadjncy[l++] = k; 
           mark[k] = i; 
         } 
       } 
       cxadj[i+1] = l; 
     } 

     graph->nvtxs = cnvtxs; 
     graph->nedges = l; 
     graph->ncon = 1; 

     idxset(graph->nedges, 1, graph->adjwgt); 
     for (i=0; i<cnvtxs; i++) 
       graph->adjwgtsum[i] = cxadj[i+1]-cxadj[i]; 

     graph->label = idxmalloc(cnvtxs, "CompressGraph: label"); 
     for (i=0; i<cnvtxs; i++) 
       graph->label[i] = i; 

   } 

   GKfree(&keys, &map, &mark, LTERM); 
 } 



 /************************************************************************* 
 * This function prunes all the vertices in a graph with degree greater  
 * than factor*average 
 **************************************************************************/ 
 void PruneGraph(CtrlType *ctrl, GraphType *graph, long nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *iperm, float factor) 
 { 
   long i, j, k, l, nlarge, pnvtxs, pnedges; 
   idxtype *pxadj, *padjncy, *padjwgt, *pvwgt; 
   idxtype *perm; 

   perm = idxmalloc(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; 
     } 
   } 

   /* printf("Pruned %ld vertices\n", nlarge); */ 

   InitGraph(graph); 

   if (nlarge == 0) { /* No prunning */ 
     graph->nvtxs = nvtxs; 
     graph->nedges = xadj[nvtxs]; 
     graph->ncon = 1; 
     graph->xadj = xadj; 
     graph->adjncy = adjncy; 

     graph->gdata = idxmalloc(3*nvtxs+graph->nedges, "CompressGraph: gdata"); 
     graph->vwgt         = graph->gdata; 
     graph->adjwgtsum    = graph->gdata+nvtxs; 
     graph->cmap         = graph->gdata+2*nvtxs; 
     graph->adjwgt       = graph->gdata+3*nvtxs; 

     idxset(nvtxs, 1, graph->vwgt); 
     idxset(graph->nedges, 1, graph->adjwgt); 
     for (i=0; i<nvtxs; i++) 
       graph->adjwgtsum[i] = xadj[i+1]-xadj[i]; 

     graph->label = idxmalloc(nvtxs, "CompressGraph: label"); 
     for (i=0; i<nvtxs; i++) 
       graph->label[i] = i; 
   } 
   else { /* Prune the graph */ 
     /* Allocate memory for the compressed graph*/ 
     graph->gdata = idxmalloc(4*pnvtxs+1 + 2*pnedges, "PruneGraph: gdata"); 
     pxadj = graph->xadj         = graph->gdata; 
     graph->vwgt                 = graph->gdata + pnvtxs+1; 
     graph->adjwgtsum            = graph->gdata + 2*pnvtxs+1; 
     graph->cmap                 = graph->gdata + 3*pnvtxs+1; 
     padjncy = graph->adjncy     = graph->gdata + 4*pnvtxs+1; 
     graph->adjwgt               = graph->gdata + 4*pnvtxs+1 + pnedges; 

     pxadj[0] = pnedges = l = 0; 
     for (i=0; i<nvtxs; i++) { 
       if (xadj[i+1]-xadj[i] < factor) { 
         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; 

     idxset(pnvtxs, 1, graph->vwgt); 
     idxset(pnedges, 1, graph->adjwgt); 
     for (i=0; i<pnvtxs; i++) 
       graph->adjwgtsum[i] = pxadj[i+1]-pxadj[i]; 

     graph->label = idxmalloc(pnvtxs, "CompressGraph: label"); 
     for (i=0; i<pnvtxs; i++) 
       graph->label[i] = i; 
   } 

   free(perm); 

 }