22 int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
23 idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
24 idxtype *moved, *swaps, *perm, *qnum;
25 float *nvwgt, *npwgts, mindiff[
MAXNCON], origbal, minbal, newbal;
27 int higain, oldgain, mincut, initcut, newcut, mincutorder;
48 limit =
amin(
amax(0.01*nvtxs, 25), 150);
51 for (i=0; i<ncon; i++) {
55 for (i=0; i<nvtxs; i++)
56 qnum[i] =
samax(ncon, nvwgt+i*ncon);
60 rtpwgts[0] = origbal*tpwgts[0];
61 rtpwgts[1] = origbal*tpwgts[1];
66 for (l=0; l<ncon; l++)
67 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
68 printf(
"] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: %.3f\n", tpwgts[0], tpwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut, origbal);
72 for (pass=0; pass<npasses; pass++) {
73 for (i=0; i<ncon; i++) {
79 newcut = mincut = initcut = graph->
mincut;
80 for (i=0; i<ncon; i++)
81 mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
90 for (ii=0; ii<nbnd; ii++) {
92 ASSERT(ed[i] > 0 ||
id[i] == 0);
97 for (nswaps=0; nswaps<nvtxs; nswaps++) {
98 SelectQueue(ncon, npwgts, rtpwgts, &from, &cnum, parts);
101 if (from == -1 || (higain =
PQueueGetMax(&parts[cnum][from])) == -1)
103 ASSERT(bndptr[higain] != -1);
105 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
106 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
108 newcut -= (ed[higain]-
id[higain]);
111 if ((newcut < mincut && newbal-origbal <= .00001) ||
112 (newcut == mincut && (newbal < minbal ||
113 (newbal == minbal &&
BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {
116 mincutorder = nswaps;
117 for (i=0; i<ncon; i++)
118 mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
120 else if (nswaps-mincutorder > limit) {
121 newcut += (ed[higain]-
id[higain]);
122 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
123 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
128 moved[higain] = nswaps;
129 swaps[nswaps] = higain;
132 printf(
"Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-
id[higain], newcut);
133 for (l=0; l<ncon; l++)
134 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
135 printf(
", %.3f LB: %.3f\n", minbal, newbal);
142 SWAP(
id[higain], ed[higain], tmp);
143 if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
146 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
148 oldgain = ed[k]-
id[k];
150 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
154 if (bndptr[k] != -1) {
162 PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-
id[k]);
169 PQueueInsert(&parts[qnum[k]][where[k]], k, ed[k]-
id[k]);
180 for (i=0; i<nswaps; i++)
181 moved[swaps[i]] = -1;
182 for (nswaps--; nswaps>mincutorder; nswaps--) {
183 higain = swaps[nswaps];
185 to = where[higain] = (where[higain]+1)%2;
186 SWAP(
id[higain], ed[higain], tmp);
187 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
189 else if (ed[higain] > 0 && bndptr[higain] == -1)
192 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
193 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
194 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
197 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
200 if (bndptr[k] != -1 && ed[k] == 0)
202 if (bndptr[k] == -1 && ed[k] > 0)
208 printf(
"\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
209 for (l=0; l<ncon; l++)
210 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
217 if (mincutorder == -1 || mincut == initcut)
221 for (i=0; i<ncon; i++) {
240 int i, part, maxgain=0;
241 float max, maxdiff=0.0;
247 for (part=0; part<2; part++) {
248 for (i=0; i<ncon; i++) {
249 if (npwgts[part*ncon+i]-tpwgts[part] >= maxdiff) {
250 maxdiff = npwgts[part*ncon+i]-tpwgts[part];
259 if (*from != -1 &&
PQueueGetSize(&queues[*cnum][*from]) == 0) {
261 for (i=0; i<ncon; i++) {
263 max = npwgts[(*from)*ncon + i];
269 for (i++; i<ncon; i++) {
270 if (npwgts[(*from)*ncon + i] > max &&
PQueueGetSize(&queues[i][*from]) > 0) {
271 max = npwgts[(*from)*ncon + i];
278 if (maxdiff <= 0.0 || *from == -1) {
281 for (part=0; part<2; part++) {
282 for (i=0; i<ncon; i++) {
308 for (i=0; i<ncon; i++)
309 ndiff[i] = fabs(tpwgts[0]-npwgts[i]);
324 for (i=0; i<ncon; i++) {
326 temp = fabs(tpwgts[0]-npwgts[i])/tpwgts[0];
327 max = (max < temp ? temp :
max);
341 for (i=0; i<ncon; i++)
342 lbvec[i] = 1.0 + fabs(tpwgts[0]-npwgts[i])/tpwgts[0];
#define Compute2WayHLoadImbalance
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define MocFM_2WayEdgeRefine
int PQueueGetSize(PQueueType *queue)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
int PQueueGetKey(PQueueType *queue)
#define INC_DEC(a, b, val)
#define Compute2WayHLoadImbalanceVec