21 if (
graph->ncon == 1) {
43 idx_t i, ii,
j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
47 idx_t higain, mincut, mindiff;
61 bndptr =
graph->bndptr;
62 bndind =
graph->bndind;
71 from = (pwgts[0] <
tpwgts[0] ? 1 : 0);
81 iset(nvtxs, -1, moved);
89 for (ii=0; ii<nbnd; ii++) {
91 ASSERT(ed[bndind[
i]] > 0 ||
id[bndind[
i]] == 0);
92 ASSERT(bndptr[bndind[
i]] != -1);
93 if (
where[bndind[
i]] == from &&
vwgt[bndind[
i]] <= mindiff)
94 rpqInsert(queue, bndind[
i], ed[bndind[
i]]-
id[bndind[
i]]);
97 mincut =
graph->mincut;
98 for (nswaps=0; nswaps<nvtxs; nswaps++) {
101 ASSERT(bndptr[higain] != -1);
106 mincut -= (ed[higain]-
id[higain]);
110 moved[higain] = nswaps;
118 SWAP(
id[higain], ed[higain], tmp);
119 if (ed[higain] == 0 &&
xadj[higain] <
xadj[higain+1])
128 if (bndptr[k] != -1) {
131 if (moved[k] == -1 &&
where[k] == from &&
vwgt[k] <= mindiff)
135 if (moved[k] == -1 &&
where[k] == from &&
vwgt[k] <= mindiff)
142 if (moved[k] == -1 &&
where[k] == from &&
vwgt[k] <= mindiff)
150 printf(
"\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
152 graph->mincut = mincut;
171 idx_t i, ii,
j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
175 idx_t higain, mincut, mindiff;
180 nvtxs =
graph->nvtxs;
188 pwgts =
graph->pwgts;
189 bndptr =
graph->bndptr;
190 bndind =
graph->bndind;
199 from = (pwgts[0] <
tpwgts[0] ? 1 : 0);
208 iset(nvtxs, -1, moved);
215 for (ii=0; ii<nvtxs; ii++) {
221 mincut =
graph->mincut;
223 for (nswaps=0; nswaps<nvtxs; nswaps++) {
230 mincut -= (ed[higain]-
id[higain]);
234 moved[higain] = nswaps;
242 SWAP(
id[higain], ed[higain], tmp);
243 if (ed[higain] == 0 && bndptr[higain] != -1 &&
xadj[higain] <
xadj[higain+1])
245 if (ed[higain] > 0 && bndptr[higain] == -1)
255 if (moved[k] == -1 &&
where[k] == from &&
vwgt[k] <= mindiff)
259 if (ed[k] == 0 && bndptr[k] != -1)
261 else if (ed[k] > 0 && bndptr[k] == -1)
267 printf(
"\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
269 graph->mincut = mincut;
283 idx_t i, ii,
j, k,
l, kwgt, nvtxs,
ncon, nbnd, nswaps, from, to, pass,
284 me, limit, tmp, cnum;
286 idx_t *moved, *swaps, *
perm, *qnum, *qsizes;
287 idx_t higain, mincut, newcut, mincutorder;
288 real_t *invtvwgt, *minbalv, *newbalv, minbal, newbal;
293 nvtxs =
graph->nvtxs;
299 invtvwgt =
graph->invtvwgt;
303 pwgts =
graph->pwgts;
304 bndptr =
graph->bndptr;
305 bndind =
graph->bndind;
324 for (
i=0;
i<nvtxs;
i++) {
331 for (from=0; from<2; from++) {
333 if (qsizes[2*
j+from] == 0) {
334 for (
i=0;
i<nvtxs;
i++) {
340 qsizes[2*qnum[
i]+from] > qsizes[2*
j+from] &&
342 qsizes[2*qnum[
i]+from]--;
355 newcut = mincut =
graph->mincut;
367 iset(nvtxs, -1, moved);
375 for (ii=0; ii<nvtxs; ii++) {
380 for (nswaps=0; nswaps<nvtxs; nswaps++) {
387 if (from == -1 || (higain =
rpqGetTop(queues[2*cnum+from])) == -1)
390 newcut -= (ed[higain]-
id[higain]);
396 if (newbal < minbal || (newbal == minbal &&
401 mincutorder = nswaps;
404 else if (nswaps-mincutorder > limit) {
405 newcut += (ed[higain]-
id[higain]);
412 moved[higain] = nswaps;
413 swaps[nswaps] = higain;
417 "Cut: %5"PRIDX", NPwgts: ", higain, from, cnum, ed[higain]-
id[higain], newcut);
420 printf(
", %+.3"PRREAL" LB: %+.3"PRREAL"\n", minbal, newbal);
427 SWAP(
id[higain], ed[higain], tmp);
428 if (ed[higain] == 0 && bndptr[higain] != -1 &&
xadj[higain] <
xadj[higain+1])
430 if (ed[higain] > 0 && bndptr[higain] == -1)
444 if (ed[k] == 0 && bndptr[k] != -1)
446 else if (ed[k] > 0 && bndptr[k] == -1)
456 for (nswaps--; nswaps>mincutorder; nswaps--) {
457 higain = swaps[nswaps];
460 SWAP(
id[higain], ed[higain], tmp);
461 if (ed[higain] == 0 && bndptr[higain] != -1 &&
xadj[higain] <
xadj[higain+1])
463 else if (ed[higain] > 0 && bndptr[higain] == -1)
474 if (bndptr[k] != -1 && ed[k] == 0)
476 if (bndptr[k] == -1 && ed[k] > 0)
483 mincut, mincutorder, nbnd);
489 graph->mincut = mincut;