24 int i, ii, j, k, nvtxs, ncon, cnvtxs, maxidx;
25 idxtype *xadj, *adjncy, *adjwgt;
45 for (ii=0; ii<nvtxs; ii++) {
52 for (j=xadj[i]; j<xadj[i+1]; j++) {
60 cmap[i] = cmap[maxidx] = cnvtxs++;
81 int i, ii, j, k, l, nvtxs, cnvtxs, ncon, maxidx, maxwgt;
82 idxtype *xadj, *adjncy, *adjwgt;
102 for (ii=0; ii<nvtxs; ii++) {
110 for (j=xadj[i]; j<xadj[i+1]; j++) {
112 if (match[k] ==
UNMATCHED && maxwgt <= adjwgt[j] &&
119 cmap[i] = cmap[maxidx] = cnvtxs++;
140 int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
141 idxtype *xadj, *adjncy, *adjwgt;
142 idxtype *match, *cmap, *degrees, *perm, *tperm;
147 nvtxs = graph->
nvtxs;
150 nvwgt = graph->
nvwgt;
162 avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
163 for (i=0; i<nvtxs; i++)
164 degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
170 for (ii=0; ii<nvtxs; ii++) {
174 if (xadj[i] < xadj[i+1])
178 for (j=nvtxs-1; j>ii; j--) {
180 if (match[k] ==
UNMATCHED && xadj[k] < xadj[k+1]) {
186 cmap[i] = cmap[maxidx] = cnvtxs++;
193 for (; ii<nvtxs; ii++) {
201 for (j=xadj[i]; j<xadj[i+1]; j++) {
203 if (match[k] ==
UNMATCHED && maxwgt <= adjwgt[j] &&
210 cmap[i] = cmap[maxidx] = cnvtxs++;
234 int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
235 idxtype *xadj, *adjncy, *adjwgt;
236 idxtype *match, *cmap, *degrees, *perm, *tperm;
241 nvtxs = graph->
nvtxs;
244 nvwgt = graph->
nvwgt;
256 avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
257 for (i=0; i<nvtxs; i++)
258 degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
264 for (ii=0; ii<nvtxs; ii++) {
268 if (xadj[i] < xadj[i+1])
272 for (j=nvtxs-1; j>ii; j--) {
274 if (match[k] ==
UNMATCHED && xadj[k] < xadj[k+1]) {
280 cmap[i] = cmap[maxidx] = cnvtxs++;
287 for (; ii<nvtxs; ii++) {
295 for (j=xadj[i]; j<xadj[i+1]; j++) {
300 (maxwgt < adjwgt[j] ||
301 (maxwgt == adjwgt[j] &&
302 BetterVBalance(ncon, norm, nvwgt+i*ncon, nvwgt+maxidx*ncon, nvwgt+k*ncon) >= 0
311 cmap[i] = cmap[maxidx] = cnvtxs++;
335 int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
336 idxtype *xadj, *adjncy, *adjwgt;
337 idxtype *match, *cmap, *degrees, *perm, *tperm;
342 nvtxs = graph->
nvtxs;
345 nvwgt = graph->
nvwgt;
357 avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
358 for (i=0; i<nvtxs; i++)
359 degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
365 for (ii=0; ii<nvtxs; ii++) {
369 if (xadj[i] < xadj[i+1])
373 for (j=nvtxs-1; j>ii; j--) {
375 if (match[k] ==
UNMATCHED && xadj[k] < xadj[k+1]) {
381 cmap[i] = cmap[maxidx] = cnvtxs++;
388 for (; ii<nvtxs; ii++) {
397 for (j=xadj[i]; j<xadj[i+1]; j++) {
401 vbal =
BetterVBalance(ncon, norm, nvwgt+i*ncon, nvwgt+maxidx*ncon, nvwgt+k*ncon);
403 if (vbal > 0 || (vbal > -.01 && maxwgt < adjwgt[j])) {
410 cmap[i] = cmap[maxidx] = cnvtxs++;
438 float sum1, sum2, max1, max2, min1, min2, diff1, diff2;
441 max1 = min1 = vwgt[0]+u1wgt[0];
442 max2 = min2 = vwgt[0]+u2wgt[0];
443 sum1 = vwgt[0]+u1wgt[0];
444 sum2 = vwgt[0]+u2wgt[0];
446 for (i=1; i<ncon; i++) {
447 if (max1 < vwgt[i]+u1wgt[i])
448 max1 = vwgt[i]+u1wgt[i];
449 if (min1 > vwgt[i]+u1wgt[i])
450 min1 = vwgt[i]+u1wgt[i];
452 if (max2 < vwgt[i]+u2wgt[i])
453 max2 = vwgt[i]+u2wgt[i];
454 if (min2 > vwgt[i]+u2wgt[i])
455 min2 = vwgt[i]+u2wgt[i];
457 sum1 += vwgt[i]+u1wgt[i];
458 sum2 += vwgt[i]+u2wgt[i];
463 else if (sum2 == 0.0)
466 return ((max1-min1)/sum1) - ((max2-min2)/sum2);
468 else if (norm == 1) {
470 for (i=0; i<ncon; i++) {
471 sum1 += vwgt[i]+u1wgt[i];
472 sum2 += vwgt[i]+u2wgt[i];
474 sum1 = sum1/(1.0*ncon);
475 sum2 = sum2/(1.0*ncon);
478 for (i=0; i<ncon; i++) {
479 diff1 += fabs(sum1 - (vwgt[i]+u1wgt[i]));
480 diff2 += fabs(sum2 - (vwgt[i]+u2wgt[i]));
483 return diff1 - diff2;
486 errexit(
"Unknown norm: %d\n", norm);
500 for (i=0; i<ncon; i++)
501 if (vwgt1[i] + vwgt2[i] > limit)
#define BucketSortKeysInc
#define AreAllVwgtsBelowFast
#define IFSET(a, flag, cmd)
#define CreateCoarseGraph