21 int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees;
22 int from, me, to, oldcut, vwgt, gain;
23 idxtype *xadj, *adjncy, *adjwgt;
24 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
43 tvwgt =
idxsum(nparts, pwgts);
46 for (i=0; i<nparts; i++) {
47 itpwgts[i] = tpwgts[i]*tvwgt;
48 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
49 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
55 printf(
"Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
56 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
60 for (pass=0; pass<npasses; pass++) {
67 for (nmoves=iii=0; iii<graph->
nbnd; iii++) {
73 myrinfo = graph->
rinfo+i;
75 if (myrinfo->
ed >= myrinfo->
id) {
77 vwgt = graph->
vwgt[i];
79 if (myrinfo->
id > 0 && pwgts[from]-vwgt < minwgt[from])
86 for (k=0; k<myndegrees; k++) {
87 to = myedegrees[k].
pid;
88 gain = myedegrees[k].
ed-j;
89 if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0)
95 for (j=k+1; j<myndegrees; j++) {
96 to = myedegrees[j].
pid;
97 if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
98 (myedegrees[j].ed == myedegrees[k].ed &&
99 itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
103 to = myedegrees[k].
pid;
106 if (myedegrees[k].ed-myrinfo->
id > 0)
108 else if (myedegrees[k].ed-myrinfo->
id == 0) {
109 if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
118 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
124 INC_DEC(pwgts[to], pwgts[from], vwgt);
125 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
126 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
127 if (myedegrees[k].ed == 0)
128 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
130 myedegrees[k].
pid = from;
132 if (myrinfo->
ed-myrinfo->
id < 0)
136 for (j=xadj[i]; j<xadj[i+1]; j++) {
140 myrinfo = graph->
rinfo+ii;
152 if (myrinfo->
ed-myrinfo->
id >= 0 && bndptr[ii] == -1)
158 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[ii] != -1)
164 for (k=0; k<myrinfo->
ndegrees; k++) {
165 if (myedegrees[k].pid == from) {
166 if (myedegrees[k].ed == adjwgt[j])
167 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
169 myedegrees[k].
ed -= adjwgt[j];
177 for (k=0; k<myrinfo->
ndegrees; k++) {
178 if (myedegrees[k].pid == to) {
179 myedegrees[k].
ed += adjwgt[j];
185 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
200 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
204 if (graph->
mincut == oldcut)
224 int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain;
225 int from, me, to, oldcut, vwgt;
226 idxtype *xadj, *adjncy, *adjwgt;
227 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
232 nvtxs = graph->
nvtxs;
240 where = graph->
where;
241 pwgts = graph->
pwgts;
247 tvwgt =
idxsum(nparts, pwgts);
250 for (i=0; i<nparts; i++) {
251 itpwgts[i] = tpwgts[i]*tvwgt;
252 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
253 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
262 printf(
"Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
263 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
267 for (pass=0; pass<npasses; pass++) {
277 for (ii=0; ii<nbnd; ii++) {
278 i = bndind[perm[ii]];
288 myrinfo = graph->
rinfo+i;
290 vwgt = graph->
vwgt[i];
292 if (pwgts[from]-vwgt < minwgt[from])
299 for (k=0; k<myndegrees; k++) {
300 to = myedegrees[k].
pid;
301 gain = myedegrees[k].
ed-j;
302 if (pwgts[to]+vwgt <= maxwgt[to]+gain && gain >= 0)
308 for (j=k+1; j<myndegrees; j++) {
309 to = myedegrees[j].
pid;
310 if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
311 (myedegrees[j].ed == myedegrees[k].ed &&
312 itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
316 to = myedegrees[k].
pid;
319 if (myedegrees[k].ed-myrinfo->
id > 0)
321 else if (myedegrees[k].ed-myrinfo->
id == 0) {
322 if ((iii&7) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
331 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
337 INC_DEC(pwgts[to], pwgts[from], vwgt);
338 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
339 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
340 if (myedegrees[k].ed == 0)
341 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
343 myedegrees[k].
pid = from;
345 if (myrinfo->
ed < myrinfo->
id)
349 for (j=xadj[i]; j<xadj[i+1]; j++) {
353 myrinfo = graph->
rinfo+ii;
362 oldgain = (myrinfo->
ed-myrinfo->
id);
367 if (myrinfo->
ed-myrinfo->
id >= 0 && bndptr[ii] == -1)
373 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[ii] != -1)
379 for (k=0; k<myrinfo->
ndegrees; k++) {
380 if (myedegrees[k].pid == from) {
381 if (myedegrees[k].ed == adjwgt[j])
382 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
384 myedegrees[k].
ed -= adjwgt[j];
392 for (k=0; k<myrinfo->
ndegrees; k++) {
393 if (myedegrees[k].pid == to) {
394 myedegrees[k].
ed += adjwgt[j];
400 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
405 if (me == to || me == from) {
406 gain = myrinfo->
ed-myrinfo->
id;
407 if (moved[ii] == 2) {
415 else if (moved[ii] == -1 && gain >= 0) {
430 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Cut: %6d\n",
434 if (graph->
mincut == oldcut)
454 int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves;
455 int from, me, to, oldcut, vwgt;
456 idxtype *xadj, *adjncy, *adjwgt;
457 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
462 nvtxs = graph->
nvtxs;
470 where = graph->
where;
471 pwgts = graph->
pwgts;
477 tvwgt =
idxsum(nparts, pwgts);
480 for (i=0; i<nparts; i++) {
481 itpwgts[i] = tpwgts[i]*tvwgt;
482 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
483 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
492 printf(
"Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
493 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
497 for (pass=0; pass<npasses; pass++) {
501 for (i=0; i<nparts; i++) {
502 if (pwgts[i] > maxwgt[i])
515 for (ii=0; ii<nbnd; ii++) {
516 i = bndind[perm[ii]];
527 myrinfo = graph->
rinfo+i;
529 vwgt = graph->
vwgt[i];
531 if (pwgts[from]-vwgt < minwgt[from])
537 for (k=0; k<myndegrees; k++) {
538 to = myedegrees[k].
pid;
539 if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
545 for (j=k+1; j<myndegrees; j++) {
546 to = myedegrees[j].
pid;
547 if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])
551 to = myedegrees[k].
pid;
553 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->
id < 0)
559 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
565 INC_DEC(pwgts[to], pwgts[from], vwgt);
566 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
567 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
568 if (myedegrees[k].ed == 0)
569 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
571 myedegrees[k].
pid = from;
573 if (myrinfo->
ed == 0)
577 for (j=xadj[i]; j<xadj[i+1]; j++) {
581 myrinfo = graph->
rinfo+ii;
590 oldgain = (myrinfo->
ed-myrinfo->
id);
595 if (myrinfo->
ed > 0 && bndptr[ii] == -1)
601 if (myrinfo->
ed == 0 && bndptr[ii] != -1)
607 for (k=0; k<myrinfo->
ndegrees; k++) {
608 if (myedegrees[k].pid == from) {
609 if (myedegrees[k].ed == adjwgt[j])
610 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
612 myedegrees[k].
ed -= adjwgt[j];
620 for (k=0; k<myrinfo->
ndegrees; k++) {
621 if (myedegrees[k].pid == to) {
622 myedegrees[k].
ed += adjwgt[j];
628 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
633 if (me == to || me == from) {
634 gain = myrinfo->
ed-myrinfo->
id;
635 if (moved[ii] == 2) {
643 else if (moved[ii] == -1 && myrinfo->
ed > 0) {
658 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d\n",
660 1.0*nparts*pwgts[
idxamax(nparts, pwgts)]/tvwgt, graph->
nbnd, nmoves, graph->
mincut));
#define Greedy_KWayEdgeBalance
#define Random_KWayEdgeRefine
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define Greedy_KWayEdgeRefine
#define IFSET(a, flag, cmd)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define INC_DEC(a, b, val)