24 int i, j, jj, k, kk, l,
m, istart, iend, nvtxs, nedges, ncon, cnedges,
v,
u, mask, dovsize;
25 idxtype *xadj, *vwgt, *vsize, *adjncy, *adjwgt, *adjwgtsum, *auxadj;
27 idxtype *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt, *cadjwgtsum;
28 float *nvwgt, *cnvwgt;
34 if (cnvtxs < 8*mask || graph->nedges/graph->
nvtxs > 15) {
56 cvsize = cgraph->
vsize;
57 cnvwgt = cgraph->
nvwgt;
65 memcpy(auxadj, adjncy, iend*
sizeof(
idxtype));
66 for (i=0; i<iend; i++)
67 auxadj[i] = cmap[auxadj[i]];
71 cxadj[0] = cnvtxs = cnedges = 0;
72 for (i=0; i<nvtxs; i++) {
74 if (cmap[v] != cnvtxs)
79 cvwgt[cnvtxs] = vwgt[
v];
81 scopy(ncon, nvwgt+v*ncon, cnvwgt+cnvtxs*ncon);
84 cvsize[cnvtxs] = vsize[
v];
86 cadjwgtsum[cnvtxs] = adjwgtsum[
v];
91 for (j=istart; j<iend; j++) {
94 if ((m = htable[kk]) == -1) {
96 cadjwgt[nedges] = adjwgt[j];
97 htable[kk] = nedges++;
99 else if (cadjncy[m] == k) {
100 cadjwgt[
m] += adjwgt[j];
103 for (jj=0; jj<nedges; jj++) {
104 if (cadjncy[jj] == k) {
105 cadjwgt[jj] += adjwgt[j];
111 cadjwgt[nedges++] = adjwgt[j];
118 cvwgt[cnvtxs] += vwgt[
u];
120 saxpy(ncon, 1.0, nvwgt+u*ncon, 1, cnvwgt+cnvtxs*ncon, 1);
123 cvsize[cnvtxs] += vsize[
u];
125 cadjwgtsum[cnvtxs] += adjwgtsum[
u];
129 for (j=istart; j<iend; j++) {
132 if ((m = htable[kk]) == -1) {
134 cadjwgt[nedges] = adjwgt[j];
135 htable[kk] = nedges++;
137 else if (cadjncy[m] == k) {
138 cadjwgt[
m] += adjwgt[j];
141 for (jj=0; jj<nedges; jj++) {
142 if (cadjncy[jj] == k) {
143 cadjwgt[jj] += adjwgt[j];
149 cadjwgt[nedges++] = adjwgt[j];
155 jj = htable[cnvtxs&mask];
156 if (jj >= 0 && cadjncy[jj] != cnvtxs) {
157 for (jj=0; jj<nedges; jj++) {
158 if (cadjncy[jj] == cnvtxs)
162 if (jj >= 0 && cadjncy[jj] == cnvtxs) {
163 cadjwgtsum[cnvtxs] -= cadjwgt[jj];
164 cadjncy[jj] = cadjncy[--nedges];
165 cadjwgt[jj] = cadjwgt[nedges];
169 ASSERTP(cadjwgtsum[cnvtxs] ==
idxsum(nedges, cadjwgt), (
"%d %d %d %d %d\n", cnvtxs, cadjwgtsum[cnvtxs],
idxsum(nedges, cadjwgt), adjwgtsum[u], adjwgtsum[v]));
171 for (j=0; j<nedges; j++)
172 htable[cadjncy[j]&mask] = -1;
173 htable[cnvtxs&mask] = -1;
176 cxadj[++cnvtxs] = cnedges;
197 int i, j, k,
m, istart, iend, nvtxs, nedges, ncon, cnedges,
v,
u, dovsize;
198 idxtype *xadj, *vwgt, *vsize, *adjncy, *adjwgt, *adjwgtsum, *auxadj;
200 idxtype *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt, *cadjwgtsum;
201 float *nvwgt, *cnvwgt;
208 nvtxs = graph->
nvtxs;
212 vsize = graph->
vsize;
213 nvwgt = graph->
nvwgt;
222 cxadj = cgraph->
xadj;
223 cvwgt = cgraph->
vwgt;
224 cvsize = cgraph->
vsize;
225 cnvwgt = cgraph->
nvwgt;
235 memcpy(auxadj, adjncy, iend*
sizeof(
idxtype));
236 for (i=0; i<iend; i++)
237 auxadj[i] = cmap[auxadj[i]];
239 cxadj[0] = cnvtxs = cnedges = 0;
240 for (i=0; i<nvtxs; i++) {
242 if (cmap[v] != cnvtxs)
247 cvwgt[cnvtxs] = vwgt[
v];
249 scopy(ncon, nvwgt+v*ncon, cnvwgt+cnvtxs*ncon);
252 cvsize[cnvtxs] = vsize[
v];
254 cadjwgtsum[cnvtxs] = adjwgtsum[
v];
259 for (j=istart; j<iend; j++) {
261 if ((m = htable[k]) == -1) {
263 cadjwgt[nedges] = adjwgt[j];
264 htable[k] = nedges++;
267 cadjwgt[
m] += adjwgt[j];
273 cvwgt[cnvtxs] += vwgt[
u];
275 saxpy(ncon, 1.0, nvwgt+u*ncon, 1, cnvwgt+cnvtxs*ncon, 1);
278 cvsize[cnvtxs] += vsize[
u];
280 cadjwgtsum[cnvtxs] += adjwgtsum[
u];
284 for (j=istart; j<iend; j++) {
286 if ((m = htable[k]) == -1) {
288 cadjwgt[nedges] = adjwgt[j];
289 htable[k] = nedges++;
292 cadjwgt[
m] += adjwgt[j];
297 if ((j = htable[cnvtxs]) != -1) {
298 ASSERT(cadjncy[j] == cnvtxs);
299 cadjwgtsum[cnvtxs] -= cadjwgt[j];
300 cadjncy[j] = cadjncy[--nedges];
301 cadjwgt[j] = cadjwgt[nedges];
306 ASSERTP(cadjwgtsum[cnvtxs] ==
idxsum(nedges, cadjwgt), (
"%d %d\n", cadjwgtsum[cnvtxs],
idxsum(nedges, cadjwgt)));
308 for (j=0; j<nedges; j++)
309 htable[cadjncy[j]] = -1;
312 cxadj[++cnvtxs] = cnedges;
332 int i, j, jj, k, kk, l,
m, istart, iend, nvtxs, nedges, ncon, cnedges,
v,
u, mask;
333 idxtype *xadj, *adjncy, *adjwgtsum, *auxadj;
335 idxtype *cxadj, *cvwgt, *cadjncy, *cadjwgt, *cadjwgtsum;
336 float *nvwgt, *cnvwgt;
342 nvtxs = graph->
nvtxs;
345 nvwgt = graph->
nvwgt;
352 cxadj = cgraph->
xadj;
353 cvwgt = cgraph->
vwgt;
354 cnvwgt = cgraph->
nvwgt;
362 memcpy(auxadj, adjncy, iend*
sizeof(
idxtype));
363 for (i=0; i<iend; i++)
364 auxadj[i] = cmap[auxadj[i]];
369 cxadj[0] = cnvtxs = cnedges = 0;
370 for (i=0; i<nvtxs; i++) {
372 if (cmap[v] != cnvtxs)
377 cadjwgtsum[cnvtxs] = adjwgtsum[
v];
382 for (j=istart; j<iend; j++) {
385 if ((m = htable[kk]) == -1) {
388 htable[kk] = nedges++;
390 else if (cadjncy[m] == k) {
394 for (jj=0; jj<nedges; jj++) {
395 if (cadjncy[jj] == k) {
402 cadjwgt[nedges++] = 1;
409 cadjwgtsum[cnvtxs] += adjwgtsum[
u];
413 for (j=istart; j<iend; j++) {
416 if ((m = htable[kk]) == -1) {
419 htable[kk] = nedges++;
421 else if (cadjncy[m] == k) {
425 for (jj=0; jj<nedges; jj++) {
426 if (cadjncy[jj] == k) {
433 cadjwgt[nedges++] = 1;
439 jj = htable[cnvtxs&mask];
440 if (jj >= 0 && cadjncy[jj] != cnvtxs) {
441 for (jj=0; jj<nedges; jj++) {
442 if (cadjncy[jj] == cnvtxs)
446 if (jj >= 0 && cadjncy[jj] == cnvtxs) {
447 cadjwgtsum[cnvtxs] -= cadjwgt[jj];
448 cadjncy[jj] = cadjncy[--nedges];
449 cadjwgt[jj] = cadjwgt[nedges];
453 ASSERTP(cadjwgtsum[cnvtxs] ==
idxsum(nedges, cadjwgt), (
"%d %d %d %d %d\n", cnvtxs, cadjwgtsum[cnvtxs],
idxsum(nedges, cadjwgt), adjwgtsum[u], adjwgtsum[v]));
455 for (j=0; j<nedges; j++)
456 htable[cadjncy[j]&mask] = -1;
457 htable[cnvtxs&mask] = -1;
460 cxadj[++cnvtxs] = cnedges;
484 cgraph->
nvtxs = cnvtxs;
492 if (graph->
ncon == 1) {
499 cgraph->
cmap = cgraph->
gdata + 4*cnvtxs+1;
508 cgraph->
cmap = cgraph->
gdata + 3*cnvtxs+1;
519 cgraph->
cmap = cgraph->
gdata + 3*cnvtxs+1;
527 cgraph->
cmap = cgraph->
gdata + 2*cnvtxs+1;
549 if (graph->
ncon == 1) {
#define CreateCoarseGraph_NVW
struct graphdef * coarser
#define CreateCoarseGraphNoMask
#define IFSET(a, flag, cmd)
#define ASSERTP(expr, msg)
#define CreateCoarseGraph