31 switch (ctrl->
IType) {
39 errexit(
"Unknown initial partition type: %d\n", ctrl->
IType);
59 int i, j, k, nvtxs, ncon, from, bestcut, mincut, nbfs;
67 bestwhere =
idxmalloc(nvtxs,
"BisectGraph: bestwhere");
71 for (; nbfs>0; nbfs--) {
84 if (bestcut >= graph->
mincut) {
86 idxcopy(nvtxs, where, bestwhere);
93 idxcopy(nvtxs, bestwhere, where);
107 int i, ii, j, k, nvtxs, ncon, from, bestcut, mincut, nbfs, qnum;
108 idxtype *bestwhere, *where, *perm;
112 nvtxs = graph->
nvtxs;
114 nvwgt = graph->
nvwgt;
117 where = graph->
where;
119 bestwhere =
idxmalloc(nvtxs,
"BisectGraph: bestwhere");
122 perm =
idxmalloc(nvtxs,
"BisectGraph: perm");
124 for (; nbfs>0; nbfs--) {
125 for (i=0; i<ncon; i++)
131 for (ii=0; ii<nvtxs; ii++) {
133 qnum =
samax(ncon, nvwgt+i*ncon);
134 where[i] = counts[qnum];
135 counts[qnum] = (counts[qnum]+1)%2;
153 if (bestcut >= graph->
mincut) {
155 idxcopy(nvtxs, where, bestwhere);
162 idxcopy(nvtxs, bestwhere, where);
180 int i, ii, j, k, l, kwgt, nvtxs, nbnd, ncon, nswaps, from, to, pass, me, cnum, tmp;
181 idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
183 float *nvwgt, *npwgts;
185 int higain, oldgain, mincut;
187 nvtxs = graph->
nvtxs;
191 nvwgt = graph->
nvwgt;
193 where = graph->
where;
209 for (l=0; l<ncon; l++)
210 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
211 printf(
"] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: %.3f [B]\n", tpwgts[0], tpwgts[1],
216 for (i=0; i<ncon; i++) {
226 for (i=0; i<nvtxs; i++)
227 qnum[i] =
samax(ncon, nvwgt+i*ncon);
231 for (ii=0; ii<nvtxs; ii++) {
233 if (where[i] == from) {
244 for (nswaps=0; nswaps<nvtxs; nswaps++) {
245 if (
AreAnyVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, tpwgts[from]))
254 mincut -= (ed[higain]-
id[higain]);
255 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
256 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
261 printf(
"Moved %6d from %d(%d). [%5d] %5d, NPwgts: ", higain, from, cnum, ed[higain]-
id[higain], mincut);
262 for (l=0; l<ncon; l++)
263 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
265 if (ed[higain] == 0 &&
id[higain] > 0)
266 printf(
"\t Pulled from the interior!\n");
273 SWAP(
id[higain], ed[higain], tmp);
274 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
276 if (ed[higain] > 0 && bndptr[higain] == -1)
279 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
281 oldgain = ed[k]-
id[k];
283 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
287 if (where[k] == from) {
288 if (ed[k] > 0 && bndptr[k] == -1) {
294 printf(
"What you thought was wrong!\n");
295 PQueueUpdate(&parts[qnum[k]][0], k, oldgain, ed[k]-
id[k]);
300 if (ed[k] == 0 && bndptr[k] != -1)
302 else if (ed[k] > 0 && bndptr[k] == -1)
311 printf(
"\tMincut: %6d, NBND: %6d, NPwgts: ", mincut, nbnd);
312 for (l=0; l<ncon; l++)
313 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
320 for (i=0; i<ncon; i++) {
344 for (i=0; i<ncon; i++) {
345 if (npwgts[from*ncon+i]-tpwgts[from] >= max &&
347 max = npwgts[from*ncon+i]-tpwgts[0];
#define Compute2WayHLoadImbalance
#define BNDInsert(nbnd, bndind, bndptr, vtx)
int SelectQueueOneWay(int ncon, float *npwgts, float *tpwgts, int from, PQueueType queues[MAXNCON][2])
#define IFSET(a, flag, cmd)
#define MocFM_2WayEdgeRefine
#define MocCompute2WayPartitionParams
int PQueueGetSize(PQueueType *queue)
void GKfree(void **ptr1,...)
#define ASSERTP(expr, msg)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define MocInit2WayBalance
#define MocInit2WayPartition
#define INC_DEC(a, b, val)
#define MocRandomBisection
int CheckGraph(GraphType *)
#define MocAllocate2WayPartitionMemory