Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * compress.c
00005  *
00006  * This file contains code for compressing nodes with identical adjacency
00007  * structure and for prunning dense columns
00008  *
00009  * Started 9/17/97
00010  * George
00011  *
00012  * $Id$
00013  */
00014 
00015 #include <metis.h>
00016 
00017 /*************************************************************************
00018 * This function compresses a graph by merging identical vertices
00019 * The compression should lead to at least 10% reduction.
00020 **************************************************************************/
00021 void CompressGraph(CtrlType *ctrl, GraphType *graph, int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *cptr, idxtype *cind)
00022 {
00023   int i, ii, iii, j, jj, k, l, cnvtxs, cnedges;
00024   idxtype *cxadj, *cadjncy, *cvwgt, *mark, *map;
00025   KeyValueType *keys;
00026 
00027   mark = idxsmalloc(nvtxs, -1, "CompressGraph: mark");
00028   map = idxsmalloc(nvtxs, -1, "CompressGraph: map");
00029   keys = (KeyValueType *)GKmalloc(nvtxs*sizeof(KeyValueType), "CompressGraph: keys");
00030 
00031   /* Compute a key for each adjacency list */
00032   for (i=0; i<nvtxs; i++) {
00033     k = 0;
00034     for (j=xadj[i]; j<xadj[i+1]; j++)
00035       k += adjncy[j];
00036     keys[i].key = k+i; /* Add the diagonal entry as well */
00037     keys[i].val = i;
00038   }
00039 
00040   ikeysort(nvtxs, keys);
00041 
00042   l = cptr[0] = 0;
00043   for (cnvtxs=i=0; i<nvtxs; i++) {
00044     ii = keys[i].val;
00045     if (map[ii] == -1) { 
00046       mark[ii] = i;  /* Add the diagonal entry */
00047       for (j=xadj[ii]; j<xadj[ii+1]; j++) 
00048         mark[adjncy[j]] = i;
00049 
00050       cind[l++] = ii;
00051       map[ii] = cnvtxs;
00052 
00053       for (j=i+1; j<nvtxs; j++) {
00054         iii = keys[j].val;
00055 
00056         if (keys[i].key != keys[j].key || xadj[ii+1]-xadj[ii] != xadj[iii+1]-xadj[iii])
00057           break; /* Break if keys or degrees are different */
00058 
00059         if (map[iii] == -1) { /* Do a comparison if iii has not been mapped */ 
00060           for (jj=xadj[iii]; jj<xadj[iii+1]; jj++) {
00061             if (mark[adjncy[jj]] != i)
00062               break;
00063           }
00064 
00065           if (jj == xadj[iii+1]) { /* Identical adjacency structure */
00066             map[iii] = cnvtxs;
00067             cind[l++] = iii;
00068           }
00069         }
00070       }
00071 
00072       cptr[++cnvtxs] = l;
00073     }
00074   }
00075 
00076   /* printf("Original: %6d, Compressed: %6d\n", nvtxs, cnvtxs); */
00077 
00078 
00079   InitGraph(graph);
00080 
00081   if (cnvtxs >= COMPRESSION_FRACTION*nvtxs) {
00082     graph->nvtxs = nvtxs;
00083     graph->nedges = xadj[nvtxs];
00084     graph->ncon = 1;
00085     graph->xadj = xadj;
00086     graph->adjncy = adjncy;
00087 
00088     graph->gdata = idxmalloc(3*nvtxs+graph->nedges, "CompressGraph: gdata");
00089     graph->vwgt         = graph->gdata;
00090     graph->adjwgtsum    = graph->gdata+nvtxs;
00091     graph->cmap         = graph->gdata+2*nvtxs;
00092     graph->adjwgt       = graph->gdata+3*nvtxs;
00093 
00094     idxset(nvtxs, 1, graph->vwgt);
00095     idxset(graph->nedges, 1, graph->adjwgt);
00096     for (i=0; i<nvtxs; i++)
00097       graph->adjwgtsum[i] = xadj[i+1]-xadj[i];
00098 
00099     graph->label = idxmalloc(nvtxs, "CompressGraph: label");
00100     for (i=0; i<nvtxs; i++)
00101       graph->label[i] = i;
00102   }
00103   else { /* Ok, form the compressed graph  */
00104     cnedges = 0;
00105     for (i=0; i<cnvtxs; i++) {
00106       ii = cind[cptr[i]];
00107       cnedges += xadj[ii+1]-xadj[ii];
00108     }
00109 
00110     /* Allocate memory for the compressed graph*/
00111     graph->gdata = idxmalloc(4*cnvtxs+1 + 2*cnedges, "CompressGraph: gdata");
00112     cxadj = graph->xadj         = graph->gdata;
00113     cvwgt = graph->vwgt         = graph->gdata + cnvtxs+1;
00114     graph->adjwgtsum            = graph->gdata + 2*cnvtxs+1;
00115     graph->cmap                 = graph->gdata + 3*cnvtxs+1;
00116     cadjncy = graph->adjncy     = graph->gdata + 4*cnvtxs+1;
00117     graph->adjwgt               = graph->gdata + 4*cnvtxs+1 + cnedges;
00118 
00119     /* Now go and compress the graph */
00120     idxset(nvtxs, -1, mark);
00121     l = cxadj[0] = 0;
00122     for (i=0; i<cnvtxs; i++) {
00123       cvwgt[i] = cptr[i+1]-cptr[i];
00124       mark[i] = i;  /* Remove any dioganal entries in the compressed graph */
00125       for (j=cptr[i]; j<cptr[i+1]; j++) {
00126         ii = cind[j];
00127         for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
00128           k = map[adjncy[jj]];
00129           if (mark[k] != i) 
00130             cadjncy[l++] = k;
00131           mark[k] = i;
00132         }
00133       }
00134       cxadj[i+1] = l;
00135     }
00136 
00137     graph->nvtxs = cnvtxs;
00138     graph->nedges = l;
00139     graph->ncon = 1;
00140 
00141     idxset(graph->nedges, 1, graph->adjwgt);
00142     for (i=0; i<cnvtxs; i++)
00143       graph->adjwgtsum[i] = cxadj[i+1]-cxadj[i];
00144 
00145     graph->label = idxmalloc(cnvtxs, "CompressGraph: label");
00146     for (i=0; i<cnvtxs; i++)
00147       graph->label[i] = i;
00148 
00149   }
00150 
00151   GKfree(&keys, &map, &mark, LTERM);
00152 }
00153 
00154 
00155 
00156 /*************************************************************************
00157 * This function prunes all the vertices in a graph with degree greater 
00158 * than factor*average
00159 **************************************************************************/
00160 void PruneGraph(CtrlType *ctrl, GraphType *graph, int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *iperm, floattype factor)
00161 {
00162   int i, j, k, l, nlarge, pnvtxs, pnedges;
00163   idxtype *pxadj, *padjncy, *padjwgt, *pvwgt;
00164   idxtype *perm;
00165 
00166   perm = idxmalloc(nvtxs, "PruneGraph: perm");
00167 
00168   factor = factor*xadj[nvtxs]/nvtxs;
00169 
00170   pnvtxs = pnedges = nlarge = 0;
00171   for (i=0; i<nvtxs; i++) {
00172     if (xadj[i+1]-xadj[i] < factor) {
00173       perm[i] = pnvtxs;
00174       iperm[pnvtxs++] = i;
00175       pnedges += xadj[i+1]-xadj[i];
00176     }
00177     else {
00178       perm[i] = nvtxs - ++nlarge;
00179       iperm[nvtxs-nlarge] = i;
00180     }
00181   }
00182 
00183   /* printf("Pruned %d vertices\n", nlarge); */
00184 
00185   InitGraph(graph);
00186 
00187   if (nlarge == 0) { /* No prunning */
00188     graph->nvtxs = nvtxs;
00189     graph->nedges = xadj[nvtxs];
00190     graph->ncon = 1;
00191     graph->xadj = xadj;
00192     graph->adjncy = adjncy;
00193 
00194     graph->gdata = idxmalloc(3*nvtxs+graph->nedges, "CompressGraph: gdata");
00195     graph->vwgt         = graph->gdata;
00196     graph->adjwgtsum    = graph->gdata+nvtxs;
00197     graph->cmap         = graph->gdata+2*nvtxs;
00198     graph->adjwgt       = graph->gdata+3*nvtxs;
00199 
00200     idxset(nvtxs, 1, graph->vwgt);
00201     idxset(graph->nedges, 1, graph->adjwgt);
00202     for (i=0; i<nvtxs; i++)
00203       graph->adjwgtsum[i] = xadj[i+1]-xadj[i];
00204 
00205     graph->label = idxmalloc(nvtxs, "CompressGraph: label");
00206     for (i=0; i<nvtxs; i++)
00207       graph->label[i] = i;
00208   }
00209   else { /* Prune the graph */
00210     /* Allocate memory for the compressed graph*/
00211     graph->gdata = idxmalloc(4*pnvtxs+1 + 2*pnedges, "PruneGraph: gdata");
00212     pxadj = graph->xadj         = graph->gdata;
00213     graph->vwgt                 = graph->gdata + pnvtxs+1;
00214     graph->adjwgtsum            = graph->gdata + 2*pnvtxs+1;
00215     graph->cmap                 = graph->gdata + 3*pnvtxs+1;
00216     padjncy = graph->adjncy     = graph->gdata + 4*pnvtxs+1;
00217     graph->adjwgt               = graph->gdata + 4*pnvtxs+1 + pnedges;
00218 
00219     pxadj[0] = pnedges = l = 0;
00220     for (i=0; i<nvtxs; i++) {
00221       if (xadj[i+1]-xadj[i] < factor) {
00222         for (j=xadj[i]; j<xadj[i+1]; j++) {
00223           k = perm[adjncy[j]];
00224           if (k < pnvtxs) 
00225             padjncy[pnedges++] = k;
00226         }
00227         pxadj[++l] = pnedges;
00228       }
00229     }
00230 
00231     graph->nvtxs = pnvtxs;
00232     graph->nedges = pnedges;
00233     graph->ncon = 1;
00234 
00235     idxset(pnvtxs, 1, graph->vwgt);
00236     idxset(pnedges, 1, graph->adjwgt);
00237     for (i=0; i<pnvtxs; i++)
00238       graph->adjwgtsum[i] = pxadj[i+1]-pxadj[i];
00239 
00240     graph->label = idxmalloc(pnvtxs, "CompressGraph: label");
00241     for (i=0; i<pnvtxs; i++)
00242       graph->label[i] = i;
00243   }
00244 
00245   free(perm);
00246 
00247 }
00248 
00249 
00250 
00251 
00252 
00253 
00254 
00255 
00256
libs/ck-libs/parmetis/METISLib/compress.c
