20 float ubfactor,
int npasses,
int ffactor)
22 int i, ii, iii, j, jj, k, kk, l,
u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain;
23 int from, me, to, oldcut, oldvol, vwgt;
24 idxtype *xadj, *adjncy, *adjwgt;
25 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
44 tvwgt =
idxsum(nparts, pwgts);
47 updind =
idxmalloc(nvtxs,
"Random_KWayVolRefine: updind");
48 marker =
idxsmalloc(nvtxs, 0,
"Random_KWayVolRefine: marker");
49 phtable =
idxsmalloc(nparts, -1,
"Random_KWayVolRefine: phtable");
51 for (i=0; i<nparts; i++) {
52 itpwgts[i] = tpwgts[i]*tvwgt;
53 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
54 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
60 printf(
"VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d\n",
61 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
65 for (pass=0; pass<npasses; pass++) {
72 for (nmoves=iii=0; iii<graph->
nbnd; iii++) {
74 if (ii >= graph->
nbnd)
79 if (myrinfo->
gv >= 0) {
81 vwgt = graph->
vwgt[i];
83 if (myrinfo->
id > 0 && pwgts[from]-vwgt < minwgt[from])
86 xgain = (myrinfo->
id == 0 && myrinfo->
ed > 0 ? graph->
vsize[i] : 0);
91 for (k=0; k<myndegrees; k++) {
92 to = myedegrees[k].
pid;
93 if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*myedegrees[k].gv && xgain+myedegrees[k].gv >= 0)
99 for (j=k+1; j<myndegrees; j++) {
100 to = myedegrees[j].
pid;
101 if (pwgts[to]+vwgt > maxwgt[to])
103 if (myedegrees[j].gv > myedegrees[k].gv ||
104 (myedegrees[j].gv == myedegrees[k].gv && myedegrees[j].ed > myedegrees[k].ed) ||
105 (myedegrees[j].
gv == myedegrees[k].
gv && myedegrees[j].
ed == myedegrees[k].
ed &&
106 itpwgts[myedegrees[k].
pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].
pid]))
110 to = myedegrees[k].
pid;
113 if (xgain+myedegrees[k].gv > 0 || myedegrees[k].ed-myrinfo->
id > 0)
115 else if (myedegrees[k].ed-myrinfo->
id == 0) {
116 if ((iii&5) == 0 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
125 INC_DEC(pwgts[to], pwgts[from], vwgt);
126 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
127 graph->
minvol -= (xgain+myedegrees[k].
gv);
130 IFSET(ctrl->
dbglvl,
DBG_MOVEINFO, printf(
"\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n",
131 i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->
id, graph->
mincut, graph->
minvol));
133 KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
142 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
144 1.0*nparts*pwgts[
idxamax(nparts, pwgts)]/tvwgt, graph->
nbnd, nmoves, graph->
mincut,
164 float ubfactor,
int npasses,
int ffactor)
166 int i, ii, iii, j, jj, k, kk, l,
u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain;
167 int from, me, to, oldcut, oldvol, vwgt, nadd, maxndoms;
168 idxtype *xadj, *adjncy, *adjwgt;
169 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
170 idxtype *pmat, *pmatptr, *ndoms;
174 nvtxs = graph->
nvtxs;
182 where = graph->
where;
183 pwgts = graph->
pwgts;
189 tvwgt =
idxsum(nparts, pwgts);
192 updind =
idxmalloc(nvtxs,
"Random_KWayVolRefine: updind");
193 marker =
idxsmalloc(nvtxs, 0,
"Random_KWayVolRefine: marker");
194 phtable =
idxsmalloc(nparts, -1,
"Random_KWayVolRefine: phtable");
201 for (i=0; i<nparts; i++) {
202 itpwgts[i] = tpwgts[i]*tvwgt;
203 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
204 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
210 printf(
"VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d\n",
211 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
215 for (pass=0; pass<npasses; pass++) {
218 maxndoms = ndoms[
idxamax(nparts, ndoms)];
224 for (nmoves=iii=0; iii<graph->
nbnd; iii++) {
226 if (ii >= graph->
nbnd)
229 myrinfo = graph->
vrinfo+i;
231 if (myrinfo->
gv >= 0) {
233 vwgt = graph->
vwgt[i];
235 if (myrinfo->
id > 0 && pwgts[from]-vwgt < minwgt[from])
238 xgain = (myrinfo->
id == 0 && myrinfo->
ed > 0 ? graph->
vsize[i] : 0);
244 for (j=0; j<myndegrees; j++) {
245 to = myedegrees[j].
pid;
247 pmatptr = pmat + to*nparts;
248 for (nadd=0, k=0; k<myndegrees; k++) {
252 l = myedegrees[k].
pid;
253 if (pmatptr[l] == 0) {
254 if (ndoms[l] > maxndoms-1) {
262 if (ndoms[to]+nadd > maxndoms)
268 for (k=0; k<myndegrees; k++) {
269 to = myedegrees[k].
pid;
272 if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*myedegrees[k].gv && xgain+myedegrees[k].gv >= 0)
278 for (j=k+1; j<myndegrees; j++) {
279 to = myedegrees[j].
pid;
280 if (!phtable[to] || pwgts[to]+vwgt > maxwgt[to])
282 if (myedegrees[j].gv > myedegrees[k].gv ||
283 (myedegrees[j].gv == myedegrees[k].gv && myedegrees[j].ed > myedegrees[k].ed) ||
284 (myedegrees[j].
gv == myedegrees[k].
gv && myedegrees[j].
ed == myedegrees[k].
ed &&
285 itpwgts[myedegrees[k].
pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].
pid]))
289 to = myedegrees[k].
pid;
292 if (xgain+myedegrees[k].gv > 0 || myedegrees[k].ed-myrinfo->
id > 0)
294 else if (myedegrees[k].ed-myrinfo->
id == 0) {
295 if ((iii&5) == 0 || phtable[myedegrees[k].
pid] == 2 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
302 for (j=0; j<myndegrees; j++)
303 phtable[myedegrees[j].pid] = -1;
309 INC_DEC(pwgts[to], pwgts[from], vwgt);
310 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
311 graph->
minvol -= (xgain+myedegrees[k].
gv);
314 IFSET(ctrl->
dbglvl,
DBG_MOVEINFO, printf(
"\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n",
315 i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->
id, graph->
mincut, graph->
minvol));
318 pmat[from*nparts+to] += (myrinfo->
id-myedegrees[k].
ed);
319 pmat[to*nparts+from] += (myrinfo->
id-myedegrees[k].
ed);
320 if (pmat[from*nparts+to] == 0) {
322 if (ndoms[from]+1 == maxndoms)
323 maxndoms = ndoms[
idxamax(nparts, ndoms)];
325 if (pmat[to*nparts+from] == 0) {
327 if (ndoms[to]+1 == maxndoms)
328 maxndoms = ndoms[
idxamax(nparts, ndoms)];
331 for (j=xadj[i]; j<xadj[i+1]; j++) {
336 if (me != from && me != to) {
337 pmat[me*nparts+from] -= adjwgt[j];
338 pmat[from*nparts+me] -= adjwgt[j];
339 if (pmat[me*nparts+from] == 0) {
341 if (ndoms[me]+1 == maxndoms)
342 maxndoms = ndoms[
idxamax(nparts, ndoms)];
344 if (pmat[from*nparts+me] == 0) {
346 if (ndoms[from]+1 == maxndoms)
347 maxndoms = ndoms[
idxamax(nparts, ndoms)];
350 if (pmat[me*nparts+to] == 0) {
352 if (ndoms[me] > maxndoms) {
353 printf(
"You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
354 maxndoms = ndoms[me];
357 if (pmat[to*nparts+me] == 0) {
359 if (ndoms[to] > maxndoms) {
360 printf(
"You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
361 maxndoms = ndoms[to];
364 pmat[me*nparts+to] += adjwgt[j];
365 pmat[to*nparts+me] += adjwgt[j];
369 KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
378 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
380 1.0*nparts*pwgts[
idxamax(nparts, pwgts)]/tvwgt, graph->
nbnd, nmoves, graph->
mincut,
403 float ubfactor,
int npasses)
405 int i, ii, iii, j, jj, k, kk, l,
u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain;
406 int from, me, to, vwgt, gain;
407 idxtype *xadj, *adjncy, *adjwgt;
408 idxtype *where, *pwgts, *perm, *moved, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
413 nvtxs = graph->
nvtxs;
421 where = graph->
where;
422 pwgts = graph->
pwgts;
428 tvwgt =
idxsum(nparts, pwgts);
431 updind =
idxmalloc(nvtxs,
"Random_KWayVolRefine: updind");
432 marker =
idxsmalloc(nvtxs, 0,
"Random_KWayVolRefine: marker");
433 phtable =
idxsmalloc(nparts, -1,
"Random_KWayVolRefine: phtable");
435 for (i=0; i<nparts; i++) {
436 itpwgts[i] = tpwgts[i]*tvwgt;
437 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
438 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
447 printf(
"VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d [B]\n",
448 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
453 for (pass=0; pass<npasses; pass++) {
456 for (i=0; i<nparts; i++) {
457 if (pwgts[i] > maxwgt[i])
467 for (ii=0; ii<graph->
nbnd; ii++) {
468 i = bndind[perm[ii]];
478 myrinfo = graph->
vrinfo+i;
480 vwgt = graph->
vwgt[i];
482 if (pwgts[from]-vwgt < minwgt[from])
485 xgain = (myrinfo->
id == 0 && myrinfo->
ed > 0 ? graph->
vsize[i] : 0);
490 for (k=0; k<myndegrees; k++) {
491 to = myedegrees[k].
pid;
492 if (pwgts[to]+vwgt <= maxwgt[to] ||
493 itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
499 for (j=k+1; j<myndegrees; j++) {
500 to = myedegrees[j].
pid;
501 if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])
505 to = myedegrees[k].
pid;
507 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] &&
508 (xgain+myedegrees[k].gv < 0 ||
509 (xgain+myedegrees[k].gv == 0 && myedegrees[k].ed-myrinfo->
id < 0))
517 INC_DEC(pwgts[to], pwgts[from], vwgt);
518 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
519 graph->
minvol -= (xgain+myedegrees[k].
gv);
522 IFSET(ctrl->
dbglvl,
DBG_MOVEINFO, printf(
"\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n",
523 i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->
id, graph->
mincut, graph->
minvol));
525 KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
533 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
535 1.0*nparts*pwgts[
idxamax(nparts, pwgts)]/tvwgt, graph->
nbnd, nmoves, graph->
mincut,
557 float ubfactor,
int npasses)
559 int i, ii, iii, j, jj, k, kk, l,
u, pass, nvtxs, nmoves, tvwgt, myndegrees, xgain;
560 int from, me, to, vwgt, gain, maxndoms, nadd;
561 idxtype *xadj, *adjncy, *adjwgt;
562 idxtype *where, *pwgts, *perm, *moved, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts, *updind, *marker, *phtable;
563 idxtype *pmat, *pmatptr, *ndoms;
568 nvtxs = graph->
nvtxs;
576 where = graph->
where;
577 pwgts = graph->
pwgts;
583 tvwgt =
idxsum(nparts, pwgts);
586 updind =
idxmalloc(nvtxs,
"Random_KWayVolRefine: updind");
587 marker =
idxsmalloc(nvtxs, 0,
"Random_KWayVolRefine: marker");
588 phtable =
idxsmalloc(nparts, -1,
"Random_KWayVolRefine: phtable");
595 for (i=0; i<nparts; i++) {
596 itpwgts[i] = tpwgts[i]*tvwgt;
597 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
598 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
607 printf(
"VolPart: [%5d %5d]-[%5d %5d], Balance: %3.2f, Nv-Nb[%5d %5d]. Cut: %5d, Vol: %5d [B]\n",
608 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
613 for (pass=0; pass<npasses; pass++) {
616 for (i=0; i<nparts; i++) {
617 if (pwgts[i] > maxwgt[i])
627 for (ii=0; ii<graph->
nbnd; ii++) {
628 i = bndind[perm[ii]];
633 maxndoms = ndoms[
idxamax(nparts, ndoms)];
640 myrinfo = graph->
vrinfo+i;
642 vwgt = graph->
vwgt[i];
644 if (pwgts[from]-vwgt < minwgt[from])
647 xgain = (myrinfo->
id == 0 && myrinfo->
ed > 0 ? graph->
vsize[i] : 0);
653 for (j=0; j<myndegrees; j++) {
654 to = myedegrees[j].
pid;
656 pmatptr = pmat + to*nparts;
657 for (nadd=0, k=0; k<myndegrees; k++) {
661 l = myedegrees[k].
pid;
662 if (pmatptr[l] == 0) {
663 if (ndoms[l] > maxndoms-1) {
671 if (ndoms[to]+nadd > maxndoms)
675 for (k=0; k<myndegrees; k++) {
676 to = myedegrees[k].
pid;
679 if (pwgts[to]+vwgt <= maxwgt[to] ||
680 itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
686 for (j=k+1; j<myndegrees; j++) {
687 to = myedegrees[j].
pid;
690 if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])
694 to = myedegrees[k].
pid;
696 for (j=0; j<myndegrees; j++)
697 phtable[myedegrees[j].pid] = -1;
699 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] &&
700 (xgain+myedegrees[k].gv < 0 ||
701 (xgain+myedegrees[k].gv == 0 && myedegrees[k].ed-myrinfo->
id < 0))
709 INC_DEC(pwgts[to], pwgts[from], vwgt);
710 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
711 graph->
minvol -= (xgain+myedegrees[k].
gv);
714 IFSET(ctrl->
dbglvl,
DBG_MOVEINFO, printf(
"\t\tMoving %6d from %3d to %3d. Gain: [%4d %4d]. Cut: %6d, Vol: %6d\n",
715 i, from, to, xgain+myedegrees[k].gv, myedegrees[k].ed-myrinfo->
id, graph->
mincut, graph->
minvol));
718 pmat[from*nparts+to] += (myrinfo->
id-myedegrees[k].
ed);
719 pmat[to*nparts+from] += (myrinfo->
id-myedegrees[k].
ed);
720 if (pmat[from*nparts+to] == 0) {
722 if (ndoms[from]+1 == maxndoms)
723 maxndoms = ndoms[
idxamax(nparts, ndoms)];
725 if (pmat[to*nparts+from] == 0) {
727 if (ndoms[to]+1 == maxndoms)
728 maxndoms = ndoms[
idxamax(nparts, ndoms)];
731 for (j=xadj[i]; j<xadj[i+1]; j++) {
736 if (me != from && me != to) {
737 pmat[me*nparts+from] -= adjwgt[j];
738 pmat[from*nparts+me] -= adjwgt[j];
739 if (pmat[me*nparts+from] == 0) {
741 if (ndoms[me]+1 == maxndoms)
742 maxndoms = ndoms[
idxamax(nparts, ndoms)];
744 if (pmat[from*nparts+me] == 0) {
746 if (ndoms[from]+1 == maxndoms)
747 maxndoms = ndoms[
idxamax(nparts, ndoms)];
750 if (pmat[me*nparts+to] == 0) {
752 if (ndoms[me] > maxndoms) {
753 printf(
"You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
754 maxndoms = ndoms[me];
757 if (pmat[to*nparts+me] == 0) {
759 if (ndoms[to] > maxndoms) {
760 printf(
"You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
761 maxndoms = ndoms[to];
764 pmat[me*nparts+to] += adjwgt[j];
765 pmat[to*nparts+me] += adjwgt[j];
769 KWayVolUpdate(ctrl, graph, i, from, to, marker, phtable, updind);
777 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, Vol: %6d\n",
779 1.0*nparts*pwgts[
idxamax(nparts, pwgts)]/tvwgt, graph->
nbnd, nmoves, graph->
mincut,
808 int ii, iii, j, jj, k, kk, l,
u, nupd, other, me, myidx;
809 idxtype *xadj, *vsize, *adjncy, *adjwgt, *where;
816 vsize = graph->
vsize;
817 where = graph->
where;
827 phtable[myedegrees[k].pid] = k;
832 for (j=xadj[v]; j<xadj[v+1]; j++) {
835 orinfo = graph->
vrinfo+ii;
839 for (k=0; k<orinfo->
ndegrees; k++) {
840 if (phtable[oedegrees[k].pid] == -1)
841 oedegrees[k].
gv += vsize[
v];
845 ASSERT(phtable[other] != -1);
847 if (myedegrees[phtable[other]].ned > 1) {
848 for (k=0; k<orinfo->
ndegrees; k++) {
849 if (phtable[oedegrees[k].pid] == -1)
850 oedegrees[k].
gv += vsize[
v];
854 for (k=0; k<orinfo->
ndegrees; k++) {
855 if (phtable[oedegrees[k].pid] != -1)
856 oedegrees[k].
gv -= vsize[
v];
863 phtable[myedegrees[k].pid] = -1;
870 myrinfo->
ed += myrinfo->
id-myedegrees[myidx].
ed;
871 SWAP(myrinfo->
id, myedegrees[myidx].
ed, j);
873 if (myedegrees[myidx].ed == 0)
874 myedegrees[myidx] = myedegrees[--myrinfo->
ndegrees];
876 myedegrees[myidx].
pid = from;
884 for (j=xadj[v]; j<xadj[v+1]; j++) {
893 myrinfo = graph->
vrinfo+ii;
911 for (k=0; k<myrinfo->
ndegrees; k++) {
912 if (myedegrees[k].pid == from) {
913 if (myedegrees[k].ned == 1) {
914 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
918 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
924 for (kk=0; kk<orinfo->
ndegrees; kk++) {
925 if (oedegrees[kk].pid == from) {
926 oedegrees[kk].
gv -= vsize[ii];
933 myedegrees[k].
ed -= adjwgt[j];
937 if (myedegrees[k].ned == 1) {
939 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
946 for (kk=0; kk<orinfo->
ndegrees; kk++)
947 oedegrees[kk].gv += vsize[ii];
961 for (k=0; k<myrinfo->
ndegrees; k++) {
962 if (myedegrees[k].pid == to) {
963 myedegrees[k].
ed += adjwgt[j];
967 if (myedegrees[k].ned == 2) {
969 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
975 if (u != v && other == to) {
976 for (kk=0; kk<orinfo->
ndegrees; kk++)
977 oedegrees[kk].gv -= vsize[ii];
993 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
999 for (kk=0; kk<orinfo->
ndegrees; kk++) {
1000 if (oedegrees[kk].pid == to) {
1001 oedegrees[kk].
gv += vsize[ii];
1021 for (k=0; k<myrinfo->
ndegrees; k++)
1022 phtable[myedegrees[k].pid] = k;
1025 for (j=xadj[v]; j<xadj[v+1]; j++) {
1028 orinfo = graph->
vrinfo+ii;
1032 for (k=0; k<orinfo->
ndegrees; k++) {
1033 if (phtable[oedegrees[k].pid] == -1)
1034 oedegrees[k].
gv -= vsize[
v];
1038 ASSERT(phtable[other] != -1);
1040 if (myedegrees[phtable[other]].ned > 1) {
1041 for (k=0; k<orinfo->
ndegrees; k++) {
1042 if (phtable[oedegrees[k].pid] == -1)
1043 oedegrees[k].
gv -= vsize[
v];
1047 for (k=0; k<orinfo->
ndegrees; k++) {
1048 if (phtable[oedegrees[k].pid] != -1)
1049 oedegrees[k].
gv += vsize[
v];
1054 for (k=0; k<myrinfo->
ndegrees; k++)
1055 phtable[myedegrees[k].pid] = -1;
1069 for (j=0; j<nupd; j++) {
1072 myrinfo = graph->
vrinfo+k;
1074 if ((myrinfo->
gv >= 0 || myrinfo->
ed-myrinfo->
id >= 0) && graph->
bndptr[k] == -1)
1077 if (myrinfo->
gv < 0 && myrinfo->
ed-myrinfo->
id < 0 && graph->
bndptr[k] != -1)
1091 int ii, iii, i, j, k, kk, l, nvtxs, me, other, pid;
1092 idxtype *xadj, *vsize, *adjncy, *adjwgt, *where;
1096 nvtxs = graph->
nvtxs;
1098 vsize = graph->
vsize;
1101 where = graph->
where;
1108 for (iii=0; iii<nupd; iii++) {
1115 if (marker[i] == 1) {
1116 for (k=0; k<myrinfo->
ndegrees; k++)
1117 myedegrees[k].gv = 0;
1119 for (j=xadj[i]; j<xadj[i+1]; j++) {
1125 for (kk=0; kk<orinfo->
ndegrees; kk++)
1126 phtable[oedegrees[kk].pid] = kk;
1131 for (k=0; k<myrinfo->
ndegrees; k++) {
1132 if (phtable[myedegrees[k].pid] == -1)
1133 myedegrees[k].
gv -= vsize[ii];
1137 ASSERT(phtable[me] != -1);
1140 if (oedegrees[phtable[me]].ned == 1) {
1142 for (k=0; k<myrinfo->
ndegrees; k++) {
1143 if (phtable[myedegrees[k].pid] != -1)
1144 myedegrees[k].
gv += vsize[ii];
1149 for (k=0; k<myrinfo->
ndegrees; k++) {
1150 if (phtable[myedegrees[k].pid] == -1)
1151 myedegrees[k].
gv -= vsize[ii];
1156 for (kk=0; kk<orinfo->
ndegrees; kk++)
1157 phtable[oedegrees[kk].pid] = -1;
1158 phtable[other] = -1;
1164 for (k=0; k<myrinfo->
ndegrees; k++) {
1165 if (myedegrees[k].gv > myrinfo->
gv)
1166 myrinfo->
gv = myedegrees[k].
gv;
1168 if (myrinfo->
ed > 0 && myrinfo->
id == 0)
1169 myrinfo->
gv += vsize[i];
1182 int i, j, k, me, nvtxs, nparts, totalv;
1183 idxtype *xadj, *adjncy, *vsize, *marker;
1186 nvtxs = graph->
nvtxs;
1191 nparts = where[
idxamax(nvtxs, where)]+1;
1192 marker =
idxsmalloc(nparts, -1,
"ComputeVolume: marker");
1196 for (i=0; i<nvtxs; i++) {
1197 marker[where[i]] = i;
1198 for (j=xadj[i]; j<xadj[i+1]; j++) {
1199 k = where[adjncy[j]];
1200 if (marker[k] != i) {
1221 int i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
1222 idxtype *xadj, *vsize, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
1223 VRInfoType *rinfo, *myrinfo, *orinfo, tmprinfo;
1226 nvtxs = graph->
nvtxs;
1228 vsize = graph->
vsize;
1231 where = graph->
where;
1239 for (i=0; i<nvtxs; i++) {
1245 for (k=0; k<myrinfo->
ndegrees; k++)
1246 tmpdegrees[k] = myedegrees[k];
1249 tmprinfo.
id = myrinfo->
id;
1250 tmprinfo.
ed = myrinfo->
ed;
1252 myrinfo = &tmprinfo;
1253 myedegrees = tmpdegrees;
1256 for (k=0; k<myrinfo->
ndegrees; k++)
1257 myedegrees[k].gv = 0;
1259 for (j=xadj[i]; j<xadj[i+1]; j++) {
1267 for (k=0; k<myrinfo->
ndegrees; k++) {
1268 pid = myedegrees[k].
pid;
1269 for (kk=0; kk<orinfo->
ndegrees; kk++) {
1270 if (oedegrees[kk].pid == pid)
1274 myedegrees[k].
gv -= vsize[ii];
1279 for (k=0; k<orinfo->
ndegrees; k++) {
1280 if (oedegrees[k].pid == me)
1284 if (oedegrees[k].ned == 1) {
1285 for (k=0; k<myrinfo->
ndegrees; k++) {
1286 if (myedegrees[k].pid == other) {
1287 myedegrees[k].
gv += vsize[ii];
1293 for (k=0; k<myrinfo->
ndegrees; k++) {
1294 if ((pid = myedegrees[k].pid) == other)
1296 for (kk=0; kk<orinfo->
ndegrees; kk++) {
1297 if (oedegrees[kk].pid == pid) {
1298 myedegrees[k].
gv += vsize[ii];
1307 for (k=0; k<myrinfo->
ndegrees; k++) {
1308 if ((pid = myedegrees[k].pid) == other)
1310 for (kk=0; kk<orinfo->
ndegrees; kk++) {
1311 if (oedegrees[kk].pid == pid)
1315 myedegrees[k].
gv -= vsize[ii];
1324 for (k=0; k<myrinfo->
ndegrees; k++) {
1325 pid = myedegrees[k].
pid;
1326 for (kk=0; kk<tmprinfo.
ndegrees; kk++) {
1327 if (tmpdegrees[kk].pid == pid) {
1328 if (tmpdegrees[kk].gv != myedegrees[k].gv)
1329 printf(
"[%d %d %d %d]\n", i, pid, myedegrees[k].gv, tmpdegrees[kk].gv);
1347 int i, j, k, me, nvtxs, ndegrees;
1348 idxtype *xadj, *adjncy, *adjwgt, *where;
1352 nvtxs = graph->
nvtxs;
1356 where = graph->
where;
1359 idxset(nparts*nparts, 0, pmat);
1361 for (i=0; i<nvtxs; i++) {
1362 if (rinfo[i].ed > 0) {
1368 for (j=0; j<ndegrees; j++)
1369 pmat[k+edegrees[j].pid] += edegrees[j].ed;
1373 for (i=0; i<nparts; i++) {
1375 for (j=0; j<nparts; j++) {
1376 if (pmat[i*nparts+j] > 0)
1389 int i, ii, j, k, me, other, nvtxs, total,
max, avg, totalout, nind, ncand, ncand2, target, target2, nadd;
1390 int min, move, cpwgt, tvwgt;
1391 idxtype *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt, *pmat, *ndoms, *mypmat, *otherpmat, *ind;
1394 nvtxs = graph->
nvtxs;
1400 where = graph->
where;
1413 for (i=0; i<nvtxs; i++) {
1415 pwgts[me] += vwgt[i];
1416 for (j=xadj[i]; j<xadj[i+1]; j++) {
1419 pmat[me*nparts+where[k]] += adjwgt[j];
1424 tvwgt =
idxsum(nparts, pwgts);
1425 for (i=0; i<nparts; i++)
1426 maxpwgt[i] = 1.25*tpwgts[i]*tvwgt;
1429 for (i=0; i<nparts; i++) {
1430 for (k=0, j=0; j<nparts; j++) {
1431 if (pmat[i*nparts+j] > 0)
1439 total =
idxsum(nparts, ndoms);
1441 max = ndoms[
idxamax(nparts, ndoms)];
1449 mypmat = pmat + me*nparts;
1450 totalout =
idxsum(nparts, mypmat);
1455 for (ncand2=0, i=0; i<nparts; i++) {
1456 if (mypmat[i] > 0) {
1457 cand2[ncand2].
key = mypmat[i];
1458 cand2[ncand2++].
val = i;
1464 for (min=0; min<ncand2; min++) {
1465 if (cand2[min].key > totalout/(2*ndoms[me]))
1472 idxset(nparts, 0, otherpmat);
1475 for (nind=0, i=0; i<nvtxs; i++) {
1476 if (where[i] == other) {
1477 for (j=xadj[i]; j<xadj[i+1]; j++) {
1478 if (where[adjncy[j]] == me) {
1487 for (cpwgt=0, ii=0; ii<nind; ii++) {
1491 for (j=xadj[i]; j<xadj[i+1]; j++) {
1493 if (where[k] != other)
1494 otherpmat[where[k]] += adjwgt[j];
1498 for (ncand=0, i=0; i<nparts; i++) {
1499 if (otherpmat[i] > 0) {
1500 cand[ncand].
key = -otherpmat[i];
1501 cand[ncand++].
val = i;
1511 target = target2 = -1;
1512 for (i=0; i<ncand; i++) {
1515 if (mypmat[k] > 0) {
1516 if (pwgts[k] + cpwgt > maxpwgt[k])
1519 for (j=0; j<nparts; j++) {
1520 if (otherpmat[j] > 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0)
1524 for (nadd=0, j=0; j<nparts; j++) {
1525 if (otherpmat[j] > 0 && pmat[nparts*k+j] == 0)
1530 if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) {
1540 if (target == -1 && target2 != -1)
1551 INC_DEC(pwgts[target], pwgts[other], cpwgt);
1554 for (ii=0; ii<nind; ii++) {
1559 for (j=xadj[i]; j<xadj[i+1]; j++) {
1561 if (where[k] != other) {
1562 if (pmat[nparts*other + where[k]] == 0)
1563 printf(
"Something wrong\n");
1564 pmat[nparts*other + where[k]] -= adjwgt[j];
1565 if (pmat[nparts*other + where[k]] == 0)
1568 if (pmat[nparts*where[k] + other] == 0)
1569 printf(
"Something wrong\n");
1570 pmat[nparts*where[k] + other] -= adjwgt[j];
1571 if (pmat[nparts*where[k] + other] == 0)
1577 for (j=xadj[i]; j<xadj[i+1]; j++) {
1579 if (where[k] != target) {
1580 if (pmat[nparts*target + where[k]] == 0)
1582 pmat[nparts*target + where[k]] += adjwgt[j];
1584 if (pmat[nparts*where[k] + target] == 0)
1586 pmat[nparts*where[k] + target] += adjwgt[j];
1616 int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, ncand, other, target, deltawgt;
1617 idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt;
1618 idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps;
1622 nvtxs = graph->
nvtxs;
1628 where = graph->
where;
1640 for (i=0; i<nvtxs; i++)
1641 perm[i] = todo[i] = i;
1648 if (first == last) {
1649 cptr[++ncmps] = first;
1650 ASSERT(touched[todo[0]] == 0);
1660 j = todo[k] = todo[--nleft];
1663 for (j=xadj[i]; j<xadj[i+1]; j++) {
1665 if (where[k] == me && !touched[k]) {
1671 cptr[++ncmps] = first;
1675 if (ncmps > nparts) {
1679 for (i=0; i<nvtxs; i++)
1680 pwgts[where[i]] += vwgt[i];
1681 tvwgt =
idxsum(nparts, pwgts);
1682 for (i=0; i<nparts; i++)
1683 maxpwgt[i] = ubfactor*tpwgts[i]*tvwgt;
1685 deltawgt = tvwgt/(100*nparts);
1688 for (i=0; i<ncmps; i++) {
1689 me = where[cind[cptr[i]]];
1690 if (npcmps[me] == 1)
1696 idxset(nparts, 0, cpvec);
1697 for (cwgt=0, j=cptr[i]; j<cptr[i+1]; j++) {
1700 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
1701 other = where[adjncy[jj]];
1703 cpvec[other] += adjwgt[jj];
1709 if (cwgt > .30*pwgts[me])
1712 for (ncand=0, j=0; j<nparts; j++) {
1714 cand[ncand].
key = -cpvec[j];
1715 cand[ncand++].
val = j;
1724 for (j=0; j<ncand; j++) {
1726 if (cwgt < deltawgt || pwgts[k] + cwgt < maxpwgt[k]) {
1737 pwgts[target] += cwgt;
1740 for (j=cptr[i]; j<cptr[i+1]; j++)
1741 where[cind[j]] = target;
1743 graph->
mincut -= cpvec[target];
1755 marker =
idxset(nparts, -1, cpvec);
1756 for (ttlv=0, i=0; i<nvtxs; i++) {
1757 marker[where[i]] = i;
1758 for (j=xadj[i]; j<xadj[i+1]; j++) {
1759 if (marker[where[adjncy[j]]] != i) {
1760 ttlv += graph->
vsize[i];
1761 marker[where[adjncy[j]]] = i;
#define EliminateVolSubDomainEdges
#define CheckVolKWayPartitionParams
#define Random_KWayVolRefine
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define Greedy_KWayVolBalance
#define IFSET(a, flag, cmd)
void EliminateVolComponents(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
#define Random_KWayVolRefineMConn
void GKfree(void **ptr1,...)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define Greedy_KWayVolBalanceMConn
#define INC_DEC(a, b, val)
#define ComputeVolSubDomainGraph
#define ComputeKWayVolume