23 int i, ii, iii, j, jj, k, l, cnvtxs, cnedges;
24 idxtype *cxadj, *cadjncy, *cvwgt, *mark, *map;
27 mark =
idxsmalloc(nvtxs, -1,
"CompressGraph: mark");
28 map =
idxsmalloc(nvtxs, -1,
"CompressGraph: map");
32 for (i=0; i<nvtxs; i++) {
34 for (j=xadj[i]; j<xadj[i+1]; j++)
43 for (cnvtxs=i=0; i<nvtxs; i++) {
47 for (j=xadj[ii]; j<xadj[ii+1]; j++)
53 for (j=i+1; j<nvtxs; j++) {
56 if (keys[i].key != keys[j].key || xadj[ii+1]-xadj[ii] != xadj[iii+1]-xadj[iii])
60 for (jj=xadj[iii]; jj<xadj[iii+1]; jj++) {
61 if (mark[adjncy[jj]] != i)
65 if (jj == xadj[iii+1]) {
83 graph->
nedges = xadj[nvtxs];
96 for (i=0; i<nvtxs; i++)
100 for (i=0; i<nvtxs; i++)
105 for (i=0; i<cnvtxs; i++) {
107 cnedges += xadj[ii+1]-xadj[ii];
111 graph->
gdata =
idxmalloc(4*cnvtxs+1 + 2*cnedges,
"CompressGraph: gdata");
113 cvwgt = graph->
vwgt = graph->
gdata + cnvtxs+1;
116 cadjncy = graph->
adjncy = graph->
gdata + 4*cnvtxs+1;
117 graph->
adjwgt = graph->
gdata + 4*cnvtxs+1 + cnedges;
122 for (i=0; i<cnvtxs; i++) {
123 cvwgt[i] = cptr[i+1]-cptr[i];
125 for (j=cptr[i]; j<cptr[i+1]; j++) {
127 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
137 graph->
nvtxs = cnvtxs;
142 for (i=0; i<cnvtxs; i++)
143 graph->
adjwgtsum[i] = cxadj[i+1]-cxadj[i];
146 for (i=0; i<cnvtxs; i++)
162 int i, j, k, l, nlarge, pnvtxs, pnedges;
163 idxtype *pxadj, *padjncy, *padjwgt, *pvwgt;
166 perm =
idxmalloc(nvtxs,
"PruneGraph: perm");
168 factor = factor*xadj[nvtxs]/nvtxs;
170 pnvtxs = pnedges = nlarge = 0;
171 for (i=0; i<nvtxs; i++) {
172 if (xadj[i+1]-xadj[i] < factor) {
175 pnedges += xadj[i+1]-xadj[i];
178 perm[i] = nvtxs - ++nlarge;
179 iperm[nvtxs-nlarge] = i;
188 graph->
nvtxs = nvtxs;
189 graph->
nedges = xadj[nvtxs];
202 for (i=0; i<nvtxs; i++)
206 for (i=0; i<nvtxs; i++)
211 graph->
gdata =
idxmalloc(4*pnvtxs+1 + 2*pnedges,
"PruneGraph: gdata");
216 padjncy = graph->
adjncy = graph->
gdata + 4*pnvtxs+1;
217 graph->
adjwgt = graph->
gdata + 4*pnvtxs+1 + pnedges;
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++) {
225 padjncy[pnedges++] = k;
227 pxadj[++l] = pnedges;
231 graph->
nvtxs = pnvtxs;
237 for (i=0; i<pnvtxs; i++)
238 graph->
adjwgtsum[i] = pxadj[i+1]-pxadj[i];
241 for (i=0; i<pnvtxs; i++)
#define COMPRESSION_FRACTION
void GKfree(void **ptr1,...)