23 int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
24 idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
25 idxtype *mptr, *mind, *moved, *swaps, *perm;
28 int higain, oldgain, mincut, initcut, mincutorder;
29 int pass, to, other, limit;
30 int badmaxpwgt, mindiff, newdiff;
56 printf(
"Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut));
58 badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2])/2);
60 for (pass=0; pass<npasses; pass++) {
66 initcut = mincut = graph->
mincut;
70 for (ii=0; ii<nbnd; ii++) {
73 PQueueInsert(&parts[0], i, vwgt[i]-rinfo[i].edegrees[1]);
74 PQueueInsert(&parts[1], i, vwgt[i]-rinfo[i].edegrees[0]);
86 mindiff = abs(pwgts[0]-pwgts[1]);
87 to = (pwgts[0] < pwgts[1] ? 0 : 1);
88 for (nswaps=0; nswaps<nvtxs; nswaps++) {
91 if (u[0] != -1 && u[1] != -1) {
92 g[0] = vwgt[u[0]]-rinfo[u[0]].
edegrees[1];
93 g[1] = vwgt[u[1]]-rinfo[u[1]].
edegrees[0];
95 to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2));
98 if (pwgts[to]+vwgt[u[to]] > badmaxpwgt)
101 else if (u[0] == -1 && u[1] == -1) {
104 else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
107 else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
116 if (moved[higain] == -1)
117 PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);
119 ASSERT(bndptr[higain] != -1);
121 pwgts[2] -= (vwgt[higain]-rinfo[higain].
edegrees[other]);
123 newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
124 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
126 mincutorder = nswaps;
130 if (nswaps - mincutorder > limit) {
131 pwgts[2] += (vwgt[higain]-rinfo[higain].
edegrees[other]);
137 pwgts[to] += vwgt[higain];
139 moved[higain] = nswaps;
140 swaps[nswaps] = higain;
146 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
149 oldgain = vwgt[k]-rinfo[k].
edegrees[to];
150 rinfo[k].
edegrees[to] += vwgt[higain];
151 if (moved[k] == -1 || moved[k] == -(2+other))
152 PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);
154 else if (where[k] == other) {
155 ASSERTP(bndptr[k] == -1, (
"%d %d %d\n", k, bndptr[k], where[k]));
160 pwgts[other] -= vwgt[k];
163 edegrees[0] = edegrees[1] = 0;
164 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
167 edegrees[where[kk]] += vwgt[kk];
169 oldgain = vwgt[kk]-rinfo[kk].
edegrees[other];
170 rinfo[kk].
edegrees[other] -= vwgt[k];
171 if (moved[kk] == -1 || moved[kk] == -(2+to))
177 if (moved[k] == -1) {
183 mptr[nswaps+1] = nmind;
186 printf(
"Moved %6d to %3d, Gain: %5d [%5d] [%4d %4d] \t[%5d %5d %5d]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
194 for (nswaps--; nswaps>mincutorder; nswaps--) {
195 higain = swaps[nswaps];
201 INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
206 edegrees[0] = edegrees[1] = 0;
207 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
210 rinfo[k].
edegrees[to] -= vwgt[higain];
212 edegrees[where[k]] += vwgt[k];
216 for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
220 INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
222 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
225 rinfo[kk].
edegrees[other] += vwgt[k];
230 ASSERT(mincut == pwgts[2]);
233 printf(
"\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
238 if (mincutorder == -1 || mincut >= initcut)
258 int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
259 idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
260 idxtype *mptr, *mind, *moved, *swaps, *perm;
263 int higain, oldgain, mincut, initcut, mincutorder;
264 int pass, to, other, limit;
265 int badmaxpwgt, mindiff, newdiff;
268 nvtxs = graph->
nvtxs;
275 where = graph->
where;
276 pwgts = graph->
pwgts;
291 printf(
"Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut));
293 badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2])/2);
295 for (pass=0; pass<npasses; pass++) {
301 initcut = mincut = graph->
mincut;
305 for (ii=0; ii<nbnd; ii++) {
306 i = bndind[perm[ii]];
308 PQueueInsert(&parts[0], i, vwgt[i]-rinfo[i].edegrees[1]);
309 PQueueInsert(&parts[1], i, vwgt[i]-rinfo[i].edegrees[0]);
321 mindiff = abs(pwgts[0]-pwgts[1]);
322 to = (pwgts[0] < pwgts[1] ? 0 : 1);
323 for (nswaps=0; nswaps<nvtxs; nswaps++) {
324 badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2]/2)/2);
328 if (u[0] != -1 && u[1] != -1) {
329 g[0] = vwgt[u[0]]-rinfo[u[0]].
edegrees[1];
330 g[1] = vwgt[u[1]]-rinfo[u[1]].
edegrees[0];
332 to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2));
335 if (pwgts[to]+vwgt[u[to]] > badmaxpwgt)
338 else if (u[0] == -1 && u[1] == -1) {
341 else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
344 else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
353 if (moved[higain] == -1)
354 PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);
356 ASSERT(bndptr[higain] != -1);
358 pwgts[2] -= (vwgt[higain]-rinfo[higain].
edegrees[other]);
360 newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
361 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
363 mincutorder = nswaps;
367 if (nswaps - mincutorder > limit) {
368 pwgts[2] += (vwgt[higain]-rinfo[higain].
edegrees[other]);
374 pwgts[to] += vwgt[higain];
376 moved[higain] = nswaps;
377 swaps[nswaps] = higain;
383 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
386 oldgain = vwgt[k]-rinfo[k].
edegrees[to];
387 rinfo[k].
edegrees[to] += vwgt[higain];
388 if (moved[k] == -1 || moved[k] == -(2+other))
389 PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);
391 else if (where[k] == other) {
392 ASSERTP(bndptr[k] == -1, (
"%d %d %d\n", k, bndptr[k], where[k]));
397 pwgts[other] -= vwgt[k];
400 edegrees[0] = edegrees[1] = 0;
401 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
404 edegrees[where[kk]] += vwgt[kk];
406 oldgain = vwgt[kk]-rinfo[kk].
edegrees[other];
407 rinfo[kk].
edegrees[other] -= vwgt[k];
408 if (moved[kk] == -1 || moved[kk] == -(2+to))
414 if (moved[k] == -1) {
420 mptr[nswaps+1] = nmind;
423 printf(
"Moved %6d to %3d, Gain: %5d [%5d] [%4d %4d] \t[%5d %5d %5d]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
431 for (nswaps--; nswaps>mincutorder; nswaps--) {
432 higain = swaps[nswaps];
438 INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
443 edegrees[0] = edegrees[1] = 0;
444 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
447 rinfo[k].
edegrees[to] -= vwgt[higain];
449 edegrees[where[k]] += vwgt[k];
453 for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
457 INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
459 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
462 rinfo[kk].
edegrees[other] += vwgt[k];
467 ASSERT(mincut == pwgts[2]);
470 printf(
"\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
475 if (mincutorder == -1 || mincut >= initcut)
495 int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
496 idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
497 idxtype *mptr, *mind, *moved, *swaps, *perm;
500 int higain, oldgain, mincut, initcut, mincutorder;
501 int pass, to, other, limit;
502 int mindiff, newdiff;
505 nvtxs = graph->
nvtxs;
512 where = graph->
where;
513 pwgts = graph->
pwgts;
528 printf(
"Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut));
530 for (pass=0; pass<npasses; pass++) {
536 initcut = mincut = graph->
mincut;
540 for (ii=0; ii<nbnd; ii++) {
541 i = bndind[perm[ii]];
543 PQueueInsert(&parts[0], i, vwgt[i]-rinfo[i].edegrees[1]);
544 PQueueInsert(&parts[1], i, vwgt[i]-rinfo[i].edegrees[0]);
556 mindiff = abs(pwgts[0]-pwgts[1]);
557 to = (pwgts[0] < pwgts[1] ? 0 : 1);
558 for (nswaps=0; nswaps<nvtxs; nswaps++) {
559 to = (pwgts[0] < pwgts[1] ? 0 : 1);
561 if (pwgts[0] == pwgts[1]) {
564 if (u[0] != -1 && u[1] != -1) {
565 g[0] = vwgt[u[0]]-rinfo[u[0]].
edegrees[1];
566 g[1] = vwgt[u[1]]-rinfo[u[1]].
edegrees[0];
568 to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2));
576 if (moved[higain] == -1)
577 PQueueDelete(&parts[other], higain, vwgt[higain]-rinfo[higain].edegrees[to]);
579 ASSERT(bndptr[higain] != -1);
581 pwgts[2] -= (vwgt[higain]-rinfo[higain].
edegrees[other]);
583 newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
584 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
586 mincutorder = nswaps;
590 if (nswaps - mincutorder > limit) {
591 pwgts[2] += (vwgt[higain]-rinfo[higain].
edegrees[other]);
597 pwgts[to] += vwgt[higain];
599 moved[higain] = nswaps;
600 swaps[nswaps] = higain;
606 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
609 oldgain = vwgt[k]-rinfo[k].
edegrees[to];
610 rinfo[k].
edegrees[to] += vwgt[higain];
611 if (moved[k] == -1 || moved[k] == -(2+other))
612 PQueueUpdate(&parts[other], k, oldgain, oldgain-vwgt[higain]);
614 else if (where[k] == other) {
615 ASSERTP(bndptr[k] == -1, (
"%d %d %d\n", k, bndptr[k], where[k]));
620 pwgts[other] -= vwgt[k];
623 edegrees[0] = edegrees[1] = 0;
624 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
627 edegrees[where[kk]] += vwgt[kk];
629 oldgain = vwgt[kk]-rinfo[kk].
edegrees[other];
630 rinfo[kk].
edegrees[other] -= vwgt[k];
631 if (moved[kk] == -1 || moved[kk] == -(2+to))
637 if (moved[k] == -1) {
643 mptr[nswaps+1] = nmind;
646 printf(
"Moved %6d to %3d, Gain: %5d [%5d] [%4d %4d] \t[%5d %5d %5d]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
654 for (nswaps--; nswaps>mincutorder; nswaps--) {
655 higain = swaps[nswaps];
661 INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
666 edegrees[0] = edegrees[1] = 0;
667 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
670 rinfo[k].
edegrees[to] -= vwgt[higain];
672 edegrees[where[k]] += vwgt[k];
676 for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
680 INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
682 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
685 rinfo[kk].
edegrees[other] += vwgt[k];
690 ASSERT(mincut == pwgts[2]);
693 printf(
"\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
698 if (mincutorder == -1 || mincut >= initcut)
719 int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
720 idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
721 idxtype *mptr, *mind, *swaps, *perm;
724 int higain, oldgain, mincut, initcut, mincutorder;
725 int pass, to, other, limit;
726 int badmaxpwgt, mindiff, newdiff;
728 nvtxs = graph->
nvtxs;
735 where = graph->
where;
736 pwgts = graph->
pwgts;
747 printf(
"Partitions-N1: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d\n", pwgts[0], pwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut));
749 badmaxpwgt = (int)(ubfactor*(pwgts[0]+pwgts[1]+pwgts[2])/2);
751 to = (pwgts[0] < pwgts[1] ? 1 : 0);
752 for (pass=0; pass<npasses; pass++) {
759 initcut = mincut = graph->
mincut;
763 for (ii=0; ii<nbnd; ii++) {
764 i = bndind[perm[ii]];
766 PQueueInsert(&parts, i, vwgt[i]-rinfo[i].edegrees[other]);
778 mindiff = abs(pwgts[0]-pwgts[1]);
779 for (nswaps=0; nswaps<nvtxs; nswaps++) {
784 ASSERT(bndptr[higain] != -1);
786 if (pwgts[to]+vwgt[higain] > badmaxpwgt)
789 pwgts[2] -= (vwgt[higain]-rinfo[higain].
edegrees[other]);
791 newdiff = abs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
792 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
794 mincutorder = nswaps;
798 if (nswaps - mincutorder > limit) {
799 pwgts[2] += (vwgt[higain]-rinfo[higain].
edegrees[other]);
805 pwgts[to] += vwgt[higain];
807 swaps[nswaps] = higain;
813 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
816 rinfo[k].
edegrees[to] += vwgt[higain];
818 else if (where[k] == other) {
819 ASSERTP(bndptr[k] == -1, (
"%d %d %d\n", k, bndptr[k], where[k]));
824 pwgts[other] -= vwgt[k];
827 edegrees[0] = edegrees[1] = 0;
828 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
831 edegrees[where[kk]] += vwgt[kk];
833 oldgain = vwgt[kk]-rinfo[kk].
edegrees[other];
834 rinfo[kk].
edegrees[other] -= vwgt[k];
845 mptr[nswaps+1] = nmind;
849 printf(
"Moved %6d to %3d, Gain: %5d [%5d] \t[%5d %5d %5d] [%3d %2d]\n",
850 higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain], pwgts[0], pwgts[1], pwgts[2], nswaps, limit));
858 for (nswaps--; nswaps>mincutorder; nswaps--) {
859 higain = swaps[nswaps];
862 ASSERT(where[higain] == to);
864 INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
869 edegrees[0] = edegrees[1] = 0;
870 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
873 rinfo[k].
edegrees[to] -= vwgt[higain];
875 edegrees[where[k]] += vwgt[k];
879 for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
883 INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
885 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
888 rinfo[kk].
edegrees[other] += vwgt[k];
893 ASSERT(mincut == pwgts[2]);
896 printf(
"\tMinimum sep: %6d at %5d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
901 if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))
920 int i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps;
921 idxtype *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
928 nvtxs = graph->
nvtxs;
935 where = graph->
where;
936 pwgts = graph->
pwgts;
939 if (abs(pwgts[0]-pwgts[1]) < (
int)((ubfactor-1.0)*(pwgts[0]+pwgts[1])))
941 if (abs(pwgts[0]-pwgts[1]) < 3*
idxsum(nvtxs, vwgt)/nvtxs)
944 to = (pwgts[0] < pwgts[1] ? 0 : 1);
953 printf(
"Partitions: [%6d %6d] Nv-Nb[%6d %6d]. ISep: %6d [B]\n", pwgts[0], pwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut));
957 for (ii=0; ii<nbnd; ii++) {
958 i = bndind[perm[ii]];
960 PQueueInsert(&parts, i, vwgt[i]-rinfo[i].edegrees[other]);
969 for (nswaps=0; nswaps<nvtxs; nswaps++) {
975 if (pwgts[other] - rinfo[higain].edegrees[other] < (pwgts[0]+pwgts[1])/2)
978 if (pwgts[other] - rinfo[higain].edegrees[other] < pwgts[to]+vwgt[higain])
982 ASSERT(bndptr[higain] != -1);
984 pwgts[2] -= (vwgt[higain]-rinfo[higain].
edegrees[other]);
987 pwgts[to] += vwgt[higain];
991 printf(
"Moved %6d to %3d, Gain: %3d, \t[%5d %5d %5d]\n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));
997 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
1000 rinfo[k].
edegrees[to] += vwgt[higain];
1002 else if (where[k] == other) {
1003 ASSERTP(bndptr[k] == -1, (
"%d %d %d\n", k, bndptr[k], where[k]));
1007 pwgts[other] -= vwgt[k];
1010 edegrees[0] = edegrees[1] = 0;
1011 for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
1014 edegrees[where[kk]] += vwgt[kk];
1016 ASSERT(bndptr[kk] != -1);
1017 oldgain = vwgt[kk]-rinfo[kk].
edegrees[other];
1018 rinfo[kk].
edegrees[other] -= vwgt[k];
1020 if (moved[kk] == -1)
1030 if (pwgts[to] > pwgts[other])
1035 printf(
"\tBalanced sep: %6d at %4d, PWGTS: [%6d %6d], NBND: %6d\n", pwgts[2], nswaps, pwgts[0], pwgts[1], nbnd));
1037 graph->
mincut = pwgts[2];
1056 for (j=xadj[0]; j<xadj[1]; j++)
1057 max += vwgt[adjncy[j]];
1059 for (i=1; i<nvtxs; i++) {
1060 for (k=0, j=xadj[i]; j<xadj[i+1]; j++)
1061 k += vwgt[adjncy[j]];
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define CheckNodePartitionParams
#define ComputeMaxNodeGain
#define IFSET(a, flag, cmd)
#define ASSERTP(expr, msg)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define FM_2WayNodeRefine_OneSided
#define FM_2WayNodeRefineEqWgt
#define FM_2WayNodeRefine
#define INC_DEC(a, b, val)
#define FM_2WayNodeBalance
void FM_2WayNodeRefine2(CtrlType *ctrl, GraphType *graph, float ubfactor, int npasses)