39 int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
40 idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
41 idxtype *moved, *swaps, *perm, *qnum;
44 int higain, oldgain, mincut, newcut, mincutorder;
45 float *maxwgt, *minwgt, tvec[
MAXNCON];
66 limit =
amin(
amax(0.01*nvtxs, 15), 100);
73 for (j=0; j<ncon; j++) {
74 maxwgt[i*ncon+j] = tpwgts[i]*ubvec[j];
75 minwgt[i*ncon+j] = tpwgts[i]*(1.0/ubvec[j]);
81 for (i=0; i<ncon; i++) {
85 for (i=0; i<nvtxs; i++)
86 qnum[i] =
samax(ncon, nvwgt+i*ncon);
89 for (i=0; i<ncon; i++)
90 minbal[i] = origbal[i];
92 newcut = mincut = graph->
mincut;
97 for (l=0; l<ncon; l++)
98 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
99 printf(
"] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: ", tpwgts[0], tpwgts[1],
101 for (i=0; i<ncon; i++)
102 printf(
"%.3f ", origbal[i]);
114 for (ii=0; ii<nvtxs; ii++) {
116 PQueueInsert(&parts[qnum[i]][where[i]], i, ed[i]-
id[i]);
120 for (nswaps=0; nswaps<nvtxs; nswaps++) {
124 SelectQueue3(ncon, npwgts, tpwgts, &from, &cnum, parts, maxwgt);
127 if (from == -1 || (higain =
PQueueGetMax(&parts[cnum][from])) == -1)
130 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
131 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
132 newcut -= (ed[higain]-
id[higain]);
138 for (i=0; i<ncon; i++)
139 minbal[i] = newbal[i];
140 mincutorder = nswaps;
142 else if (nswaps-mincutorder > limit) {
143 newcut += (ed[higain]-
id[higain]);
144 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
145 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
150 moved[higain] = nswaps;
151 swaps[nswaps] = higain;
154 printf(
"Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-
id[higain], newcut);
155 for (i=0; i<ncon; i++)
156 printf(
"(%.3f, %.3f) ", npwgts[i], npwgts[ncon+i]);
160 for (i=0; i<ncon; i++)
161 printf(
"%.3f ", tvec[i]);
162 if (mincutorder == nswaps)
172 SWAP(
id[higain], ed[higain], tmp);
173 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
175 if (ed[higain] > 0 && bndptr[higain] == -1)
178 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
180 oldgain = ed[k]-
id[k];
182 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
187 PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-
id[k]);
190 if (ed[k] == 0 && bndptr[k] != -1)
192 else if (ed[k] > 0 && bndptr[k] == -1)
203 for (i=0; i<nswaps; i++)
204 moved[swaps[i]] = -1;
205 for (nswaps--; nswaps>mincutorder; nswaps--) {
206 higain = swaps[nswaps];
208 to = where[higain] = (where[higain]+1)%2;
209 SWAP(
id[higain], ed[higain], tmp);
210 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
212 else if (ed[higain] > 0 && bndptr[higain] == -1)
215 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
216 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
217 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
220 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
223 if (bndptr[k] != -1 && ed[k] == 0)
225 if (bndptr[k] == -1 && ed[k] > 0)
231 printf(
"\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
232 for (i=0; i<ncon; i++)
233 printf(
"(%.3f, %.3f) ", npwgts[i], npwgts[ncon+i]);
236 for (i=0; i<ncon; i++)
237 printf(
"%.3f ", tvec[i]);
245 for (i=0; i<ncon; i++) {
266 void SelectQueue3(
int ncon,
float *npwgts,
float *tpwgts,
int *from,
int *cnum,
270 float maxdiff=0.0, diff;
276 for (j=0; j<2; j++) {
277 for (i=0; i<ncon; i++) {
278 diff = npwgts[j*ncon+i]-maxwgt[j*ncon+i];
279 if (diff >= maxdiff) {
295 if (*from != -1 &&
PQueueGetSize(&queues[*cnum][*from]) == 0) {
296 for (i=0; i<ncon; i++) {
298 maxdiff = (npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i]);
304 for (i++; i<ncon; i++) {
305 diff = npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i];
306 if (diff > maxdiff &&
PQueueGetSize(&queues[i][*from]) > 0) {
316 for (j=0; j<2; j++) {
317 for (i=0; i<ncon; i++) {
void fwspacefree(CtrlType *ctrl, int n)
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define IsBetter2wayBalance
#define MocGeneral2WayBalance2
int PQueueGetSize(PQueueType *queue)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
int PQueueGetKey(PQueueType *queue)
#define INC_DEC(a, b, val)
#define Compute2WayHLoadImbalanceVec