23 int i, j, nvtxs, from, imax, gain, mindiff;
27 mindiff = abs(tpwgts[0]-graph->
pwgts[0]);
30 if (graph->
pwgts[0] > tpwgts[0] && graph->
pwgts[0] < (
int)(ubfactor*tpwgts[0]))
32 if (graph->
pwgts[1] > tpwgts[1] && graph->
pwgts[1] < (
int)(ubfactor*tpwgts[1]))
50 int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
51 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
54 int higain, oldgain, mincut, mindiff;
72 mindiff = abs(tpwgts[0]-pwgts[0]);
73 from = (pwgts[0] < tpwgts[0] ? 1 : 0);
77 printf(
"Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d [B]\n",
78 pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut));
91 for (ii=0; ii<nbnd; ii++) {
93 ASSERT(ed[bndind[i]] > 0 ||
id[bndind[i]] == 0);
94 ASSERT(bndptr[bndind[i]] != -1);
95 if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)
96 PQueueInsert(&parts, bndind[i], ed[bndind[i]]-
id[bndind[i]]);
100 for (nswaps=0; nswaps<nvtxs; nswaps++) {
103 ASSERT(bndptr[higain] != -1);
105 if (pwgts[to]+vwgt[higain] > tpwgts[to])
108 mincut -= (ed[higain]-
id[higain]);
109 INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
112 moved[higain] = nswaps;
115 printf(
"Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-
id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
120 SWAP(
id[higain], ed[higain], tmp);
121 if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
124 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
126 oldgain = ed[k]-
id[k];
128 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
132 if (bndptr[k] != -1) {
135 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
139 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
146 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
154 printf(
"\tMinimum cut: %6d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, pwgts[0], pwgts[1], nbnd));
176 int i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
177 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
180 int higain, oldgain, mincut, mindiff;
182 nvtxs = graph->
nvtxs;
187 where = graph->
where;
190 pwgts = graph->
pwgts;
198 mindiff = abs(tpwgts[0]-pwgts[0]);
199 from = (pwgts[0] < tpwgts[0] ? 1 : 0);
203 printf(
"Partitions: [%6d %6d] T[%6d %6d], Nv-Nb[%6d %6d]. ICut: %6d [B]\n",
204 pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut));
216 for (ii=0; ii<nvtxs; ii++) {
218 if (where[i] == from && vwgt[i] <= mindiff)
224 for (nswaps=0; nswaps<nvtxs; nswaps++) {
228 if (pwgts[to]+vwgt[higain] > tpwgts[to])
231 mincut -= (ed[higain]-
id[higain]);
232 INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
235 moved[higain] = nswaps;
238 printf(
"Moved %6d from %d. [%3d %3d] %5d [%4d %4d]\n", higain, from, ed[higain]-
id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
243 SWAP(
id[higain], ed[higain], tmp);
244 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
246 if (ed[higain] > 0 && bndptr[higain] == -1)
249 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
251 oldgain = ed[k]-
id[k];
253 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
257 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
261 if (ed[k] == 0 && bndptr[k] != -1)
263 else if (ed[k] > 0 && bndptr[k] == -1)
269 printf(
"\tMinimum cut: %6d, PWGTS: [%6d %6d], NBND: %6d\n", mincut, pwgts[0], pwgts[1], nbnd));
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define IFSET(a, flag, cmd)
#define General2WayBalance
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define INC_DEC(a, b, val)