# SCM Repository

[matrix] View of /pkg/src/Metis/compress.c
 [matrix] / pkg / src / Metis / compress.c

# View of /pkg/src/Metis/compress.c

Mon Mar 22 20:20:05 2004 UTC (15 years, 11 months ago) by bates
File size: 7259 byte(s)
`Initial import`
```/*
* 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 2003/12/31 21:32:30 bates 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, int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *cptr, idxtype *cind)
{
int i, ii, iii, j, jj, k, l, cnvtxs, cnedges;
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;
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 */

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

for (j=i+1; j<nvtxs; j++) {
iii = keys[j].val;

break; /* Break if keys or degrees are different */

if (map[iii] == -1) { /* Do a comparison if iii has not been mapped */
break;
}

map[iii] = cnvtxs;
cind[l++] = iii;
}
}
}

cptr[++cnvtxs] = l;
}
}

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

InitGraph(graph);

if (cnvtxs >= COMPRESSION_FRACTION*nvtxs) {
graph->nvtxs = nvtxs;
graph->ncon = 1;

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

idxset(nvtxs, 1, graph->vwgt);
for (i=0; i<nvtxs; 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]];
}

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

/* Now go and compress the graph */
idxset(nvtxs, -1, mark);
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];
if (mark[k] != i)
mark[k] = i;
}
}
}

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

for (i=0; i<cnvtxs; 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, int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *iperm, float factor)
{
int i, j, k, l, nlarge, pnvtxs, pnedges;
idxtype *perm;

perm = idxmalloc(nvtxs, "PruneGraph: perm");

pnvtxs = pnedges = nlarge = 0;
for (i=0; i<nvtxs; i++) {
perm[i] = pnvtxs;
iperm[pnvtxs++] = i;
}
else {
perm[i] = nvtxs - ++nlarge;
iperm[nvtxs-nlarge] = i;
}
}

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

InitGraph(graph);

if (nlarge == 0) { /* No prunning */
graph->nvtxs = nvtxs;
graph->ncon = 1;

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

idxset(nvtxs, 1, graph->vwgt);
for (i=0; i<nvtxs; 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");
graph->vwgt         	= graph->gdata + pnvtxs+1;
graph->cmap                 = graph->gdata + 3*pnvtxs+1;
graph->adjwgt            	= graph->gdata + 4*pnvtxs+1 + pnedges;

pxadj[0] = pnedges = l = 0;
for (i=0; i<nvtxs; i++) {
if (k < pnvtxs)
}
}
}

graph->nvtxs = pnvtxs;
graph->nedges = pnedges;
graph->ncon = 1;

idxset(pnvtxs, 1, graph->vwgt);
for (i=0; i<pnvtxs; i++)

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

free(perm);

}

```