23 idx_t i, ii,
j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
25 idx_t *mptr, *mind, *moved, *swaps;
28 idx_t higain, oldgain, mincut, initcut, mincutorder;
30 idx_t badmaxpwgt, mindiff, newdiff;
41 bndind =
graph->bndind;
42 bndptr =
graph->bndptr;
45 rinfo =
graph->nrinfo;
56 badmaxpwgt = (
idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
61 for (pass=0; pass<niter; pass++) {
62 iset(nvtxs, -1, moved);
67 initcut = mincut =
graph->mincut;
72 for (ii=0; ii<nbnd; ii++) {
73 i = bndind[swaps[ii]];
88 mindiff =
iabs(pwgts[0]-pwgts[1]);
89 to = (pwgts[0] < pwgts[1] ? 0 : 1);
90 for (nswaps=0; nswaps<nvtxs; nswaps++) {
93 if (u[0] != -1 && u[1] != -1) {
97 to = (
g[0] >
g[1] ? 0 : (
g[0] <
g[1] ? 1 : pass%2));
99 if (pwgts[to]+
vwgt[u[to]] > badmaxpwgt)
102 else if (u[0] == -1 && u[1] == -1) {
105 else if (u[0] != -1 && pwgts[0]+
vwgt[u[0]] <= badmaxpwgt) {
108 else if (u[1] != -1 && pwgts[1]+
vwgt[u[1]] <= badmaxpwgt) {
117 if (moved[higain] == -1)
120 ASSERT(bndptr[higain] != -1);
124 if (nmind +
xadj[higain+1]-
xadj[higain] >= 2*nvtxs-1)
129 newdiff =
iabs(pwgts[to]+
vwgt[higain] - (pwgts[
other]-rinfo[higain].edegrees[
other]));
130 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
132 mincutorder = nswaps;
136 if (nswaps - mincutorder > 2*limit ||
137 (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
144 pwgts[to] +=
vwgt[higain];
146 moved[higain] = nswaps;
147 swaps[nswaps] = higain;
158 if (moved[k] == -1 || moved[k] == -(2+
other))
170 edegrees[0] = edegrees[1] = 0;
171 for (jj=
xadj[k]; jj<
xadj[k+1]; jj++) {
178 if (moved[kk] == -1 || moved[kk] == -(2+to))
184 if (moved[k] == -1) {
190 mptr[nswaps+1] = nmind;
193 printf(
"Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] [%4"PRIDX" %4"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to,
g[to],
g[
other],
vwgt[u[to]],
vwgt[u[
other]], pwgts[0], pwgts[1], pwgts[2]));
201 for (nswaps--; nswaps>mincutorder; nswaps--) {
202 higain = swaps[nswaps];
213 edegrees[0] = edegrees[1] = 0;
223 for (
j=mptr[nswaps];
j<mptr[nswaps+1];
j++) {
229 for (jj=
xadj[k]; jj<
xadj[k+1]; jj++) {
237 ASSERT(mincut == pwgts[2]);
240 printf(
"\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
242 graph->mincut = mincut;
245 if (mincutorder == -1 || mincut >= initcut)
265 idx_t i, ii,
j, k, jj, kk, nvtxs, nbnd, nswaps, nmind, iend;
267 idx_t *mptr, *mind, *swaps;
270 idx_t higain, mincut, initcut, mincutorder;
272 idx_t badmaxpwgt, mindiff, newdiff;
277 nvtxs =
graph->nvtxs;
282 bndind =
graph->bndind;
283 bndptr =
graph->bndptr;
285 pwgts =
graph->pwgts;
286 rinfo =
graph->nrinfo;
295 badmaxpwgt = (
idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
300 to = (pwgts[0] < pwgts[1] ? 1 : 0);
301 for (pass=0; pass<2*niter; pass++) {
308 initcut = mincut =
graph->mincut;
313 for (ii=0; ii<nbnd; ii++) {
314 i = bndind[swaps[ii]];
329 mindiff =
iabs(pwgts[0]-pwgts[1]);
330 for (nswaps=0; nswaps<nvtxs; nswaps++) {
334 ASSERT(bndptr[higain] != -1);
338 if (nmind +
xadj[higain+1]-
xadj[higain] >= 2*nvtxs-1)
341 if (pwgts[to]+
vwgt[higain] > badmaxpwgt)
346 newdiff =
iabs(pwgts[to]+
vwgt[higain] - (pwgts[
other]-rinfo[higain].edegrees[
other]));
347 if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
349 mincutorder = nswaps;
353 if (nswaps - mincutorder > 3*limit ||
354 (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
361 pwgts[to] +=
vwgt[higain];
363 swaps[nswaps] = higain;
385 edegrees[0] = edegrees[1] = 0;
386 for (jj=
xadj[k], iend=
xadj[k+1]; jj<iend; jj++) {
402 mptr[nswaps+1] = nmind;
408 higain, to, (
vwgt[higain]-rinfo[higain].edegrees[
other]),
vwgt[higain],
409 pwgts[0], pwgts[1], pwgts[2], nswaps, limit));
418 for (nswaps--; nswaps>mincutorder; nswaps--) {
419 higain = swaps[nswaps];
429 edegrees[0] = edegrees[1] = 0;
439 for (
j=mptr[nswaps];
j<mptr[nswaps+1];
j++) {
445 for (jj=
xadj[k], iend=
xadj[k+1]; jj<iend; jj++) {
454 ASSERT(mincut == pwgts[2]);
457 printf(
"\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
459 graph->mincut = mincut;
462 if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))
478 idx_t i, ii,
j, k, jj, kk, nvtxs, nbnd, nswaps, gain;
479 idx_t badmaxpwgt, higain, oldgain, pass, to,
other;
486 nvtxs =
graph->nvtxs;
491 bndind =
graph->bndind;
492 bndptr =
graph->bndptr;
494 pwgts =
graph->pwgts;
495 rinfo =
graph->nrinfo;
499 badmaxpwgt = (
idx_t)(mult*(pwgts[0]+pwgts[1]));
500 if (
gk_max(pwgts[0], pwgts[1]) < badmaxpwgt)
502 if (
iabs(pwgts[0]-pwgts[1]) < 3*
graph->tvwgt[0]/nvtxs)
507 to = (pwgts[0] < pwgts[1] ? 0 : 1);
520 for (ii=0; ii<nbnd; ii++) {
521 i = bndind[
perm[ii]];
532 for (nswaps=0; nswaps<nvtxs; nswaps++) {
539 badmaxpwgt = (
idx_t)(mult*(pwgts[0]+pwgts[1]));
542 if (pwgts[to] > pwgts[
other])
546 if (gain < 0 && pwgts[
other] < badmaxpwgt)
550 if (pwgts[to]+
vwgt[higain] > badmaxpwgt)
553 ASSERT(bndptr[higain] != -1);
558 pwgts[to] +=
vwgt[higain];
581 edegrees[0] = edegrees[1] = 0;
582 for (jj=
xadj[k]; jj<
xadj[k+1]; jj++) {
603 printf(
"\tBalanced sep: %6"PRIDX" at %4"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", pwgts[2], nswaps, pwgts[0], pwgts[1], nbnd));
605 graph->mincut = pwgts[2];