38 int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
39 idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
40 idxtype *moved, *swaps, *perm, *qnum;
41 float *nvwgt, *npwgts, mindiff[
MAXNCON], origbal, minbal, newbal;
43 int higain, oldgain, mincut, newcut, mincutorder;
64 limit =
amin(
amax(0.01*nvtxs, 15), 100);
67 for (i=0; i<ncon; i++) {
70 qsizes[i][0] = qsizes[i][1] = 0;
73 for (i=0; i<nvtxs; i++) {
74 qnum[i] =
samax(ncon, nvwgt+i*ncon);
75 qsizes[qnum[i]][where[i]]++;
85 for (from=0; from<2; from++) {
86 for (j=0; j<ncon; j++) {
87 if (qsizes[j][from] == 0) {
88 for (i=0; i<nvtxs; i++) {
92 k =
samax2(ncon, nvwgt+i*ncon);
93 if (k == j && qsizes[qnum[i]][from] > qsizes[j][from] && nvwgt[i*ncon+qnum[i]] < 1.3*nvwgt[i*ncon+j]) {
94 qsizes[qnum[i]][from]--;
112 for (i=0; i<ncon; i++)
113 mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
115 newcut = mincut = graph->
mincut;
120 for (l=0; l<ncon; l++)
121 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
122 printf(
"] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: %.3f [B]\n", tpwgts[0], tpwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut, origbal);
133 for (ii=0; ii<nvtxs; ii++) {
135 PQueueInsert(&parts[qnum[i]][where[i]], i, ed[i]-
id[i]);
138 for (nswaps=0; nswaps<nvtxs; nswaps++) {
139 if (minbal < lbfactor)
142 SelectQueue(ncon, npwgts, tpwgts, &from, &cnum, parts);
145 if (from == -1 || (higain =
PQueueGetMax(&parts[cnum][from])) == -1)
148 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
149 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
150 newcut -= (ed[higain]-
id[higain]);
153 if (newbal < minbal || (newbal == minbal &&
154 (newcut < mincut || (newcut == mincut &&
BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {
157 mincutorder = nswaps;
158 for (i=0; i<ncon; i++)
159 mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
161 else if (nswaps-mincutorder > limit) {
162 newcut += (ed[higain]-
id[higain]);
163 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
164 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
169 moved[higain] = nswaps;
170 swaps[nswaps] = higain;
173 printf(
"Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-
id[higain], newcut);
174 for (l=0; l<ncon; l++)
175 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
176 printf(
", %.3f LB: %.3f\n", minbal, newbal);
183 SWAP(
id[higain], ed[higain], tmp);
184 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
186 if (ed[higain] > 0 && bndptr[higain] == -1)
189 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
191 oldgain = ed[k]-
id[k];
193 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
198 PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-
id[k]);
201 if (ed[k] == 0 && bndptr[k] != -1)
203 else if (ed[k] > 0 && bndptr[k] == -1)
213 for (nswaps--; nswaps>mincutorder; nswaps--) {
214 higain = swaps[nswaps];
216 to = where[higain] = (where[higain]+1)%2;
217 SWAP(
id[higain], ed[higain], tmp);
218 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
220 else if (ed[higain] > 0 && bndptr[higain] == -1)
223 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
224 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
225 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
228 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
231 if (bndptr[k] != -1 && ed[k] == 0)
233 if (bndptr[k] == -1 && ed[k] > 0)
239 printf(
"\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
240 for (l=0; l<ncon; l++)
241 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
249 for (i=0; i<ncon; i++) {
#define Compute2WayHLoadImbalance
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define INC_DEC(a, b, val)
#define MocGeneral2WayBalance