67 idx_t *
where, *pwgts, *
perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
68 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
88 bndind =
graph->bndind;
89 bndptr =
graph->bndptr;
156 for (pass=0; pass<niter; pass++) {
162 if (pwgts[
i] > maxwgt[
i])
169 oldcut =
graph->mincut;
178 for (ii=0; ii<nbnd; ii++) {
179 i = bndind[
perm[ii]];
180 rgain = (
graph->ckrinfo[
i].nnbrs > 0 ?
189 for (nmoved=0, iii=0;;iii++) {
194 myrinfo =
graph->ckrinfo+
i;
202 if (myrinfo->
id > 0 && pwgts[from]-
vwgt < minwgt[from])
206 if (pwgts[from]-
vwgt < minwgt[from])
218 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
219 if (!safetos[to=mynbrs[k].pid])
221 gain = mynbrs[k].
ed-myrinfo->
id;
222 if (gain >= 0 && pwgts[to]+
vwgt <= maxwgt[to]+ffactor*gain)
228 for (
j=k-1;
j>=0;
j--) {
229 if (!safetos[to=mynbrs[
j].pid])
231 gain = mynbrs[
j].
ed-myrinfo->
id;
232 if ((mynbrs[
j].ed > mynbrs[k].ed && pwgts[to]+
vwgt <= maxwgt[to]+ffactor*gain)
234 (mynbrs[
j].ed == mynbrs[k].ed &&
235 itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid]))
241 gain = mynbrs[k].
ed-myrinfo->
id;
244 && (pwgts[from] >= maxwgt[from]
245 || itpwgts[to]*pwgts[from] > itpwgts[from]*(pwgts[to]+
vwgt)
246 || (iii%2 == 0 && safetos[to] == 2)
254 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
255 if (!safetos[to=mynbrs[k].pid])
257 if (pwgts[to]+
vwgt <= maxwgt[to] ||
258 itpwgts[from]*(pwgts[to]+
vwgt) <= itpwgts[to]*pwgts[from])
264 for (
j=k-1;
j>=0;
j--) {
265 if (!safetos[to=mynbrs[
j].pid])
267 if (itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
273 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] &&
274 mynbrs[k].ed-myrinfo->
id < 0)
283 graph->mincut -= mynbrs[k].
ed-myrinfo->
id;
288 i, to, mynbrs[k].ed-myrinfo->
id,
graph->mincut));
298 if (me != from && me != to) {
308 bndptr, bndind, bndtype);
314 myrinfo =
graph->ckrinfo+ii;
316 oldnnbrs = myrinfo->
nnbrs;
319 from, to, myrinfo,
adjwgt[
j], nbnd, bndptr, bndind, bndtype);
322 nupd, updptr, updind, bndtype);
331 for (
i=0;
i<nupd;
i++) {
332 ASSERT(updptr[updind[
i]] != -1);
335 updptr[updind[
i]] = -1;
377 idx_t *
where, *pwgts, *
perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
378 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
386 idx_t *vmarker, *pmarker, *modind;
393 nvtxs =
graph->nvtxs;
396 bndptr =
graph->bndptr;
397 bndind =
graph->bndind;
399 pwgts =
graph->pwgts;
469 for (pass=0; pass<niter; pass++) {
475 if (pwgts[
i] > maxwgt[
i])
482 oldcut =
graph->mincut;
483 oldvol =
graph->minvol;
491 for (ii=0; ii<
graph->nbnd; ii++) {
492 i = bndind[
perm[ii]];
499 for (nmoved=0, iii=0;;iii++) {
504 myrinfo =
graph->vkrinfo+
i;
512 if (myrinfo->
nid > 0 && pwgts[from]-
vwgt < minwgt[from])
516 if (pwgts[from]-
vwgt < minwgt[from])
526 xgain = (myrinfo->
nid == 0 && myrinfo->
ned > 0 ?
graph->vsize[
i] : 0);
530 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
531 if (!safetos[to=mynbrs[k].pid])
533 gain = mynbrs[k].
gv + xgain;
534 if (gain >= 0 && pwgts[to]+
vwgt <= maxwgt[to]+ffactor*gain)
540 for (
j=k-1;
j>=0;
j--) {
541 if (!safetos[to=mynbrs[
j].pid])
543 gain = mynbrs[
j].
gv + xgain;
544 if ((mynbrs[
j].gv > mynbrs[k].gv &&
545 pwgts[to]+
vwgt <= maxwgt[to]+ffactor*gain)
547 (mynbrs[
j].
gv == mynbrs[k].
gv &&
548 mynbrs[
j].
ned > mynbrs[k].
ned &&
549 pwgts[to]+
vwgt <= maxwgt[to])
551 (mynbrs[
j].gv == mynbrs[k].gv &&
552 mynbrs[
j].ned == mynbrs[k].ned &&
553 itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
559 ASSERT(xgain+mynbrs[k].gv >= 0);
562 if (xgain+mynbrs[k].gv > 0 || mynbrs[k].ned-myrinfo->
nid > 0)
564 else if (mynbrs[k].ned-myrinfo->
nid == 0) {
565 if ((iii%2 == 0 && safetos[to] == 2) ||
566 pwgts[from] >= maxwgt[from] ||
567 itpwgts[from]*(pwgts[to]+
vwgt) < itpwgts[to]*pwgts[from])
574 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
575 if (!safetos[to=mynbrs[k].pid])
577 if (pwgts[to]+
vwgt <= maxwgt[to] ||
578 itpwgts[from]*(pwgts[to]+
vwgt) <= itpwgts[to]*pwgts[from])
584 for (
j=k-1;
j>=0;
j--) {
585 if (!safetos[to=mynbrs[
j].pid])
587 if (itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
592 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] &&
593 (xgain+mynbrs[k].gv < 0 ||
594 (xgain+mynbrs[k].gv == 0 && mynbrs[k].ned-myrinfo->
nid < 0))
605 graph->minvol -= (xgain+mynbrs[k].
gv);
612 i, from, to, xgain+mynbrs[k].gv, mynbrs[k].ned-myrinfo->
nid,
623 if (me != from && me != to) {
632 updind, bndtype, vmarker, pmarker, modind);
639 for (
i=0;
i<nupd;
i++) {
640 ASSERT(updptr[updind[
i]] != -1);
643 updptr[updind[
i]] = -1;
688 idx_t i, ii, iii,
j, k,
l, pass, nvtxs,
ncon,
nparts, gain;
689 idx_t from, me, to, cto, oldcut;
692 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
696 real_t *ubfactors, *pijbm;
700 idx_t nbnd, oldnnbrs;
709 nvtxs =
graph->nvtxs;
716 bndind =
graph->bndind;
717 bndptr =
graph->bndptr;
720 pwgts =
graph->pwgts;
804 for (pass=0; pass<niter; pass++) {
811 oldcut =
graph->mincut;
820 for (ii=0; ii<nbnd; ii++) {
821 i = bndind[
perm[ii]];
822 rgain = (
graph->ckrinfo[
i].nnbrs > 0 ?
831 for (nmoved=0, iii=0;;iii++) {
836 myrinfo =
graph->ckrinfo+
i;
843 if (myrinfo->
id > 0 &&
860 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
861 if (!safetos[to=mynbrs[k].pid])
863 gain = mynbrs[k].
ed-myrinfo->
id;
871 for (
j=k-1;
j>=0;
j--) {
872 if (!safetos[to=mynbrs[
j].pid])
874 if ((mynbrs[
j].ed > mynbrs[k].ed &&
877 (mynbrs[
j].ed == mynbrs[k].ed &&
880 1, pwgts+to*
ncon, pijbm+to*
ncon))) {
887 gain = mynbrs[k].
ed-myrinfo->
id;
891 -1, pwgts+from*
ncon, pijbm+from*
ncon,
893 || (iii%2 == 0 && safetos[to] == 2)
901 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
902 if (!safetos[to=mynbrs[k].pid])
906 -1, pwgts+from*
ncon, pijbm+from*
ncon,
914 for (
j=k-1;
j>=0;
j--) {
915 if (!safetos[to=mynbrs[
j].pid])
926 if (mynbrs[k].ed-myrinfo->
id < 0 &&
928 -1, pwgts+from*
ncon, pijbm+from*
ncon,
938 graph->mincut -= mynbrs[k].
ed-myrinfo->
id;
943 i, to, mynbrs[k].ed-myrinfo->
id,
graph->mincut));
953 if (me != from && me != to) {
964 nbnd, bndptr, bndind, bndtype);
970 myrinfo =
graph->ckrinfo+ii;
972 oldnnbrs = myrinfo->
nnbrs;
975 from, to, myrinfo,
adjwgt[
j], nbnd, bndptr, bndind, bndtype);
978 nupd, updptr, updind, bndtype);
987 for (
i=0;
i<nupd;
i++) {
988 ASSERT(updptr[updind[
i]] != -1);
991 updptr[updind[
i]] = -1;
1030 idx_t i, ii, iii,
j, k,
l, pass, nvtxs,
ncon,
nparts, gain;
1031 idx_t from, me, to, cto, oldcut;
1034 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
1038 real_t *ubfactors, *pijbm;
1043 idx_t oldvol, xgain;
1044 idx_t *vmarker, *pmarker, *modind;
1051 nvtxs =
graph->nvtxs;
1056 bndptr =
graph->bndptr;
1057 bndind =
graph->bndind;
1059 pwgts =
graph->pwgts;
1062 pijbm = ctrl->
pijbm;
1106 adids = ctrl->
adids;
1148 for (pass=0; pass<niter; pass++) {
1155 oldcut =
graph->mincut;
1156 oldvol =
graph->minvol;
1164 for (ii=0; ii<
graph->nbnd; ii++) {
1165 i = bndind[
perm[ii]];
1172 for (nmoved=0, iii=0;;iii++) {
1177 myrinfo =
graph->vkrinfo+
i;
1184 if (myrinfo->
nid > 0 &&
1199 xgain = (myrinfo->
nid == 0 && myrinfo->
ned > 0 ?
graph->vsize[
i] : 0);
1203 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
1204 if (!safetos[to=mynbrs[k].pid])
1206 gain = mynbrs[k].
gv + xgain;
1214 for (
j=k-1;
j>=0;
j--) {
1215 if (!safetos[to=mynbrs[
j].pid])
1217 gain = mynbrs[
j].
gv + xgain;
1218 if ((mynbrs[
j].gv > mynbrs[k].gv &&
1221 (mynbrs[
j].
gv == mynbrs[k].
gv &&
1222 mynbrs[
j].
ned > mynbrs[k].
ned &&
1225 (mynbrs[
j].gv == mynbrs[k].gv &&
1226 mynbrs[
j].ned == mynbrs[k].ned &&
1229 1, pwgts+to*
ncon, pijbm+to*
ncon))) {
1237 if (xgain+mynbrs[k].gv > 0 || mynbrs[k].ned-myrinfo->
nid > 0)
1239 else if (mynbrs[k].ned-myrinfo->
nid == 0) {
1240 if ((iii%2 == 0 && safetos[to] == 2) ||
1242 -1, pwgts+from*
ncon, pijbm+from*
ncon,
1250 for (k=myrinfo->
nnbrs-1; k>=0; k--) {
1251 if (!safetos[to=mynbrs[k].pid])
1255 -1, pwgts+from*
ncon, pijbm+from*
ncon,
1263 for (
j=k-1;
j>=0;
j--) {
1264 if (!safetos[to=mynbrs[
j].pid])
1268 1, pwgts+to*
ncon, pijbm+to*
ncon)) {
1275 if ((xgain+mynbrs[k].gv < 0 ||
1276 (xgain+mynbrs[k].gv == 0 && mynbrs[k].ned-myrinfo->
nid < 0))
1279 -1, pwgts+from*
ncon, pijbm+from*
ncon,
1289 graph->minvol -= (xgain+mynbrs[k].
gv);
1296 i, from, to, xgain+mynbrs[k].gv, mynbrs[k].ned-myrinfo->
nid,
1307 if (me != from && me != to) {
1320 updind, bndtype, vmarker, pmarker, modind);
1327 for (
i=0;
i<nupd;
i++) {
1328 ASSERT(updptr[updind[
i]] != -1);
1331 updptr[updind[
i]] = -1;
1397 ii = bfsind[
head++];
1402 if (++nhits == tnhits)
1405 if (bfslvl[k] == 0 && bfslvl[ii] < BFSDEPTH) {
1407 bfslvl[k] = bfslvl[ii]+1;
1411 if (nhits == tnhits)
1418 bfslvl[bfsind[
j]] = 0;
1422 if (nhits < tnhits) {
1428 return (nhits != tnhits);
1465 idx_t i, ii, iii,
j, jj, k, kk,
l, u, nmod,
other, me, myidx;
1475 myrinfo =
graph->vkrinfo+
v;
1482 for (k=0; k<myrinfo->
nnbrs; k++)
1483 pmarker[mynbrs[k].pid] = k;
1486 myidx = pmarker[to];
1491 orinfo =
graph->vkrinfo+ii;
1494 if (
other == from) {
1495 for (k=0; k<orinfo->
nnbrs; k++) {
1496 if (pmarker[onbrs[k].pid] == -1)
1503 if (mynbrs[pmarker[
other]].ned > 1) {
1504 for (k=0; k<orinfo->
nnbrs; k++) {
1505 if (pmarker[onbrs[k].pid] == -1)
1510 for (k=0; k<orinfo->
nnbrs; k++) {
1511 if (pmarker[onbrs[k].pid] != -1)
1518 for (k=0; k<myrinfo->
nnbrs; k++)
1519 pmarker[mynbrs[k].pid] = -1;
1527 myidx = myrinfo->
nnbrs++;
1529 mynbrs[myidx].
ned = 0;
1531 myrinfo->
ned += myrinfo->
nid-mynbrs[myidx].
ned;
1533 if (mynbrs[myidx].ned == 0)
1534 mynbrs[myidx] = mynbrs[--myrinfo->
nnbrs];
1536 mynbrs[myidx].
pid = from;
1551 modind[nmod++] = ii;
1554 myrinfo =
graph->vkrinfo+ii;
1555 if (myrinfo->
inbr == -1)
1562 else if (me == to) {
1568 for (k=0; k<myrinfo->
nnbrs; k++) {
1569 if (mynbrs[k].pid == from) {
1570 if (mynbrs[k].ned == 1) {
1571 mynbrs[k] = mynbrs[--myrinfo->
nnbrs];
1575 for (jj=
xadj[ii]; jj<
xadj[ii+1]; jj++) {
1578 orinfo =
graph->vkrinfo+u;
1581 for (kk=0; kk<orinfo->
nnbrs; kk++) {
1582 if (onbrs[kk].pid == from) {
1597 if (mynbrs[k].ned == 1) {
1599 for (jj=
xadj[ii]; jj<
xadj[ii+1]; jj++) {
1603 if (
other == from) {
1604 orinfo =
graph->vkrinfo+u;
1612 for (kk=0; kk<orinfo->
nnbrs; kk++)
1613 onbrs[kk].gv +=
vsize[ii];
1632 for (k=0; k<myrinfo->
nnbrs; k++) {
1633 if (mynbrs[k].pid == to) {
1637 if (mynbrs[k].ned == 2) {
1639 for (jj=
xadj[ii]; jj<
xadj[ii+1]; jj++) {
1643 if (u !=
v &&
other == to) {
1644 orinfo =
graph->vkrinfo+u;
1646 for (kk=0; kk<orinfo->
nnbrs; kk++)
1647 onbrs[kk].gv -=
vsize[ii];
1661 if (k == myrinfo->
nnbrs) {
1667 for (jj=
xadj[ii]; jj<
xadj[ii+1]; jj++) {
1670 orinfo =
graph->vkrinfo+u;
1673 for (kk=0; kk<orinfo->
nnbrs; kk++) {
1674 if (onbrs[kk].pid == to) {
1694 myrinfo =
graph->vkrinfo+
v;
1696 for (k=0; k<myrinfo->
nnbrs; k++)
1697 pmarker[mynbrs[k].pid] = k;
1703 orinfo =
graph->vkrinfo+ii;
1707 for (k=0; k<orinfo->
nnbrs; k++) {
1708 if (pmarker[onbrs[k].pid] == -1)
1715 if (mynbrs[pmarker[
other]].ned > 1) {
1716 for (k=0; k<orinfo->
nnbrs; k++) {
1717 if (pmarker[onbrs[k].pid] == -1)
1722 for (k=0; k<orinfo->
nnbrs; k++) {
1723 if (pmarker[onbrs[k].pid] != -1)
1729 for (k=0; k<myrinfo->
nnbrs; k++)
1730 pmarker[mynbrs[k].pid] = -1;
1738 for (iii=0; iii<nmod; iii++) {
1742 myrinfo =
graph->vkrinfo+
i;
1745 if (vmarker[
i] == 1) {
1746 for (k=0; k<myrinfo->
nnbrs; k++)
1752 orinfo =
graph->vkrinfo+ii;
1755 for (kk=0; kk<orinfo->
nnbrs; kk++)
1756 pmarker[onbrs[kk].pid] = kk;
1761 for (k=0; k<myrinfo->
nnbrs; k++) {
1762 if (pmarker[mynbrs[k].pid] == -1)
1767 ASSERT(pmarker[me] != -1);
1770 if (onbrs[pmarker[me]].ned == 1) {
1772 for (k=0; k<myrinfo->
nnbrs; k++) {
1773 if (pmarker[mynbrs[k].pid] != -1)
1779 for (k=0; k<myrinfo->
nnbrs; k++) {
1780 if (pmarker[mynbrs[k].pid] == -1)
1786 for (kk=0; kk<orinfo->
nnbrs; kk++)
1787 pmarker[onbrs[kk].pid] = -1;
1788 pmarker[
other] = -1;
1795 for (k=0; k<myrinfo->
nnbrs; k++) {
1796 if (mynbrs[k].gv > myrinfo->
gv)
1797 myrinfo->
gv = mynbrs[k].
gv;
1801 if (myrinfo->
ned > 0 && myrinfo->
nid == 0)
1809 if (myrinfo->
gv >= 0 &&
graph->bndptr[
i] == -1)
1812 if (myrinfo->
gv < 0 &&
graph->bndptr[
i] != -1)
1816 if (myrinfo->
ned > 0 &&
graph->bndptr[
i] == -1)
1819 if (myrinfo->
ned == 0 &&
graph->bndptr[
i] != -1)
1827 if (queue !=
NULL) {
1829 if (
graph->bndptr[
i] != -1) {