31 idx_t i, ii,
j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, limit, tmp;
35 idx_t higain, mincut, mindiff, origdiff, initcut, newcut, mincutorder, avgvwgt;
49 bndptr =
graph->bndptr;
50 bndind =
graph->bndind;
60 avgvwgt =
gk_min((pwgts[0]+pwgts[1])/20, 2*(pwgts[0]+pwgts[1])/nvtxs);
69 iset(nvtxs, -1, moved);
70 for (pass=0; pass<niter; pass++) {
75 newcut = mincut = initcut =
graph->mincut;
84 for (ii=0; ii<nbnd; ii++) {
86 ASSERT(ed[bndind[
i]] > 0 ||
id[bndind[
i]] == 0);
87 ASSERT(bndptr[bndind[
i]] != -1);
91 for (nswaps=0; nswaps<nvtxs; nswaps++) {
92 from = (
tpwgts[0]-pwgts[0] <
tpwgts[1]-pwgts[1] ? 0 : 1);
95 if ((higain =
rpqGetTop(queues[from])) == -1)
97 ASSERT(bndptr[higain] != -1);
99 newcut -= (ed[higain]-
id[higain]);
102 if ((newcut < mincut &&
iabs(
tpwgts[0]-pwgts[0]) <= origdiff+avgvwgt) ||
103 (newcut == mincut &&
iabs(
tpwgts[0]-pwgts[0]) < mindiff)) {
106 mincutorder = nswaps;
108 else if (nswaps-mincutorder > limit) {
109 newcut += (ed[higain]-
id[higain]);
115 moved[higain] = nswaps;
116 swaps[nswaps] = higain;
124 SWAP(
id[higain], ed[higain], tmp);
125 if (ed[higain] == 0 &&
xadj[higain] <
xadj[higain+1])
135 if (bndptr[k] != -1) {
161 for (
i=0;
i<nswaps;
i++)
162 moved[swaps[
i]] = -1;
163 for (nswaps--; nswaps>mincutorder; nswaps--) {
164 higain = swaps[nswaps];
167 SWAP(
id[higain], ed[higain], tmp);
168 if (ed[higain] == 0 && bndptr[higain] != -1 &&
xadj[higain] <
xadj[higain+1])
170 else if (ed[higain] > 0 && bndptr[higain] == -1)
180 if (bndptr[k] != -1 && ed[k] == 0)
182 if (bndptr[k] == -1 && ed[k] > 0)
187 graph->mincut = mincut;
193 if (mincutorder <= 0 || mincut == initcut)
209 idx_t i, ii,
j, k,
l, kwgt, nvtxs,
ncon, nbnd, nswaps, from, to, pass,
210 me, limit, tmp, cnum;
214 idx_t higain, mincut, initcut, newcut, mincutorder;
215 real_t *invtvwgt, *ubfactors, *minbalv, *newbalv;
216 real_t origbal, minbal, newbal, rgain, ffactor;
221 nvtxs =
graph->nvtxs;
227 invtvwgt =
graph->invtvwgt;
231 pwgts =
graph->pwgts;
232 bndptr =
graph->bndptr;
233 bndind =
graph->bndind;
248 ffactor = .5/
gk_max(20, nvtxs);
254 for (
i=0;
i<nvtxs;
i++)
271 iset(nvtxs, -1, moved);
272 for (pass=0; pass<niter; pass++) {
277 newcut = mincut = initcut =
graph->mincut;
287 for (ii=0; ii<nbnd; ii++) {
288 i = bndind[
perm[ii]];
297 for (nswaps=0; nswaps<nvtxs; nswaps++) {
302 if (from == -1 || (higain =
rpqGetTop(queues[2*cnum+from])) == -1)
304 ASSERT(bndptr[higain] != -1);
306 newcut -= (ed[higain]-
id[higain]);
312 if ((newcut < mincut && newbal <= ffactor) ||
313 (newcut == mincut && (newbal < minbal ||
317 mincutorder = nswaps;
320 else if (nswaps-mincutorder > limit) {
321 newcut += (ed[higain]-
id[higain]);
328 moved[higain] = nswaps;
329 swaps[nswaps] = higain;
333 "Cut:%5"PRIDX", NPwgts:", higain, from, cnum, ed[higain]-
id[higain], newcut);
344 SWAP(
id[higain], ed[higain], tmp);
345 if (ed[higain] == 0 &&
xadj[higain] <
xadj[higain+1])
355 if (bndptr[k] != -1) {
362 if (moved[k] == -1) {
374 if (moved[k] == -1) {
391 for (
i=0;
i<nswaps;
i++)
392 moved[swaps[
i]] = -1;
393 for (nswaps--; nswaps>mincutorder; nswaps--) {
394 higain = swaps[nswaps];
397 SWAP(
id[higain], ed[higain], tmp);
398 if (ed[higain] == 0 && bndptr[higain] != -1 &&
xadj[higain] <
xadj[higain+1])
400 else if (ed[higain] > 0 && bndptr[higain] == -1)
411 if (bndptr[k] != -1 && ed[k] == 0)
413 if (bndptr[k] == -1 && ed[k] > 0)
418 graph->mincut = mincut;
424 if (mincutorder <= 0 || mincut == initcut)
468 if (
rpqLength(queues[2*(*cnum)+(*from)]) == 0) {
520 if (mincutorder == -2) {
529 ntpwgts[
i], ntpwgts[
graph->ncon+
i]);