23 int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
24 idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
25 idxtype *moved, *swaps, *perm, *qnum;
28 int higain, oldgain, mincut, initcut, newcut, mincutorder;
49 limit =
amin(
amax(0.01*nvtxs, 15), 100);
52 for (i=0; i<ncon; i++) {
53 origdiff[i] = fabs(tpwgts[0]-npwgts[i]);
54 ubvec[i] =
amax(origbal[i], orgubvec[i]);
62 for (j=0; j<ncon; j++) {
63 maxwgt[i*ncon+j] = tpwgts[i]*ubvec[j];
64 minwgt[i*ncon+j] = tpwgts[i]*(1.0/ubvec[j]);
69 for (i=0; i<ncon; i++) {
73 for (i=0; i<nvtxs; i++)
74 qnum[i] =
samax(ncon, nvwgt+i*ncon);
79 for (l=0; l<ncon; l++)
80 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
81 printf(
"] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: ", tpwgts[0], tpwgts[1],
83 for (i=0; i<ncon; i++)
84 printf(
"%.3f ", origbal[i]);
89 for (pass=0; pass<npasses; pass++) {
90 for (i=0; i<ncon; i++) {
96 newcut = mincut = initcut = graph->
mincut;
105 for (ii=0; ii<nbnd; ii++) {
106 i = bndind[perm[ii]];
107 ASSERT(ed[i] > 0 ||
id[i] == 0);
109 PQueueInsert(&parts[qnum[i]][where[i]], i, ed[i]-
id[i]);
112 for (nswaps=0; nswaps<nvtxs; nswaps++) {
113 SelectQueue2(ncon, npwgts, tpwgts, &from, &cnum, parts, maxwgt);
116 if (from == -1 || (higain =
PQueueGetMax(&parts[cnum][from])) == -1)
118 ASSERT(bndptr[higain] != -1);
120 newcut -= (ed[higain]-
id[higain]);
121 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
122 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
125 if ((newcut < mincut &&
AreAllBelow(ncon, tvec, ubvec)) ||
128 for (i=0; i<ncon; i++)
130 mincutorder = nswaps;
132 else if (nswaps-mincutorder > limit) {
133 newcut += (ed[higain]-
id[higain]);
134 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
135 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
140 moved[higain] = nswaps;
141 swaps[nswaps] = higain;
144 printf(
"Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-
id[higain], newcut);
145 for (l=0; l<ncon; l++)
146 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
149 for (i=0; i<ncon; i++)
150 printf(
"%.3f ", tvec[i]);
151 if (mincutorder == nswaps)
161 SWAP(
id[higain], ed[higain], tmp);
162 if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
165 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
167 oldgain = ed[k]-
id[k];
169 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
173 if (bndptr[k] != -1) {
181 PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-
id[k]);
188 PQueueInsert(&parts[qnum[k]][where[k]], k, ed[k]-
id[k]);
199 for (i=0; i<nswaps; i++)
200 moved[swaps[i]] = -1;
201 for (nswaps--; nswaps>mincutorder; nswaps--) {
202 higain = swaps[nswaps];
204 to = where[higain] = (where[higain]+1)%2;
205 SWAP(
id[higain], ed[higain], tmp);
206 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
208 else if (ed[higain] > 0 && bndptr[higain] == -1)
211 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
212 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
213 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
216 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
219 if (bndptr[k] != -1 && ed[k] == 0)
221 if (bndptr[k] == -1 && ed[k] > 0)
227 printf(
"\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
228 for (l=0; l<ncon; l++)
229 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
232 for (i=0; i<ncon; i++)
233 printf(
"%.3f ", tvec[i]);
240 if (mincutorder == -1 || mincut == initcut)
244 for (i=0; i<ncon; i++) {
263 void SelectQueue2(
int ncon,
float *npwgts,
float *tpwgts,
int *from,
int *cnum,
267 float diff,
max, maxdiff=0.0;
273 for (j=0; j<2; j++) {
274 for (i=0; i<ncon; i++) {
275 diff = npwgts[j*ncon+i]-maxwgt[j*ncon+i];
276 if (diff >= maxdiff) {
284 if (*from != -1 &&
PQueueGetSize(&queues[*cnum][*from]) == 0) {
286 for (i=0; i<ncon; i++) {
288 max = (npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i]);
294 for (i++; i<ncon; i++) {
295 diff = npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i];
304 if (maxdiff <= 0.0 || *from == -1) {
307 for (j=0; j<2; j++) {
308 for (i=0; i<ncon; i++) {
329 float max1=0.0, max2=0.0, sum1=0.0, sum2=0.0, tmp;
331 for (i=0; i<ncon; i++) {
332 tmp = (newbal[i]-1)/(ubvec[i]-1);
333 max1 = (max1 < tmp ? tmp : max1);
336 tmp = (oldbal[i]-1)/(ubvec[i]-1);
337 max2 = (max2 < tmp ? tmp : max2);
343 else if (max1 > max2)
void fwspacefree(CtrlType *ctrl, int n)
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define MocFM_2WayEdgeRefine2
#define IsBetter2wayBalance
int PQueueGetSize(PQueueType *queue)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
int PQueueGetKey(PQueueType *queue)
#define INC_DEC(a, b, val)
#define Compute2WayHLoadImbalanceVec