Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
compress.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * compress.c
5  *
6  * This file contains code for compressing nodes with identical adjacency
7  * structure and for prunning dense columns
8  *
9  * Started 9/17/97
10  * George
11  *
12  * $Id: compress.c,v 1.1 1998/11/27 17:59:12 karypis Exp $
13  */
14 
15 #include <metis.h>
16 
17 /*************************************************************************
18 * This function compresses a graph by merging identical vertices
19 * The compression should lead to at least 10% reduction.
20 **************************************************************************/
21 void CompressGraph(CtrlType *ctrl, GraphType *graph, int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *cptr, idxtype *cind)
22 {
23  int i, ii, iii, j, jj, k, l, cnvtxs, cnedges;
24  idxtype *cxadj, *cadjncy, *cvwgt, *mark, *map;
25  KeyValueType *keys;
26 
27  mark = idxsmalloc(nvtxs, -1, "CompressGraph: mark");
28  map = idxsmalloc(nvtxs, -1, "CompressGraph: map");
29  keys = (KeyValueType *)GKmalloc(nvtxs*sizeof(KeyValueType), "CompressGraph: keys");
30 
31  /* Compute a key for each adjacency list */
32  for (i=0; i<nvtxs; i++) {
33  k = 0;
34  for (j=xadj[i]; j<xadj[i+1]; j++)
35  k += adjncy[j];
36  keys[i].key = k+i; /* Add the diagonal entry as well */
37  keys[i].val = i;
38  }
39 
40  ikeysort(nvtxs, keys);
41 
42  l = cptr[0] = 0;
43  for (cnvtxs=i=0; i<nvtxs; i++) {
44  ii = keys[i].val;
45  if (map[ii] == -1) {
46  mark[ii] = i; /* Add the diagonal entry */
47  for (j=xadj[ii]; j<xadj[ii+1]; j++)
48  mark[adjncy[j]] = i;
49 
50  cind[l++] = ii;
51  map[ii] = cnvtxs;
52 
53  for (j=i+1; j<nvtxs; j++) {
54  iii = keys[j].val;
55 
56  if (keys[i].key != keys[j].key || xadj[ii+1]-xadj[ii] != xadj[iii+1]-xadj[iii])
57  break; /* Break if keys or degrees are different */
58 
59  if (map[iii] == -1) { /* Do a comparison if iii has not been mapped */
60  for (jj=xadj[iii]; jj<xadj[iii+1]; jj++) {
61  if (mark[adjncy[jj]] != i)
62  break;
63  }
64 
65  if (jj == xadj[iii+1]) { /* Identical adjacency structure */
66  map[iii] = cnvtxs;
67  cind[l++] = iii;
68  }
69  }
70  }
71 
72  cptr[++cnvtxs] = l;
73  }
74  }
75 
76  /* printf("Original: %6d, Compressed: %6d\n", nvtxs, cnvtxs); */
77 
78 
79  InitGraph(graph);
80 
81  if (cnvtxs >= COMPRESSION_FRACTION*nvtxs) {
82  graph->nvtxs = nvtxs;
83  graph->nedges = xadj[nvtxs];
84  graph->ncon = 1;
85  graph->xadj = xadj;
86  graph->adjncy = adjncy;
87 
88  graph->gdata = idxmalloc(3*nvtxs+graph->nedges, "CompressGraph: gdata");
89  graph->vwgt = graph->gdata;
90  graph->adjwgtsum = graph->gdata+nvtxs;
91  graph->cmap = graph->gdata+2*nvtxs;
92  graph->adjwgt = graph->gdata+3*nvtxs;
93 
94  idxset(nvtxs, 1, graph->vwgt);
95  idxset(graph->nedges, 1, graph->adjwgt);
96  for (i=0; i<nvtxs; i++)
97  graph->adjwgtsum[i] = xadj[i+1]-xadj[i];
98 
99  graph->label = idxmalloc(nvtxs, "CompressGraph: label");
100  for (i=0; i<nvtxs; i++)
101  graph->label[i] = i;
102  }
103  else { /* Ok, form the compressed graph */
104  cnedges = 0;
105  for (i=0; i<cnvtxs; i++) {
106  ii = cind[cptr[i]];
107  cnedges += xadj[ii+1]-xadj[ii];
108  }
109 
110  /* Allocate memory for the compressed graph*/
111  graph->gdata = idxmalloc(4*cnvtxs+1 + 2*cnedges, "CompressGraph: gdata");
112  cxadj = graph->xadj = graph->gdata;
113  cvwgt = graph->vwgt = graph->gdata + cnvtxs+1;
114  graph->adjwgtsum = graph->gdata + 2*cnvtxs+1;
115  graph->cmap = graph->gdata + 3*cnvtxs+1;
116  cadjncy = graph->adjncy = graph->gdata + 4*cnvtxs+1;
117  graph->adjwgt = graph->gdata + 4*cnvtxs+1 + cnedges;
118 
119  /* Now go and compress the graph */
120  idxset(nvtxs, -1, mark);
121  l = cxadj[0] = 0;
122  for (i=0; i<cnvtxs; i++) {
123  cvwgt[i] = cptr[i+1]-cptr[i];
124  mark[i] = i; /* Remove any dioganal entries in the compressed graph */
125  for (j=cptr[i]; j<cptr[i+1]; j++) {
126  ii = cind[j];
127  for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
128  k = map[adjncy[jj]];
129  if (mark[k] != i)
130  cadjncy[l++] = k;
131  mark[k] = i;
132  }
133  }
134  cxadj[i+1] = l;
135  }
136 
137  graph->nvtxs = cnvtxs;
138  graph->nedges = l;
139  graph->ncon = 1;
140 
141  idxset(graph->nedges, 1, graph->adjwgt);
142  for (i=0; i<cnvtxs; i++)
143  graph->adjwgtsum[i] = cxadj[i+1]-cxadj[i];
144 
145  graph->label = idxmalloc(cnvtxs, "CompressGraph: label");
146  for (i=0; i<cnvtxs; i++)
147  graph->label[i] = i;
148 
149  }
150 
151  GKfree(&keys, &map, &mark, LTERM);
152 }
153 
154 
155 
156 /*************************************************************************
157 * This function prunes all the vertices in a graph with degree greater
158 * than factor*average
159 **************************************************************************/
160 void PruneGraph(CtrlType *ctrl, GraphType *graph, int nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *iperm, float factor)
161 {
162  int i, j, k, l, nlarge, pnvtxs, pnedges;
163  idxtype *pxadj, *padjncy, *padjwgt, *pvwgt;
164  idxtype *perm;
165 
166  perm = idxmalloc(nvtxs, "PruneGraph: perm");
167 
168  factor = factor*xadj[nvtxs]/nvtxs;
169 
170  pnvtxs = pnedges = nlarge = 0;
171  for (i=0; i<nvtxs; i++) {
172  if (xadj[i+1]-xadj[i] < factor) {
173  perm[i] = pnvtxs;
174  iperm[pnvtxs++] = i;
175  pnedges += xadj[i+1]-xadj[i];
176  }
177  else {
178  perm[i] = nvtxs - ++nlarge;
179  iperm[nvtxs-nlarge] = i;
180  }
181  }
182 
183  /* printf("Pruned %d vertices\n", nlarge); */
184 
185  InitGraph(graph);
186 
187  if (nlarge == 0) { /* No prunning */
188  graph->nvtxs = nvtxs;
189  graph->nedges = xadj[nvtxs];
190  graph->ncon = 1;
191  graph->xadj = xadj;
192  graph->adjncy = adjncy;
193 
194  graph->gdata = idxmalloc(3*nvtxs+graph->nedges, "CompressGraph: gdata");
195  graph->vwgt = graph->gdata;
196  graph->adjwgtsum = graph->gdata+nvtxs;
197  graph->cmap = graph->gdata+2*nvtxs;
198  graph->adjwgt = graph->gdata+3*nvtxs;
199 
200  idxset(nvtxs, 1, graph->vwgt);
201  idxset(graph->nedges, 1, graph->adjwgt);
202  for (i=0; i<nvtxs; i++)
203  graph->adjwgtsum[i] = xadj[i+1]-xadj[i];
204 
205  graph->label = idxmalloc(nvtxs, "CompressGraph: label");
206  for (i=0; i<nvtxs; i++)
207  graph->label[i] = i;
208  }
209  else { /* Prune the graph */
210  /* Allocate memory for the compressed graph*/
211  graph->gdata = idxmalloc(4*pnvtxs+1 + 2*pnedges, "PruneGraph: gdata");
212  pxadj = graph->xadj = graph->gdata;
213  graph->vwgt = graph->gdata + pnvtxs+1;
214  graph->adjwgtsum = graph->gdata + 2*pnvtxs+1;
215  graph->cmap = graph->gdata + 3*pnvtxs+1;
216  padjncy = graph->adjncy = graph->gdata + 4*pnvtxs+1;
217  graph->adjwgt = graph->gdata + 4*pnvtxs+1 + pnedges;
218 
219  pxadj[0] = pnedges = l = 0;
220  for (i=0; i<nvtxs; i++) {
221  if (xadj[i+1]-xadj[i] < factor) {
222  for (j=xadj[i]; j<xadj[i+1]; j++) {
223  k = perm[adjncy[j]];
224  if (k < pnvtxs)
225  padjncy[pnedges++] = k;
226  }
227  pxadj[++l] = pnedges;
228  }
229  }
230 
231  graph->nvtxs = pnvtxs;
232  graph->nedges = pnedges;
233  graph->ncon = 1;
234 
235  idxset(pnvtxs, 1, graph->vwgt);
236  idxset(pnedges, 1, graph->adjwgt);
237  for (i=0; i<pnvtxs; i++)
238  graph->adjwgtsum[i] = pxadj[i+1]-pxadj[i];
239 
240  graph->label = idxmalloc(pnvtxs, "CompressGraph: label");
241  for (i=0; i<pnvtxs; i++)
242  graph->label[i] = i;
243  }
244 
245  free(perm);
246 
247 }
248 
249 
250 
251 
252 
253 
254 
255 
256 
#define COMPRESSION_FRACTION
Definition: defs.h:145
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
#define ikeysort
Definition: rename.h:289
idxtype key
Definition: struct.h:31
HitTile_Vector graph
#define LTERM
Definition: defs.h:18
#define PruneGraph
Definition: rename.h:39
int idxtype
Definition: struct.h:19
#define idxsmalloc
Definition: rename.h:386
idxtype * label
Definition: struct.h:170
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
void GKfree(void **ptr1,...)
Definition: util.c:121
int ncon
Definition: struct.h:194
#define GKmalloc
Definition: rename.h:387
idxtype * vwgt
Definition: struct.h:163
int nedges
Definition: struct.h:161
#define idxmalloc
Definition: rename.h:383
idxtype * gdata
Definition: struct.h:157
int nvtxs
Definition: struct.h:161
idxtype val
Definition: struct.h:32
#define CompressGraph
Definition: rename.h:38
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define InitGraph
Definition: rename.h:168