24 int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees;
25 int from, me, to, oldcut, vwgt, gain;
27 idxtype *xadj, *adjncy, *adjwgt;
28 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
29 idxtype *phtable, *pmat, *pmatptr, *ndoms;
54 tvwgt =
idxsum(nparts, pwgts);
57 for (i=0; i<nparts; i++) {
58 itpwgts[i] = tpwgts[i]*tvwgt;
59 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
60 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
66 printf(
"Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
67 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
71 for (pass=0; pass<npasses; pass++) {
74 maxndoms = ndoms[
idxamax(nparts, ndoms)];
80 for (nmoves=iii=0; iii<graph->
nbnd; iii++) {
86 myrinfo = graph->
rinfo+i;
88 if (myrinfo->
ed >= myrinfo->
id) {
90 vwgt = graph->
vwgt[i];
92 if (myrinfo->
id > 0 && pwgts[from]-vwgt < minwgt[from])
99 for (j=0; j<myndegrees; j++) {
100 to = myedegrees[j].
pid;
102 pmatptr = pmat + to*nparts;
103 for (nadd=0, k=0; k<myndegrees; k++) {
107 l = myedegrees[k].
pid;
108 if (pmatptr[l] == 0) {
109 if (ndoms[l] > maxndoms-1) {
117 if (ndoms[to]+nadd > maxndoms)
125 for (k=0; k<myndegrees; k++) {
126 to = myedegrees[k].
pid;
129 gain = myedegrees[k].
ed-j;
130 if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0)
136 for (j=k+1; j<myndegrees; j++) {
137 to = myedegrees[j].
pid;
140 if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
141 (myedegrees[j].ed == myedegrees[k].ed &&
142 itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
146 to = myedegrees[k].
pid;
149 if (myedegrees[k].ed-myrinfo->
id > 0)
151 else if (myedegrees[k].ed-myrinfo->
id == 0) {
152 if ( phtable[myedegrees[k].pid] == 2 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
161 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
166 pmat[from*nparts+to] += (myrinfo->
id-myedegrees[k].
ed);
167 pmat[to*nparts+from] += (myrinfo->
id-myedegrees[k].
ed);
168 if (pmat[from*nparts+to] == 0) {
170 if (ndoms[from]+1 == maxndoms)
171 maxndoms = ndoms[
idxamax(nparts, ndoms)];
173 if (pmat[to*nparts+from] == 0) {
175 if (ndoms[to]+1 == maxndoms)
176 maxndoms = ndoms[
idxamax(nparts, ndoms)];
181 INC_DEC(pwgts[to], pwgts[from], vwgt);
182 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
183 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
184 if (myedegrees[k].ed == 0)
185 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
187 myedegrees[k].
pid = from;
189 if (myrinfo->
ed-myrinfo->
id < 0)
193 for (j=xadj[i]; j<xadj[i+1]; j++) {
197 myrinfo = graph->
rinfo+ii;
209 if (myrinfo->
ed-myrinfo->
id >= 0 && bndptr[ii] == -1)
215 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[ii] != -1)
221 for (k=0; k<myrinfo->
ndegrees; k++) {
222 if (myedegrees[k].pid == from) {
223 if (myedegrees[k].ed == adjwgt[j])
224 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
226 myedegrees[k].
ed -= adjwgt[j];
234 for (k=0; k<myrinfo->
ndegrees; k++) {
235 if (myedegrees[k].pid == to) {
236 myedegrees[k].
ed += adjwgt[j];
242 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
247 if (me != from && me != to) {
248 pmat[me*nparts+from] -= adjwgt[j];
249 pmat[from*nparts+me] -= adjwgt[j];
250 if (pmat[me*nparts+from] == 0) {
252 if (ndoms[me]+1 == maxndoms)
253 maxndoms = ndoms[
idxamax(nparts, ndoms)];
255 if (pmat[from*nparts+me] == 0) {
257 if (ndoms[from]+1 == maxndoms)
258 maxndoms = ndoms[
idxamax(nparts, ndoms)];
261 if (pmat[me*nparts+to] == 0) {
263 if (ndoms[me] > maxndoms) {
264 printf(
"You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
265 maxndoms = ndoms[me];
268 if (pmat[to*nparts+me] == 0) {
270 if (ndoms[to] > maxndoms) {
271 printf(
"You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
272 maxndoms = ndoms[to];
275 pmat[me*nparts+to] += adjwgt[j];
276 pmat[to*nparts+me] += adjwgt[j];
290 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %5d, Vol: %5d, %d\n",
292 1.0*nparts*pwgts[
idxamax(nparts, pwgts)]/tvwgt, graph->
nbnd, nmoves,
295 if (graph->
mincut == oldcut)
314 int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves;
315 int from, me, to, oldcut, vwgt, maxndoms, nadd;
316 idxtype *xadj, *adjncy, *adjwgt;
317 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
318 idxtype *phtable, *pmat, *pmatptr, *ndoms;
323 nvtxs = graph->
nvtxs;
331 where = graph->
where;
332 pwgts = graph->
pwgts;
345 tvwgt =
idxsum(nparts, pwgts);
348 for (i=0; i<nparts; i++) {
349 itpwgts[i] = tpwgts[i]*tvwgt;
350 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
351 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
360 printf(
"Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
361 pwgts[
idxamin(nparts, pwgts)], pwgts[
idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
365 for (pass=0; pass<npasses; pass++) {
369 for (i=0; i<nparts; i++) {
370 if (pwgts[i] > maxwgt[i])
383 for (ii=0; ii<nbnd; ii++) {
384 i = bndind[perm[ii]];
389 maxndoms = ndoms[
idxamax(nparts, ndoms)];
396 myrinfo = graph->
rinfo+i;
398 vwgt = graph->
vwgt[i];
400 if (pwgts[from]-vwgt < minwgt[from])
407 for (j=0; j<myndegrees; j++) {
408 to = myedegrees[j].
pid;
410 pmatptr = pmat + to*nparts;
411 for (nadd=0, k=0; k<myndegrees; k++) {
415 l = myedegrees[k].
pid;
416 if (pmatptr[l] == 0) {
417 if (ndoms[l] > maxndoms-1) {
425 if (ndoms[to]+nadd > maxndoms)
429 for (k=0; k<myndegrees; k++) {
430 to = myedegrees[k].
pid;
433 if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
439 for (j=k+1; j<myndegrees; j++) {
440 to = myedegrees[j].
pid;
443 if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])
447 to = myedegrees[k].
pid;
449 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->
id < 0)
455 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
460 pmat[from*nparts+to] += (myrinfo->
id-myedegrees[k].
ed);
461 pmat[to*nparts+from] += (myrinfo->
id-myedegrees[k].
ed);
462 if (pmat[from*nparts+to] == 0) {
464 if (ndoms[from]+1 == maxndoms)
465 maxndoms = ndoms[
idxamax(nparts, ndoms)];
467 if (pmat[to*nparts+from] == 0) {
469 if (ndoms[to]+1 == maxndoms)
470 maxndoms = ndoms[
idxamax(nparts, ndoms)];
476 INC_DEC(pwgts[to], pwgts[from], vwgt);
477 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
478 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
479 if (myedegrees[k].ed == 0)
480 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
482 myedegrees[k].
pid = from;
484 if (myrinfo->
ed == 0)
488 for (j=xadj[i]; j<xadj[i+1]; j++) {
492 myrinfo = graph->
rinfo+ii;
501 oldgain = (myrinfo->
ed-myrinfo->
id);
506 if (myrinfo->
ed > 0 && bndptr[ii] == -1)
512 if (myrinfo->
ed == 0 && bndptr[ii] != -1)
518 for (k=0; k<myrinfo->
ndegrees; k++) {
519 if (myedegrees[k].pid == from) {
520 if (myedegrees[k].ed == adjwgt[j])
521 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
523 myedegrees[k].
ed -= adjwgt[j];
531 for (k=0; k<myrinfo->
ndegrees; k++) {
532 if (myedegrees[k].pid == to) {
533 myedegrees[k].
ed += adjwgt[j];
539 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
544 if (me != from && me != to) {
545 pmat[me*nparts+from] -= adjwgt[j];
546 pmat[from*nparts+me] -= adjwgt[j];
547 if (pmat[me*nparts+from] == 0) {
549 if (ndoms[me]+1 == maxndoms)
550 maxndoms = ndoms[
idxamax(nparts, ndoms)];
552 if (pmat[from*nparts+me] == 0) {
554 if (ndoms[from]+1 == maxndoms)
555 maxndoms = ndoms[
idxamax(nparts, ndoms)];
558 if (pmat[me*nparts+to] == 0) {
560 if (ndoms[me] > maxndoms) {
561 printf(
"You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
562 maxndoms = ndoms[me];
565 if (pmat[to*nparts+me] == 0) {
567 if (ndoms[to] > maxndoms) {
568 printf(
"You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
569 maxndoms = ndoms[to];
572 pmat[me*nparts+to] += adjwgt[j];
573 pmat[to*nparts+me] += adjwgt[j];
577 if (me == to || me == from) {
578 gain = myrinfo->
ed-myrinfo->
id;
579 if (moved[ii] == 2) {
587 else if (moved[ii] == -1 && myrinfo->
ed > 0) {
602 printf(
"\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, %d\n",
627 int i, j, k, me, nvtxs, total,
max;
628 idxtype *xadj, *adjncy, *adjwgt, *pmat;
630 nvtxs = graph->
nvtxs;
635 pmat =
idxsmalloc(nparts*nparts, 0,
"ComputeSubDomainGraph: pmat");
637 for (i=0; i<nvtxs; i++) {
639 for (j=xadj[i]; j<xadj[i+1]; j++) {
642 pmat[me*nparts+where[k]] += adjwgt[j];
648 for (i=0; i<nparts; i++) {
649 for (k=0, j=0; j<nparts; j++) {
650 if (pmat[i*nparts+j] > 0)
666 printf(
"Total adjacent subdomains: %d, Max: %d\n", total, max);
678 int i, j, k, me, nvtxs, ndegrees;
679 idxtype *xadj, *adjncy, *adjwgt, *where;
683 nvtxs = graph->
nvtxs;
687 where = graph->
where;
688 rinfo = graph->
rinfo;
690 idxset(nparts*nparts, 0, pmat);
692 for (i=0; i<nvtxs; i++) {
693 if (rinfo[i].ed > 0) {
699 for (j=0; j<ndegrees; j++)
700 pmat[k+edegrees[j].pid] += edegrees[j].ed;
704 for (i=0; i<nparts; i++) {
706 for (j=0; j<nparts; j++) {
707 if (pmat[i*nparts+j] > 0)
723 int i, ii, j, k, me, other, nvtxs, total,
max, avg, totalout, nind, ncand, ncand2, target, target2, nadd;
724 int min, move, cpwgt, tvwgt;
725 idxtype *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt, *pmat, *ndoms, *mypmat, *otherpmat, *ind;
728 nvtxs = graph->
nvtxs;
734 where = graph->
where;
735 pwgts = graph->
pwgts;
751 tvwgt =
idxsum(nparts, pwgts);
752 for (i=0; i<nparts; i++)
753 maxpwgt[i] = 1.25*tpwgts[i]*tvwgt;
758 total =
idxsum(nparts, ndoms);
760 max = ndoms[
idxamax(nparts, ndoms)];
768 mypmat = pmat + me*nparts;
769 totalout =
idxsum(nparts, mypmat);
774 for (ncand2=0, i=0; i<nparts; i++) {
776 cand2[ncand2].
key = mypmat[i];
777 cand2[ncand2++].
val = i;
783 for (min=0; min<ncand2; min++) {
784 if (cand2[min].key > totalout/(2*ndoms[me]))
791 idxset(nparts, 0, otherpmat);
794 for (nind=0, i=0; i<nvtxs; i++) {
795 if (where[i] == other) {
796 for (j=xadj[i]; j<xadj[i+1]; j++) {
797 if (where[adjncy[j]] == me) {
806 for (cpwgt=0, ii=0; ii<nind; ii++) {
810 for (j=xadj[i]; j<xadj[i+1]; j++)
811 otherpmat[where[adjncy[j]]] += adjwgt[j];
813 otherpmat[other] = 0;
815 for (ncand=0, i=0; i<nparts; i++) {
816 if (otherpmat[i] > 0) {
817 cand[ncand].
key = -otherpmat[i];
818 cand[ncand++].
val = i;
828 target = target2 = -1;
829 for (i=0; i<ncand; i++) {
833 if (pwgts[k] + cpwgt > maxpwgt[k])
836 for (j=0; j<nparts; j++) {
837 if (otherpmat[j] > 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0)
841 for (nadd=0, j=0; j<nparts; j++) {
842 if (otherpmat[j] > 0 && pmat[nparts*k+j] == 0)
847 if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) {
857 if (target == -1 && target2 != -1)
868 INC_DEC(pwgts[target], pwgts[other], cpwgt);
870 MoveGroupMConn(ctrl, graph, ndoms, pmat, nparts, target, nind, ind);
893 int nparts,
int to,
int nind,
idxtype *ind)
895 int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees;
897 idxtype *xadj, *adjncy, *adjwgt;
898 idxtype *where, *bndptr, *bndind;
902 nvtxs = graph->
nvtxs;
907 where = graph->
where;
913 for (iii=0; iii<nind; iii++) {
917 myrinfo = graph->
rinfo+i;
926 for (k=0; k<myrinfo->
ndegrees; k++) {
927 if (myedegrees[k].pid == to)
931 myedegrees[k].
pid = to;
932 myedegrees[k].
ed = 0;
936 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
939 pmat[from*nparts+to] += (myrinfo->
id-myedegrees[k].
ed);
940 pmat[to*nparts+from] += (myrinfo->
id-myedegrees[k].
ed);
941 if (pmat[from*nparts+to] == 0)
943 if (pmat[to*nparts+from] == 0)
948 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
949 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
950 if (myedegrees[k].ed == 0)
951 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
953 myedegrees[k].
pid = from;
955 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[i] != -1)
959 for (j=xadj[i]; j<xadj[i+1]; j++) {
963 myrinfo = graph->
rinfo+ii;
975 if (myrinfo->
ed-myrinfo->
id >= 0 && bndptr[ii] == -1)
981 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[ii] != -1)
987 for (k=0; k<myrinfo->
ndegrees; k++) {
988 if (myedegrees[k].pid == from) {
989 if (myedegrees[k].ed == adjwgt[j])
990 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
992 myedegrees[k].
ed -= adjwgt[j];
1000 for (k=0; k<myrinfo->
ndegrees; k++) {
1001 if (myedegrees[k].pid == to) {
1002 myedegrees[k].
ed += adjwgt[j];
1008 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
1013 if (me != from && me != to) {
1014 pmat[me*nparts+from] -= adjwgt[j];
1015 pmat[from*nparts+me] -= adjwgt[j];
1016 if (pmat[me*nparts+from] == 0)
1018 if (pmat[from*nparts+me] == 0)
1021 if (pmat[me*nparts+to] == 0)
1023 if (pmat[to*nparts+me] == 0)
1026 pmat[me*nparts+to] += adjwgt[j];
1027 pmat[to*nparts+me] += adjwgt[j];
1050 int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, other, target, deltawgt;
1051 idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt;
1052 idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps;
1054 nvtxs = graph->
nvtxs;
1060 where = graph->
where;
1061 pwgts = graph->
pwgts;
1072 for (i=0; i<nvtxs; i++)
1073 perm[i] = todo[i] = i;
1080 if (first == last) {
1081 cptr[++ncmps] = first;
1082 ASSERT(touched[todo[0]] == 0);
1092 j = todo[k] = todo[--nleft];
1095 for (j=xadj[i]; j<xadj[i+1]; j++) {
1097 if (where[k] == me && !touched[k]) {
1103 cptr[++ncmps] = first;
1107 if (ncmps > nparts) {
1109 tvwgt =
idxsum(nparts, pwgts);
1110 for (i=0; i<nparts; i++)
1111 maxpwgt[i] = ubfactor*tpwgts[i]*tvwgt;
1115 for (i=0; i<ncmps; i++) {
1116 me = where[cind[cptr[i]]];
1117 if (npcmps[me] == 1)
1123 for (cwgt=0, j=cptr[i]; j<cptr[i+1]; j++)
1124 cwgt += vwgt[cind[j]];
1126 if (cwgt > .30*pwgts[me])
1130 idxset(nparts, 0, cpvec);
1131 for (j=cptr[i]; j<cptr[i+1]; j++) {
1133 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++)
1134 cpvec[where[adjncy[jj]]] += adjwgt[jj];
1139 for (j=0; j<nparts; j++) {
1140 if (cpvec[j] > 0 && (cwgt < deltawgt || pwgts[j] + cwgt < maxpwgt[j])) {
1141 if (target == -1 || cpvec[target] < cpvec[j])
1150 INC_DEC(pwgts[target], pwgts[me], cwgt);
1153 MoveGroup(ctrl, graph, nparts, target, i, cptr, cind);
1176 int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees;
1178 idxtype *xadj, *adjncy, *adjwgt;
1179 idxtype *where, *bndptr, *bndind;
1183 nvtxs = graph->
nvtxs;
1188 where = graph->
where;
1194 for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
1198 myrinfo = graph->
rinfo+i;
1207 for (k=0; k<myrinfo->
ndegrees; k++) {
1208 if (myedegrees[k].pid == to)
1212 myedegrees[k].
pid = to;
1213 myedegrees[k].
ed = 0;
1217 graph->
mincut -= myedegrees[k].
ed-myrinfo->
id;
1222 myrinfo->
ed += myrinfo->
id-myedegrees[k].
ed;
1223 SWAP(myrinfo->
id, myedegrees[k].
ed, j);
1224 if (myedegrees[k].ed == 0)
1225 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
1227 myedegrees[k].
pid = from;
1229 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[i] != -1)
1233 for (j=xadj[i]; j<xadj[i+1]; j++) {
1237 myrinfo = graph->
rinfo+ii;
1249 if (myrinfo->
ed-myrinfo->
id >= 0 && bndptr[ii] == -1)
1252 else if (me == to) {
1255 if (myrinfo->
ed-myrinfo->
id < 0 && bndptr[ii] != -1)
1261 for (k=0; k<myrinfo->
ndegrees; k++) {
1262 if (myedegrees[k].pid == from) {
1263 if (myedegrees[k].ed == adjwgt[j])
1264 myedegrees[k] = myedegrees[--myrinfo->
ndegrees];
1266 myedegrees[k].
ed -= adjwgt[j];
1274 for (k=0; k<myrinfo->
ndegrees; k++) {
1275 if (myedegrees[k].pid == to) {
1276 myedegrees[k].
ed += adjwgt[j];
1282 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
#define Random_KWayEdgeRefineMConn
#define EliminateComponents
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define IFSET(a, flag, cmd)
#define EliminateSubDomainEdges
#define PrintSubDomainGraph
void GKfree(void **ptr1,...)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define ComputeSubDomainGraph
#define INC_DEC(a, b, val)
#define Greedy_KWayEdgeBalanceMConn