21 float *orgubvec,
int npasses)
23 int i, ii, iii, j, jj, k, l, pass, nvtxs, ncon, nmoves, nbnd, myndegrees, same;
24 int from, me, to, oldcut, gain;
25 idxtype *xadj, *adjncy, *adjwgt;
26 idxtype *where, *perm, *bndptr, *bndind;
29 float *npwgts, *nvwgt, *minwgt, *maxwgt, maxlb, minlb, ubvec[
MAXNCON], tvec[
MAXNCON];
48 maxlb = minlb = orgubvec[0];
49 for (i=1; i<ncon; i++) {
50 minlb = (orgubvec[i] < minlb ? orgubvec[i] : minlb);
51 maxlb = (orgubvec[i] > maxlb ? orgubvec[i] : maxlb);
53 same = (fabs(maxlb-minlb) < .01 ? 1 : 0);
58 for (i=0; i<ncon; i++)
59 ubvec[i] =
amax(ubvec[i], orgubvec[i]);
62 for (i=0; i<nparts; i++) {
63 for (j=0; j<ncon; j++) {
64 maxwgt[i*ncon+j] = ubvec[j]/nparts;
65 minwgt[i*ncon+j] = 1.0/(ubvec[j]*nparts);
71 for (i=1; i<ncon; i++)
72 maxlb = (ubvec[i] > maxlb ? ubvec[i] : maxlb);
74 for (i=0; i<nparts; i++) {
75 for (j=0; j<ncon; j++) {
76 maxwgt[i*ncon+j] = maxlb/nparts;
77 minwgt[i*ncon+j] = 1.0/(maxlb*nparts);
86 printf(
"Partitions: [%5.4f %5.4f], Nv-Nb[%6d %6d]. Cut: %6d, LB: ",
87 npwgts[
samin(ncon*nparts, npwgts)], npwgts[
samax(ncon*nparts, npwgts)],
90 for (i=0; i<ncon; i++)
91 printf(
"%.3f ", tvec[i]);
95 for (pass=0; pass<npasses; pass++) {
102 for (nmoves=iii=0; iii<graph->
nbnd; iii++) {
108 myrinfo = graph->
rinfo+i;
110 if (myrinfo->
ed >= myrinfo->
id) {
112 nvwgt = graph->
nvwgt+i*ncon;
114 if (myrinfo->
id > 0 &&
AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, -1.0, nvwgt, minwgt+from*ncon))
120 for (k=0; k<myndegrees; k++) {
121 to = myedegrees[k].
pid;
122 gain = myedegrees[k].
ed - myrinfo->
id;
131 for (j=k+1; j<myndegrees; j++) {
132 to = myedegrees[j].
pid;
133 if ((myedegrees[j].ed > myedegrees[k].ed &&
136 (myedegrees[j].ed == myedegrees[k].ed &&
137 IsHBalanceBetterTT(ncon, nparts, npwgts+myedegrees[k].pid*ncon, npwgts+to*ncon, nvwgt, ubvec)))
141 to = myedegrees[k].
pid;
143 if (myedegrees[k].ed-myrinfo->
id == 0
145 &&
AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, npwgts+from*ncon, maxwgt+from*ncon))
151 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
156 saxpy(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);
157 saxpy(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);
159 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
160 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
161 if (myedegrees[k].ed == 0)
162 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
164 myedegrees[k].
pid = from;
166 if (myrinfo->
ed-myrinfo->
id < 0)
170 for (j=xadj[i]; j<xadj[i+1]; j++) {
174 myrinfo = graph->
rinfo+ii;
186 if (myrinfo->
ed-myrinfo->
id >= 0 && bndptr[ii] == -1)
192 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[ii] != -1)
198 for (k=0; k<myrinfo->
ndegrees; k++) {
199 if (myedegrees[k].pid == from) {
200 if (myedegrees[k].ed == adjwgt[j])
201 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
203 myedegrees[k].
ed -= adjwgt[j];
211 for (k=0; k<myrinfo->
ndegrees; k++) {
212 if (myedegrees[k].pid == to) {
213 myedegrees[k].
ed += adjwgt[j];
219 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
234 printf(
"\t [%5.4f %5.4f], Nb: %6d, Nmoves: %5d, Cut: %6d, LB: ",
235 npwgts[
samin(ncon*nparts, npwgts)], npwgts[
samax(ncon*nparts, npwgts)],
236 nbnd, nmoves, graph->
mincut);
238 for (i=0; i<ncon; i++)
239 printf(
"%.3f ", tvec[i]);
243 if (graph->
mincut == oldcut)
258 float *ubvec,
int npasses)
260 int i, ii, iii, j, jj, k, l, pass, nvtxs, ncon, nbnd, myndegrees, oldgain, gain, nmoves;
261 int from, me, to, oldcut;
262 idxtype *xadj, *adjncy, *adjwgt;
263 idxtype *where, *perm, *bndptr, *bndind, *moved;
267 float *npwgts, *nvwgt, *minwgt, *maxwgt, tvec[
MAXNCON];
269 nvtxs = graph->
nvtxs;
278 where = graph->
where;
285 for (i=0; i<nparts; i++) {
286 for (j=0; j<ncon; j++) {
287 maxwgt[i*ncon+j] = ubvec[j]/nparts;
288 minwgt[i*ncon+j] = 1.0/(ubvec[j]*nparts);
298 printf(
"Partitions: [%5.4f %5.4f], Nv-Nb[%6d %6d]. Cut: %6d, LB: ",
299 npwgts[
samin(ncon*nparts, npwgts)], npwgts[
samax(ncon*nparts, npwgts)],
302 for (i=0; i<ncon; i++)
303 printf(
"%.3f ", tvec[i]);
308 for (pass=0; pass<npasses; pass++) {
322 for (ii=0; ii<nbnd; ii++) {
323 i = bndind[perm[ii]];
334 myrinfo = graph->
rinfo+i;
336 nvwgt = graph->
nvwgt+i*ncon;
338 if (
AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, -1.0, nvwgt, minwgt+from*ncon))
344 for (k=0; k<myndegrees; k++) {
345 to = myedegrees[k].
pid;
352 for (j=k+1; j<myndegrees; j++) {
353 to = myedegrees[j].
pid;
354 if (
IsHBalanceBetterTT(ncon, nparts, npwgts+myedegrees[k].pid*ncon, npwgts+to*ncon, nvwgt, ubvec))
358 to = myedegrees[k].
pid;
361 if (!
AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, maxwgt+from*ncon))
363 if (myedegrees[k].ed-myrinfo->
id >= 0)
381 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
386 saxpy(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);
387 saxpy(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);
389 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
390 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
391 if (myedegrees[k].ed == 0)
392 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
394 myedegrees[k].
pid = from;
396 if (myrinfo->
ed == 0)
400 for (j=xadj[i]; j<xadj[i+1]; j++) {
404 myrinfo = graph->
rinfo+ii;
413 oldgain = (myrinfo->
ed-myrinfo->
id);
418 if (myrinfo->
ed > 0 && bndptr[ii] == -1)
424 if (myrinfo->
ed == 0 && bndptr[ii] != -1)
430 for (k=0; k<myrinfo->
ndegrees; k++) {
431 if (myedegrees[k].pid == from) {
432 if (myedegrees[k].ed == adjwgt[j])
433 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
435 myedegrees[k].
ed -= adjwgt[j];
443 for (k=0; k<myrinfo->
ndegrees; k++) {
444 if (myedegrees[k].pid == to) {
445 myedegrees[k].
ed += adjwgt[j];
451 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
457 if (me == to || me == from) {
458 gain = myrinfo->
ed-myrinfo->
id;
459 if (moved[ii] == 2) {
467 else if (moved[ii] == -1 && myrinfo->
ed > 0) {
482 printf(
"\t [%5.4f %5.4f], Nb: %6d, Nmoves: %5d, Cut: %6d, LB: ",
483 npwgts[
samin(ncon*nparts, npwgts)], npwgts[
samax(ncon*nparts, npwgts)],
484 nbnd, nmoves, graph->
mincut);
486 for (i=0; i<ncon; i++)
487 printf(
"%.3f ", tvec[i]);
512 int AreAllHVwgtsBelow(
int ncon,
float alpha,
float *vwgt1,
float beta,
float *vwgt2,
float *limit)
516 for (i=0; i<ncon; i++)
517 if (alpha*vwgt1[i] + beta*vwgt2[i] > limit[i])
529 int AreAllHVwgtsAbove(
int ncon,
float alpha,
float *vwgt1,
float beta,
float *vwgt2,
float *limit)
533 for (i=0; i<ncon; i++)
534 if (alpha*vwgt1[i] + beta*vwgt2[i] < limit[i])
550 for (i=0; i<ncon; i++) {
552 for (j=0; j<nparts; j++) {
553 if (npwgts[j*ncon+i] > max)
554 max = npwgts[j*ncon+i];
557 lbvec[i] = max*nparts;
570 for (i=0; i<ncon; i++) {
572 for (j=0; j<nparts; j++) {
573 if (npwgts[j*ncon+i] > max)
574 max = npwgts[j*ncon+i];
577 if (ubvec[i] < max*nparts)
596 float blb1=0.0, alb1=0.0, sblb=0.0, salb=0.0;
597 float blb2=0.0, alb2=0.0;
600 for (i=0; i<ncon; i++) {
601 temp =
amax(pfrom[i], pto[i])*nparts/ubvec[i];
606 else if (blb2 < temp)
610 temp =
amax(pfrom[i]-vwgt[i], pto[i]+vwgt[i])*nparts/ubvec[i];
615 else if (alb2 < temp)
644 float m11=0.0, m12=0.0, m21=0.0, m22=0.0, sm1=0.0, sm2=0.0, temp;
646 for (i=0; i<ncon; i++) {
647 temp = (pt1[i]+vwgt[i])*nparts/ubvec[i];
656 temp = (pt2[i]+vwgt[i])*nparts/ubvec[i];
#define ComputeHKWayLoadImbalance
#define MCGreedy_KWayEdgeBalanceHorizontal
#define IsHBalanceBetterFT
void fwspacefree(CtrlType *ctrl, int n)
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define AreAllHVwgtsBelow
#define IFSET(a, flag, cmd)
#define AreAllHVwgtsAbove
#define MCRandom_KWayEdgeRefineHorizontal
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define IsHBalanceBetterTT
#define INC_DEC(a, b, val)